Raytracing and Design Patterns

While working on a ray tracer I found a pretty convenient design pattern for applying custom material types to the fragments encountered while colliding view rays with scene geometry. The figure below shows a general outline of what the pattern looks like in the context of the ray tracer.


The idea here is that various materials will require differing parameters for shading a particular pixel (e.g., basic Phong shading may simply require a normal, while something more complex like Greg Ward's full Bidirectional Reflectance Distribution Function (BRDF), may require a tangent and binormal as well). In order to accommodate this problem there are two hierarchies of objects: fragments which hold the appropriate parameters for specific material types and the material types themselves. While ray tracing, geometry in the scene is tested against rays from the eye for collisions, when a collision occurs the geometry it occurs with should be aware of 1) what the geometry is (as a mesh or primitive) and 2) its respective material. Using that material we can then figure out what fragment we want to generate - the material is responsible for doing this since it knows what parameters it needs from the fragment and is therefore capable of generating the correct kind of fragment.
When pixel colouring is being done (later on) in the ray tracing program, the colour can be more dynamically derived from fragments without having to worry about having the appropriate parameters to feed into the material calculations. A simple call to the render function in a Fragment is all that is required.

Advantages
- Dyanamic accomidation of materials by fragments
- Saved memory space: only use the fragment parameters needed
- Scales to new materials

Disadvantages
- Very high coupling between Fragment and Material and between the two hierarchies in general
- Slow down due to virtual table look-ups (polymorphism)

Improvements, Additions and Side Notes
Obviously you will be passing other parameters to functions like render, for example you will probably need to pass the scene graph for things like recursive rays. You will definitely need to accommodate lights somewhere (probably as another parameter to the render function).
One question that might arise is "how do I know what parameters to extract when I'm performing the actual collision itself?". For example, lets say I have a primitive of a sphere and I have my eye ray and it collides with the sphere - how do I know what parameters I want (other then the ones I would always want (i.e., position of collision, normal, view direction), for specific materials. This could be taken care of by introducing a method for every primitive type into the Fragment class hierarchy (ugly slow way), or in a more object oriented, design-pattern approach, which would be to use the Visitor pattern and have a separate visitor node hierarchy with a method for dealing with each primitive type in relation to every fragment type. Either way, this will become complicated to maintain any form of object orientedness.

Outline for a Mesh Object Architecture

The idea for this comes from both my work at NVIDIA as well as from my own prior frustrations in creating a flexible, fast and object-oriented framework for representing meshes in a 3D application. The framework I want to present is very simple in concept and reflects a tendancy of stucture that many 3D file formats exhibit (specifically the more modern ones that I have seen: FBX, COLLADA, X File).

Meshes consist of vertices, normals, texture coordinates, tangents, binormals, vertex colours, etc. Some of these are not always necessary, however having the ability to load all of this information whenever an artist feels like it is still very useful. Meshes also consist of polygons (usually a big mess of triangles), which can be represented by appropriately arranging the sets of information previously mentioned. Lastly (note: I'm not going to be talking about bones and animation in this posting) meshes have materials associated with them. All of this information is easy enough to digest; the more annoying part is pieceing it together with the right structure. For example, we could have a "Vertex" object which contains attributes for its position, colour, normal, etc. and then associate that with a "Polygon" object, which could have a type (e.g., triangle, quad) and we could finally associate a whole bunch of those with a "Mesh" object. Having done this before, there are pitfalls to such an approach. For one, it's not very fast - representing everything as objects creates tons of nested drawing calls from one function to the next and code gets bloated quickly due to object composition. Furthermore, there are many cases where polygons can share vertices or other significant attributes, just as vertices may share normals (which may duplicate information unnecessarily), this kind of tracking and monitoring of objects is a huge pain and without smart pointers it can get really messy in an unmanaged language like C++.

A better solution is just to avoid bulky OO relationships altogether when it comes to storing vertex-related values as well as polygons. It is better to represent such information as streams of data and indices into those streams. Vertex-related attributes like position, normals, texture coordinates, etc. can all be seperated into their own stream/array of data, that data can then be indexed to retrieve information without having to duplicate it (or manage it) for seperate objects. Polygon representations can then be simple objects that hold arrays of indices into the streams that are relevant to representing that particular polygon (see the diagram below for an illustration of this).

In the above diagram a Mesh contains a variable set of information streams pertaining to how it is defined. These streams are inconsequential, however, without the definition of one or more PolygonGroups, which are the base unit for seperating one type of surface on the mesh from another (due to the fact that each is associated with exactly one Material). Consider this in the case of a mesh representing a spoon with a wooden handle; we would want the handle to have one material (a wood material) and the rest to have a another (a metal material perhaps). In such an example these two parts of the spoon would be represented by seperate PolygonGroups each with its own material (which could be shared amongst other PolygonGroups. Each PolygonGroup is then built up of a set of Polygons (these are not shared between groups). An important point for a Polygon is that each one contains a set of interleaved indices that refer to the sets of streams belonging to the mesh they are a part of. Though it is not specified in the diagram, I believe it should be flexible as to what streams a PolygonGroup is indexing. So, for example, if there were streams for position, normal, texture and tangent, a PolygonGroup may tell its set of Polygons to only index the position and normal (or some other subset of what is available). The reason I chose the PolygonGroup level and not the Polygon level is because this happens to be the structure in COLLADA files and also because it tends to make more sense - there are few/no situations where you have some random polygon (that isn't already part of a larger or equal sized group and associated with a distinct material) that has a preference in exactly what data it needs to build itself. One final point to make concerns the MeshInstance object. The purpose of this object is to illustrate the possiblity of instancing meshes, each with different possible materials associated with them etc. Such instances could then be placed into a structure like a scene graph so that less information needs to be stored in memory.

Below is a completely hypothetical, pseudocode implementation of the creation of a mesh object to better illustrate this architecture.

Mesh mesh = new Mesh();

// Note: position and normal arrays are just arrays of 3 vectors
Stream posStream = new Stream(InfoType.POSITION, posArray);  
Stream normStream = new Stream(InfoType.NORMAL, normArray);
// ... other streams

// The follow is an example of just one polygon group
// being created
PolygonGroup polyGrp = new PolygonGroup(PolygonType.TRIANGLES);
Polygon[] polygons = new Polygon[NUM_POLYS];

for (int i = 0; i < NUM_POLYS; i++){
   Indexer posIndices = new Indexer(InfoType.POSITION);
   Indexer normIndices = new Indexer(InfoType.NORMAL);
   for (int j = 0; j < 3; j++){
      posIndices[j] = positionsFromFile[i][j];
      normIndices[j] = normalsFromFile[i][j];
   }
   polygons[i].addIndices(posIndices);
   polygons[i].addIndices(normIndices);
}

Material mat = new Material(...);
polyGrp.setPolyArray(polygons);
polyGrp.setMaterial(mat);

mesh.addStream(posStream);
mesh.addStream(normStream);
mesh.addPolygonGroup(polyGrp);

Avoid Numerical Error with Strict Floating Point Types

Code is much better off when it takes the discreteness of numerical computation seriously, here is a robust and flexible "Real" class as an example (The following is done using C# style code... but it can be done in any other language just as easily).

It should also be noted that the epsilon value chosen in the example below is somewhat arbitrary. The value at a absolute maximum should be 1E-6, but it is acceptable for values all the way to 1E-12 (and possibly smaller). Just remember that the whole point of it is to provide a work around for the numerical error the results from storing values in a binary mantissa, with a binary exponent. I don't doubt that there is/are thes(is)/(es) on this subject with a statistical study of what a good epsilon is, but for the purposes of a non-critical 3D application I would say you can just fudge it.

struct Real{
   
   public const float EPSILON = 0.0000001f;
   private float number;
   
   public float Value{
      get{ return this.number; }
      set{ this.number = value; }
   }

   public Real(float num){
      this.number = num;
   }

   public static bool operator==(Real lhs, Real rhs){
      if (Abs(lhs.number - rhs.number) < EPSILON){
         return true;
      }
      return false;
   }
   
   // Implement "Equals" if Java or C# using == operator
   // ...

   public static Real operator/(Real lhs, Real rhs){
      ASSERT(Abs(rhs.number) >= EPSILON);
      Real result = new Real(lhs.number/rhs.number);
      return result;
   }
   public static Real operator*(Real lhs, Real rhs){
      Real result = new Real(lhs*rhs);
      return result;
   }
   // ... all other operators   

}

Calculating Normals

It happens time and again where I have to read in a certain file format or I'm creating the initial code for a 3D engine and I completely forget how to go about calculating normals given a set of vertices and faces. So I've decided to write down the pseudo code for this to avoid future aggravation.

The following code assumes that a vertex array exists, a face array exists (where faces are simply a set of indices into the vertex array) and that suitable data structures for holding 3D vectors, faces etc. exist.

// Step 1: Initialize all the vertices to (0,0,0)
foreach vertex v{
   v = Vertex3D(0,0,0);
}

// Step 2: Assign normals...
foreach face f1{
   Vector faceNormal = CrossProduct(f1.v1-f1.v0, f1.v2-f1.v0);
   foreach vertex v1 in f1{
      if (v1.normal is not initialized){
         v1.normal = faceNormal;
      }
      else{
         if (condition for not smoothing){
               /* duplicate v1 */
               /* set the index in f1 to the index 
                   of the duplicated vertex*/
               /* set the normal of the duplicated vertex to 
                   be the normal of f1*/
         }
         else{
            v1.normal += faceNormal;
         }
      }
   }
}

// Step 3: Average normals in vertices that were stupidly 
// duplicated (optional - but necessary for .3DS file loading)
foreach vertex v1{
   foreach vertex v2{
      if (v1 == v2){
         continue;
      }
      if (v1.position == v2.position && condition for smoothing 
          e.g., v1.smoothgrp == v2.smoothgrp){
         v1.position = v2.position;
         v1.normal += v2.normal;
         v2.normal += v1.normal;
      }
   }
}

// Step 4: Normalize every normal
foreach vertex v{
   v.normalize();
}

Explanation:
In step 1 we make sure all normals are initialized to a null vector so that we can add onto them without any consequences (as we do in the next part of the algorithm). In step 2 we iterate through each face and calculate its face normal (this would be the normal of all its vertices in the case of a purely faceted mesh). With this normal we can now pick and choose what vertices will average that with other face normals and which will actually be faceted/unsmoothed.

I have placed the phrase "condition for not smoothing", typically this can be derived from smoothing groups (e.g., in the case of .3DS file loading we could check to see if the smoothing group associated with v1 isn't the same as f1's) or it could be derived from the angle between v1's normal and the current faceNormal (e.g., if the angle between the two normals is greater than 75 degrees then we don't average the normal). In the case where the smoothing group isn't the same or the angle is greater then we have to make another vertex and ensure that f1 uses that vertex instead (this is because the normal must be different to allow for a faceted/unsmoothed look).

Step 3 is a bit of a caveat, in certain cases we have file formats (*cough .3DS), that decided to duplicate certain vertices in the same smoothing group (or within a degree/radian range that should be considered smooth). As a result this will give the appearence of seams on certain rounded objects - most notably spheres. The seam is a result of the point where multiple normals are present at a single vertex; these normals are pointing in the directions of their faces, which leads to multiple normals at a single location in space which should be smooth. The effect of this is faceted faces around the affected vertices. By averaging out the normals of these vertices we gain a normal which is appropriate and eliminates the hideous seams in the mesh. Another important point to mention is that when doing the comparsion between the positions of the two vertices (i.e., v1.position == v2.position, we should be using an "EPSILON" value) - numerical compuation is a slippery slope and we need to ensure that we take the floating point accuracy of the two positions very seriously (floats can very often not be completely equal even when they are supposed to be). Thus the "equals" (==) computation should be carried out as follows:

bool operator==(vector v1, vector v2){
   if (v1 - EPSILON  <= v2 <= v1 + EPSILON){
      return true;
   }
   return false;
}

Where an operation like v1 + EPSILON is interpretted:

(v1.x + EPSILON, v1.y + EPSILON, v1.z + EPSILON)

(Note that there are better ways to do this... epsilon should be a well established concept in your type sturctures/classes/libraries). With that said I would like to point out that we are very lucky that this is a loading procedure and not a real-time, per frame procedure... because O(n^2) algorithms suck.

The final step (step 4) in the algorithm is to simply normalize the normals for every vertex. In doing this we average the normals for any vertices where multiple normals were added on and make the normals acceptable by any typical graphics API (e.g., OpenGL, D3D).

Further Points:

• It might be a good idea to simply remove duplicated vertices within the same smoothing group altogether - this is especially true if you plan on deforming surfaces or manipulating the normals in the future (... and in real-time especially).


• The above procedure could be accomplished as follows:
  

  foreach smoothing group (or some other condition) s{
     foreach vertex v1 in s{
        foreach vertex v2 in s{
           if (v1 == v2){  continue; }
           // As before, use EPSILON in the following
           if (v1.position == v2.position){
              // We must now eliminate either v1 or v2 
              // and point (i.e., change the reference on) 
              // all faces that referenced that vertex towards 
              // the one we don't eliminate
              
              // 1. Eliminate v2
              // 2. Foreach face with a previous 
              // reference to v2, reference it to v1
           }
        }
     }
  }



• Don't fall into the floating point error trap, becareful of reading in very small vertex coordinates as well as calculating very small normals (usually < 1E-06 can be a bad thing, especially when you're dividing)