Goldsmith Salmon Bounding hierarchies

This teapot was ray traced in 28 seconds. Time before
optimization was a few hours.                   

Given a list of polygons to display, we want to create a tree of optimum bounding volumes. We start building the tree from the root, and add each new polygon at the best possible location. The best location is decided by evaluating a cost function for each possible insertion method. The minimum cost method is selected. The tree should ideally be traversed in breadth first order, first choosing the best child node location for a given level and only then exploring the children for that location.

There are three possible ways of inserting new nodes to a hierarchy. Of these the third is not a unique method in itself, but rather an application of the first two methods at a child node.

Method 1: Given a leaf node (polygon) or a bounding volume node , generate a new bounding volume (see BV below) that encloses the current location and the new node.

cost difference from before= 2 * P(BV)

where P(BV) means the area of the BV (remember that probability of ray intersection is proportional to the surface area) We multiply the cost by 2 because there are two children, so the volume must be intersected twice to ray trace each child.

Method 2: Given a bounding volume node, add the new node as a child (leaf node), and increase the parent bounding volume if needed (a parent volume increase is shown below for adding new node 3):

Method 3:

Try one of the above methods for child nodes ( a recursive process).

Let BV'= new bounding volume, k is number of children before adding new node

cost difference from before = ( P(BV') - P(BV) ) * k

At each step in the algorithm, we evaluate the cost of the above methods at each node, and selct the location to add based on minimum cost difference.

Ideally one should shuffle the list of polygons before building the tree, though I did not notice a significant difference.