It has been a long time since I last posted anything here. For the last two years the majority of my spare time went into making that 64k intro. In fact the last post, *“Intersection of a ray and a cone”*, was related to it. I was implementing volumetric lighting for the underwater scenes, and wanted to resolve cones of light with ray tracing, before marching inside those cones. LLB and I have talked about the creation process in two making-of articles: *“A dive into the making of Immersion”*, and *“Texturing in a 64kB intro”*.

During that time, a lot of new things have happened in the computer graphics community. It has been difficult to keep track of everything. The last topic I started experimenting with is point cloud and mesh capture from photos; I might expend on it here in the future. I also want to experiment with DIY motion capture. Anyway, it’s time to resume posting here.

]]>So here goes, the solution to the intersection of a ray and a cone, in vector notation.

- We define a ray with its origin $O$ and its direction as a unit vector $\hat{D}$.

Any point $X$ on the ray at a signed distance $t$ from the origin of the ray verifies: $\vec{X} = \vec{O} + t\vec{D}$.

When $t$ is positive $X$ is in the direction of the ray, and when $t$ is negative $X$ is in the opposite direction. - We define a cone with its tip $C$, its axis as a unit vector $\hat{V}$ in the direction of increasing radius, and $\theta$ the half angle between the axis and the surface.

Any point $X$ on the cone verifies: $(\vec{X} – \vec{C}) \cdot \vec{V} = \lVert \vec{X} – \vec{C} \rVert \cos\theta$ - Finally we define $P$ the intersection or the ray and the cone, and which we are interested in finding.

$P$ verifies both equations, so we can write:

$$

\left\{

\begin{array}{l}

\vec{P}=\vec{O} + t\vec{D} \\

\frac{ \vec{P} – \vec{C} }{\lVert \vec{P} – \vec{C} \rVert} \vec{V} = \cos\theta

\end{array}

\right.

$$

We can multiply the second equation by itself to work with it, then reorder things a bit.

$$

\left\{

\begin{array}{l}

\vec{P}=\vec{O} + t\vec{D} \\

\frac{ ((\vec{P} – \vec{C}) \cdot \vec{V})^2 }{ (\vec{P} – \vec{C}) \cdot (\vec{P} – \vec{C}) } = \cos^2\theta

\end{array}

\right.

$$

$$

\left\{

\begin{array}{l}

\vec{P}=\vec{O} + t\vec{D} \\

((\vec{P} – \vec{C}) \cdot \vec{V})^2 – (\vec{P} – \vec{C}) \cdot (\vec{P} – \vec{C}) \cos^2\theta = 0

\end{array}

\right.

$$

Remember the mouthful earlier about $\hat{V}$ being in the direction of increasing radius? By elevating $\cos\theta$ to square, we’re making negative values of $\cos$ positive: values of $\theta$ beyond 90° become indistinguishable from values below 90°. This has the side effect of turning it into the equation of not one, but two cones sharing the same axis, tip and angle, but in opposite directions. We’ll fix that later.

We replace $\vec{P}$ with $\vec{O} + t\vec{D}$ and work the equation until we get a good old quadratic function that we can solve.

$$

\require{cancel}

((\vec{O} + t\vec{D} – \vec{C})\cdot\vec{V})^2 – (\vec{O} + t\vec{D} – \vec{C}) \cdot (\vec{O} + t\vec{D} – \vec{C}) \cos^2\theta = 0

$$

$$

((t\vec{D} + \vec{CO})\cdot\vec{V})^2 – (t\vec{D} + \vec{CO}) \cdot (t\vec{D} + \vec{CO}) \cos^2\theta = 0

$$

$$

(t\vec{D}\cdot\vec{V} + \vec{CO}\cdot\vec{V})^2 – (t^2\cancel{\vec{D}\cdot\vec{D}} + 2t\vec{D}\cdot\vec{CO} + \vec{CO}\cdot\vec{CO}) \cos^2\theta = 0

$$

$$

(t^2(\vec{D}\cdot\vec{V})^2 + 2t(\vec{D}\cdot\vec{V})(\vec{CO}\cdot\vec{V}) + (\vec{CO}\cdot\vec{V})^2) – (t^2 + 2t\vec{D}\cdot\vec{CO} + \vec{CO}\cdot\vec{CO}) \cos^2\theta = 0

$$

$$

t^2(\vec{D}\cdot\vec{V})^2

+ 2t(\vec{D}\cdot\vec{V})(\vec{CO}\cdot\vec{V})

+ (\vec{CO}\cdot\vec{V})^2

– t^2\cos^2\theta

– 2t\vec{D}\cdot\vec{CO}\cos^2\theta

– \vec{CO}\cdot\vec{CO}\cos^2\theta

= 0

$$

Reorder a bit:

$$

t^2((\vec{D}\cdot\vec{V})^2 – \cos^2\theta)

+ 2t((\vec{D}\cdot\vec{V})(\vec{CO}\cdot\vec{V}) – \vec{D}\cdot\vec{CO}\cos^2\theta)

+ (\vec{CO}\cdot\vec{V})^2 – \vec{CO}\cdot\vec{CO}\cos^2\theta

= 0

$$

There we go, we have our $at^2 + bt + c = 0$ equation, with:

$$

\left\{

\begin{array}{l}

a = (\vec{D}\cdot\vec{V})^2 – \cos^2\theta \\

b = 2\Big((\vec{D}\cdot\vec{V})(\vec{CO}\cdot\vec{V}) – \vec{D}\cdot\vec{CO}\cos^2\theta\Big) \\

c = (\vec{CO}\cdot\vec{V})^2 – \vec{CO}\cdot\vec{CO}\cos^2\theta

\end{array}

\right.

$$

From there, you know the drill: calculate the determinant $\Delta = b^2 – 4ac$ then depending on its value:

- If $\Delta < 0$, the ray is not intersecting the cone.
- If $\Delta = 0$, the ray is intersecting the cone once at $t = \frac{-b}{2a}$.
- If $\Delta > 0$, the ray is intersecting the cone twice, at $t_1 = \frac{-b – \sqrt{\Delta}}{2a}$ and $t_2 = \frac{-b + \sqrt{\Delta}}{2a}$.

But wait! We don’t have one cone but two, so we have to reject solutions that intersect with the shadow cone. $P$ must still verify $\frac{ \vec{P} – \vec{C} }{\lVert \vec{P} – \vec{C} \rVert} \vec{V} = \cos\theta$, or simply, if $\theta < 90°$: $(\vec{P} – \vec{C})\cdot\vec{V} > 0$.

Note that there is also the corner case of the ray tangent to the cone and having an infinity of solutions to consider. I’ve completely swept it under the rug since it doesn’t matter in the context I was, but if it does to you, you’ve been warned about it. Also remember to check the sign of $t$ to know whether $P$ is in the direction of the ray. You may need to determine which of $t_1$ or $t_2$ you want to use, which depends on your use case. For example is your ray origin inside or outside of the cone?

Now for a little sanity test, let’s consider the corner case $C=O$, where the ray origin is the tip of the cone (thanks Rubix for the suggestion!). We have $b=0$ and $c=0$ thus $\Delta=0$ and $t=\frac{-b}{2a}=0$ which is the expected result.

I also tried the cases $\theta=0$ and $\theta=\pi/2$, but expanding $\Delta$ proved too tedious to proceed to the end. So this is left as an exercise, as they say. :)

Finally, to demonstrate that the result is indeed correct, here is a glorious ray traced cone scene on ShaderToy:

I hope this can prove useful to others too.

Oh, and Happy New Year by the way!

]]>The presentation covers in layman’s terms topics like Moore’s law (obviously), pipelining, parallelism, power consumption, heat dissipation, processor specialization and cost of production among other things. As explained, all those aspects are facing difficult challenges that are likely to shape the future of microprocessors, which in turns impacts both hardware and software engineers.

Here is the same presentation in 2016:

]]>Francesca Da Rimini was a historical figure portrayed in the Divine Comedy and numerous works of art, including a symphonic poem by Tchaikovsky. In 2014 the director Tarik Abdel-Gawad and his team recorded a performance by two dancers of the San Francisco Ballet, Maria Kochetkova and Joan Boada, using a robot controlled camera. Tarik was also the technical and creative director of the demonstration video featuring the same Bot&Dolly robots (a company acquired by Google in 2013) and which turned viral, “Box”.

In the accompanying back stage video, he explains how seeing dancers rehearse over and over gave him the idea of experimenting with a pre-programmed robot, in order to make the camera part of the choregraphy, and allow the viewer to have a closer, more intimate, view of the performance.

]]>It was a long shot of a dancer turning limb after limb into a lattice body while performing. That film is in fact the music video of the song “Wide Open”, by the Chemical Brothers, and directed by Dom&Nic. It is a brilliant piece of technical and artistic work, that I can only recommend to watch.

Some of the details of the creation are shared in an article by the excellent fxguide, as well as in this interview for Solid Angle, like for example how they dealt with the challenges posed by a single long shot under varying natural light. Finally, there is this behind the scenes video from the studio, The Mill:

]]>Earlier this year filmmaker Stu Maschwitz posted on Twitter a series of messages recounting the work he did, as a then junior visual effects artist, on the scene of the house crashing on the road in the 1996 summer blockbuster, Twister. He later copied them to his website: go read it there.

The story comes with a fair amount of detail, hacks and tricks to make the best of the technical limitations of the time, and gives an idea of the amount of work such a scene in a prominent Hollywood film entails.

Twenty years ago today, TWISTER was released. I’m going to share a bit about my involvement in the film. pic.twitter.com/6RBphItaLT

— Stu Maschwitz (@5tu) May 10, 2016

]]>The first shot alone took four months. I animated the house by hand, and every board and prop that flies off it. pic.twitter.com/tD29jQouOP

— Stu Maschwitz (@5tu) May 10, 2016

Mappings between Sphere, Disc, and Square.

]]>

Abstract:

A variety of mappings between a sphere and a disc and between a disc and a square, as well as combinations of both, are used in computer graphics applications, resulting in mappings between spheres and squares. Many options exist for each type of mapping; to pick the right methods for a given application requires knowledge about the nature and magnitude of mapping distortions.This paper provides an overview of forward and inverse mappings between a unit sphere, a unit disc, and a unit square. Quality measurements relevant for computer graphics applications are derived from tools used in the field of map projection, and a comparative analysis of the mapping methods is given.