Item

Abstract

Using well-adapted object hierarchies can support the rendering
of large scenes in different ways. For instance, the quality of the lighting
simulation may be improved, or the computational cost for rendering may be
reduced. However, the meaning of ``well-adapted'' depends heavily on the
criterion due to which the hierarchy has been constructed. Different
applications typically have different demands like low average intersection
cost for a ray tracer or grouping objects with similar material properties
or surface orientation for hierarchical radiosity.

In this paper we propose a new algorithm for the automatic creation of
object hierarchies. The hierarchies are constructed by sequentially
inserting all scene objects into the hierarchy created so far. By
basing the insertion decision on a cost function defined by the user, the
method can be guided to create hierarchies tailored to the desired
application.

The results can be improved significantly by running a global optimization
on the completed hierarchy. During this optimization step we perform a
re-grouping
of the objects in the hierarchy. Any ill-formed groups that were created
during the initial algorithm are subject to being eliminated by our global
optimization.