Editing Glome tutorial (section)

===Tracing Rays===


Glome's Solid typeclass defines a ray-intersection function "rayint" that pattern matches against a primitive and returns an appropriate Rayint.

For instance, let's look at the "disc" case, as it is short and simple:

<haskell>
instance Solid (Disc t m) t m where
 rayint = rayint_disc
 shadow = shadow_disc
 inside (Disc _ _ _) _ = False
 bound = bound_disc

rayint_disc :: Disc tag mat -> Ray -> Flt -> [Texture tag mat] -> [tag] -> Rayint tag mat
rayint_disc (Disc point norm radius_sqr) r@(Ray orig dir) d t tags =
 let dist = plane_int_dist r point norm 
 in if dist < 0 || dist > d 
    then RayMiss
    else let pos = vscaleadd orig dir dist
             offset = vsub pos point
         in 
          if (vdot offset offset) > radius_sqr
          then RayMiss
          else RayHit dist pos norm r vzero t tags
</haskell>

"rayint" takes five arguments: the Solid to be intersected, the Ray to intersect with it, a maximum trace depth, a Texture stack, and a tag stack.  "rayint" is expected to return a RayHit value if a ray intersection exists that's closer than the maximum depth.  If there is more than one hit, rayint should return the closest one, but never an intersection that is behind the Ray's origin.

Rayint_disc extracts the Ray's origin and direction from "r", and then uses a function called "plane_int_dist" defined in Vec.hs.  This returns the distance to the plane defined by a point on the plane and it's normal, and intersected by ray r.

Then Glome checks if the distance is less than zero or more than the maximum allowed, and if so returns RayMiss.

Otherwise, Glome computes the hit location from the Ray and distance to the plane.  "vscaleadd" is another function from Vec.hs that takes one vector, and then adds a second vector after scaling the second vector by some scalar.  By taking the Ray's (normalized) direction vector scaled by the distance to the plane and adding it to the Ray's origin, we get the hit location.  (This technique is used in many of the ray-intersection tests.)

Once we know the location on the disc's plane where our ray hit, we need to know if it is within the radius of the disc.  For that, we compute an offset vector from the center of the disc ("point") to the hit location ("pos").  Then we want to check if this offset vector is less than the radius of the disc.  Or, in other words:

 sqrt (offset.x^2 + offset.y^2 + offset.z^2) < r

We can square both sides to get rid of the square root, and then observe that squaring the components of a vector is the same as taking the dot product of that vector with itself:

 vdot offset offset < r^2

Also, Glome doesn't store the radius with a disc but rather it's radius squared (to avoid a multiply, since we don't often need to know the disc's actual radius), and that explains the last if statement.

The RayHit constructor needs a little explanation, though.  What are all those fields for?

First, there's the distance to the nearest hit and the position.  (You might notice some redundancy here, since the calling function could infer the distance to the nearest hit from the ray and the hit position, or the the hit position from the distance and the ray.  We return both to save the trouble of recomputing values we've already determined.)  "norm" is the vector perpendicular to the surface of the disc, used in lighting calculations.  For discs, this is easy: the normal is stored as part of the disc's definition.  For other objects (like Spheres or Cones), we might have to compute a normal.  

The texture passed in as an argument to "rayint" is simply returned in the returned Rayint record.  All of the ray intersection cases behave this way except Tex, which pushes a new texture onto the stack.

As for the other basic primitives like Triangle, Sphere, Cylinder, Cone, Plane, and Box, Glome uses fairly typical intersection tests that can be found in graphics textbooks (such as [http://pbrt.org/ Physically Based Rendering] and Graphics Gems volume one).  

A "Void" object is a special case: its ray intersector simply returns "RayMiss" regardless of input.  The existence of "Void" is somewhat redundant, since it is equivalent to "Group []".

The composite primitives (Group, Difference, Intersection, Tex, Bih, Instance,  and Bound) are more interesting, as their ray-intersection tests are defined recursively.  This recursion is what allows us to treat a complex object made up of many sub-objects the same as we would treat a simple base primitive like a Sphere, and in fact Glome makes no distinction whatsoever between base primitives and composite primitives.

We'll look at Group as our composite ray-intersection test example:

<haskell>
instance Solid [SolidItem t m] t m where
 rayint xs r d t tags  = foldl' nearest RayMiss (map (\s -> rayint s r d t tags) xs)
 ...
</haskell>

Here, we traverse the list calling "rayint" for each primitive and returning the nearest hit.  ("nearest" is defined in Solid.hs, and returns the nearest of two ray intersections, or RayMiss if they both miss.)

One important thing to keep in mind about Group is that intersecting with a large group is very inefficient.  That's why we have Bih.  However, even Bih uses Groups as leaf nodes, so Groups are still important in some cases.

There is a second ray intersection function called "shadow" that only takes the primitive, a ray, and a maximum distance, and returns True if the ray hits the object and False otherwise.

"shadow" is used for shadow-ray occlusion tests.  In order to test whether a particular point is lit by a particular light, a shadow ray is traced from the ray intersection point to the light.  If there is something in the way, that light is in shadow and it does not contribute to the illumination at that point.

For most scenes with more than one light, more shadow rays are traced than regular rays.  Therefore, we want the shadow ray intersection tests to be as fast as possible.

<haskell>
instance Solid [SolidItem t m] t m where
  shadow xs r d = foldl' (||) False (map (\s -> shadow s r d) xs)
</haskell>

This is faster in some cases than the full ray intersection, because we can stop as soon as one of the results comes back as True.

Primitives are not required to implement a shadow test.  Glome defines a reasonable default case:

<haskell>
shadow s !r !d =
  case (rayint s r d undefined []) of
   RayHit _ _ _ _ _ _ _ -> True
   RayMiss -> False
</haskell>

For base primitives, the performance penalty of using the full ray intersection test instead of a shadow test may be insignificant.  However, composite primitives should always define a shadow test.  Consider, for instance, if Group did not implement a shadow test: all it's children would be tested with "rayint" rather than "shadow", and if any of those objects have sub-objects, they will be tested with "rayint" as well!  A single primitive type high in the tree that doesn't support "shadow" will force its entire subtree to be evaluated with "rayint".

There is one case where "rayint" actually calls "shadow", rather than the other way around: Bound uses a shadow test to determine if the ray hits the bounding object or not.