Long hiatus

Last week I was lucky enough to attend SIGGRAPH 2018, in Vancouver. My colleagues and I were presenting on a booth the work we had done, a VR story with a distinctive comic book look. I was also invited to participate to a panel session on demoscene, where I shared some lessons learned while making the 64k intro H – Immersion. The event brought a certain sense of conclusion to this work, aside from filling me with inspiration and motivation to try new things.

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.

Intersection of a ray and a cone

Some time ago I needed to solve analytically the intersection of a ray and a cone. I was surprised to see that there are not that many resources available; there are some, but not nearly as many as on the intersection of a ray and a sphere for example. Add to it that they all use their own notation and that I lack math exercise, after a bit of browsing I decided I needed to write a proof by myself to get a good grasp of the result.

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

  1. 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.
  2. 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$
  3. 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!

Various links on ray tracing

Here are some links related to ray tracing, and more specifically, path tracing.

Some ray tracing related projects or blogs:

Some major publications:

  • The rendering equation, SIGGRAPH 1986, James T. Kajiya. From the paper:

    We present an integral equation which generalizes a variety of known rendering algorithms.
    […]
    We mention that the idea behind the rendering equation is hardly new.
    […]
    However, the form in which we present this equation is well suited for computer graphics, and we believe that this form has not appeared before.

  • Bi-directional path tracing, Compugraphics 1993, Eric P. Lafortune and Yves D. Willems. From the paper:

    The basic idea is that particles are shot at the same time from a selected light source and from the viewing point, in much the same way. All hit points on respective particle paths are then connected using shadow rays and the appropriate contributions are added to the flux of pixel  in question.

  • Optimally Combining Sampling Techniques for Monte Carlo Rendering, SIGGRAPH 1995, Eric Veach and Leonidas J. Guibas. From the abstract:

    We present a powerful alternative for constructing robust Monte Carlo estimators, by combining samples from several distributions in a way that is provably good.

  • Metropolis Light Transport, SIGGRAPH 1997, Eric Veach and Leonidas J. Guibas. From the abstract:

    To render an image, we generate a sequence of light transport paths by randomly mutating a single current path (e.g. adding a new vertex to the path).

  • Robust Monte Carlo methods for light transport simulation, 1998, Erich Veach PhD thesis (432 pages pdf): it presents bidirectional path tracing, and introduces Metropolis Light Transport and Multiple Importance Sampling. From the abstract:

    Our statistical contributions include a new technique called multiple importance sampling, which can greatly increase the robustness of Monte Carlo integration. It uses more than one sampling technique to evaluate an integral, and then combines these samples in a way that is provably close to optimal. This leads to estimators that have low variance for a broad class of integrands. We also describe a new variance reduction technique called efficiency-optimized Russian roulette.

    […]

    The second algorithm we describe is Metropolis light transport, inspired by the Metropolis sampling method from computational physics. Paths are generated by following a random walk through path space, such that the probability density of visiting each path is proportional to the contribution it makes to the ideal image.

Other:

On a slightly different topic, fxguide had a great series of articles on the state of rendering in the film industry, which I previously mentioned.

John Carmack on Oculus at GDC 2015

John Carmack, the CTO of Oculus VR, gave a talk at the Game Developers Conference that just ended this week. Various topics are addressed, including the story behind Samsung’s Gear VR and what’s coming next, the democratization of virtual reality, the work on the API, the unsolved problem of controllers in VR, or the use of real-time ray tracing in VR.

John Carmack’s GDC 2015 talk.

It is a fairly long video (1h30), and as often with him, there are no pictures to see, just hear his personal views and insights on the work he is currently taking care of.

Relativistic and non euclidean space rendering

The Portal series built a full game concept out of non euclidean spaces. Besides being great games, I think it is fascinating how true the tagline “Now you’re thinking with portals” is.

Here are two interesting experiments putting the person in different spaces than we are used to due to real world conditions. This video by Varun Ramesh demonstrates a non-euclidean ray tracer:

This other video by the MIT Game Lab demonstrates OpenRelativity, a Unity toolkit allowing simulation of navigation at relativistic speeds, used for the prototype game A Slower Speed of Light:

Update: Sylvain mentioned in comments that Carl Sagan explains those effects in the following video:

Real time stereo ray tracing engineer position in Tokyo

I have retweeted this already, but information tends to get buried pretty quickly on Twitter so I put it here. Syoyo, a real time ray tracing enthusiast, is looking for a talented ray tracing engineer to join his company, Light Transport.

Given their existing technology (interactive to real time ray tracing, interactive shader editing with JIT compilation) and their current focus on the Oculus DK2, I can let you imagine how exciting this position is.

Oculus Rift and eye tracking

People on twitter are starting to mention that their Oculus DK2 are being shipped or are arriving. Exciting.

Meanwhile some people have mentioned how eye tracking could be a great addition to a VR set, and some have even started hacking their headset. See for example:

So what’s the point? One use is explained in this paper: Foveated Real-Time Ray Tracing for Virtual Reality Headset. In this excerpt from AMD Developer Summit 2013, the rendering architect of the Frosbite engine, Johan Andersson talks briefly about foveated rendering.

Long story short: Oculus and eye tracking could really mean real-time ray tracing in a matter of years.

Exciting. But I’m repeating myself.