I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments Jonathan D. Cohen Ming C. Lin * Dinesh Manocha Madhav Ponamgi Department of Computer Science University of North Carolina Chapel Hill, NC 27599-3175 {cohenj,lin,manocha,ponamgi}Qcs.unc.edu ABSTRACT: We present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the mod- els. The algorithm does not assume the objects’ motions can be expressed as a closed form function of time. The collision detection system is general and can be easily in- terfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple- object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than l/20 of a second to determine all the collisions and contacts in an environment consisting of more than a 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750. 1 INTRODUCTION Collision detection is a fundamental problem in computer animation, physically-based modeling, computer simu- lated environments and robotics. In these applications, an object’s motion is constrained by collisions with other objects and by other dynamic constraints. The prob- lem has been well studied in the literature. However, no good general collision detection algorithms and systems are known for interactive large-scale environments. A large-scale virtual environment, like a walkthrough, creates a computer-generated world, filled with real and virtual objects. Such an environment should give the user a feeling of presence, which includes making the images of both the user and the surrounding objects feel solid. For example, the objects should not pass through each other, and things should move as expected when pushed, pulled *Currently at NC A k T State University, Greensboro Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for +3Ct commercial advantage, the ACM copyright notice and the title of the publication and Its date appear, and notice /s given that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1995 Symposium on Interactive 3D Graphics, Monterey CA USA (0 1995 ACM O-69791 -736-7l95lOOO4...$3.50 or grasped. Such actions require accurate collision detec- tion. However, there may be hundreds, even thousands of objects in the virtual world, so a brute-force approach that tests all possible pairs for collisions is not acceptable. Efficiency is critical in a virtual environment, otherwise its interactive nature is lost [24]. A fast and interactive colIision detection algorithm is a fundamental component of a complex virtual environment. The objective of collision detection is to report all geo- metric contacts between objects. If we know the positions and orientations of the objects in advance, we can solve collision detection as a function of time. However, this is not the case in virtual environments or other interac- tive applications. In fact, in a walkthrough environment, we usually do not have any information regarding the maximum velocity or acceleration, because the user may move with abrupt changes in direction and speed. Due to these unconstrained variables, collision detection is cur- rently considered to be one of the major bottlenecks in building interactive simulated environments [20]. Main Contribution: We present a collision de- tection algorithm and system for interactive and exact collision detection in complex environments. In contrast to the previous work, we show that accurate, interac- tive performance can be attained in most environments if we use coherence to speed up pairwise interference tests and to reduce the actual number of these tests we per- form. We are able to successfully trim the O(n2) pos- sible interactions of n simultaneously moving objects to O(n + m) where m is the number of objects very clolre to each other. In particular, two objects are very close, if their axis-aligned bounding boxes overlap. Our ap- proach is flexible enough to handle dense environments without making assumptions about object velocity or ac- celeration. The system has been successfully applied to architectural walkthroughs and simulated environments and works well in practice. The rest of the paper is organized as follows. In Sec- tion 2, we review some of the previous work in collision detection. Section 3 defines the concept of coherence and describes an exact pairwise collision detection algorithm which applies it. We describe our algorithm for collision detection between multiple objects in Section 4 and dis- cuss its implementation in Sections 5 and 6. Section 7 presents our experimental results on walkthrough envi- ronments and simulations. 1892 PREVIOUS WORK The problem of collision detection has been extensively studied in robotics, computational geometry, and com- puter graphics. The goal in robotics has been the planning of collision-free paths between obstacles [15]. This differs from virtual environments and physically- based :simulations, where the motion is subject to dy- namic constraints or external forces and cannot typi- cally be expressed as a closed form function of time [l, 3, 11, 18, 20, 211. At the same time, the emphasis in the computational geometry has been on theoretically efficient intersection detection algorithms [32].