and Penetration Depth Computation

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

• 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 ⁱ

 t

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

ToC = + + +  ^t ₁  t ₂  t ₃  t ₄

Calculating

Calculating  t t in CA in CA

p v

p d, n: closest distance,

direction vector

d

v: velocity

n

| ( ) ( ) |

t

v t n t dt



 ^{ }  ^{t max(| ( )}  ^{v t   n t d ( ) |) dt}





0

| ( ) v t  n t ( ) | dt

 ^{ d}

0

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

  

Calculating

Calculating  tt in CA in CA

t d

   t d

  

| ( ) ( ) |

t

v t n t dt



  ^{ }  ^{t max(| ( ) v t  n t ( ) |) dt  d}



 t

    t d

  

0

| ( ) v t n t ( ) | dt

 ^{ 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

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)

 ¹ 

  ω  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

^A Without  C2A

(ms)

Without C

A (ms)

26

Dynamic Bunnies

C2A FAST

C

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 ₀ 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

  t

q

q

31

0 1 1

t ^ t ^

    Collision-free



t



t



q

q

0

32

0 1 1

t ^ t ^

   

Check collision at

t

at

1/ 2

2

t t

t 



t

t

  t

t 1/ 2

q

t ⁰ t ¹ q

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

  

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

: velocity of link i

1

L

2

L

0 1

ω

2

ω

ω

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

0

L

0

ω

i-1

L

: difference vector btwn the links

35

Problems in Straightforward CA Problems in Straightforward CA

• Problems

– O(n O(n ) checking ² ) 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 ³ n ³ ) 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 ₀

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 ₁ ^q ₂ ^q ₀

q ^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 ³ n ³ )

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

A: Controlled Conservative

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

A: Controlled Conservative

Advancement for Interactive Continuous Collision Detection,

IEEE ICRA 2009 http://graphics.ewha.ac.kr/C2A

Main References Main References

• M. Tang, M. Lee, Y. Kim, Interactive Hausdorff Distance

Computation for General Polygonal Models, SIGGRAPH 2009 http://graphics.ewha.ac.kr/HDIST

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

• C. Je, M. Tang, Y. Lee, M. Lee, Y. Kim, PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-space Projection, ACM Transactions on Graphics 2012

http://graphics.ewha.ac.kr/PolyDepth p g p y p

• M. Tang, Y. Kim, D. Manocha, Efficient Local Planning using

C ti C lli i Q W k h Al ith i

Connection Collision Query, Workshop on Algorithmic Foundations of Robotics 2010

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

Thank you for listening!

http://graphics.ewha.ac.kr p g p