Collision Graph-based Multi-Body Simultaneous Collision Detection Mechanism

X. Zhang, C. Wu, K. Ben, and S. Cao (PRC)


virtual environment; collision propagation; heterogeneouscollision graph; pairwise collision detection mechanism(PCDM); simultaneous collision detection mechanism(SCDM).


Collision detection and response is crucial to behavioral modelling in virtual environments. In collision intensive multi-body system, collision topology of the system could occur differently at different time; even at the same time, the topology could change due to instant collision propagation. The heterogeneous collision topology generally requires distinct computing models; hence multibody collision simulation needs appropriate model switching logic. The widely-used pairwise collision detection mechanism(PCDM) and some of multi-body simulation systems did not at all either concern the essential concept of collision propagation and required model switching, or employed sophisticated model switching scheme. The work in this paper is firstly to illustrate that the traditional PCDM is unable to solve multi-body collision via theoretical analysis and calculation of two simple counterexamples; introduce a new concept of collision propagation, and modify PCDM to deal with the propagation to eliminate caused time delay; secondly, to introduce another concept of heterogeneous collision graph to identify the kinds of required computing models, formulate the complexity of computing time, and analyze some effect of collision propagation on collision graph. In the end, multi-body simultaneous collision detection mechanism (SCDM) is presented, in which both collision propagation and simulation model switching based on collision graph are taken into account.

Important Links:

Go Back