Enhanced Automatic Creation of Multi-Purpose Object Hierarchies

of large scenes in terms of quality and computational cost. However, the
meaning of ``well-adapted'' depends heavily on the criterion due to which
the hierarchy has been constructed. Different applications typically use
different criteria like minimizing the overall intersection cost for a ray
tracer or clustering objects with similar material properties or surface
orientation for hierarchical radiosity.

In this talk a new algorithm for the automatic creation of object hierarchies
is proposed, which overcomes many of the drawbacks of previous approaches.
This is achieved by defining a generic cost function that contains previously
presented ones as special cases. Based on an enhanced set of insertion rules
an O(n log n) incremental algorithm is presented that creates object
hierarchies by sequentially inserting each of the n scene objects into the
hierarchy built up so far.

Even better results can be obtained by running a global optimization on the
completed hierarchy. During this optimization step a re-grouping of the
objects in the hierarchy is performed. Any ill-formed groups that were created
during the initial algorithm are subject to being eliminated by the global
optimization.