Collision detection on the GPU

Overview

Quick Background
CPU Methods
CULLIDE
RCULLIDE
QCULLIDE
CUDA Methods

Background

Need to find collisions for lots of reasons
Physics engines
Seeing if a

Background

Broad phase:
Looks at entire scene
Looks at proxy geometry (bounding shapes)
Determines if

Background

Narrow phase:
Looks at pairs of objects flagged by broad phase
Looks at

Background

Resolution
Compute forces according to the contact points returned from the narrow

CPU Methods

Brute Force
Check every object against every other
N(N-1)/2 tests O(N²)
Sweep and

Sweep and Prune

Bounding volume is projected onto x, y, z axis
Determine

Spatial Subdivisions

1

2

3

4

5

6

7

8

Images from pg 699, 700 GPU Gems III

O1

O2

O3

O4

1

2

3

4

5

6

7

8

Example

CULLIDE

Came out of Dinesh’s group at UNC in 2003
Uses graphics hardware

Outline

Overview
Pruning Algorithm
Implementation and Results
Conclusions and Future Work

Outline

Overview
Pruning Algorithm
Implementation and Results
Conclusions and Future Work

Overview

Potentially Colliding Set (PCS) computation
Exact collision tests on the PCS

Algorithm

Object Level Pruning

Sub-object Level Pruning

Exact Tests

Potentially Colliding Set (PCS)

Potentially Colliding Set (PCS)

PCS

Outline

Problem Overview
Overview
Pruning Algorithm
Implementation and Results
Conclusions and Future Work

Algorithm

Object Level Pruning

Sub-object Level Pruning

Exact Tests

Visibility Computations

Lemma 1: An object O does not collide with

Collision Detection using Visibility Computations

PCS Pruning

Lemma 2: Given n objects O1,O2,…,On , an object Oi

PCS Pruning

O1 O2 … Oi-1 Oi Oi+1 … On-1 On

O1 O2

PCS Pruning

O1 O2 … Oi-1 Oi

PCS Pruning

Oi Oi+1 … On-1 On

PCS Computation

Each object tested against all objects but itself
Naive algorithm is

PCS Computation: First Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

PCS Computation: First Pass

O1

PCS Computation: First Pass

O1 O2

O1 O2 … Oi-1 Oi

PCS Computation: First Pass

PCS Computation: First Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

PCS Computation: Second Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

PCS Computation: Second Pass

On

PCS Computation: Second Pass

On-1 On

PCS Computation: Second Pass

Oi Oi+1 … On-1 On

PCS Computation: Second Pass

Fully Visible?

O1 O2 … Oi-1 Oi Oi+1 …

PCS Computation

O1 O2 … Oi-1 Oi Oi+1 … On-1 On

PCS Computation

O1 O3 … Oi-1 Oi+1 … On-1

Example

O1

O2

O3

O4

Scene with 4 objects O1and O2 collide O3, O4 do not collide

Initial PCS

O3

O1

First Pass

O2

Order of rendering: O1 O4

O4

Second Pass

O1

O3

O2

Order of rendering: O4 O1

O4

After two passes

O1

O2

O3

O4

Potential Colliding Set

O1

O2

PCS ={O1,O2}

Algorithm

Object Level Pruning

Sub-object Level Pruning

Exact Tests

Overlap Localization

Each object is composed of sub-objects
We are given n objects

Overlap Localization

Our solution
Test if each sub-object of Oi overlaps with sub-objects

Overlap Localization

Sub-objects

Overlap Localization: First Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

Overlap Localization: First Pass

O1 O2 … Oi-1 Oi

Rendered sub-objects

Overlap Localization: First Pass

O1 O2 … Oi-1

Rendered sub-objects

Overlap Localization: First Pass

O1 O2 … Oi-1

Rendered sub-objects

Overlap Localization: First Pass

Rendered sub-objects

O1 O2 … Oi-1

Overlap Localization: First Pass

Rendered sub-objects

O1 O2 … Oi-1

Overlap Localization: First Pass

O1 O2 … Oi-1 Oi

Rendered sub-objects

Overlap Localization: First Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

Overlap Localization: Second Pass

O1 O2 … Oi-1 Oi Oi+1 … On-1

Overlap Localization

O1 O2 … Oi-1 Oi Oi+1 … On-1 On

Sub-objects

Potential Colliding Set

O1

O2

PCS = {O1,O2}

O1

Sub-objects

O2

PCS = sub-objects of {O1,O2}

First Pass

Rendering order: Sub-objects of O1 O2

First Pass

First Pass

First Pass

First Pass

First Pass

First Pass

Second Pass

Rendering order: Sub-objects of O2 O1

Second Pass

Second Pass

Second Pass

Fully Visible

Second Pass

Fully Visible

Second Pass

After two passes

PCS

Algorithm

Object Level Pruning

Sub-object level Pruning

Exact Tests

Exact Overlap tests using CPU

Visibility Queries

We require a query
Tests if a primitive is fully visible

Visibility Queries

Depth function

GEQUAL

LESS

All fragments

Pass

Examples - HP_Occlusion_test, NV_occlusion_query

Bandwidth Analysis

Read back only integer identifiers
Independent of screen resolution

Optimizations

First use AABBs as object bounding volume
Use orthographic views for pruning
Prune

Advantages

No coherence
No assumptions on motion of objects
Works on generic models
A fast

Limitations

No distance or penetration depth information
Resolution issues
No self-collisions
Culling performance varies with

Assumptions

Makes assumptions that their algorithm will get faster as hardware improves.
Luckily

RCULLIDE

An improvement on CULLIDE in 2004
Resolves issue of screen resolution precision

Overview

A main issue with CULLIDE was the fact that it wasn’t

Overview

3 kinds of error associated with visibility based overlap
Perspective error
Strange shapes

Reliable Queries

The three errors cause the following:
A fragment to not be

Reliable Queries

Use “fat” triangles
Generate 2 fragments for each pixel touched by

Minkowski Sum

Scary name…easy math

A = { (1, 0), (0, 1), (0, −1)}

Reliable Queries

In practice, we use the Minkowski sum of a bounding

Reliable Queries

Cubes only work for z-axis projections so in practice use

Bounding Offset

So far we’ve just dealt with single triangles but we

Algorithm

Improvement over CULLIDE

Performance

Still runs faster than CPU implementations
3x slower than CULLIDE due to

QCULLIDE

Extends CULLIDE to handle self collisions in complex meshes
All running in

Self Collision Culling

Note that only intersecting triangles that don’t share a

Self Collision Culling

Algorithm
Include all potentially colliding primitives and PCS where each

Q-CULLIDE

Sets
BFV – Objects fully visible in both passes and are pruned

Q-CULLIDE

Properties of sets
FFV and SFV are collision free
No object in FFV

Algorithm

Algorithm

What’s Happening

Improvement Over CULLIDE

Improvements Over CULLIDE

Sends an order of magnitude less collisions to the

Spatial Subdivision

Partition space into uniform grid
Grid cell is at least as

Parallel Spatial Subdivision

Complications:
Single object can be involved in multiple collision tests
Need

Guaranteed Individual Collision Tests

Prove: No two cells updated in parallel may

Example of Parallel Spatial Subdivision

O1

O2

O3

O4

1

2

1

2

3

4

3

4

O1

O2

O3

O4

1

2

1

2

3

4

3

4

Avoiding Extra Collision Testing

Associate each object a set of control bits

Implementing in CUDA

Store list of object IDs, cell IDs in device

Initialization

Cell ID Array

OBJ 1 Cell ID 1
OBJ 1 Cell ID 2
OBJ

Construct the Cell ID Array

Host Cells (H – Cells)
Contain the centroid

Sorting the Cell ID Array

What we want:
Sorted by Cell ID
H cells

Sorting Cell Array

010
0

011
1

111
2

101
3

021
4

021
n

020
0

110
2

100
3

011
4

011
n

011
0

100
2

021
n

021
0

000
2

111
n

001
2

022
n

101
2

011
2

010
2

...

Cell ID Array

000
2

011
n

101
3

001
2

020
0

101
2

010
0

021
4

110
2

010
2

021
n

111
2

011
1

021
0

111
n

011
0

022
n

111
n

011
2

100
2

102
n

011
4

100
3

103
3

...

Sorted Cell ID Array

011
1

100
2

Invalid Cell

Home Cell

Phantom

Spatial Subdivision

1

2

3

4

5

6

7

8

Images from pg 699, 700 GPU Gems III

O1

O2

O3

O4

1

2

3

4

5

6

7

8

Example

Assign to each

Create the Collision Cell List

Scan sorted cell ID array for changes

Create Collision Cell List

000
2

011
n

101
3

001
2

020
0

101
2

010
0

021
4

110
2

010
2

021
n

111
2

011
1

021
0

111
n

011
0

022
n

111
n

011
2

100
2

102
n

011
4

100
3

103
3

...

Sorted Cell ID Array

Cell Index & Size