Editing Glome tutorial (section)

===The Bounding Interval Hierarchy===

Fortunately, there's an easier way, and we've mentioned it before: use "bih".

The "bih" constructor takes a list of primitives and sorts them into a hierarchy of bounding planes called a Bounding Interval Hierarchy.

(more information on this method can be found here: Carsten Wächter and Alexander Keller,[http://ainc.de/Research/BIH.pdf Instant Ray Tracing: The Bounding Interval Hierarchy])

BIH is one of many acceleration structures used in ray tracing.  Other choices are: regular grids, BSP trees, octrees, bounding volume hierarchies (BVH), and kd-trees.  Currently, Glome only supports BIH (though there is an earlier written in Ocaml that supports kd-trees as well).

In general, BIH is well-behaved but there are a few cases to avoid when possible.  For instance: try not to use very long skinny things, especially if they're overlapping a lot of other long skinny things.  If you want to render a thousand toothpicks spilled on the floor, then you might want to consider representing each toothpick as a series of short cylinders instead of one long cylinder.

Another problem with the bih constructor is that it doesn't know how to interpret complex hierarchies.  For instance, if you pass a list containing a single transformation of a group of objects, then bih will treat it as a list of a single object.

There is a useful helper function to flatten out complex hierarchies of bound objects, transformations, and groups.  The function is "flatten_transform":

<haskell>
flatten_transform :: Solid -> [Solid]
flatten_transform (Group slds) =
 flatten_group $ concat (map flatten_transform slds)

flatten_transform (Instance s xfm) =
 case s of 
  Group slds -> flatten_transform $ group (map (\x -> transform x [xfm]) slds)
  Bound sa sb -> flatten_transform (transform sb [xfm])
  Instance sa xfm2 -> flatten_transform (transform s [xfm])
  _ -> [transform s [xfm]]

flatten_transform (Bound sa sb) = flatten_transform sb
</haskell>

flatten_transform throws away manually created bounding objects it finds, and pushes all transformations out to the leaves of the tree.  In many cases, this will mean that the scene will consume more memory; however, it may also render much faster.