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
下载后可阅读完整内容，剩余8页未读，立即下载
wd1879804
- 粉丝: 0
- 资源: 15
我的内容管理
展开
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器：工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析：故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化：二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法：Beta与Alpha测试详解
- 软件测试周期详解：从需求分析到维护测试
- CMMI模型详解：软件企业能力提升的关键
- 移动Web开发框架选择：jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
