Editing Glome tutorial (section)

==A guide to the Glome source code==

Editing scenes directly in Haskell makes it possible to use the pre-existing ray tracing infrastructure to help us create our scene.  For instance, the "trace" function can be used to help us place one object on another; a plant growing on a non-flat surface, for instance.  Also, we may want our scene to include geometric primitives of a type that Glome does not yet support, and so we might want to add our own.

This section of the tutorial is for those who are interested in understanding not just how to use Glome, but how it works and how it can be extended.

===File Reference===

First, an overview of the source code files.  Glome is currently split amongst many source files and between GlomeTrace and GlomeVec is about 3500 lines of code.  Some of the interesting files are:

;Vec.hs
:This is the vector library.  It contains all the things you might want to do with vectors: add, subtract, normalize, take dot products and cross products, reverse a vector, etc...  It also includes the transformation matrix code, and routines for transforming vectors, points, and normals.  A data type "Flt" is defined for floating point numbers.  Switching from Float to Double or vice versa is a matter of changing the definition of Flt in Vec.hs and CFlt in Clr.hs.

;Clr.hs
:Color library.  Colors are records of three floats in RGB format.  There's nothing surprising or particularly clever here.

;Solid.hs
:This is where most of the interesting definitions are: definitions of the Solid typeclass and SolidItem existential type, definitions of the Rayint type, and a few of the base primitives (like Group, Void, and Instance).

;Trace.hs
:This contains the "trace" function, which converts a ray and a scene into a color to be drawn to the screen.

;Shader.hs
:This provides an illumination model.  (You can implement your own, but most of the time you'll want to stick with materialShader.)

;Bih.hs
:The BIH acceleration structure.

;Sphere.hs, Triangle.hs, Box.hs, Plane,hs, Cone.hs, etc..
:Basic geometric primitives.

;Glome.hs
:The main loop of the program, part of the GlomeView package.  All SDL-related code resides in this module.  Also included is a get_color function that accepts screen coordinates and a scene, and computes the ray for that screen coordinate, traces the ray, and returns the color.

;TestScene.hs
:This is what gets rendered if no input file is specified.  This is meant to be edited by users.  Provided in GlomeView package.

;SolidTexture.hs
:Perlin noise and other related texture functions.  Part of GlomeVec package.

;Spd.hs
:NFF file parser for SPD scenes.

===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.