Ray tracing
A ray tracer colours a sample by following a line. The line starts at the camera, or at a lamp, or at a previous hit, and it runs in one direction until the algorithm decides to stop. The first question is geometric. Which surface is the nearest one along that line? Arthur Appel, at IBM in 1968, used that test to shade solid objects and to mark the regions in shadow. Turner Whitted's 1980 model kept going. From the hit it could send a reflection ray, a refraction ray, and a shadow ray toward each lamp. Three-dimensional computer graphics carries the story on to Kajiya's rendering equation of 1986, and to path tracing, which replaces Whitted's fixed tree of rays with random samples. Light, materials, and the rendered picture is the note on what those samples cost, and on the noise they leave.
Search dominates the cost. Once a scene holds more triangles than anyone wants to test one by one, trying every triangle against every ray spends most of its time on misses a box could have rejected. An acceleration structure, very often a bounding volume hierarchy, packs primitives into nested boxes. The ray walks the boxes it actually meets. Camera models, materials, and the choice of the next ray change with the algorithm. The walk is the part they share.
Steven G. Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hoberock, David Luebke, David McAllister, Morgan McGuire, Keith Morley, Austin Robison and Martin Stich described a way to share that walk in OptiX: a general purpose ray tracing engine, ACM Transactions on Graphics, volume 29 (2010), 13 pages, DOI 10.1145/1778765.1778803. McGuire was at Williams College and at NVIDIA. The rest of the authors were at NVIDIA. The 2010 implementation ran on the company's Quadro, GeForce and Tesla GPUs, through CUDA. Earlier interactive tracers, among them OpenRT, Manta, Razor and Arauna, were built around one renderer or one machine. Work that had already put ray tracing on a GPU had chased speed. OptiX chased a programming model.
The engine does not know what a light is. Shadows and reflectance are absent from it too. Those belong to the program that called it. What OptiX offers is a handful of small programs, each written for a single ray, and a just-in-time compiler that joins them into a kernel. The programmer still writes recursion, the way a Whitted shader recurses. Batching, reordering, and the construction of the acceleration structure stay inside the engine. A closest-hit program does not schedule the GPU.
The programs
Seven program types handle one ray at a time. A bounding-box program sits beside them and runs on geometry, not on a ray, so that the acceleration structure has a box to insert. The paper treats the box program as extra. The table is the whole set.
| Program | When it runs |
|---|---|
| Ray generation | Entrance. Often one copy per pixel. |
| Intersection | During the walk. Does this primitive touch the ray, and where? |
| Bounding box | When the structure is built. A conservative box around a primitive. |
| Closest hit | Once, at the nearest hit. The surface shader. |
| Any hit | At every reported hit, in any order. May stop the ray, or skip the hit. |
| Miss | The ray left the scene. A background colour, or an environment map. |
| Exception | The ray failed, or the user's code threw. |
| Selector visit | At a selector node. Chooses which child the ray walks into. |
Ray generation is where a launch enters. One call starts many copies. In the usual camera, each copy builds one ray for one pixel, traces it, and stores a colour. The same type of program can spray photons, bake lighting, or take ray requests that an OpenGL pass has already queued. Intersection is the geometric test. It can be a triangle, a sphere, a cylinder, or something with no mesh at all. Figure 1 of the paper includes a procedural Julia set. The bounding box for a procedural primitive may only be an estimate. The estimate has to contain the primitive. A baggy box makes the walk longer. The picture does not change.
Closest hit runs a single time, after the nearest intersection is known. It is the surface shader. It may shade, it may fire more rays, and it writes the result into the ray's payload. Any hit runs on the way there, once per intersection the walk reports, and the reports can arrive out of order. From an any-hit program the ray can die immediately, which is the right behaviour for a shadow ray that has found a blocker, or the hit can be ignored, which is how an alpha texture punches a hole without starting the search again. Miss runs when nothing was hit inside the interval. A flat background colour, or an environment map, lives there. Exception runs when a ray goes wrong: the recursion stack outgrew the memory kept for that thread, or a buffer index was out of range. User code can throw its own exception. Selector visit runs at a coarse node and picks a child. Level of detail is the plain use. A far ray gets the coarse model.
The payload is a record the user defines and attaches to the ray. Shading results and shadow attenuation travel in it. There is no fixed lighting structure to write into. The applications drawn in the paper's first figure are path tracing, the Julia set, photon mapping, line of sight and collision tests at large scale, Whitted shading of dynamic geometry, and ambient occlusion. The abstract also names collision detection, artificial-intelligence queries, and scientific work such as sound propagation. A ray, in this design, is a query. The picture is one kind of answer.
The scene graph
Geometry sits in a context, as a directed graph. A group node has children and an acceleration structure, and it can be the top of a two-level walk, a common way to move rigid objects without rebuilding the whole tree. A geometry group is a leaf. It holds primitives and materials, and it has an acceleration structure of its own. A transform node has one child and a 4 by 3 matrix, enough for an affine map. A selector node has children and one visit program. Any node may be the root, so a camera ray and a shadow ray can start in different graphs. Nodes may have several parents. That is instancing: one mesh, many places, and one material shared by shapes whose intersection tests differ.
A geometry instance is the join. It binds one geometry object to a set of materials. Intersection and bounding-box programs hang off the geometry. Closest-hit and any-hit programs hang off the material. The split is on purpose. A triangle format used by a rasterizer can stay in that format, because the intersection program reads it where it already lies. A copy into a tracer-specific mesh is no longer the toll for getting in.
The reflection formula was old by 2010. What stayed open was a programmable search on a parallel machine, one that a new algorithm would not have to write again. When computer pictures became ordinary, a frame could be ray traced while it was still on the screen.