Overview Algorithms Comparison Timing
Examples Animations Publications Downloads

Sphere-Tree Construction Toolkit

Overview

Interruptible collision detection aims to provide real-time simulations with constant high frame-rates. This is achieved using a proxy object to represent the objects. This proxy object is then used to perform level-of-detail collision handling in a time-critical fashion. The most common proxy representation is a sphere-tree, which represents the objects as a hierarchy of spheres. Our sphere-tree construction toolkit implements a number of algorithms for the construction of sphere-trees. These algorithms include our new algorithms, which are detailed in various publications .


Algorithms

The sphere-tree 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 sub-section of the object's volume. The Sphere Tree Generator algorithm controls the construction of the sphere-tree by managing how the object is sub-divided. 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 sphere-tree. 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 sphere-tree, which would typically contain around 8 spheres. Prior to the approximation of the sub-sections 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 sphere-tree. The following summarises the sphere-tree generation algorithms that are available :

Octree

The Octree algorithm is the simplest and fastest algorithm for the construction of sphere-trees. The first step of the algorithm is to construct a bounding cube that surrounds the object. This cube is then divided into 8 sub-cubes by splitting it along the X, Y and Z axes. The sub-cubes that are contained within the object are further sub-divided to create a set of children nodes. This sub-division can continue to an arbitrary depth. The nodes of the octree are finally used to construct a sphere-tree by creating a sphere that contains each of the "solid" nodes, i.e. nodes that represent part of the object. Our implementation of this algorithm is capable of creating either a shell of the object or a solid representation. When constructing a solid object the algorithm doesn't need to sub-divide any nodes that are completely contained within the object as areas inside the object don't need to be refined.


Grid

This algorithm is an extension to the Octree algorithm. Each set of children spheres is created by sub-dividing the parent node but the grid algorithm allows more freedom in the sub-division. Where the octree algorithm only ever produced a 2*2*2 division, the Grid algorithm can produce a grid of spheres with ANY dimensions as long as the number of spheres produced is within the specified maximum. The algorithm also optimises the orientation of the grid of spheres, and their size, so as to minimise the error in the approximation and to minimise the volume of each of the resulting regions.


Hubbard

Hubbard uses an approximation of the object's medial axis to construct sphere-trees. The medial axis is approximated using a set of spheres which are then used to construct the sphere-tree. This algorithm often produces tight fitting sphere-trees, certainly tighter than the Octree algorithm.


Merge

The merge algorithm is similar to the algorithm used by Hubbard. The set of spheres approximating the medial-axis is reduced down to the number required for the sphere-tree by successively merging pairs of spheres together. The merge algorithm uses the adaptive medial axis approximation algorithm to generate the initial set of spheres. It also considers the effects of merging pairs of spheres together that will actually improve regions of the approximation.


Burst

The burst algorithm is another medial axis based algorithm. It aims to improve upon the merge algorithm by better distributing the error across the resulting set of spheres. The algorithm iteratively reduces the set of spheres by bursting (removing) a sphere and using the surrounding sphere to fill in the gaps. This algorithm is typically well suited to constructing the top levels of sphere-trees but may not perform so well for the lower levels.


Expand

The expand algorithm takes a different approach to reducing the set of medial spheres. In order to reduce the worst error in the approximation, the algorithm tries to distribute the error evenly across the entire region. This is achieved by growing each of the spheres so that they all hang over the surface by the same amount and selecting a sub-set of the spheres that will cover the object. A search algorithm is needed to find the "stand-off distance" that will result in the desired number of spheres.


Spawn

The spawn algorithm aims to produce similar results as the expand algorithm. Each set of spheres is produced by creating a set of spheres that hang over the surface by the same amount, thus distributing the error evenly across the approximation. Instead of using the object's medial axis for the construction, a local optimisation algorithm is used to generate the set of spheres. For each sphere in the set, the optimisation algorithm chooses the location that covers the most object, hence keeping the set of spheres small. A search algorithm is again used to find the "stand-off" distance that yields the required number of spheres.


Combined

The combined algorithm allows a number of different algorithms to be used in conjunction. For each set of spheres, the algorithm tries a number of the other algorithms and chooses the one that results in the lowest error. Any of the sphere reduction algorithms can be used in this algorithm, i.e. Grid, Merge, Burst, Expand and Spawn, however we typically only use Merge and Expand as these are usually produce the tightest approximations.


Comparison

The following graphs compare the various algorithms in the toolkit. As we use the sphere-trees for real-time interactive simulations, we are most interested in the worst case error for each level of the sphere-tree. This is an upper bound on the gap that will exist between two objects that are thought to be in contact. A number of additional algorithms are also included. The "Hybrid" algorithm is a post-processed version of the "Grid" algorithm, each sphere in the sphere-tree has been replaced with one that covers the same region of the object by has minimum error rather than minimum volume. The "Optimised" algorithm is the "Combined" algorithm with a simplex based optimisation that further improves the fit of the sphere prior to their inclusion in the sphere-tree. The "Opt 0%" and "Opt 5%" are also an optimised version of the "Combined" algorithm except that the algorithm is allowed to throw away spheres as long as the worst error is less than 100% or 105% of its original value.

Level 2 Level 3
Bunny
Dragon
Block
S-Shape

Timings

The following table shows the time taken to construct the sphere-trees using some of our algorithms. Each sphere-tree has 3 levels and a branching factor of 8. This gives us 8, 64 and 512 spheres at the different levels. The times are measured in seconds and the sphere-trees where constructed on a 2GHz Pentium IV with 512MB RAM running WindowsXP. Hubbard's algorithm used a medial axis approximation containing 2500 spheres for the bunny and 20,000 spheres for the dragon and the lamp. The adaptive medial axis algorithm used an initial set of 500 spheres and updated the medial axis so that it contained 200 spheres and less than 1/2 the error of the parent sphere.

Bunny Dragon Lamp
Hubbard 69 1629 1454
Merge 473 595 428
Burst 2083 2000 456
Expand 284 342 1474
Combined 2131 1353 894

Examples

The following pictures show some of the sphere-trees constructed using the combined medial axis algorithm. They were constructed using the "makeTree" program with the following parameters, which we have found to work very well on most models :


-branch 8 The tree's branching factor is 8.
-depth 3 The tree is to have 3 levels, with 8, 64 and 512 spheres.
-testerLevels 1 For measuring error a sphere is going to be represented by a set of points created by sub-dividing an iso hedron once, i.e. 42 points, 2 would use 162 points, -1 uses a tester that assumes the body is CONVEX.
-numCover 10000 A set of 10K points is to be used to represent the surface of the object.
-minCover 5 Each triangle is to be represented by at least 5 points.
-initSpheres 1000 The initial medial axis approximation will be built to have 1000 spheres.
-minSpheres 200 When updating the medial axis approximation each region is to be covered by at least 200 spheres.
-erFact 2 When updating the medial axis approximation each region it to have at most half the error that was present in the parent sphere.





Animations

These animations show the use of sphere-trees 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.
NOTE : You'll need the
DivX 5 codec to play these AVI's.

ShammyShoot
Level 1
Level 2

These animations show a number of shamrocks falling down a set of shoots. The collision detection is performed using levels 1 and 2 of the sphere-tree (i.e. 8 or 64 spheres). The approximated object can be seen on the left hand side of the screen. When using the level 2 spheres, some of the shamrocks manage to slip between the gaps in the shoots. As the level 1 of the sphere-tree represents a fat version of the shamrocks, they are unable to fit through the gap.


BunnyRamp
Level 0
Level 1
Level 2
Level 3

These animations show a number of bunnies bouncing off a set of ramps. Collision detection is performed using non-interruptible collision detection where the sphere-tree is traversed down to a specific level. As the approximation being used for the collision detection gets tighter the gaps get smaller. Some interpenetration does occur at the lower levels due to the small sizes of the spheres.


BunnyBowling
Wide View
Close Up

These animations show a variation on 10 pin bowling. The pins have been replaced with bunnies and a dragon shoots down the alley to knock them into the gutter. The simulation uses the interruptible collision detection algorithm and the frame-rate has been set to 10fps.


CowDrop
Front
Side

This animation shows a giant cow falling onto the letters ISG. The interruptible collision detection algorithm was set to run the simulation at 10fps.


LampBowling
1 2 3

These animations show the bowling alley using lamps as pins and a teapot instead of the ball. The interruptible collision detection algorithm was set to run the simulation at 5fps.


Related Publications


Downloads

You can download a ZIP archive containing ALL the models and sphere-trees that we have featured on this page. The models are supplied as OBJ files and SUR files, which contain pre-computed triangle neighbourhood information for faster loading.

The sphere-tree construction algorithms are also freely available for download. The GUI version is only available for windows platforms but the command line version works on any UNIX-like system, i.e. those capable of compiling supporting programs distributed using autoconf and automake.

Source Code:
Version 1.0 (Feb 2003)
DOWNLOAD...

Pre-compiled Binaries (Win32):
Version 1.0 (Feb 2003) DOWNLOAD...

Sample Data: DOWNLOAD...


Gareth Bradshaw
12 February 2003