Saar COR - Introduction: Ray Tracing and Rasterization

Introduction: Ray Tracing and Rasterization

The problem of rendering 3D graphics can be conceptually presented as finding all intersections between a set of "primitives" (typically triangles or polygons) and a set of "rays" (typically one or more per pixel).

Up to 2010 all typical graphic acceleration boards, called graphics processing units (GPUs), use rasterization algorithms. The ray tracing algorithm solves the rendering problem in a different way. In each step, it finds all intersections of a ray with a set of relevant primitives of the scene.

Both approaches have their own benefits and drawbacks. Rasterization can be performed using devices based on a stream computing model, one triangle at the time, and access to the complete scene is needed only once. The drawback of rasterization is that non-local effects, required for an accurate simulation of a scene, such as reflections and shadows are difficult; and refractions nearly impossible to compute.

The ray tracing algorithm is inherently suitable for scaling by parallelization of individual ray renders. However anything other than ray casting requires recursion of the ray tracing algorithm (and random access to the scene graph) to complete their analysis, since reflected, refracted, and scattered rays require that various parts of the scene be re-accessed in a way not easily predicted. But it can easily compute various kinds of physically correct effects, providing much more realistic impression than rasterization.

Whilst the complexity of the computation for rasterization scales linearly with number of triangles the complexity of a properly implemented ray tracing algorithm scales logarithmically; this is due to objects (triangles and collections of triangles) being placed into BSP trees or similar structures, and only being analyzed if a ray intersects with the bounding volume of the binary space partition.