Bounding Volume Hierarchy - Construction

Construction

There are three primary categories of tree construction methods: top-down, bottom-up, and insertion methods. Top-down methods proceed by partitioning the input set into two (or more) subsets, bounding them in the chosen bounding volume, then keep partitioning (and bounding) recursively until each subset consists of only a single primitive (leaf nodes are reached). Top-down methods are easy to implement, fast to construct and by far the most popular, but do not result in the best possible trees in general. Bottom-up methods start with the input set as the leaves of the tree and then group two (or more) of them to form a new (internal) node, proceed in the same manner until everything has been grouped under a single node (the root of the tree). Bottom-up methods are more difficult to implement, but likely to produce better trees in general. Both top-down and bottom-up methods are considered off-line methods as they both require all primitives to be available before construction starts. Insertion methods build the tree by inserting one object at a time, starting from an empty tree. The insertion location should be chosen that causes the tree to grow as little as possible according to a cost metric. Insertion methods are considered on-line methods since they do not require all primitives to be available before construction starts and thus allow updates to be performed at runtime.