Week 7: Path tracing/Ray Marching methods

Quiz 2 Topics

Quiz 2 will focus mostly on topics used in lab 4 and 5.

  • Matrix transforms (translation, rotation, scaling)

    • Given a shape and coordinate system, could you sketch the location of the shape after a series of transforms?

    • How would the Matrix M=RT change the location of a point p? What about M=TR?

    • Given a before/after location of a shape, could you determine the matrix transform that produced the change? You would not need to compute the full matrix, but could you describe the sequence of transforms (e.g. rotate 30 degrees about y, then translate by (1,0,0))?

  • View matrix and camera transforms

    • Given a lookAt(eye, center, up) specification, could you determine how a scnence would appear from that camera location? Given a scene in world coordinates, and a separate camera specification, could you determine a possible set of lookAt parameters to view the scene from a particular angle?

  • Perspective and orthographic projections

    • How do perspective and orthographic projections differ?

    • If you modeled/animated, would there be any way to test which projection was being used just by looking at the output image?

    • What is perspective division?

  • Matrix math

    • Given a matrix M and point p or vector v, could you compute Mp or Mv? On a quiz, the arithmetic would be simple enough to do by hand.

Reading

Also browse some of the short examples of ray marching on Jamie Wong’s Shader Toy profile. Or browse the general Shader Toy site. Shader Toy allows users to browse, edit, and view GLSL code in a slightly modified fragment shader. You may notice there is no vertex shader code. Why not? Where is the geometry specified in these demos?

Just for fun: Inigo Quilez

Inigo Quilez’s YouTube Playlist has a number of interesting videos on ray marching and signed distance fields. These are not required viewing, but if you are interested in learning more about the topic, they are worth checking out. I do not expect you to be able to follow all the math in these videos (we will cover things like noise in a few weeks), but they do give a good sense of the possibilities of ray marching methods.

Path Tracing methods

Until this point we have been focused primarily on the standard OpenGL Pipeline consisting of the following primary steps:

  1. Creation of Geometry Buffers on the CPU

  2. Geometry processing in the Vertex Shader on the GPU

  3. Primitive Assembly and Rasterization (GPU)

  4. Fragment Processing in the Fragment Shader in the GPU

  5. Output of the final image

The key components we implemented or used, including model transforms, the view matrix, orthographic and perspective projections, and the Blinn-Phong lighting model, were once built into a legacy version of OpenGL as a fixed function pipeline. The flexibility of programmable shaders allows us to recreate these now deprecated or disabled features of OpenGL as well as explore more advanced topics not possible in the fixed function pipeline.

We will now take a pause from the standard pipeline, to talk about path tracing methods, an alternative rendering technique. We will be using some new tools, features, and ideas that we have not seen before in this course, but we will also be reusing some ideas and concepts such as our linear algebra toolbox and components of our lighting model.

Historically, path tracing, ray tracing, and ray marching relied more on CPU methods than GPU methods as the the GPU architecture was better suited for the traditional geometry buffer pipeline. But this is beginning to change, and you will see how we can leverage the fragment shader to write a basic ray marcher for your midterm project.

Rays

At the core of ray tracing and ray marching are the geometric primitives rays. A ray is a path extending infinitely in a given direction from an origin point. We typically use a parametric definition of a ray:

\[\vec{r}(t) = p + \vec{d} t\]

The ray \(\vec{r}(t)\) above starts at point \(p\) and travels in the direction \(\vec{d}\). We can define points along the ray with the parameter \(t\). At \(t=0\), we are at the point \(p\). At \(t=2\), we are at the point \(p + 2 \vec{d}\)

Path tracing basics

To render an image with path tracing techniques we define the following key components.

  • The eye or camera origin. This will be the origin of all our primary rays

  • An image plane. The image plane is a region in space where we will be projecting our final image on to. You can think of it is the near plane in the perspective projection frustum, though we will not be explicitly using a perspective projection matrix.

  • Scene objects: what we want to view.

The basic path tracing algorithm divides the image plane into a 2D array of pixels. For each pixel, we create a ray starting from the eye and passing through the center of the pixel. The goal in path tracing is to determine the color of each pixel by tracing the ray as it interacts with the scene.

Since the basic step is something that is done on a per pixel basis, it seems like a good candidate for parallelization through the fragment shader. Two primary methods of path tracing include ray tracing and ray marching. In ray tracing, you can specify the scene as a set of analytic surfaces. To model e.g., a sphere, you can specify its center and radius. Some basic algebra allows you to compute the intersection point between a ray and a sphere, if it exists. This can simplify the need to partition a sphere into a triangular mesh. However, to determine which object a ray intersects, you may need to check all the objects in the scene, or build separate acceleration structures. Ray tracing is an active area of graphics development and research, but we will explore a different path tracing method known as ray marching or sphere tracing.

Signed distance fields and Ray Marching

The primary challenge in all path tracing techniques is how to model the scene and compute ray object intersections. In the ray marching method, an object surface is represented by a signed distance field, or SDF. The SDF is a function that when given a point returns a scalar distance indicating how close that point is to a surface. The result is signed with a positive value indicating the point is outside the surface and negative value is inside the surface.

The SDF for a sphere of radius \(r\) centered at the origin is given by

\[f(p) = \sqrt{p \cdot p} - r\]

When the value of the SDF is 0, the point is on the surface. The basic ray marching method uses an SDF for the entire scene to gradually traverse or march along the ray until it hits the surface of an object.

2D Ray Marching

ShaderToy Mock up

ShaderToy is a site for sharing procedural shaders, many of which use ray marching methods. At its core, you can edit a modified glsl fragment shader to create real time images in the browser. The Shader Toy Demo shows how we might create something similar using the tools we are familiar with in CS40 without all the extra features of ShaderToy.

One question you might have regarding Shader Toy in the context of our prior work is "what happened to the Vertex Shader?" Take a look at the demo and see if you can determine why we don’t need to specify the vertex shader in Shader Toy.

Shader Toy supports several built in variables that are not part of the GLSL standard. Examples include iTime and iResolution. We can recreate these using uniforms in our code. Shader Toy also has a slightly different function prototype for its main function, but again, this is mostly syntactic sugar that we could easily recreate if needed.

With this mock up, you can create full images completely in the fragment shader. Very little Qt or vertex shader code is necessary.

Ray Marching Sketch

We can convert the Ray Marching concepts into the pseudocode sketch below:

given: eye, image plane, scene

for each pixel in image plane:
  ray = makeRay(eye, pixel)
  object = march(ray)
  if object :
    color = lighting(object.material, object.p, object.n, eye)
  else :
    color = background

When implementing a ray marcher in the fragment shader, the shader automatically runs for each pixel in the image plane, so the outer for loop is not necessary in the shader source.

To make a ray, we just need to determine the coordinates of the center of the pixel and create a direction vector from the eye to the center of the current pixel.

The lighting model can be the standard Blinn-Phong illumination model, though with the availability of the entire scene, we can do some global illumination methods like detecting if an object is in shadow.

The primary steps to figure out are how to march and how to compute surface normals given only signed distance fields.

Marching

To march a given ray, we start at the eye and query the SDF of the entire scene to find the distance \(d\) to closest surface. We then march along the ray direction a distance \(d\) and repeat the queries until:

  1. You hit something, SDF returns a small \(\epsilon > 0\)

  2. You travel too far (some max distance) from eye

  3. You take too many steps.

The sphereSDF is just the beginning of the basic shapes you can create with signed distance functions. For a basic introductory list, see Iñigo Quílez’s Distance Function Article

Constructive Solid Geometry - Combining objects

Signed distance fields use the union, intersection, and subtraction operators (see Primitive combinations section)to compose scenes of multiple objects in a variety of ways, many of which are difficult to do with traditional vertex buffer approaches.

Shape transforms

To transform a shape, e.g., to move it from its default location, apply the inverse transform first to the point. Then use the transformed point to sample the original SDF. In the case of translations and rotations where distances are preserved, this is sufficient.

Let’s consider the case where we want to have a sphere orbiting around the \(y\) axis clockwise. This can be expressed as a combination of translation matrix \(T\) and a time varying rotation matrix \(R_y(\theta(t))\). In the SDF, we want to construct a matrix \(M\) that is the inverse of the orbit transform from e.g. lab 4. What would \(M\) look like?

\[M = T^{-1} R_y(-\theta(t))\]

Our SDF for the orbiting sphere would be

\[f_o(p) = f(Mp)\]

Where \(f(Mp)\), is the standard sphere SDF.

Handling scaling transforms is somewhat more complicated. We can apply the inverse scaling transform to the point, but when we do so, we also scale the distance returned by the SDF. And we are using this information to determine how far to move in the original scene. If the scaled distance is an underestimate of the true distance, this may be OK as the ray march step will just be slower and more conservative. But if the scaled distance is an overestimate of the the true distance, we could march past the surface of the scene. To correct the scaled distance, we apply the original scaling factor (not its inverse) to the returned SDF value. In the case of non-uniform scaling, we apply the minimum scaling factor to SDF and fall back to a conservative underestimate of the true distance.

In general, while it is possible to compute exact SDFs for many shapes, in cases where it is not possible, it is better to return an underestimate of the distance during the ray march step than an overestimate.

Materials

The SDF for a single shape is typically described as returning a single floating point distance value. For a complex scene, we can use the union, intersection and subtraction operators to create a more elaborate SDF using constructive solid geometry (CSG). But the standard description of these operators again just describe returning the distance, and not the object or type of surface material encountered. Most ray marchers actually modify their scenes to return both the SDF distance value and an object or material identifier in their implementations when sampling the scene.

This is typically done in GLSL by having the scene SDF return a vec2 type, with one component being the traditional SDF distance and the second component being a material or object label.

vec2 sceneSDF(vec3 p)

The GLSL vec4 type can access the individual components through swizzle operators xyzw (geometry), rgba (colors), or stpq (texture coordinates). So you can index the vec2 types using xy, rg, or st. I prefer using st and letting the first .s component be the surface or material id and the second .t component be the distance or time to reach the surface.

vec2 sceneSDF(vec3 p){
  vec2 obj1 = vec2(1., sphereSDF(p-vec3(1.,0.,0.), 1.));
  vec2 obj2 = vec2(2., sphereSDF(p+vec3(1.,0.,0.), 1.));
  return union(obj1,obj2);
}

Note that the union operator here still is a CSG SDF operation that needs no knowledge of materials. However, it may need modification in implementation to accept vec2 inputs.

Shadows

One of the advantages of path tracing methods over the triangle geometry pipeline is the ability to support global illumination models. While it is possible to do some shadows in the traditional pipeline, it is conceptually easier in the path tracing model.

First consider what it means conceptually for a point \(p\) to be in shadow. A point \(p\) is in shadow if …​

Now let’s consider how to compute if \(p\) is in shadow. What would we need to know as inputs? Can we express this as a ray marching problem?