Primitives and Multiple Light Sources
download mac os x application and source code (72k)
First released wednesday january 23, 2002. Developed with apple's free developer tools on mac os 10.1
This document, images, source and application are the intellectual property of forrest briggs. You may freely use the source code i provide. Email me with questions or suggestions.
Restructured code
Before we begin with lights and primitives, i should note that since the previous tutorial, i have revised the example code's structure in several ways.
In reflections, some functions take as their final parameter, a pointer or reference to the variable where they are to return the value they calculate.
For example, VectorSub() took the parameters a, b and c. It set c to a - b. I did this because i thought it would be more efficient, but it isnt. It now takes a and b as parameters and returns a - b, which
Often leads to more easily understood code.
An exception to this is CalculateLightRay(), which needs to return the distance to the light, which is subsequently used in checking for shadows as well as set up the ray to the light. In this case, the final
Parameter is a reference to a structure that the function fills out.
I also modularized the enormous Shade() function, which had grown bloated and complex. It now calls several smaller inline functions that should be more readable. This change is not attributed to any decrease In performance. I have however, noticed (and investigated) that in tests of identical scenes, this version of the ray tracer is roughly only half as fast. Im not at all sure what is causing it, Even after testing each function. Further profiling will be necessary. I remind the reader that the program in its Current state is almost completely unoptimized and will unquestionably become orders of magnitude faster.
A New Lighting model
After reworking the Shade() function, adding support for multiple colored light sources was very simple. For each intersection, rather than calculating the lighting contributions of the light source,
We now go through a loop and calculate it for each light source. It is a value ranging from 0 to 1, 1 indicating full illumination.
If there is an object in between the intersection and the light source (it is shadowed,) then the coefficient is 0. In order to model colored light sources, we must now assign a rgb value to each light as
Well as a location. The code below shows how these values are calculated, then added (light is additive,) to produce a final color for an intersection.
For(int i=0; i<numLightSources; i++)
{
Ray rayToLight;
Float distanceToLight = CalculateLightRay(lightSources[i].Location, intersection, rayToLight); // sets rayToLight
Float lightCoef = CalculateLightingCoef(
IsShadowed(currPrimitiveNum, rayToLight, distanceToLight, primitives, numPrimitives),
RayToLight.Direction, normal);
ReturnColor.R += primitive.Surface.BaseColor.R * lightCoef * lightSources[i].Color.R;
ReturnColor.G += primitive.Surface.BaseColor.G * lightCoef * lightSources[i].Color.G;
ReturnColor.B += primitive.Surface.BaseColor.B * lightCoef * lightSources[i].Color.B;
}
|
Multiple Primitives and Code Structure
Substantial changes were also required to incorporate support for any primitive. A reason ray tracers are often coded using object oriented paradigms is that polymorphism allows for a very elegant way of
Implementing specific primitives as derived classes from a base primitive class. The overhead of object orientation is too great for my purposes though. The structures i have implemented allow the coder
To very easily create any new kind of primitive, so long as he or she can provide a function to get its intersection with a ray and find its normal at a point. It relies on the efficient switch statement to
Handle the specifics of each primitive.
The Primitive structure holds all of the information common to all primitives. It has pointers to a structure containing specific information of each kind of primitive. Before using a primitive, one of these Pointers must be used to instantiate the appropriate data structure. These structures must be cleaned up later. Instead of calling IntersectSphere(), TraceRay() now calls IntersectPrimitive(), which uses A switch statement to call the Appropriate intersection function. Other functions follow similar patterns.
Planes
The standard equation for a plane is A*x + B*y + C*z + D = 0, where the vector (A,B,C) is the normal to the plane and D is the perpendicular distance from the origin to the plane.
Recall that the parametric equation for a ray is
X=xo+xdt
Y=yo+ydt
Z=zo+zdt
Substituting this into the plane equation, we get
A*(xo + xd*t) + B*(yo + yd*t) + C*(zo + zd*t) + D = 0
Distribute A, B and C
A*xo + A*xd*t + B*yo + B*yd*t + C*zo + C*zd*t + D = 0
Subtract terms not containing t
A*xd*t + B*yd*t + C*zd*t = -(A*xo + B*yo + C*zo + D)
Factor t from the left side
T*(A*xd + B*yd + C*zd) = -(A*xo + B*yo + C*zo + D)
Then t = -(A*xo + B*yo + C*zo + D) / (A*xd + B*yd + C*zd)
This gives the distance to the intersection of a ray and a plane. Make sure to discard intersections at negative values of t. If this were a sphere, now we would need to calculate the normal at the point of
Intersection, but planes have the normal (A,B,C) built into them.
Cylinders
If you did not understand the algebriac solution to the ray-sphere intersection, go back and read it again and realize that it is much like solving for the intersection with a plane except that the quadratic
Formula must be used to get t by itself. In fact, you can ray trace any object for which you know the algebraic equation by substituting (x,y,z) from the parametric equation for a ray into the equation and solving for
T. The equation for a cylinder that is infinite in the z-axis is (x-a)2 + (y-b)2 = r2. For a cylinder infinite in the x-axis, it is
(y-b)2 + (z-c)2 = r2. You can probably infer the equation for a y-axis infinite cylinder. At this point we could go through the process of substituting the ray equation and solving
For t, but being the lazy programmers we are, well take a short cut instead. Try working it out if you dont believe that the results are the same. The equation for a cylinder is identical to that of a sphere, but ignoring the infinite axis.
You can therefore find the intersection between a ray and a cylinder by simply removing all of the parts in the ray-sphere intersection that relate to a single axis. For example, A, B and C in the quadratic formula
For a y-axis infinite cylinder are
A = xd2 + zd2
B = 2[xd * (xo - a) + zd * (zo - c)]
C = (xo - a)2 + (zo - c)2 - r2
The same idea applies to finding the normal
Nx = (ix - a) / r
Ny = 0
Nz = (iz - c) / r
Where N is the normal, i is the intersection and (a,b,c) is the center of the cylinder. The value of b does not matter.
But wait... The geometric solution to ray-sphere intersection is faster. Shouldnt we use it for cylinders too? Unfortunately, simply cutting out one axis in the geometric solution does not work because the ray
Is usually already normalized in 3d space. Even though it is easy to use the dot product on 2d vectors, the calculation that yields tca assumes that the length of the ray is 1. It is 1 in 3d space,
But usually any random 2 components of that vector do not have a 2d length of 1. You might want to limit your cylinders so they are not infinite. For this, investigate constructive solid geometry. For my purposes,
More complex objects will be modeled with triangles.
Triangles
Triangles are a useful primitive because they can approximate any surface.
My implementation of the ray-triangle intersection comes directly from this paper by Tomas Moller and Ben Trumbore. I wont restate their method, but i will provide a few
Observations. First, always make sure that you discard intersections at negative distances as invalid (their example code does not do this.) To get the normal to a polygon from its vertices (which are the input data to moller and trumbore's algorithm,)
One must employ the cross product, which like the dot product is a way of multiplying vectors. Unlike the dot product however, the cross product returns a vector rather than a scalar. The resultant vector
Is perpendicular to both of the original vectors. The component definition of the cross product if C = A x B ('x' means cross product) is
Cx = Ay * Bz - Az * By
Cy = Az * Bx - Ax * Bz
Cz = Ax * By - Ay * Bx
Cross products are not commutative, meaning that A x B does not always equal B x A. There are two different vectors pointing in opposite directions that are both perpendicular to any two vectors.
In other words, A x B = -(B x A).
A triangle is defined by vertices V1, V2 and V3. Since the normal is perpendicular to a plane tangent to a surface at a point, it is also equal to the cross product of any Two vectors that lie in the tangent plane. All points of a triangle lie on the same plane. We will use the vectors from one arbitrarily selected vertex to the others. If A = V1 - V2 and B = V1 - V3, then A x B is the normal. An important consequence of the non-commutative nature of the cross product is that triangles are one-sided. Some versions of the ray-triangle intersection algorithm exploit this by Immediately discarding polygons that face away from the ray. This is called backface cullling. The normal is also used in shading calculations, so you must make sure that your triangles face in the correct direction By switching the order of the cross product or the order in which vertices are defined. Otherwise, triangles that should be illuminated will usually appear black.