Introduction

Ray tracing, also known as ray casting, determines the visibility of surfaces by tracing imaginary rays of light from the viewers's eye to the objects in the scene. A center of projection and a window on an arbitrary view plane are selected. The window may be thought of as being divided into a regular grid, whose elements correspond to pixels at the desired resolution. Then for each pixel in the window, an eye ray is fired from the center of projection through the pixel's center into the scene. The pixel colour is set to that of the object at the closest point of interaction.

Applications

In automated machining
Graphical Rendering of objects during design process

Code for a simple ray tracer

Select a center of projection and a view window
for each grid do
	determine ray from center of projection through center of grid
	for each object in scene do
		if object is intersect and is closest considered so far then
			record intersection and object name
		set pixel'color to that at closest object intersection
	endfor
endfor

Intersection Computation

Parametric Equation of a ray :

x = x0 + t*diff_x,
y = y0 + t*diff_y,
z = z0 + t*diff_z,	where diff_x = x1 - x0,
		              diff_y = y1 - y0,
			      diff_z = z1 - z0
(x0,y0,z0) is the center of projection
(x1,y1,z1) is the center of grid

Intersection with general quadratic surfaces

General Equation : A*sqr(x) + B*sqr(y) + C*sqr(z) + D*x*y + E*y*z + F*x*z = G
substitution of parametric equation of a ray will give quadratic in 't'

Intersection with a Polygon

Polygon is represented as an array of points (x1,y1,z1) -> ..... -> (xN,yN,zN)

Get the plane equation A*x + B*y + C*z = D

Substitution of parametric equation of ray gives linear equation in 't'

Determine whether intersection point lies inside the polygon by projecting the polygon and the point on any of the co-ordinate planes and using PMC

Efficiency Considerations

Bounding Volume Bounding volumes provide an attractive way to decrease the amount of time spent on intersection calculations. An object that is relatively expensive to test for intersection may be enclosed in a bounding volume whose intersection test is less expensive such as a sphere, ellipsoid, or rectangle.

Spatial Partitioning Spatial partitioning subdivides space top-down. The bounding box of the scene is calculated first. The bounding box is then divided into a regular grid of equal-sized extents. Each partition is associated with a list of objects it contains either wholly or in part. A ray needs to be intersected with only those objects that are contained within the partitions through which it passes. The partitions may be examined in the order in which the ray passes through them. As soon as, we find a partition in which there is an intersection, no more partition need to be inspected.

Boolean Set Operations

Determining the 3D union, difference, or intersection of two solids is difficult when it must be done by direct comparision of one solid with another. In contrast, ray tracing allows the 3D problem to be reduced to a set of simple 1D calculations. The intersections of each ray and primitive object yield a set of t values, each of which specifies a point at which the ray enters or exits the object. Each t value thus defines the beginning of a span in which the ray is either in or out of the object. Boolean set operations are calculated one ray at a time by determining the 1D union, difference, or intersection of spans from the two objects along the same ray. The CSG hierarchy is traversed for each ray by evaluating the left and right intersection lists at each node.

Pseudocode for evaluating the intersection of a ray with a CSG hierarchy


function CSG_intersect(var ray:^Ray; var node:^CSG_node):spanList
var
  leftIntersect,rightIntersect : spanList;
begin
  if node is composite then
     begin
        leftIntersect := CSG_intersect(ray,node^.leftChild);
	if(leftIntersect = nil) and (node^.op <> union) then
	   CSG_intersect := nil
	else
	   begin
	      rightIntersect := CSG_intersect(ray,node^.rightChild);
	      CSG_intersect := CSG_combine(node^.op,leftIntersect,rightIntersect)
	   end
     end
   else
     CSG_intersect := intersection of object with ray
end;

The CSG_combine function takes two lists of intersection records, each ordered by increasing t, and combines them according to the operation being performed. The following table summarizes the boolean operations on two span lists.

Point Classification for objects
combined by boolean set operations

Left	Right	Union	Intersection	Minus
in	in	in	in	out
in	out	in	out	in
out	in	in	out	out
out	out	out	out	out