Real-Time Collision Detection and Response Using Sphere-Trees

O'Sullivan, C. Dingliana, J.
Image Synthesis Group, Trinity College Dublin.

Abstract such approaches, the problem is postponed rather than

eliminated, and such computational power will not be
In this paper we address the problem of collision available to a wide range of users. An additional
detection and response in real-time animation systems. challenge is maintaining a constant frame rate. The time
We describe an approach, which approximates objects taken to render a given scene is dependent on the current
using sphere-trees, and uses an interruptible detection level of complexity. Some frames may require only one
algorithm to approximately test for collisions between object to be rendered, whereas a sudden change of view
them, trading accuracy for speed. A model of human may cause many more interacting objects to be visible in
visual perception of collisions is used to decide which subsequent frames. Obviously, the latter set of frames will
collisions deserve more processing time. Collision take longer to process than the former, regardless of the
processing is then scheduled to minimise the perceived computational power available. Hence, increasing
inaccuracy within the time available. In response to such computational power alone is not the solution. It may
approximate collisions, a new adaptive collision response sometimes be necessary to trade realism and accuracy for
algorithm is presented, which also uses sphere-trees to speed, and aim to achieve optimal realism in the time
approximate the appropriate response for colliding available, thus maintaining a high and constant frame-
objects. rate.
In this paper, we address the problem of collision
handling, and demonstrate how interactions between
1 INTRODUCTION objects may be handled in real-time, reducing the
variability of the frame-rate by interrupting processing
Many interactive animation systems, such as games or when required. Artefacts will inevitably be introduced
simulations, require large numbers of virtual entities due to the reduced accuracy of our calculations, but we
which are moving and interacting with each other, and/or reduce the visual impact of these inaccuracies by using
with one or more users. In these applications, we cannot perceptual information. In Section 2 we introduce the
predict in advance how the user or the entities will problems of collision detection and response, and review
behave, so we must create the animation as we watch it, current work. In Section 3 we describe the collision
i.e. in real-time. This means that the image must be re- handling algorithms we have developed, and an
drawn at least 10 times per second, although for true real- application which uses them. Section 4 presents
time performance the generation of up to 60 frames per conclusions and plans for future work.
second (f.p.s) may be required. Hence, there will be 100
milliseconds available, at the most, to update all entities
in the simulation, and then render the new scene.
2 BACKGROUND
A possible scenario could be a game where a user
must navigate his/her way through a rockfall without In many interactive real-time animation systems,
being hit. As multiple rocks are falling, they hit off each such as those described above, the entities often need to
other and the edges of a ravine, either bouncing or be viewed not as geometric shapes devoid of physical
breaking into smaller rocks. In order to achieve this properties, but as real entities having properties such as
effect, collisions between the rocks and with the ravine mass, moment of inertia, elasticity, and friction. Their
edges must be detected. Many other application areas motions are constrained not only by their own physical
exist: Large-scale Virtual Reality (VR) systems with properties, but also by collisions with other objects. If two
thousands of moving entities; Crowd simulations; Flocks solid objects collide in the real world, they bounce off
of birds or other organisms; Educational simulations with each other, or break into pieces, and deform if their
chemical molecules or blood cells. Anything, in fact, surfaces are non-rigid. In a computer world, there is
where you have large numbers of entities moving around nothing to stop geometrically modelled objects from
a virtual world in real-time. simply floating through each other like ghosts! A
There are many bottlenecks in such systems. Collision Handling system is necessary to enforce
Depending on the level of realism required, rendering and solidness, and ensure that entities behave as expected
motion synthesis algorithms require a large amount of when they come into contact, i.e. they should not
processing power. In multi-user systems, network lag is a interpenetrate, and their behaviour subsequent to collision
major issue. Some solutions to these problems could be to should be compatible with their physical properties. This
increase the computational power, add hardware involves two very distinct phases: Collision Detection,
accelerators, and develop parallel algorithms that may be and Collision Response. Detection is a problem of
implemented on multiple processors. However, using kinematics, while response is a problem of dynamics.
2.1 Collision Detection incompletely tested collisions as real collisions, and
compute the appropriate collision response. In the former
Traditional collision detection algorithms have required a case, it takes the risk of letting two entities float into each
large amount of geometrical intersection tests, checking if other i.e. interpenetrate. In the latter case, some entities
any of the polygons used to model the surface of one may be seen to approach each other, and then strangely
entity touch or penetrate any polygon on the other entity. repulse each other without touching, as if by some form
To improve the efficiency of such algorithms, hierarchical of magnetic repulsion. We will refer to these two cases
representations of entities were generated, to localise the respectively as inter-penetration and repulsion from
areas where the actual collision occurred. Such now on.
representations approximate the topology of an object at The advantage of an interruptible algorithm is that
different levels of detail. These include Sphere-Trees the application has full control over the length of time that
[Palmer and Grimsdale 1995][Hubbard the collision detection algorithm may take. It can then use
1995,1996][Quinlan 1994], OBB-trees (Oriented this to control frame rate, keeping it constant and high.
Bounding Boxes) [Gottschalk et al. 1995], ShellTrees The disadvantages of this approach are obvious. The
[Krishnan et al. 1998], and hierarchies of k-DOPs viewer may be unlucky enough to see the artefacts we
(Discrete Orientation Polytopes)[Klosowski et al. 1997]. have just mentioned, i.e. repulsions or inter-penetrations.
Most of these algorithms are actually hybrid algorithms, The application can control which of these artefacts
involving two or more phases of detection at varying occur, depending on how it handles collisions which have
degrees of accuracy. The broad phase is where not been fully processed, but it cannot prevent them
approximate intersections are detected, eliminating occurring. With a simple round-robin approach, the
objects which are far away from each other. More collision detection algorithm may have been busy with
accurate collision detection is then performed in the some collisions that are out of sight, either out of the
narrow phase. camera view, or far away in the distance, while two large
While the speed and efficiency of algorithms has entities directly in front of the viewer, parallel with the
been the main focus of such research, the issue of a viewing plane, are allowed to repulse or interpenetrate
constant frame rate is also paramount. Consider a room dramatically.
with a hundred bouncing balls in it. As long as the balls
are evenly distributed around the room, the number of 2.2 Collision Response
collisions will be reasonable, with several small groups of
two or slightly more balls coming into contact with each Closely related to collision detection is the issue of
other every few milliseconds. As long as the balls remain collision response. The problem of predicting how objects
evenly distributed around the room, the time to detect react to collisions is not a new one and methods exist for
collisions between them, and hence the frame-rate, will calculating to a high degree of accuracy, in real-time, how
remain fairly constant, e.g. about 10 milliseconds. simple objects react to collision events [Baraff 97].
However, eventually the balls all drift to one corner of the However this is based on the assumption that accurate
room. Now each ball in the room will be in contact with data is available about the collision such as the exact
many other balls, each of which will also be colliding instant of the collision, the states of the colliding objects
with many others. There are now very many possible at this instant in time and the exact point (or indeed
combinations of entity-entity collisions to detect every points) of contact between the colliding entities. Before
few milliseconds, so the time to process collisions, and we can apply any mathematics to the problem we must
hence the frame rate, will increase dramatically. This first derive the required parameters which will determine
could result in several frames that take 200, 300 or even how an object reacts to a collision. It is not enough
more milliseconds to process until the balls again separate merely to determine whether or not objects have collided
to a more even distribution. The resulting animation will but we must also determine the nature of the collision
be very jerky and unrealistic. which has occurred.
This problem has been addressed in part by With the burden of delivering real-time frame
exploiting coherence [Cohen et al. 1995]. This approach rates, we must always be aware that any processor time
uses the fact that with small time-steps, the positions of spent on collision response determination must be
objects are unlikely to change too much from frame to subtracted from the time available for the collision
frame, enabling efficient sorting algorithms to be used. detection mechanism in our system. However, collision
Another approach to the problem has been to develop an detection is the main bottleneck in real-time animation
interruptible collision detection algorithm [Hubbard because we have to check all objects in the scene (at the
95,96]. The entities are approximated by sphere-trees, and very least in the broad phase) to determine if they have
entities close to each other are tested for collisions at collided. Whereas collision response (including all
increasing levels of accuracy in round-robin order. When required data gathering operations) is required only when
the application wishes, e.g. after an allocated amount of we actually detect such a collision. With this in mind
time runs out, the collision detection algorithm is many Physically Based Simulation systems attempt to
interrupted, even though it may not have finished implement highly accurate collision response calculations
processing each collision fully. The application may then and this is a feasible option when the number of colliding
decide to completely ignore the collisions that have not objects is always expected to be fairly small. In such
been fully tested, or it may decide to treat such cases we might have a resolution mechanism, which is
largely independent of the detection system, with the a computational bottleneck.
required parameters passed to it by the detection
mechanism. 3 THE APPLICATION
On the other hand, for crowded scenes with a large
number of potential collisions in each frame (e.g. To apply and test the concepts and algorithms
rockfalls, debris) a quick and efficient mechanism would described above, a real-time animation system has been
seem the ideal choice; trading accuracy for speed. In such developed. This allows implementation and testing of
cases we would have to strive to deliver plausibility of various different collision scheduling and testing
response rather than mathematical accuracy [Barzel et al. strategies.
1996]. In fact it would be desirable if collision response
determination (including all data gathering operations
involved) could also be packaged into a refineable 3.1 Overall design
process in a similar way to our detection system, with the
accuracy of response increasing with the amount of CPU The application may be considered as consisting of
time allocated to it. However, refining the response of an an object, of type Animation. This Animation object
object to a collision is not a straightforward problem. represents a "world" in which entities exist, move around
Making guesses about the response of an object falls and interact depending on their physical properties, and
under the broader topic of Behavioural Culling [Chenny are rendered and displayed on a 2-dimensional display.
97] and certain problems arise where dependencies exist
between the behaviour of several objects. Certain
guidelines must always be followed (e.g. laws of
conservation of energy and momentum) and we must
ensure that some level of consistency is always
maintained in our system.

2.3 Visual Perception of Collisions

Considering the above problems, some common-sense
solutions immediately spring to mind: Process the
collisions in the camera view more fully than those
outside the current viewing window; Attach more
importance to entities that are bigger, nearer, parallel with Figure 1. Some sample entities
the viewing plane. These actions in themselves would
alleviate the problem considerably. However, much more The Animation object contains the entities in the world,
is possible. What effects do entity properties such as represented as an array of objects of type Entity, a
colour, luminance, velocity, and semantics have on our volume/box within which the entities move and interact,
perception of the collisions in which they are involved? and viewing parameters, i.e. a description of the current
How can a combination of weights be given to these state of the "synthetic camera" used to gain a view of the
effects, in order to prioritise and schedule collision world. It also contains lists and tables to keep track of
processing? What if it was known where exactly in the interactions and collisions between objects. An all-pairs
visible scene the viewer was looking? It is a well- table sets a flag for every pair of entities if the projection
established fact that visual and spatial acuity falls off of their bounding boxes onto each of the x, y and z axes
rapidly with increasing eccentricity of stimuli from the overlap. Overlaps in all three dimensions means that the
point of the eye's fixation. Is this also true for collisions? bounding boxes themselves overlap, indicating a potential
Would a viewer be less likely to notice a repulsion or collision of the entities themselves. In addition, two or
inter-penetration if it happened on a part of the screen at more lists of collisions are maintained, represented as
which they were not directly looking, or how close to the linked lists of objects of type Collision:
point of fixation, and how significant must the anomaly
be for it to be noticed? - The active collision lists: one or more lists of
In [O'Sullivan 1999] a model of human visual potential collisions created from the all-pairs table,
perception of collisions is presented, based on two- and consisting of all pairs of entities suspected of
dimensional measures of eccentricity and separation. colliding, due to an overlap of their bounding boxes,
The model is validated by performing psychophysical but which need further processing by our
experiments. It is demonstrated how this model could be intersection-testing algorithm to determine whether
used as the basis for perceptual scheduling of interruptible they are really colliding or not.
collision detection in a real-time animation of large - The real collision list, which contains all pairs of
numbers of homogeneous objects. Using an eye-tracker entities that have been detected as really colliding by
to locate the user's point of fixation, perceived collision our intersection-testing algorithm.
inaccuracy was approximately halved for up to 500
tightly-packed objects. The ideas presented are applicable The main methods/operations that an Animation object
to other tasks where the processing of fine detail leads to can perform are Construction/Initialisation and Execution.
A new animation can be instantiated, specifying exactly - Two pointers to objects of type Entity, i.e. to the
how the "world" should be, i.e. number of objects, entities involved in the collision
dimensions of the box, initial viewing parameters. The - A pointer to the previous collision in the list (if any).
objects will be given their initial positions in the world, - A pointer to the next collision in the list (if any).
and the collision lists and tables will be set to reflect the - A sphere hit list (see section 3.3)
interactions of the objects. Once the world has been - The centre of collision (see section 3.4)
created, with all the objects in it, the animation may then - The distance of the centre of collision from the
begin. In its simplest form, execution consists of the (estimated) fixation location
following loop: - The priority of the collision.
- The status of the collision (i.e. colliding, not
DO
colliding, or further processing required).
- Update the position of all objects
- Update the all-pairs table by testing object bounding The main methods/operations that an object of type
boxes for overlaps in all three dimensions Collision may perform are:
- Generate the active collision list from the all-pairs
table - Initialisation
- Process the active collision list, removing collisions - Maintain the links to the previous and next collisions
as they are resolved, placing detected collisions on in the list
the real collision list, and discarding those where the - Intersection test: Tests one level of one sphere tree
objects are found not to be touching. against one sphere on the other tree. Section 3.3
- Process the real collision list, computing the discusses the sphere-tree intersection algorithm in
appropriate collision response for each colliding pair more detail.
of objects. - Set collision priority: This is where we will use the
- Draw all objects perceptual model, which is based on the results of
UNTIL animation is terminated. psychophysical and physiological studies.
The Entity objects contain all information about
the entity, such as position, size, translational and
3.2 Broad Phase Collision Detection
rotational velocity, colour, material, along with a pointer
For the broad phase of our collision detection algorithm,
to an object of type Sphere, which will be the root of the
we use the “Sweep and Prune” algorithm proposed by
sphere tree that approximates it. We have used a very
[Cohen et al. 95]. This algorithm is based on the
simple volumetric representation for the entities in our
observation that:
application. Each entity is defined by a 3-dimensional
array of 1's and 0's, a 1 indicating the presence of a cube,
For two 3-dimensional objects to overlap
a 0 representing the absence. This simplifies the tasks of
in 3-dimensional space, their 2-
rendering, updating and generating sphere-trees greatly,
dimensional projections onto each of the
and it is for this reason that we chose this scheme. Figure
xy, xz, and yz planes must overlap in all
1 shows some entities modelled in this way. Although this
three cases.
modelling scheme is fairly simplistic, the collision
detection routines are designed to work with any sphere-
If axis-aligned bounding boxes are used, they can be
trees generated from any type of model. Therefore, our
projected onto the x,y and z axes, resulting in one-
work may easily be adapted to work in more general
dimensional intervals. Intersection of a pair of 3-
cases. The main methods/operations that an object of type
dimensional bounding boxes would result in overlaps of
Entity may perform are:
their corresponding intervals in all three dimensions. This
leads to a very quick and simple one-dimensional
- Initialisation
algorithm. At the first iteration, the bounding boxes are
- Set initial properties, i.e. colour, position, etc... generated for all objects, and projected onto the x, y and z
- Generate sphere tree, centred at origin. axes. A list is constructed for each dimension, containing
- Update the endpoints of all intervals corresponding to that
- Render dimension. These lists are then sorted using an efficient
sorting algorithm for previously unsorted lists, such as
The Sphere objects are the building blocks of the Quick Sort. Any intervals that overlap are then detected,
sphere hierarchies that approximate an entities, described and if overlaps occur in all three dimensions for a pair of
in detail in section 3.3. A sphere contains the information bounding boxes, the Narrow Phase is triggered.
about its radius, its centre relative to the origin, and its At each subsequent iteration of the application,
centre relative to the entity in its updated state. The sphere bounding boxes are updated, and appropriate changes
also contains pointers to other spheres, allowing the made to the interval lists. Due to inter-frame coherence,
sphere tree to be built up recursively. The Collision and the fact that the lists were previously sorted,
objects are nodes which may be linked together to make a Insertion Sort is used to keep them sorted. Again,
dynamic list. These objects consist of: overlaps in all three dimensions will trigger the Narrow
Phase of the algorithm. One issue which arises is whether 3. Each hierarchy should fit the entity as tightly as
to use Fixed-Size bounding cubes, which are large possible.
enough to hold the convex object at any orientation, or
Dynamically-Sized bounding boxes, which will be Because of criterion 2, (i.e. efficient searching and
recomputed at every frame to be the smallest axis-aligned elimination at each level), a tree is the obvious data
box that contains the object at its current orientation. structure to use. Another possible structure is a Directed
Although dynamically sized boxes are more accurate, Acyclic Graph (DAG) in which parents can share
they add a computational load at each frame. Fixed-sized children. The structure of the sphere-tree which we use is
cubes are simpler to update, but may give rise to many shown in Figure 3. Each sphere in the tree contains a
unnecessary Narrow Phase collision tests. The choice of pointer to the first sphere in its child list. If this sphere is a
bounding volume may depend on the shape of the object. leaf, this pointer will be NULL. In turn, each sphere
If it is almost spherical, the fixed cube fits it well, and if contains a pointer to its parent (NULL for the root), and
it’s long and thin, dynamically sized rectangles fit it to its next sibling in the sibling list, if any.
better, and give rise to fewer overlaps. Perhaps both could Sphere trees may be built so that children must
be used, with each object being bounded by the most fully cover all parts of the object that their parent does, or
suitable volume. simply a subset of those parts. We have chosen to build
The number of objects moving in the scene may our sphere-trees to represent a conservative over-
also be a factor. [Cohen et al. 95] claim that if many approximation of the object’s exposed volume. Collisions
objects are moving, the computational burden of updating involving any uncovered areas of the surface will remain
bounding volumes at each frame could significantly undetected by the detection system so we require that our
degrade performance, whereas if only a few objects are hierarchy of spheres at each level encompasses the object
moving, the reduction in Narrow Phase collision tests completely. On the other hand, we need to ensure that
achieved by using tighter bounding boxes, outweighs the there are no redundant spheres in our sphere-tree such as
computational cost of computing the boxes. We choose those that are occluded by other spheres and thus play no
to use fixed-size bounding boxes for our application, as part in the actual collision detection. The accuracy of both
we will be animating large numbers of entities. collision detection and response in our system is
dependent on our sphere-tree representations of the
3.3 Sphere trees. objects in our system so we would desire that the sphere
trees fit the object as tightly as possible. At the same time,
Spheres are frequently used in computer graphics limiting the number of nodes at each level of the sphere
as approximations to objects. One reason is that it is very tree directly implies less computation for the detection
simple to test for intersections between them. Another mechanism so a simple model would also be desirable.
more important reason is the fact that they are rotationally What we require then is an automatic method of
invariant. Because of this property, it is possible to build a generating sphere-tree representations, which will be as
hierarchy of spheres to approximate any non-convex tight as possible and yet simple enough so that it would be
object once in a pre-processing phase, centred at the feasible to use it in our real-time application. The method
origin. Whenever we wish to test for a collision between implemented in our system is based on octree subdivision
two entities, we translate and rotate the centres of the of the object volume.
spheres on each approximating tree as we need them, and
test for intersections between them
For the narrow phase of our algorithm, we have
developed an interruptible algorithm based on sphere
trees. We have adapted a "staircase" algorithm from
[Palmer and Grimsdale 1995], and have made it
interruptible, as in [Hubbard 1995]. The sphere trees are
generated during a pre-processing phase, each tress
Figure 2. An entity and 4 levels of its sphere-tree
consisting of 4 levels of spheres, each level representing
a closer approximation to the surface of the object (see
An octree representation of the object is generated
Figure. 2).
by recursive subdivision [Sammet & Webber 88]. The
smallest bounding cube needs to be determined, which
3.3.1 Building Sphere Trees
will completely encompass the object. This is the coarsest
level of the octree and represents the bounding cube for
[Hubbard 1996] lists three requirements for generating
our object. This cube is then subdivided into eight equal
hierarchies of spheres:
partitions or octants. If any of these partitions contains
any part of the object then it is enabled as a node on the
1. The pre-processing phase must be automatic, with no
octree. Each octant is then recursively subdivided in a
user-intervention necessary
similar way up to the level of decomposition required.
2. The hierarchy must be structured in such a way as to
Determining whether or not a 3D sub-partition contains
make searching it efficient, with each level
any part of the object can be done in several ways
eliminating the need to search a significant subset of
depending on the method initially used to describe the
the next level
object’s volume (e.g. face intersection tests). In our
present system we require that each object has a voxel children of the old target becoming the new test list. In
representation of its volume so determining whether or this way, the algorithm is fully interruptible, allowing the
not to attach a child node simply involves checking if the detection to descend one level of one tree at a time,
corresponding octant contains an enabled voxel. reducing the complexity of the algorithm, and enabling a
Once the required octree has been generated, it is a fast, albeit approximate, response when necessary.
simple matter to find the smallest radius of sphere
required to completely encompass any particular node of 3.4 Interruptible Collision Detection
the octree. For regular cubes (side α) the required radius
is simply: The application performs the broad-phase testing,
and creates a list of collision objects called the active
collision list. This is a linked list of all collisions that have
not yet been resolved. As collisions are resolved, they are
For a cuboid of dimensions x, y, z : placed on the real collision list if a real collision was
detected, or are destroyed, if it has been determined that
the entities are definitely not colliding. If all collisions are
fully resolved, the frame-rate will be highly variable.
Therefore, it is sometimes desirable to interrupt
Finally we remove all nodes from the octree which are processing when a target time has elapsed. The control of
occluded on all sides by other nodes and the finished the processing order of collisions on the active collision
sphere-tree is obtained by generating all the spheres list is determined by the chosen scheduling mechanism.
corresponding to the remaining nodes of the octree.
3.4.1 Adding Interruption

At any point in time during collision processing,

there will be unresolved collisions on the active list, and
resolved collisions on the real list. At some point the
application will deem that collision processing should
stop. In our case the criterion for stopping is when a pre-
defined target time has been exceeded. However, other
criteria could just as easily be used. When the request for
an interruption is generated, the collision processing must
stop, and this will leave us with a list of real collisions
and a list of unresolved collisions still on the active
collision list. We have chosen to treat these collisions as
real collisions. In this case all the active collisions are
Figure 3.Design of a sphere-tree added to the end of the real collision list. We could just as
easily have chosen to reject these collisions, thus allowing
3.3.2 Sphere-Tree Intersection Algorithm inter-penetration, but for reasons explained in later
chapters, we will accept all unresolved collisions as being
We test for intersection between two sphere trees real. There are four possible results at each iteration of the
as follows: Take two sphere-trees, tree 1 and tree 2, which test for a collision object.
approximate two objects whose bounding boxes overlap
in all three dimensions. This has caused an object of type 1. An intersection is detected between two leaves of the
Collision to be created, with pointers to the roots of both trees. In this case the objects are deemed to be
trees. Each collision object contains a pointer to a list of colliding, and the collision is resolved. The collision
sphere hits. A sphere hit contains a record of the current will be removed from the active collision list, and
state of the collision object, i.e. what spheres on one tree added to the real collision list.
must be tested against what spheres on the other tree. This 2. No intersections are detected between any of the
consists of a target sphere on one tree, and a test list of targets of each sphere hit and the members of the test
spheres on the other tree. lists. In this case, the objects are definitely not
At the start of the algorithm, the list consists of one colliding, and the collision is resolved. The collision
sphere hit, i.e. the root of tree 1 is the target, and the root is removed from the active collision list and
of tree 2 is the test list. If these do not intersect, then there destroyed.
is no collision between the objects. If they do, a new 3. An intersection is detected between the target sphere
sphere hit is added to the collision's sphere hit list, the and a test sphere of at least one sphere hit, but at
root of tree 2 becomes the target sphere, and the children most one of the spheres is a leaf, so the collision test
of the root of tree 1 now become the test list. Continuing is non-conclusive. In this case, new sphere hits are
on in this fashion, every time an intersection is found created, and the collision remains on the active
between a target sphere and a member of the test list, a collision list for further processing if needed.
new sphere hit is created with the intersecting member of 4. During the iteration, the application indicates that it
the test list becoming the new target sphere, and the wishes to interrupt collision processing. In this case,
 if the sphere hit list is non-empty, the entities are [Hubbard 1995]), and use the sum of these distances as
deemed to be colliding, and the collision is removed our estimate.
from the active collision list and added to the real Not all collision inaccuracies contribute equally to
collision list. the inaccuracy perceived by the user in a single frame of
an animation. Hence, the perceived inaccuracy P present
Although our application creates 4 levels of sphere in two frames of an animation with identical geometrical
trees for every object, the intersection algorithm has been inaccuracy ∇, may be quite different depending on how
designed to handle intersection tests between two sphere the frame is viewed. It has been proven that eccentricity e,
trees of unequal height. This is handled by stopping the i.e. distance from the viewer's fixation point, and
cross-over in the algorithm, i.e. instead of adding a new separation, estimated by maximum 2D gap size g, are the
sphere hit between the children of the old target, and the two most important factors which affect perceived
intersecting member of the test list, if the old target has no inaccuracy, when large numbers of similar objects are
child, the new sphere hit is created with the old target being animated. Work is ongoing to determine the effect
remaining as target, and the test list is the child list of the of other factors, in other circumstances.
intersecting member of the old test list. The target If two spheres are interpenetrating, we find the
remains the same until an intersection is detected between midpoint on the line segment inside the intersection. We
it and a leaf of the other sphere tree, or until an call this the Centre of Collision. We track the user's gaze,
interruption occurs. This means that in the future, more so we know the fixation point F for each frame,
complex objects can be approximated by more levels of expressed as an x,y location on screen. We can therefore
more spheres, and more simple objects by only a few calculate the eccentricity e as follows: We find the x,y
levels (or even just one, in the case of spherical objects). location in screen co-ordinates of the centre of collision
projected onto the view-plane, then e is simply the 2-
3.4.2 Measuring Inaccuracy and Prioritising dimensional distance from F of the centre of collision.
Collisions Collisions closer to the fixation point contribute more to
the perceived inaccuracy of a frame than those further
This application provides a framework within which away and hence should receive higher weighting.
different collision detection, prioritisation and scheduling Collisions closer to F should receive lower weighting.
algorithms may be implemented and evaluated for Similarly, the size of the maximum on-screen gap,
computational and perceptual performance. A model of g, may also be used to weight each collision, with larger
collision perception based on eccentricity and separation gaps contributing more to inaccuracy than smaller ones.
is used both to prioritise collisions, and also to estimate We calculate an upper bound on the 2-dimensional gap
perceived inaccuracy [O'Sullivan 1999]. This model, size as follows: We take the centres of the last two
plotted in figure 4, has been validated by psychophysical spheres found to be intersecting, and calculate the 2-
means, and represents a good approximation to a human's dimensional distance between their projections onto the
perception of collision anomalies (i.e. repulsions) at screen.
different eccentricities and separation distances.
When considering the inaccuracy present in a
frame of an animation, we must distinguish between
geometrical inaccuracy ∇, and perceived inaccuracy P. f(e,g) = g / (exp(e/100))
The geometrical inaccuracy in a scene is an estimate of g
1.2 10
the overall three-dimensional error that has been incurred
by accepting non-collisions as real, causing entities to 20
f(e,g)

repulse without touching. It can be estimated by summing 30

the sizes of all potential gaps left during such "non-

collisions". In our applications, we cannot calculate the 0.0
exact size of the gap between two colliding entities, as 0 e 320
this would take an excessive amount of time and defeat
the purpose of approximate collision testing. Instead, we
can use the information available to us to estimate an
upper bound on the maximum gap size between two Figure 4. Perceptual function, f, showing the relationship
entities. We use the three-dimensional distance between between eccentricity e, and gap size g, The function f(e g)
the centres of the last two spheres found to be intersecting shows the probability of the viewer noticing a gap of that
from the sphere-trees of each colliding pair, or the size at that eccentricity.
distance between the centres of the two entities if
collision testing is interrupted before any spheres have 3.4.3 Scheduling
been tested. We estimate the geometrical inaccuracy ∇ in
a given frame by simply summing these distances. Hence, The key to controlling the collision inaccuracy
the further down the sphere-tree hierarchy each collision perceived by a viewer in a given frame of an animation
is allowed to progress, the more accurate the estimate will lies in the scheduling method adopted. We have seen in
become. Alternatively, we could pre-compute the previous sections that upon completion of the broad phase
Hausdorff distance for all spheres in each tree (as in of collision testing, an active list of collisions exists, one
collision object for each pair of entities whose bounding these calculations. The details required for an adequate
boxes overlap. In [Hubbard 1995] round-robin level of response calculations are outlined below:
scheduling is used, i.e. this list is resolved in round-robin
order, descending one level in the hierarchy of every i. mass (or relative mass of objects)
sphere tree at each iteration of the algorithm. However, no ii. centre of mass of objects
account is taken of the perceptual importance of each iii.moment of inertia of objects
collision. Other strategies are: sequential scheduling iv. state of colliding objects at the instance of collision
collisions are resolved fully one by one until completion (e.g. velocity, position).
or interruption. Again, perception is ignored with this v. the points of collision and
strategy. In perceptually sorted sequential scheduling, vi. the direction of the applied impulses
perceptual information is used to schedule collision
testing. A perceptual importance is attached to each Mass and centre of mass are determined at the pre-
collision, based on some criteria, and the active collision computation phase; moment of inertia can be computed
list is then sorted based on this priority. Sequential relatively quickly based on the current orientation of the
scheduling is then used, but now the collisions which are object and some pre-computed constant. We treat the
most important perceptually will be resolved first, leaving objects as if they actually were a union of spheres and use
the more unimportant collisions to be resolved only if this to approximate the other required parameters (i.e. the
there is time left. However, a significant overhead is collision direction, and collision points). Due to the very
incurred through the sorting process, and has been shown nature of our collision detection system the data passed on
to reduce the time for collision detection so much as to to the collision response system will at best be an
degrade, rather than improve performance. approximation for all but the highest priority collision
Another strategy is to generate not one active events in the scene. Once our detection system has
collision list, but a set of priority queues, and to round indicated that the nodes of two sphere trees have collided
robin within them. The perceptual model is used only to that is when the collision resolution phase begins. We
decide which queue a collision belongs to, thus reducing cannot justify doing further intersection tests (e.g.
the computational overhead. A higher priority queue checking for polygon level intersections) to determine the
would be resolved first, and only when all collisions on exact nature of the collision, as that would defeat the
that queue have been resolved would the next highest purpose of our interruptible algorithm. However given the
queue be handled. This is called priority queue positions of the colliding spheres, a fair approximation of
scheduling. It has been shown that priority queue the collision data can be made.
scheduling, using the above model of collision perception
to measure inaccuracy and to prioritise collisions, is the
most effective scheduling mechanism, with perceived
inaccuracy being approximately halved for large numbers
of objects.

3.5 Collision Response

A simple way of achieving refineable collision
response might be by treating all of the objects in our
system as the union of spheres represented by their sphere
trees. This seems like a logical approach as we have
already made this assumption in the detection phase. Not
only will we inherit all the data (variables and pre-
computed constants) but we also have a built in
Figure 5: A quick approximation of the collision data
consistency to our system. It becomes possible to
(given the identities and properties of the colliding
interleave the two processes of detection and response
spheres on the sphere trees)
(including all contact point determination etc.) and make
our whole system more cohesive. This is desirable in a
time-critical system as it would allow for more interaction Collision direction is taken as line joining the centres of
between the two processes. Certain calculations (for the two spheres (see Fig. 5). The collision point C lies on
this line and divides the line between O1 and O2 in
instance determination of gap-size, and the centre of
proportion to the radii of the spheres. We have illustrated
collision) would be useful to both detection and response
the situation when we let the sphere trees interpenetrate,
mechanisms and interleaving the two processes would
however the same principles would be applied if we
avoid repetition and make the system more efficient.
forced them to repulse at a distance. Note: similar
A simplified impulse based method is used to
calculations are done to compute the “centre of collision”
calculate responses [Baraff 97][Baraff & Witkin 98]
in the Collision Detection phase. Using this method, we
given the point of collision and the collision direction.
do not require a separate mechanism for prioritising
The full details of the collision response calculations fall
events for the purposes of response calculation. This has
outside the scope of this paper and we only describe here
been done for us at the detection phase, as the more
the process involved in obtaining the required data used in
important collision events will have been resolved to a
deeper sphere-tree level. The deeper we go down the certain if the actual objects will overlap when sphere trees
sphere tree, the more accurate our representation of the intersect but it may be preferable to have objects
object and hence our approximations of the collision point overlapping during collisions than to have a large gap-
and collision plane. In Figure 6, a, b and c show different size.
levels of detail for the collision data approximation. Fig. Inter-penetration in the system is a direct result of
6d shows the actual collision point determined by being limited to discrete time-steps; a limitation which all
polygon intersection tests. Note that in 6c two collision real-time systems suffer from. It is the single largest
points are detected. However resolving the two impulses source of inaccuracy in our system and we would want to
leads to a reasonably accurate approximation of the actual minimise this as much as possible. If our time-steps were
impulse. arbitrarily short or the velocities of entities in our system
were arbitrarily small, inter-penetration and the resulting
inaccuracy could be reduced to an acceptable level. This
cannot always be guaranteed in a real-time system and the
exact values, if required, must be obtained by performing
some form of backtracking or interpolation to determine
the states of the objects at the exact instant of collision
(i.e. before they actually interpenetrate).

4 CONCLUSIONS
In this paper we introduced a method of collision
handling which produces a refineable approximation of
the behaviour of objects due to collisions. The computing
cost for the response phase is fairly minimal so there is
more time available for other parts of the system
including collision detection and rendering, making it
suitable for an interactive real-time system. An
approximate model of collision response is implemented
in the attempt to generate plausible motion as opposed to
mathematically accurate motion, which would be
computationally more expensive. This is usually justified
as there is always a certain degree of uncertainty in the
real world which prevents us from predicting how exactly
an object will behave. The question that needs to be
answered is how to get the best return from the speed-
accuracy trade-off.
The model of collision perception which we use is
very specific. It represents typical human reactions to
Figure 6: How the response data automatically gets collision anomalies, where large numbers of
refined as we go deeper into the sphere tree homogeneous objects are being animated. Work is in
progress to make it applicable in more general cases.
The response mechanism will only have an Other factors, such as location and direction of motion,
approximation of the actual values at the moment of velocity, acceleration, colour and luminance can have
collision. A conservative approximation of the state of the very strong effects under certain circumstances, and if
objects, the point of collision and the collision plane necessary must also be included if the model is to be truly
would be obtained by taking the states of the objects the representative of human behaviour.
frame before inter-penetration of sphere-trees was At present all collision events are prioritised on a
detected. This would ensure that no inter-penetration of scheme based on tests, which were done with a number of
the actual objects ever takes place. However, as the subjects to determine how sensitive they were to
sphere tree bounds themselves are conservative approximate collision events occurring on different parts
approximations of the space occupied by objects such an of the scene. So far, this has largely been a test of how
restriction would even further increase the inaccuracy. A collision detection can be prioritised effectively. Similar
simpler approximation would be the states of the objects tests might be done to determine how sensitive viewers
at the instance when collisions were detected. This would are to approximations of particular responses to collisions
mean that our spatial model of the objects (i.e. the sphere and implement this in our prioritisation scheme. Inter-
tree representations) would in fact overlap over the course penetration is a major source of inaccuracy and needs to
of the animation. Again because the spheres are be minimised (or ideally eliminated) in order to ensure the
overestimates of the object volume, overlap to a certain robust and consistent operation of our system. However it
degree is acceptable. There is no way of determining for would be undesirable to err too far on the side of caution
as this too affects accuracy and more so the believability
of the animation. Some means of closely approximating [Hubbard 1995] Hubbard, P.M. (1995) Collision
the collision point needs to be implemented in real-time Detection for Interactive Graphics Applications. IEEE
by backtracking or interpolation. Transactions on Visualization and Computer Graphics.
Further behavioural detail still needs to be added 1(3) 218-230.
to the system to increase the realism and the general
applicability of the system. For instance, friction forces [Hubbard 1996] Hubbard, P.M. (1996) Approximating
during collisions, gravity and elasticity of collisions have Polyhedra with Spheres for Time-Critical Collision
been experimented with but are not fully implemented in Detection. ACM Trans. on Graphics, 15(3) 179-210.
the current system. Such factors would undoubtedly add
further complexity to the system and we need to [Klosowski et al. 1998] Klosowski, J.T. Held, M.
investigate how much more complexity we can afford and Mitchell, J.S.B. Sowizral, H. Zikan, K. (1998) Efficient
how we might also cull these behaviours in a fully Collision Detection Using Bounding Volume Hierarchies
adaptive real-time system. of k-DOPs. IEEE Trans. on Visualization and Computer
Graphics 4(1).
Bibliography
[Krishnan et al. 1998] Krishnan, S. Gopi, M. Lin, M.
[Baraff 97] Baraff, D. Physically Based Modelling. Manocha, D. Pattekar, A. Rapid and Accurate Contact
SIGGRAPH ’97 Course Notes. Determination Between Spline Models using ShellTrees.
in Proceedings of Eurographics'98.
[Baraff & Witkin 98] Baraff, D. and Andrew Witkin.
Physically Based Modelling. SIGGRAPH ’98 Course [O'Sullivan 1999] O'Sullivan, C. A Model of Collision
Notes. Perception for Real-Time Animation. Technical Report
TCD-CS-1999-01, Trinity College Dublin, January 1999.
[Barzel et al. 1996] Barzel, R. Hughes, J.F. Wood, D.N.
(1996) Plausible Motion Simulation for Computer [O'Sullivan and Reilly 1997] O'Sullivan, C. Reilly, R.
Graphics Animation. Computer Animation and REACT: REal-time Adaptive Collision Testing, , D.
Simulation '96. 183-197. Thalman, M. van de Panne (eds.) Computer Animation
and Simulation '97 163-175.
[Chenny 97] Chenny, S. Culling Dynamical Systems in
Virtual Environments. 1997 Symposium on Interactive [Mirtich 96] Mirtich, B. Impulse Based Dynamic
3D Graphics. Simulation of Rigid Body Systems. Phd Thesis, University
of California, Berkeley, 1996.
[Cohen et al. 1995] Cohen, J.D. Lin, M.C. Manocha, D.
Ponamgi, M.K.(1995) I-COLLIDE: An Interactive and [Mirtich and Canny 95] Mirtich, B. and Canny, J.
Exact Collision Detection System for Large-Scaled Impulse-based Dynamic Simulation. In Proceedings of
Environments. Proceedings of ACM Int. 3D Graphics 1995 Symposium on Interactive 3D Graphics. 181-188.
Conference. 189-196.
[Palmer and Grimsdale 1995] Palmer, I.J. Grimsdale,
[Ferwerda et al. 1996] Ferwerda, J.A. Pattanaik, S.N. R.L.(1995) Collision Detection for Animation using
Shirley, P. Greenberg, D.P. (1996) A Model of Visual Sphere-Trees. Computer Graphics Forum, 14(2) 105-116
Adaptation for Realistic Image Synthesis. SIGGRAPH
'96. 249-258. [Quinlan 1994] Quinlan, S. (1994) Efficient Distance
Computation between Non-Convex Object. Proceedings
[Ferwerda et al. 1997] Ferwerda, J.A. Pattanaik, S.N. International Conference on Robotics and Automation.
Shirley, P. Greenberg, D.P. (1997) A Model of Visual 3324-3329.
Masking for Computer Graphics. SIGGRAPH '97. 143-
152. [Sammet and Webber 1988] Sammet, H. and Webber, R.
Hierarchical Data Structures and Algorithms for
[Funkhouser and Sequin 1993] Funkhouser,T.A. Sequin, Computer Graphics. 1988 in IEEE Comp. Graphics and
C.H. (1993) Adaptive Display Algorithm for Interactive Applications. Vol.8 No. 3 48-68
Frame Rates During Visualization of Complex Virtual
Environments. SIGGRAPH '93 247-254.

[Gottschalk et al. 1996] Gottschalk, S. Lin, M.C.

Manocha, D. (1996) OBB-Tree: A Hierarchical Structure
for Rapid Interference Detection. SIGGRAPH '96.

[Greenberg et al. 1997] Greenberg D.P. et al. A

Framework for Realistic Image Synthesis.
SIGGRAPH'97. 477-494.