AlgorithmsThe spheretree construction framework contains a number of different algorithms. The Octree and Hubbard algorithms implement the existing algorithms upon which we have based our comparisons. Our own algorithms are based around the notion of a Sphere Reducer. The sphere reducer algorithms produce a set of spheres to approximate a subsection of the object's volume. The Sphere Tree Generator algorithm controls the construction of the spheretree by managing how the object is subdivided. When a set of spheres is constructed the generator uses the spheres to partition the object into a number of regions, each of which is then approximated using a sphere reducer algorithm. There are also a number of optimisers available in the toolkit. The generator algorithm can apply an optimiser to a set of spheres to improve the approximation prior to their inclusion in the spheretree. Many of our algorithms are based on Hubbard's medial axis algorithm. We, however, have extended the notion to allow the medial axis to be approximated in an adaptive manner. Initially the medial axis approximation would contain a relatively small number of spheres, typically 500 to 1000. This is sufficient to construct the top level of the spheretree, which would typically contain around 8 spheres. Prior to the approximation of the subsections of the object the adaptive medial axis approximation algorithm is used to improve the medial axis around the region being processed. This means that the medial axis will always be detailed enough to construct a tight fitting spheretree. The following summarises the spheretree generation algorithms that are available :

Animations
These animations show the use of spheretrees in out interruptible collision handling system. The REact II
(react to) system uses Sweep and Prune for its broad phase and interruptible collision detection for the narrow phase.

Related Publications

Downloads
You can download a ZIP archive containing ALL the models and spheretrees that we have featured on this page.
The models are supplied as OBJ files and SUR files, which contain precomputed triangle neighbourhood information for faster loading.
Version 1.0 (Feb 2003) DOWNLOAD... Precompiled Binaries (Win32): Version 1.0 (Feb 2003) DOWNLOAD... Sample Data: DOWNLOAD... 
Gareth Bradshaw 12 February 2003 