I-COLLIDE: 实时大尺度环境精确碰撞检测系统

需积分: 0 174 浏览量更新于2024-08-03 收藏 351KB PDF 举报

I-COLLIDE是一种交互式且精确的碰撞检测系统，专为大规模环境设计。该系统由Jonathan D. Cohen、Ming C. Lin、Dinesh Manocha和Madha V. Ponamgi在北卡罗来纳大学教堂山分校计算机科学系开发。在大规模环境中，如包含大量运动中的刚体物体和复杂模型的场景，传统的碰撞检测方法可能难以应对，因为它们假设物体运动可以被时间的封闭形式函数表示。 I-COLLIDE算法的核心优势在于其灵活性和效率。它采用了一种两级处理策略，首先通过使用包围盒技术进行多对象对的剪枝，这有助于减少需要进行精确碰撞检测的对象对数量。这种方法大大降低了计算复杂性，特别适合处理动态变化且实时交互的场景，比如游戏开发、虚拟现实或机器人导航等应用。在第一级，算法通过比较物体的边界框（bounding boxes）来快速排除大部分不相交的组合。如果两个对象的边界框有重叠，则进入第二级，即执行精确的碰撞检测。这一阶段主要依赖于多边形模型（polyhedral models），通过对这些模型的顶点和边缘进行细致的几何测试，确保碰撞的准确判断，即使对于复杂的形状也能得到正确结果。 I-COLLIDE算法的特点包括： 1. **非线性运动支持**：它不需要预先假设物体运动是可解析的时间函数，这意味着它能够适应更真实世界的动态行为。 2. **交互性**：设计为与各种应用程序无缝集成，能够在用户界面中提供实时反馈，例如游戏中的角色碰撞检测或者虚拟现实中的物体交互。 3. **性能优化**：通过有效的剪枝和层次结构，提高碰撞检测的效率，减少不必要的计算，确保在大型场景中的实时性能。 4. **模型通用性**：适用于多种多边形模型，无论是简单的几何体还是复杂的三维模型，都能提供准确的碰撞检测结果。通过演示，I-COLLIDE展示了其在实际应用中的高效性和准确性，证明了它是处理大规模、动态环境碰撞检测问题的理想解决方案。这种技术的进步不仅提升了用户体验，也推动了实时三维图形学和物理模拟技术的发展。

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

cohenj,lin,manocha,ponamgi

@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.

Eciency 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

(

) pos-

sible interactions of

simultaneously moving ob jects to

(

) where

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 denes 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.

下载后可阅读完整内容，剩余8页未读，立即下载

wd1879804

粉丝: 0
资源: 15

I-COLLIDE: 实时大尺度环境精确碰撞检测系统

Fast Collision Detection for Interactive Games 互动游戏的快速碰撞检测.doc

Collision-Detection-Algorithm:使用p5.play库的碰撞检测算法

mesh-collision:返回运动中的两个 3d 网格之间的接触集

DXRuby-Game-Tutorial:用于学习使用 DXRuby 创建游戏

svg-path-collider:测试SVG路径之间的冲突

cyclone-physics-js:Cyclone C++ 物理引擎到 JavaScript 的手动移植

C-20：设置对撞机

Space-Invaders:Java的Space Invaders游戏

phaser-pong:Phaser 内置的简单 Pong 克隆

高斯白噪声matlab代码-bachelor-of-science:碰撞，整理，收集：识别无线碰撞中的发件人

最新资源