**Real time Continuous Collision Detection** **Real-time Continuous Collision Detection **

**and Penetration Depth Computation**

**Young J Kim** **Young J. Kim**

### http://graphics.ewha.ac.kr

### Ewha Womans University

### Ewha Womans University

**A t** ** I** ** S** **i** ** R b t** **A t** ** I** ** S** **i** ** R b t** **Autonomous Ice Serving Robot** **Autonomous Ice Serving Robot**

**(with **

**(with Zhixing** **Zhixing Xue** **Xue at FZI)** **at FZI)**

**Non**

**Non--penetration Constraint** **penetration Constraint**

### • **No overlap between geometric objects **

### i t i ( ) *A* *B*

### interior( ) *A* *B*

### A

### A B

### A

### A B A A B

### • **Crucial for mimicking the physical presence**

**Earlier Research** **Earlier Research**

### • **Focused on checking for whether there is**

### • **Focused on checking for whether there is ** **any overlap between A and B, fixed in space**

### Tons of papers published in the area of *collision* – Tons of papers published in the area of collision

*detection*

### – Well-studied and matured technology Well studied and matured technology

**N t l** **h** **t** **l** **h** **l**

### • **Not clear how to resolve such overlap**

**Recent Research Trends** **Recent Research Trends**

### • **Avoid inter-penetration**

### – Continuous collision detection (CCD) Continuous collision detection (CCD)

### • **Allow inter-penetration but backtrack**

### Penetration depth (PD) – Penetration depth (PD)

### A

### A B A A

**Applications of Continuous CD** **Applications of Continuous CD**

### • **Rigid body dynamics**

### – Find the time of contact (ToC) to apply forces Find the time of contact (ToC) to apply forces

**Applications of Continuous CD** **Applications of Continuous CD**

### • **Motion planning**

### – Check whether a path is collision-free Check whether a path is collision free

**Applications of Penetration Depth** **Applications of Penetration Depth**

### • **Dynamics simulation**

### Penalty based Point of

### – Penalty-based – Impulse-based

### A B A

### Point of Impact

### Impulse A A B

### Impulse

### Penetration

### Depth

**Goal** **Goal**

### • **Recent research results**

### – CCD (rigid polygon-soups articulated) CCD (rigid, polygon soups, articulated) – PD (pointwise, translational)

### • **Applications**

### Real time rigid body dynamics – Real-time rigid body dynamics – Robotic grasping

### CAD di bl

### – CAD disassembly

**CONTINUOUS COLLISION ** **DETECTION**

10

**Discrete Collision Detection** **Discrete Collision Detection**

**Collision Missing**

11

**Continuous Collision Detection** **Continuous Collision Detection**

### • **Motion trajectory f(t)** **is known in advance**

### ( )

**Time of Contact** *f t*

**Time of Contact**

**Previous Work on CCD** **Previous Work on CCD**

### • Algebraic solution - [Canny86], [Redon00], [Kim03], [Choi06]

### S l

### • Swept volume -[Abdel-Malek02],[Hubbard93], [Redon04a,b]

### • ^{Bisection} Bisection -[Redon02], [Schwarzer02] [Redon02], [Schwarzer02]

### • Kinetic data structures -[Kim98], [Kirkpatrick00], [Agarwal01]

### • Minkowski sum -[Bergen04]

### • Conservative advancement

### • Conservative advancement

### – [Mirtich96], [Mirtich00],[Coumans 2006],[Zhang06], [Tang09]

**Conservative Advancement (CA)** **Conservative Advancement (CA)**

### • **Assume objects are convex**

### • **Find the 1** ^{st} **time of contact (ToC) of a moving**

^{st}

### • **Find the 1 time of contact (ToC) of a moving **

**object**

**Conservative Advancement (CA)** **Conservative Advancement (CA)**

**1. Find a step size to conservatively **

**advance the object until collision occurs** ^{i}

^{i}

### *t*

**advance the object until collision occurs** **2. Repeat until inter-distance < ε**

*ToC = + + +* ^{t} _{1} *t* _{2} *t* _{3} *t* _{4}

^{t}

_{1}

_{2}

_{3}

_{4}

**Calculating **

**Calculating ** **t ** **t in CA** **in CA**

**t**

**t in CA**

**p** **v**

**p**

**v**

**p** **d, n: closest distance, **

**p**

**d, n: closest distance,**

### direction vector

*d*

**v: velocity**

**v: velocity**

**n**

**n**

### | ( ) ( ) |

*t*

*v t* *n t* *dt*

###

### ^{} ^{} ^{t} ^{max(| ( )} ^{v t} ^{} ^{} ^{n t} ^{d} ^{( ) |)} ^{dt}

^{t}

^{v t}

^{n t}

^{d}

^{dt}

###

###

### 0

### | ( ) *v t* *n t* ( ) | *dt*

### ^{} ^{d}

^{d}

### 0

### max(| ( ) *v t* *n t* ( ) |) *dt*

###

**Calculating **

**Calculating ** **tt** **in CA** **in CA**

**tt**

*t* *d*

### *t* *d*

###

### | ( ) ( ) |

*t*

*v t* *n t* *dt*

###

### ^{} ^{} ^{t} ^{max(| ( )} ^{v t} ^{} ^{n t} ^{( ) |)} ^{dt} ^{} ^{d}

^{t}

^{v t}

^{n t}

^{dt}

^{d}

###

### *t*

### *t* *d*

###

### 0

### | ( ) *v t* *n t* ( ) | *dt*

### ^{} ^{d}

^{d}

### 0

### max(| ( ) *v t* *n t* ( ) |) *dt*

###

**Extension to Non**

**Extension to Non convex** **convex** **Extension to Non**

**Extension to Non--convex** **convex**

### [Zhang et. al PG 06]

### [Zhang et. al PG 06]

### • **Use of convex decomposition**

### • **Use of convex decomposition**

### • **Build a hierarchy of decomposed convex ** **pieces and perform CA** **hierarchically**

**hierarchically**

**pieces and perform CA hierarchically**

**Santa vs. Thin Board** **Santa vs. Thin Board**

### 37K triangles 51,546 FPS

### # of iterations

### 3.68

**Bunny vs. Bunny** **Bunny vs. Bunny**

### 70K triangles/bunny 110 FPS # of iterations 4.7

**Torusknot vs. Torusknot** **Torusknot vs. Torusknot**

### 2 8K 2.8K

### 1067 FPS

### # of iterations 4 49 11K

### # of iterations 4.49 11K

### 400 FPS

### # f it ti 4 49 34K

### # of iterations 4.49 34K

### 186 FPS

### # f

### # of iterations 4.46

**Extension to Polygon**

**Extension to Polygon Soups** **Soups** **Extension to Polygon**

**Extension to Polygon--Soups** **Soups**

### [Tang et. al IEEE ICRA 09]

### [Tang et. al IEEE ICRA 09]

### • **Construct the bounding volume hierarchy of ** **polygons**

**polygons**

### • **Motion bound calculation** *d*

### – Bounding volume

*t* *d*

###

### g

### – Triangles

**Extension to Polygon**

**Extension to Polygon Soups** **Soups** **Extension to Polygon**

**Extension to Polygon--Soups** **Soups**

### [Tang et. al IEEE ICRA 09]

### [Tang et. al IEEE ICRA 09]

### • **We use swept sphere volumes**

### [Larsen et. al IEEE ICRA 1999]

**Motion Bound Calculation** **Motion Bound Calculation**

### • **Motion bound of SSV (e.g. PSS)**

## ^{1}

### **ω** **n c** ^{} **r**

### : :

### closest direction rotational velocity **n**

**ω** : :

### closest direction radius of PSS

**r**

**n**

**Controlling the CA Iterations**

### 3 2 3

### timing(ms) 1

### 2 timing(ms)

### Di t

### 0 1

### Normalized distance

### Distance threshold

### 1 2 3 4 5 6 7 8

### timing distance

### Iteration step

### 1. Compute approximate distance in the beginning 2. Compute exact distance toward the end p

25

### C lubs

### 4X

### C

### mer rs 4X 28X

### Ham Ge ar 28X

### 0 5 10 15 20 25 30 35 40 45 50 55

### C2A ^{C}

^{2}

^{A } Without C2A

### (ms)

### Without C

^{2}

### A (ms)

26

### Dynamic Bunnies

### C2A FAST

### C

^{2}

### A

### Zhang 06

### Dynamic Bunnies FAST ^{Zhang 06}

### Bunnies

### Toruskots

### [Zhang 06] can handle only manifold surfaces

### 0 1 2 3 4 5 (ms)

### • [Zhang 06] can handle only manifold surfaces

27

### • Check whether or not where is the configuration of a

### ( ) Free Space , t [0,1]

### *q t*

### ( )

### or not, where is the configuration of a *q t* robot at

### ( ) *q t* *t*

### False

**q** _{0} **q**

**q** 1

**q** 1

### 0 True

**q**

**q** 1

28

**q** 0

**Construction phase** **and query phase**

### Configuration space g p

### goal goal

### start Local Planning

29

### start Local Planning

### • Find the time of violation (ToV)

### If T V 1 lid th th i t lid

### • If ToV>=1, valid path; otherwise, not valid

**q** 1

### ToV<1

**q**

**q** 1

**q** 0

### ToV>=1

**q** 0

30

**q** 0

### • Dual advancements from the both end- configurations

### configurations

*t*

0^{}

### *t*

_{1}

^{}

**q**

0 **q**

^{1}

31

### 0 1 1

*t* ^{} *t* ^{}

### Collision-free

###

*t*

0^{}

###

*t*

1^{}

###

**q**

0 **q**

^{1}

0

32

### 0 1 1

*t* ^{} *t* ^{}

###

### Check collision at

*t*

### at

_{0}

_{1}

1/ 2

### 2

*t* *t*

*t*

###

*t*

*t*

0^{}

### *t*

_{1}

^{}

*t* 1/ 2

**q**

0 *t* ^{0} *t* ^{1} **q**

^{1}

33

### Extension to Articulated Models Extension to Articulated Models Extension to Articulated Models Extension to Articulated Models

### [Zhang et. al SIGGRAPH 07]

### [Zhang et. al SIGGRAPH 07]

### • Treat each link as a rigid body

### • Apply CA to each link independently

### independently

### • Taking the minimum of CA results

34

**Motion Bound Calculation** *d*

**Motion Bound Calculation** *t* ^{d}

^{d}

###

### 1 *j*

*i*

###

###

### 1

### 0 0 0 1 0 1 1

### 1 1 1 1

### 2 2

*i* *j*

*j* *k* *j*

*j* *k* *j*

*j* *k*

###

###

###

###

###

###

###

###

**υ** **n** **n** **ω** **L** **υ** **n** **ω** **ω** **L**

0

### v

_{i}

### : velocity of link i

1

**L**

_{2}

2

**L**

_{3}

0 1

### ω

_{2}

2

### ω

_{3}

_{i-1}

### ω

_{i}

### : rotational velocity of link i w.r.t. link i-1

0

**L**

_{1}

0

### ω

_{1}

i-1

### L

_{i}

### : difference vector btwn the links

35

**Problems in Straightforward CA** **Problems in Straightforward CA**

### • Problems

### – O(n O(n ) checking ^{2} ) checking

### between individual links

36

**Spatial Culling** **Spatial Culling**

### • Cull the link pairs that p are far apart

### • Use bounding volume-based volume-based collision-culling

37

**Spatial Culling using Dynamic AABB** **Spatial Culling using Dynamic AABB**

### • Goal

### Compute an axis aligned – Compute an axis-aligned

### bounding box (AABB) that bounds the motion of a

### bounds the motion of a moving link

38

**Bounding Volume Culling** **Bounding Volume Culling**

### Interval Arithmetic Taylor Models Interval Arithmetic Taylor Models

39

**Locomotion Benchmark** **Locomotion Benchmark**

### • **CCD **

**performance** **p**

### – **1.22 msec**

### • Mannequin Mannequin

### – 15 links, 20K tri

### • Obstacles

### • Obstacles

### – 101K tri

### L ti SW

### • Locomotion SW

### – Footstep ^{TM}

40

**Exercise Benchmark** **Exercise Benchmark**

### • Mannequin

### • Mannequin

### – 15 links, 20K triangles

### triangles

**S lf CCD**

### • **Self-CCD **

**performance**

### – **0.38 msec**

41

**Motion Planning Benchmark 1** **Motion Planning Benchmark 1**

### • Excavator

### – 52 links 19K tri – 52 links, 19K tri

### • Obstacles

### 0 4M t i – 0.4M tri

### • **CCD **

**performance**

### – **100~700 msec**

42

**Motion Planning Benchmark 2** **Motion Planning Benchmark 2**

### • Tower crane

### • Tower crane

### – 14 links, 1288 tri

### • **CCD **

**performance**

### – **5.66~15.1 msec**

43

**Articulated Body Dynamics Benchmark** **Articulated Body Dynamics Benchmark**

### • Four trains

### • Four trains

### – 10 links, 23K tri (each)

### (each)

### • **CCD**

### • **CCD **

**performance**

**535 msec** – **535 msec**

44

**Software Implementations** **Software Implementations**

### • **Source codes are available**

### – http://graphics.ewha.ac.kr/FAST (2-manifold)

### http://graphics ewha ac kr/C2A (polygon soups) – http://graphics.ewha.ac.kr/C2A (polygon-soups) – http://graphics.ewha.ac.kr/CATCH (articulated)

### http://graphics ewha ac kr/CCQ (for motion planning)

### – http://graphics.ewha.ac.kr/CCQ (for motion planning)

**PENETRATION DEPTH** **PENETRATION DEPTH ** **COMPUTATION**

**COMPUTATION**

46

**Pointwise Penetration Depth** **Pointwise Penetration Depth** **Pointwise Penetration Depth** **Pointwise Penetration Depth**

### [Tang et. al SIGGRAPH 09]

### [Tang et. al SIGGRAPH 09]

### • **Defined as deepest interpenetrating points**

**Pointwise**

**Pointwise Penetration Depth** **Penetration Depth**

### 1. Find intersection surfaces and

### 22. Penetration depth =

###

**P** **t ti**

###

**Penetration **

**Depth**

**Pointwise Penetration Depth** **Pointwise Penetration Depth**

### Demo (40K Bunny vs 40K Bunny)

### Demo (40K Bunny vs 40K Bunny)

**Benchmark: Pointwise PD** **Benchmark: Pointwise PD**

### Model complexity

### – 50K tri

### Avg Performance Avg. Performance

### – 3.88ms/pair

**Benchmark: Pointwise PD** **Benchmark: Pointwise PD**

### Model complexity

### – 3.5K tri

### Avg performance Avg. performance

### – 0.95ms/pair

### Penetration Depth Penetration Depth Penetration Depth Penetration Depth

### [[Dobkin Dobkin 93] 93]

### • Minimum translational

### distance to separate A A B

### distance to separate overlapping objects

### A B A

### Penetration Depth

52

**Previous Work on PD** **Previous Work on PD**

### • Convex polytopes - [Cameron and Culley86], [Dobkin93], [Agarwal00], [Bergen01], [Kim04]

### [Agarwal00], [Bergen01], [Kim04]

### • Non-convex polyhedra -[Kim02],[Redon and Lin06], [Lien08a b] [Hachenberger09]

### [Lien08a,b], [Hachenberger09]

### • Distance fields -[Fisher and Lin01], [Hoff02], [Sud06]

### • Pointwise PD -[Tang09]

### • Generalized PD – [Ong and Gilbert96], [Ong96], [Zhang07]

### • Volumetric PD - Volumetric PD [Wellner and Zachmann09] [Wellner and Zachmann09]

**Minkowski**

**Minkowski Sum** **Sum**

### { | , }

*P* *Q* **p q p** *P* **q** *Q*

### { | }

*P* *Q* { | *P* , *Q* } *P* *Q* **p q p** *P* **q** *Q*

### Q

### P *P* *Q*

54

**Proximity VS **

**Proximity VS Minkowski** **Minkowski Sum** **Sum**

### Penetration Depth Penetration Depth Closest Distance

*P* *Q*

55

**Combinatorial Explosion** **Combinatorial Explosion**

### • **Complexity of Minkowski Sum**

### – O(m O(m n ) with m and n triangles ^{3} n ^{3} ) with m and n triangles

**PD Estimation** **PD Estimation** **PD Estimation** **PD Estimation**

**o**

### Penetration Depth

**o** Boundary of

### Minkowski Sums Minkowski Sums

57

**Out**

**Out--Projection = CCD** **Projection = CCD** **Out**

**Out--Projection = CCD** **Projection = CCD**

**q** *f*

### Out-Projection

**q** 0 _{0}

**q**

**oo** Boundary of

### Minkowski Sums Minkowski Sums

58

**In**

**In--Projection = LCP** **Projection = LCP** **In**

**In--Projection = LCP ** **Projection = LCP **

**(Linear Complementarity Problem)**

### l h

**q** 2

### Je et. al Tech Report 2010

**q** 2

**o**

### In-Projection

**o** Boundary of

### Minkowski Sums Minkowski Sums

59

**PolyDepth**

**PolyDepth: Iterative Optimization** **: Iterative Optimization** **PolyDepth**

**PolyDepth: Iterative Optimization** **: Iterative Optimization**

**q** *f*

### Out-Projection

**q** 0

**q** 1 _{1} ^{q} _{2} ^{q} _{0}

^{q}

^{q}

**q** ^{q} _{2}

^{q}

**o**

### In-Projection Penetration Depth

**o** Boundary of

### Minkowski Sums Minkowski Sums

60

**PolyDepth**

**PolyDepth Performance** **Performance**

### • Spoon: 1.3K triangles

### • Cup: 8 4K triangles

### • Cup: 8.4K triangles

### • Time: 1~7 msec

61

**PolyDepth**

**PolyDepth Performance** **Performance**

### • Bunny: 40K triangles

### • Dragon: 174K

### • Dragon: 174K triangles

### • Time: 2~15 msec

62

**Comparison against Exact Solution** **Comparison against Exact Solution**

### Accuracy

### Performance Performance

63

**APPLICATIONS**

64

**Real**

**Real--time Physics Simulation using PD** **time Physics Simulation using PD**

### 802K triangles in total 214K triangles in total g 802K triangles in total

65

**Integration with Physics Engine** **Integration with Physics Engine**

**htt // i t** **l h i**

**http://virtualphysics.**

**kr**

**Robotic Grasping using CCD** **Robotic Grasping using CCD**

### With Zhixing Xue @ FZI

67

**CAD Disassembly using CCD** **CAD Disassembly using CCD**

### With Liangjun Zhang @ Stanford/UNC With Liangjun Zhang @ Stanford/UNC

68

**Summary** **Summary**

**CCD** **PD**

### Concept Collision avoidance Collision correction 1 Constraint based

### Usages

### 1. Constraint‐based dynamics

### 2 Exact motion

### 1. Penalty‐, impulse‐

### based dynamics Usages 2. Exact motion

### planning 3 Grasping

### 2. Retraction‐based motion planning 3. Grasping

### Complexities O(mn) O(m ^{3} n ^{3} )

**Future Work** **Future Work**

### • **Continuous collision detection**

### – N-body N body

### – Non-linear motion

### • **PD**

### Articulated body – Articulated body – Deformable

### N b d

### – N-body

**GPUs** **GPUs**

### Real-time Dynamics Simulation of 16,000 Rigid Bodies

**Acknowledgements** **Acknowledgements**

### • **Min Tang, Xinyu Zhang, Minkyoung Lee, ** **Youngeun Lee (Ewha)**

**Youngeun Lee (Ewha)**

### • **Stephane Redon (INRIA)** **Dinesh Manocha (UNC)**

### • **Dinesh Manocha (UNC)**

### • **Liangjun Zhang (Stanford)**

### • **Zhixing Xue (FZI)**

### • **KEIT/MKE (IT core research)**

### • **KRF (Young investigator award)**

### • **KRF (Young investigator award)**

**Main References** **Main References**

### • **X. Zhang, M. Lee, Y. Kim, Interactive Continuous Collision ** **Detection for Non-convex Polyhedra, Pacific Graphics 2006 ** **Detection for Non convex Polyhedra, Pacific Graphics 2006 ** **http://graphics.ewha.ac.kr/FAST**

**X Zh** **S R d** **M L** **Y Ki** **C** **i** **C lli i**

### • **X. Zhang, S. Redon, M. Lee, Y. Kim, Continuous Collision ** **Detection for Articulated Models using Taylor Models and ** **Temporal Culling, SIGGRAPH 2007 **

**http://graphics.ewha.ac.kr/CATCH**

### • **M Tang Y Kim D Manocha C**

^{2}**A: Controlled Conservative**

### • **M. Tang, Y. Kim, D. Manocha, C**

^{2}