Collision Detection in

Real Time Simulations of 3D Systems

Theoretic Analysis


Introduction

Collision detection is a time consuming task and thus one of the main factors limiting the simulations of physical systems. It has been the bottleneck for the size of 3d worlds in the massively multiplayer roleplaying games like EverQuest. In this white paper the collision detection problem and optimized solutions are analyzed in relation with different types of systems and a practical approach is suggested for Simulation of Earth Like System from human perspective (SELS).
 

Required Collision Detection Frequency

The minimum required collision detection frequency becomes an issue if the collision detection check is not carried out in every dynamic update of the system. The dynamic update refers to update where dynamic objects are transformed in 3d space. The frequency requirement is set by the maximum speed Vmax and overlapping Omax of the colliding objects.  The required collision detection frequency is then:

Fmin=Vmax/Omax.

If we want to allow a maximum overlap of 10 cm and a maximum speed of 10 m the required update frequency is at least 100 Hz. As the minimum frequency requirement for the illusion of smooth movement is only 20 Hz it seems evident that collision detection is needed in each dynamic update of the system. This also removes the problem of the correction leaps of colliding objects when the collision is detected after certain amount of overlapping.
 

Principal Time Consumption

The principal way to carry out collision detection is to check for collision between every object in the system. This it extremely burdening in the case of complex worlds, and the required computing time is analyzed in this chapter.

The minimum amount of required computing time Tij to deduce possible collision is fundamentally limited by the number of the dimensions in the coordinate space and the complexity of the possibly colliding objects i and j. When the objects consists of parts of equal complexity (for example triangles) the Tij can be calculated using the following equation:

Tij=TpNiNj,

where Tp is the time required to find out if two parts are overlapping and Ni, Nj are the number of parts in the objects i and j, respectively. Furthermore, the total collision detection time Tdc of a system with objects of equal complexity is as follows:

 Tdc=To(1+No)No/2=TpNp^2(1+No)*No/2,

where To is the computing time needed for deciding if two objects have collided and No is the number of objects. It can be immediately seen that Tdc is O(N) dependent on Tp and O(N^2) dependent on Np and No.
 

Levels of Optimization

To develop a practical collision detection algorithm for large worlds the optimization is needed. After defining the number of the dimensions in the system, the total computing time can be minimized at three levels:

First Level

The first level of optimization is the limiting of the number of the objects in the system for example by division to subsystems. This level is two fold: Both the amount of static and dynamic objects can be minimized. Static objects need to be checked against dynamic objects only whereas dynamic objects may collide with all objects. When dynamic objects are checked against all other objects the required time is:

Tdc=To( (1+Nod)Nod/2 + NodNos)= TpNp^2( (1+Nod)Nod/2 + Nod*Nos),

where Nod is the number of dynamic objects and Nos is the number of static objects. Tdc is O(N^2) dependent on Nod and O(N) dependent on Nos. Consequently, it is more effective to limit the amount of dynamic objects.

Second Level

The second level of optimization is rough collision detection. It can be used to decide if more precise collision detection algorithm is needed for a pair of objects. The rough collision detection is often realized by approximating objects with cubes (axis aligned bounding box AABB) or spheres. The effect of second level optimization to the total collision detection time Tdc can be calculated by setting the number of parts in object Np to 1.

Tdc=To( (1+Nod)Nod/2 + NodNos)= Tp1( (1+Nod)Nod/2 + Nod*Nos).

As the Tdc is O(N^2) dependent on Np this is very efficient in the case of complex objects.

Third Level

The third level of optimization is the minimazion of the object complexity and the development of the exact or semiexact collision detection algorithms and implementations. This level affects mostly Tp and Np which are O(N) factors of Tdc. Due to the general improvements in algorithms other factors of Tdc are also minimized but these are not included in this simple analysis.

The effectiveness of optimization at each level depends on the characteristics of the systems. For example, large systems can be optimized by division to subsystems i.e. by a first level solution. Optimization of collision detection in sparse system depends mostly on the second level and in dense systems on the third level.
 

Collision Detection in Simulation of Earth Like System (SELS)

Earth like systems can be categorized to large and sparse systems if simulated from human perspective. In other words they contain large number of objects which rarely collide with more than one object. Consequently, optimization in the first and second level is of most importance.

The second level optimization is fairly straightforward and sets limits for maximum subsystem size.  Thus the seemless and time efficient division to subsystems remains as the main issue of collision detection in SELS.

A possible practical approach to optimize the collision detection in SELS is to use such in memory data structures for objects that effectively divide the SELS in spatial subsystems and possibly use multiple levels of subsystems. A typical example of this kind of data structure is octree which has been implemented in the world forge project (Stage::Shepherd::Sylvanus::Entity3dTree).


This paper was authored by Tommi Laukkanen (tlaukkan@cc.hut.fi) on the 8th of March, 2001.