Game Development Reference

In-Depth Information

a mesh is more effective than a hierarchical division into octrees and becomes useful

only for a sufficient number of objects (some dozens) compared to the approaches based

on inter-object distances or separator planes. He also shows that
k
-DOP hierarchies

can be more effective than OBB hierarchies. However, this study does not consider all

the criteria operating in the choice of a collision detection strategy, which remains a

random choice even today. In addition, several acceleration methods remain unsuit-

able for deformable bodies and new approaches are necessary (Teschner et al., 2004).

However, the problem of acceleration is crucial because it is linked to the manage-

ment of calculation time. Since the calculation time is not limited and the complexity

is not constant, the programmer using a collision detection never knows how much

calculation time it will require. This lacuna is very detrimental to certain applications,

where time management is critical. He can at the most design some routines so as to

try mastering this time either by reducing the accuracy or by using a stochastic but not

guaranteed detection or by defining collision in probabilistic terms. Certain research

projects are exploring hardware acceleration, but these projects are still in their initial

stages.

17.3 PROCESSINGTHE COLLISION

The step of collision detection is crucial in graphic animation of virtual environments.

Once the collision is specified and the space of contacts is determined, the animation

models take over from there. A simple solution is to select and impose a position of

objects which guarantees that there will be no collision. However, this solution can

sometimes create discontinuity in positions and in any case makes the object movement

look non-realistic.

Physical approaches provide a more realistic collision resolution. It is however

necessary to choose a suitable detection method to be able to use various response cal-

culation methods. Since it is necessary to measure interpenetration, it is clear that the

possible collision detection algorithms can be none other than those based on intersec-

tion detection and quantification. However, these algorithms should be able to provide

interpenetration measurement used to calculate penalty. A volume measurement can

be used for calculation, but the penalty is generally based on an assessment of depth

and direction of interpenetration. However, the response calculated by this method is

sometimes very different than the expected one. In fact, an interpenetration vector cal-

culated only on the basis of a geometrical approach, i.e. without considering the paths,

provides a direction of the repulsive forces that is not consistent with the movement

(see figure 17.14).

A contact detection is necessary for other response calculations such as approaches

by constraints or by impulsions. The moment of contact can be determined by a suit-

able temporal detection (discrete or continuous). As a result, the 4D collision detection

algorithms prove to be the most suitable. In case of constraints, it is even desirable to

be able to integrate the constraints well in advance so that the acceleration of objects

can be corrected to prevent interpenetration. In this case, the most appropriate colli-

sion detection algorithms are in fact the distance calculating algorithms. In fact, the

constraint is then built based on the primitives closest to each of the objects on the

basis of a certain predefined threshold.

Search Nedrilad ::

Custom Search