Collision Detection

  • 格式:pdf
  • 大小:374.58 KB
  • 文档页数:30

2003-12-17 2003- 12-
5
Introduction
Different kinds of colliding bodies: Three levels of difficulity: (1) Convex rigid bodies; (2) General rigid bodies; (3) Deformable bodies;
The hybrid bottom-up/top-down tree update method.
2003-12-17 2003- 1228
Some Other Topics
Collision Response
Collision response for a sphere approaching a plane. To the left the velocity vector V is divided into two components, Vn and Vp. To the right, pergectly elastic collision is shown, where the new velocity is V'=Vp-Vn. For a less elastic collision, the length of –Vn could be decreased.
2003-12-17 2003- 12-
2
Introduction
Collision Collision is a fundamental task in virtual reality: (1) Haptic rendering (force--feedback); (2) Physically-based simulation; (3) Virtual training ( Medical, drivers ); (4) Robot technique; (5) Computer games.
Better hierarchical decomposition of model :
Lower value of nv, np, nu
2003-12-17 2003- 12-
Better methods for determining whether two things overlaps 19
2003-12-17 2003- 12-
13
Dynamic CD using BSP Trees
e = n (t p o )
2003-12-17 2003- 1214
Dynamic CD using BSP Trees
Pseudo code
Pseudo code for finding the impact poin by traversing BSP tree.
2003-12-17 2003- 12-
21
OBBTree Method
Overlap Test
2003-12-17 2003- 12-
22
OBBTree Method
Hierarchical Building
Building the OBBTree: Recursively partition the 2003-12-17 bounded polygons and bound the resulting groups. 2003- 12-
Lower value of c , c
OBBTree Method
At siggraph'96, Gottschalk et al. presented a paper called "OBBTree: A Hierarchical Structure for Rapid Interference Detection".
7
Introduction
Strategies: (1) Spatial partitioning; (2) Multiphase algorithms; (3) Categorize objects (static, dynamic..);
2003-12-17 2003- 12-
8
Multi-phase detection strategy
2003-12-17 2003- 1226
Some Other Topics
Distance Query (cont.)
GTK Algorithm
2003-12-17 2003- 12-
27
Some Other Topics
Deformed Objects
Obviously, there are other sorts of motion, such as waves on the water or a piece of cloth swaying in the wind.
4
Introduction
Good CD Algorithms should satisfy: (1) Interactive rate for large-scale scene; (2) No requirement of geometric shape; (3) Applied for dynamic scene; (4) Fast creation of bounding box;
18
Hierarchical Method
Evaluating the performance of CD algorithms
t = nvcv + npcp + nucu
Where nv : number of BV/BV overlap tests cv : cost for a BV/BV overlap test np : number of primitive pairs tested for overlap cp : cost for testing whether two primitives overlap nu : number of BVs updated due to the model's motion cu : cost for updating a BV
2003-12-17 2003- 12-
25
Some Other Topics
Distance Query
To the left, two convex objects A and B are shown. To construct AB, first move A and B so that one reference point is at origin. Then B is reflected, as shown in the middle, and the chosen reference point on B is put on the surface of A and then the reflected B is swept around A. In this way, A-B is created.
Determine collisions between the geometry described by a BSP tree and a collider.
2003-12-17 2003- 12-
12
Dynamic CD using BSP Trees
A sphere does not approximate a character in a game very well, while cylinder does to some extend.
23
Some Other Topics
Front Tracking It uses temporal coherence for speeding up collision queries.
2003-12-17 2003- 12-
24
Some Other Topics
Time-Critical Collision Detection The detection task must be finished in a certain time.
2003-12-17 2003- 12-
3
Introduction
Three Topics Related to Collision: (1) Collision detection (2) Collision determination (3) Collision response.
2003-12-17 2003- 12-
Collision Detection
Pu Jiantao. 2003-12-09
Content
Introduction CD with rays Dynamic CD using BSP Trees Hierarchical Method OBBTree Method Some Other Topics
2003-12-17 2003- 12-
17
Hierarchical Method
Hierarchy Building
Bottom-up (BOXTREE) Top-down (divide and conquer) Incremental tree-insertion
2003-12-17 2003- 12-
2003-12-17 2003- 12-
16
Hierarchical Method
Features.
Interactive rates with models consisting of a large number of polygons, both when far away and close together Handling polygon soup. Possible to undergo rigid-body motion Efficient BV fitting.