Introduction

As GPU power is becoming significantly better than CPU, ray casting / tracing, path tracing, and ray marching is widely used in 4k intros, demoscenes, and movies to create interactive 3D graphical scenes.

– Thanks to all the references listed in the end, I learnt so much about and I would like to share with the knowledge to my friends. This tutorial might contain some shortcomings, so please, if you find anything wrong, correct my errors.

This tutorial is built on rendering with two triangles and invoking a pixel shader that will create an animated or static image.

Everyone* was a “noob” at one point!
None* of us was born knowing this stuff!

“If I have seen further it is by standing on the shoulders of giants.” — Isaac Newton

Terminology and Background

All of the three technologies (ray casting / tracing and marching) can handle global effects such as shadows and reflections; they need all objects available to render any object. Some say that it is not a real-time strategy yet while others disagree.

  • Ray casting
    • Ray casting, as the original method of the other two variants, is a technique that transform a limited form of data (a very simplified map or floor plan) into a 3D projection by tracing rays from the view point into the viewing volume.
    • Computation: Rays are cast and traced in groups based on some geometric constraints.
    • For instance: on a 320×200 display resolution, a ray-caster traces only 320 rays
    • Speed: Very fast compared to ray-tracing; suitable for real time process.
    • Limitation: Simple geometric objects.
    • Resulting image is not very realistic. Often, they are blocky.
  • Ray tracing
    • Ray tracing is a more sophisticated algorithm in global rendering involving diffraction and reflection, thus generating images looking even more realistic; alas, it emulates the physics but is computationally more expensive.
    • Computation: Each ray is traced separately, so that every point (usually a pixel) on the display is traced by one ray.
    • For instance: on a 320×200 display resolution, a ray-tracer needs to trace 320×200 (64,000) rays.
    • Speed: slow; unsuitable for real time process
    • Resulting image is very realistic – sometimes too realistic
    • Applications: Raster space antialiasing; Time antialiasing; Camera exposition simulation; Surface shaders (procedural texturing and lighting); Volume shaders (procedural volumetric effects, see first video); Reflections, refractions, shadows; Able of raytrace spheres, cylindres, cubes, planes, cones, revolution objects, 3d julias and polygonal meshes; Lame bump mapping.
    • Accelerations: Use kd-trees, bih or bvh acceleration structure does a couple million rays per second (per core) in modern CPUs.
    • GPU: GPUs are so fast that even brute force implementations of raytracing run fast at high screen resolutions.
  • Path tracing
    • Construct paths incrementally starting at the eye
    • Shoot shadow rays at each path vertex
    • “Each eye ray contributes one path of each length”
    • Each eye ray contributes one sample to integrate for each path length
  • Ray marching (a.k.a. sphere tracing)
    • Ray marching is a variant of ray casting that permits the use of objects for which there is no analytic formula so that the intersection with the ray cannot be simply computed by solving an algebraic equation.
    • Ray marching can be considered as an approximation of ray tracing with a limited number of uniformly distributed samples per ray
    • Accelerations: Demo coders and researchers do raymarching for heightmaps, volume texture, procedural isosurfaces and analytic surfaces.
    • Special Thanks to Iñigo Quilez (rgba) – for ShaderToy and for sharing his rendering knowledge!

In contrast, traditional graphics pipeline uses the pipeline model, which renders one object at a time and tricks to get global effects.

In pipeline model, geometry is in the form of vertices: two vertices form a line or a sphere (one center and one radius), three vertices form a triangle. Clipping is used to decide what can be seen. Rasterizer produces potential pixels (fragments).

gl_pipeline

Prior Knowledge

Interaction of a Ray with An Object

A ray is a straight line. In 2D, it can be defined as y = k * x + d; in 3D, we need an additional coordinate: z = l * x + e. With two points, it is easy to compute the line:

Thus,

Take that into a sphere, we can get, but the solution to X is really long, a.k.a. solving

Ray Tracing

Here is a nice demo of ray tracing from Polytonic:

This is from iq. Once you have such a function f(x,z), the goal is to use a raytracing setup to render the image and do other effects as shadows or reflections. That means that for a given ray with some starting point in space (like the camera position) and a direction (like the view direction) we want to compute the intersection of the ray and the terrain f. The simplest approach is to slowly advance in the ray direction in small steps, and at each stepping point determine if we are above of below the terrain level. The image below shows the process. We start at some point in the ray close to the camera (the leftmost blue point in the image). We evaluate the terrain function f at the current x and z coordinates to get the altitude of the terrain h: h = f(x,z). Now we compare the altitude of the blue sampling point y with h, and we realize that y > h, or in other words, that the blue point is above the mountains. So, we step to the next blue point in the ray, and we repeat the process. At some point, perhapse, one of the sampling point will fall below the terrain, like the yellow point in the image. When that happens, y < h, and we know our ray crossed the terrain surface. We can just stop here and mark the current yellow point as the intersection point (even if we know it’s slightly further than the real intersection point), or peharse take the last blue point as interesection point (slightly closer than the real intersection) or the average of the last blue and yellow points.

ray_casting_iq

Ray Casting Illustration by iq

The mint, maxt and delt constants should be adapted for every scene. The first one is the distance to the near clipping plane, you can set it to zero. The second one is the maximun distance the ray is allowed to travel, ie, the visibility distance. The third one is the step size, and it directly influences the rendering speed and the quality of the image. The bigger it is, the faster of course, but the lower the terrain sampling quality will be.

As you can see the code is terribly simple. There are many optimizations and improvements possible of course. For example, the accuracy of the intersection can be done more accurately by doing a linear approximation of the terrain altitudes between the blue and yellow points and compute the analytical intersection between the ray and the idealized terrain.

The other optimization is to note that as the marching moves the potential intersection point further and further (the bigger t becomes), the less important the error becomes, as geometric details get smaller in screen space as they get further from the camera. In fact, details decay inverse-linearly with the distance, so we can make our error or accuracy delt linear to the distance. This saves lot of rendering time and gives more uniform artifactas than the naive approach. This trick is described in several places, for example in the “Texturing And Modeling – A Procedural Approach” book.

Main Idea

Ray Marching

Instead of computing the sophisticated intersection points, ray marching algorithm walks along the ray and simply check after each step whether you’ve hit an object.

ray_marching

Raymarching is kind of raytracing for all those objects that don’t have an analytic intersection function. (from iq/rgba)

paniq designed a set of interactive, step-by-step illustration of ray marching:

 

 

Walking

Suppose A is the location of the camera and B is the surface point which you want to compute its color. All we need to do is calculate the x, y, z coordinates for the current point and insert it into the formulas of the objects. The walking steps is increased each time we did not hit the surface.  By keeping track of the number of steps you have walked on the ray, we have automatically obtained the distance, and thus are able to calculate the color of the pixel to put.

Disadvantages

Ray marching is not precise and depends on the distance we walk per step.

Distance field

The basic idea is that the distance per step D is not constant, but variable. D depends on the distance of the current point to the object that is closest to it. If we know D, it is safe to walk exactly that distance on the ray, as chances are zero that we will hit an object if we walk less than that.

The hack is that the distance to the closest objects is not computed directly, but is read from a 3D matrix – the distance field.

Advantages

  • Much faster than constant-size stepping.
  • Much easier to control than root finders (bisection, Newton… )
  • Room for optimization, like using bigger steps when we are further from the ray origin
    • Error in world coordinates decreases as 1/ d • So stepping proportionally to d results in constant screen space error.

Disadvantages

  • Slow on the boundaries of the objects (can be controlled by imposing a minimum step size)
Number of raymarching steps for primary rays encoded as colors - iq/rgba

Number of raymarching steps for primary rays encoded as colors – iq/rgba

Combination Equals to Minimization

Since only the pixel from the closest objects is rendered, combination of geometry objects is equivalent to minimization of distance field. For example,

Domain Distortion (example by iq/rgba)

Here is a single rotate on a column:

Here is slightly rotated tentacles:
r1

Here is how the tentacles are lifted and rotated:
r2

Blending Fields

blending_fields

Lighting

Normal Map

Normal Maps are usually computed by central differences on the distance field at the shading point (gradient apprixmation).

Bump Map

Bump map are usually computed by adding the gradient of a fractal sum of Perlin noise function to the surface normal.

Perlin noise is a type of gradient noise developed by Ken Perlin in 1983 as a result of his frustration with the “machine-like” look of computer graphics at the time.

Phone

Bui Tuong Phong was a student at the University of Utah when he invented the process that took his name (Phong lighting). It is a quick and dirty (while I think clever) way to render objects that reflect light in a privileged direction without a full blown reflection.

Ambient Occulusion

The basic technique was invented by Alex Evans, aka Statix (“Fast Approximation for Global Illumnation on Dynamic Scenes”, 2006)

Fog

I added this section from iq’s tutorial:

Fog is very popular element in computer graphics, so popular that in fact we are always introduced to it early in textbooks or tutorials. Iñigo Quilez introduced a nice advanced tutorial on Better Fog.

The fog quickly helps us understand the distances and therefore scale of objects, and the world itself.

A basic fog looks like this:

Adding camera and sun light direction to the fog provides a more vivid scene:

Note how fog colors tints to yellow in the background mountains near the sun. - iq/rgba

Note how fog colors tints to yellow in the background mountains near the sun. – iq/rgba

As for extintion and inscattering of the light vs. fog, we can adjust the parameters more carefully:

Real atmosphere is less dense in the height athmosphere than at the sea level. We can model that density variation with an exponential. The good thing of the exponential function is that the soluting to the formulas is analytical. Let’s see. We start with this exponential density function, which depends on the height y of our point:

Note low altitude parts get extra fog. iq/rgba

Note low altitude parts get extra fog. iq/rgba

Path Tracing Pseudocode

a.k.a. Russian roulette, it never terminates at very first steps, usually q1 = q2 = 0

One of the core challenges in path tracing is:

How to sample as many significant paths as possible?

Here “significant” implies the path contributes more irradiance to the rendering results.

Compared with bidirectional path tracing, MLT is more robust and can handle complex scenes. For example, with an entire scene, light coming from a door seam, MLT handles it well while traditional method does not.

Reference

  1. Kajiya, James T. “The rendering equation.” In ACM Siggraph Computer Graphics, vol. 20, no. 4, pp. 143-150. ACM, 1986.
  2. Andre LaMothe. Black Art of 3D Game Programming. 1995, ISBN 1-57169-004-2, pp. 14, 398, 935-936, 941-943.
  3. Jon Macey, University of Bournemouth Ray-tracing and other Rendering Approaches” (PDF), lecture notes, MSc Computer Animation and Visual Effects,
  4. Evans, Alex. “Fast approximations for global illumination on dynamic scenes.” In ACM SIGGRAPH 2006 Courses, pp. 153-171. ACM, 2006.
  5. Whitted, Turner. “An improved illumination model for shaded display.” In ACM SIGGRAPH Computer Graphics, vol. 13, no. 2, p. 14. ACM, 1979.
  6. Veach, Eric, and Leonidas J. Guibas. “Metropolis light transport.” In Proceedings of the 24th annual conference on Computer graphics and interactive techniques, pp. 65-76. ACM Press/Addison-Wesley Publishing Co., 1997.
  7. Lafortune, Eric P., and Yves D. Willems. “Bi-directional path tracing.” (1993): 145-153.
  8. Iñigo Quilez (rgba). Rendering Worlds with Two Triangles with raytracing on the GPU in 4096 bytes in NVScene 2008.
  9. glöplog on pouet.net. Raymarching Tutorial.
  10. F. PermadiRaycasting Tutorial. 1996.
  11. Codermind team in UCI. Raytracing Turoial
  12. Iñigo Quilez (rgba). Better Fog.2010
  13. Iñigo Quilez (rgba). Modeling with Distance Functions. 2008
  14. Iñigo Quilez (rgba). Raymarching Distance Fields. 2012.
  15. Iñigo Quilez (rgba). Menger Fractal. 2011
  16. Bui Tuong Phong. Illumination for computer generated pictures. 1975
  17. Iñigo Quilez (rgba). Simple Pathtracing  2012
  18. Iñigo Quilez (rgba). Terrain Raymarching. 2002. 2007.
  19. Iñigo Quilez (rgba). Menger Fractal
  20. Nop Jiarathanakul. “Ray Marching Distance Fields in Real-time on WebGL
  21. 9bit Science. “Raymarching Distance Fields”
  22. László Szirmay-Kalos, Tamás Umenhoffer “Displacement Mapping on the GPU ― State of the Art” 2006.

More collections can be found in http://d.hatena.ne.jp/hanecci/20131005/p1.