![](https://csdnimg.cn/release/download_crawler_static/89132245/bg1.jpg)
I-COLLIDE: An Interactive and Exact Collision Detection System
for Large-Scale Environments
Jonathan D. Cohen Ming C. Lin
Dinesh Mano cha MadhavK. Ponamgi
Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
f
cohenj,lin,manocha,ponamgi
g
@cs.unc.edu
ABSTRACT:
We present an exact and interactive collision detection
system, I-COLLIDE, for large-scale environments. Such
environments are characterized by the numb er of ob jects
undergoing rigid motion and the complexity of the mod-
els. The algorithm do es not assume the ob jects' motions
can b e expressed as a closed form function of time. The
collision detection system is general and can be easily in-
terfaced with a variety of application s. The algorithm
uses a two-level approach based on pruning multiple-
ob ject pairs using bounding boxes and p erforming 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 numberofmoving ob jects. In particular, the
system takes less than 1
=
20 of a second to determine all
the collisio ns and contacts in an environment consisting
of more than a 1000 moving polytop es, 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 ob ject's motion is constrained by collisio ns with other
ob jects and by other dynamic constraints. The prob-
lem has b een well studied in the literature. However, no
goo d general collision detection algorithms and systems
are known for interactive large-scale environments.
A large-scale virtual environment, likeawalkthrough,
creates a computer-generated world, lled with real and
virtual ob jects. Suchanenvironment should give the user
a feeling of presence, which includes making the images of
both the user and the surrounding ob jects feel solid. For
example, the ob jects should not pass through each other,
and things should move as expected when pushed, pulled
Currently atNCA&TState University, Greensboro. Ap-
proved by ARPA for public release; distribution unlimited
or grasp ed. Such actions require accurate collision detec-
tion. However, there maybe hundreds, even thousands
of ob jects in the virtual world, so a brute-force approach
that tests all possible pairs for collisions is not acceptable.
Eciency is critical in a virtual environment, otherwise
its interactive nature is lost [24]. A fast and interactive
collision detection algorithm is a fundamental comp onent
of a complex virtual environment.
The ob jective of collision detection is to report all geo-
metric contacts b etween ob jects. If we know the p ositions
and orientations of the ob jects 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 haveany information regarding the
maximum velocity or acceleration, b ecause the user may
move with abrupt changes in direction and sp eed. Due to
these unconstrained variables, collision detection is cur-
rently considered to be one of the ma jor 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 p erformance 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
(
n
2
) pos-
sible interactions of
n
simultaneously moving ob jects to
O
(
n
+
m
) where
m
is the numb er of ob jects
very close
to each other. In particular, two ob jects are very close,
if their axis-aligned bounding b oxes overlap. Our ap-
proach is exible enough to handle dense environments
without making assumptions about ob ject velocity or ac-
celeration. The system has b een 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 denes the concept of coherence and
describes an exact pairwise collision detection algorithm
which applies it. We describ e our algorithm for collision
detection between multiple ob jects 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.
1