Approach:

Basic Idea:

To render the scene we use ray tracing. A ray is casted from the center of projection of the camera, through a location in the image plane and into the scene. The ray bounces around the scence and accumulates color. This current image pixel is set to this color value. This method is applyed to for each pixel in the image array to get a snap shot of the scene. The idea behind this method is that we are following a ray of light as it came from the scene and hit the camera.

Ineraction of ray with scene

To actually trace the ray we test for intersection with all the objects in the scene, and the closest point is then chosen as the point the ray first intersects in the scene. At this point the color sent to the camera draws its value from the lighting model:

For each rgb channel. Where ka,kd,ks are constants that describe the material in question. Li is a vector in the direction of the light and V is in the view direction. The vectors are unit. N is the surface normal, Ri is the direction of the ray.

The above equation acounts for diffuse, ambient and specular lighting. The first term, ka Ia is the ambient term that approximates light that has undergone many reflections by a constant term. The next term, the diffuse term, is a property of lambetion surfaces. It acounts for the the illumination due due to the direction of the surface with respect to the light. If the surface faces the light (N*L ==1) the surface is lit, if the surface is perpendicular to the surface ( N*L ==0) then it is dark. The 3rd term is the specular term that accounts for specular highlighs present in materials. Ri is the reflected ray and V is a unit vector i the direction of the light. ns controls the roll off of the specular highlight.

Crl and Crf are the colors returned by the refelected and referacted rays. These are the rays that are generated at the surface. Crl is the color of the reflected ray and it is simpley Rfl = 2N-Rin. The refracted ray is determined by snells law.

The color of these rays are determeind in the same way as the primary ray. That is they will be cast into the scene and intersections with objects will be found. At the closest point of intersection the lighting model is applied again. This process is a recursive process and will continue until the rays no longer hit objects in the scene. In practice this many not happen and is too comptationly intenseve. Thus we go to a recurvie depth of 5 in generating the colors in the image plane.

Intersection:

Paramanount in generating an image of the scene is finding intersections with objects. In this ray tracer all objects are generated from triangles. To test the intersection of a triangle wit a ray we first find the interesection of the ray with the plane the triangle contains. If this point exists we then see if this point is in the triangle. The triangle inside outside test is done by throwing out the least significant dimension,ie the dimension coresponding that of the triangle's normal's greatsest magnitude. We then perform a fast 2d inside outside test. This method is the one persribed by Glassner in "An Introduction to Ray Tracing".

Spatial Data structures.

The greatest bottle neck in a raytracer is computing the intersections. To speed this up we employ the octree spatial data structure. Using this data structure we only need to test collisions with objects nearby the ray.

Octrees are built as follows. First the entire scene is considered. If there are too many objects in the current voxel we break it up into 8 smaller cells and assign each triangle to the cell it is in. This may involove assinging one triangle to more then one voxel, but that is okay, since it overlaps both of them. We then look at each of the resulting voxels and see if we need to split them. This repeats until all voxels have a number of objects, below a threshold or, we reach a maximum depth.

This data structure is used to determine which objects a ray should test for intersection. To trace a ray we first find the starting point of a ray in the octree. This can be done by traversing the tree until an end voxel is reached. The objects in this voxel are then tested against the ray. If no intersection if found, we proced to the next voxel the ray intersects with. This is found by finding the intersection of the ray with the walls of the voxel and that taking a tiny step further outside of the voxel. The resulting point will be in the next voxel along the ray and it cound by found by search the octree.

Forward Ray Tracing

Caustic surfaces are also imlemented in this ray tracer. This is done using forward raytracing. In forward raytracing the scene is built in 2 passes. In the first pass, rays are cast from each light source to the corners of each non-causitci triangle. This forms a triangular light beam. At the triangle a reflective and refaractive beams are formed. These beams are then cast onto the other trianlges in the scene. For each non-caustic trinagle a beam hits, a caustiic triangle is formed that lies in the plane of the hit triangle. If this caustic trianlge overlaps the triangle it is assigned to that traingle and is stored. This caustic trinagle are triangle of constant intesity which is determined by:

On the second pass, which is a normal raytracering pass, when determinig the color at a point location we add the contribution of any caustic triangles, if they exist.