Chapter 3 A Math and Geometry Primer

3.4 Barycentric Coordinates

• barycentric coordinates are also called areal coordinates

3.8 Polyhedra

• simplex

• • A d-simplex is the convex hull of d+1 affinely independent points in d-dimensional space.

• supporting point (extreme points)

• • P is a supporting point of C if for a given direction d it holds that $$d·P = max { d · V : V ∈ C }$$; that is, P is a point for which $$d·P$$ is maximal.

• support mapping (support function)

• • A support mapping (or support function) is a function, SC(d), associated with a convex set C that maps the direction d into a supporting point of C.

• supporting plane

• separating plane

• separating axis

• • For two nonintersecting convex sets, it can be shown that a separating axis (or plane) always exists.

• The surface of a polyhedron is often referred to as a 2-manifold.

3.9 Computing Convex Hulls

3.9.1 Andrew’s Algorithm

3.9.2 The Quickhull Algorithm

works in both 2D and 3D

3.10 Voronoi Regions

Given a set S of points in the plane, the Voronoi region of a point P in S is defined as the set of points in the plane closer to (or as close to) P than to any other points in S.

3.11 Minkowski Sum and Difference

• The Minkowski difference is important from a collision detection perspective because two point sets A and B collide (that is, have one or more points in common) if and only if their Minkowski difference C (C = A - B) contains the origin.

• computing the minimum distance between A and B is equivalent to computing the minimum distance between C and the origin.

• The Minkowski difference of two objects is also sometimes referred to as the translational configuration space obstacle (or TCSO). Queries on the TCSO are said to be performed in configuration space.

Chapter 4 Bounding Volumes

4.1 Desirable BV Characteristics

Desirable properties for bounding volumes include:

• ● Inexpensive intersection tests
• ● Tight fitting
• ● Inexpensive to compute
• ● Easy to rotate and transform
• ● Use little memory

4.2 Axis-aligned Bounding Boxes (AABBs)

4.2.1 AABB-AABB Intersection

4.2.2 Computing and Updating AABBs

For updating or reconstructing the AABB, there are four common strategies:

• ● Utilizing a fixed-size loose AABB that always encloses the object
• ● Computing a tight dynamic reconstruction from the original point set
• ● Computing a tight dynamic reconstruction using hill climbing
• ● Computing an approximate dynamic reconstruction from the rotated AABB

4.2.3 AABB from the Object Bounding Sphere

4.2.4 AABB Reconstructed from Original Point Set

4.2.5 AABB from Hill-climbing Vertices of the Object Representation

4.2.6 AABB Recomputed from Rotated AABB

4.3 Spheres

4.3.1 Sphere-sphere Intersection

4.3.2 Computing a Bounding Sphere

4.3.3 Bounding Sphere from Direction of Maximum Spread

principal component analysis (PCA)

4.3.4 Bounding Sphere Through Iterative Refinement

4.3.5 The Minimum Bounding Sphere

Welzl’s algorithm

4.4 Oriented Bounding Boxes (OBBs)

4.4.2 Making the Separating-axis Test Robust

4.4.3 Computing a Tight OBB

// TODO

4.4.4 Optimizing PCA-based OBBs

// TODO

4.4.5 Brute-force OBB Fitting

4.5 Sphere-swept Volumes (SSVs)

• sphere-swept points (SSPs): spheres
• sphere-swept lines (SSLs): capsules (capped cylinders or spherocylinders)
• sphere-swept rectangles (SSRs): lozenges

4.5.1 Sphere-swept Volume Intersection

4.5.2 Computing Sphere-swept Bounding Volumes

4.6 Halfspace Intersection Volumes

4.6.1 Kay–Kajiya Slab-based Volumes

4.6.2 Discrete-orientation Polytopes (k-DOPs)

discrete-orientation polytopes (k-DOPs) or fixed-direction hulls (FDHs)

The largest drawback to k-DOPs is that even if the volumes are rarely colliding the k-DOPs must still be updated, or “tumbled.”

In general, k-DOPs perform best when there are few dynamic objects being tested against many static objects (few k-DOPs have to update) or when the same object is involved in several tests (the cost of updating the k-DOP is amortized over the tests).

4.6.3 k-DOP–k-DOP Overlap Test

4.6.4 Computing and Realigning k-DOPs

method of alternating projection (MAP)

4.6.5 Approximate Convex Hull Intersection Tests

Chapter 5 Basic Primitive Tests

5.1 Closest-point Computations

5.1.1 Closest Point on Plane to Point

5.1.2 Closest Point on Line Segment to Point

5.1.2.1 Distance of Point to Segment

5.1.3 Closest Point on AABB to Point

5.1.3.1 Distance of Point to AABB

5.1.4 Closest Point on OBB to Point

5.1.4.1 Distance of Point to OBB

5.1.4.2 Closest Point on 3D Rectangle to Point

5.1.5 Closest Point on Triangle to Point

// TODO

5.2 Testing Primitives

5.2.1 Separating-axis Test

• separating hyperplane theorem: given two convex sets A and B, either the two sets are intersecting or there exists a separating hyperplane P such that A is on one side of P and B is on the other.

For two general polytopes with the same number of faces (F) and edges (E) there are 2F + E^2 potential separating axes.

• ● Axes parallel to face normals of object A
• ● Axes parallel to face normals of object B
• ● Axes parallel to the vectors resulting from the cross products of all edges in A with all edges in B

5.2.1.1 Robustness of the Separating-axis Test

5.2.2 Testing Sphere Against Plane

// TODO

Chapter 6 Bounding Volume Hierarchies

Comparing bounding volume hierarchies with spatial partitioning schemes, the main differences are that two or more volumes in a BVH can cover the same space and objects are generally only inserted in a single volume. In contrast, in a spatial partitioning scheme the partitions are disjoint and objects contained in the spatial partitioning are typically allowed to be represented in two or more partitions.

6.1 Hierarchy Design Issues

6.2 Building Strategies for Hierarchy Construction

6.3 Hierarchy Traversal

6.3.1 Descent Rules

6.3.2 Generic Informed Depth-first Traversal

6.3.3 Simultaneous Depth-first Traversal

6.3.4 Optimized Leaf-direct Depth-first Traversal

6.4 Sample Bounding Volume Hierarchies

6.4.1 OBB Trees

It can also be shown that hierarchies of OBBs converge quadratically to match the bounded geometry, whereas AABBs and spheres converge only linearly.

6.4.2 AABB Trees and BoxTrees

6.5 Merging Bounding Volumes

6.6 Efficient Tree Representation and Traversal

6.7 Improved Queries Through Caching

• positive (meaning it helps in more quickly detecting that the two objects are colliding)
• negative (meaning it aids in determining the separation of the two objects)
• witnesses: Specific pieces of information that can help quickly answer decision problems

6.7.1 Surface Caching: Caching Intersecting Primitives

• shared cache: a global cache that contains any number of pair entries
• distributed cache: a local cache wherein the primitives are stored within the objects themselves

6.7.2 Front Tracking

front of the tree serves as witness to the disjointedness of the two objects

Chapter 7. Spatial Partitioning

7.1 Uniform Grids

7.1.1 Cell Size Issues

7.1.2 Grids as Arrays of Linked Lists

7.1.3 Hashed Storage and Infinite Grids

7.1.4 Storing Static Data

7.1.5 Implicit Grids

7.2 Hierarchical Grids

7.2.1 Basic Hgrid Implementation

7.2.2 Alternative Hierarchical Grid Representations

hierarchical spatial hash table

7.2.3 Other Hierarchical Grids

7.3 Trees

7.3.1 Octrees (and Quadtrees)

7.3.2 Octree Object Assignment

7.3.3 Locational Codes and Finding the Octant for a Point

locational code: Morton order

childKey = (parentKey << 3) + childIndex

7.3.4 Linear Octrees (Hash-based)

7.3.5 Computing the Morton Key

7.3.6 Loose Octrees

7.5 Sort and Sweep Methods

7.5.1 Sorted Linked-list Implementation

Chapter 9. Convexity-based Methods

Convex objects have certain properties that make them highly suitable for use in collision detection tests. One important property is the existence of a separating plane for nonintersecting convex objects (see Section 3.8). Another property of convex objects is that the distance between two points — one from each object — is at a local minimum. The distance is also a global minimum (Figure 9.1a).

9.1 Boundary-based Collision Detection

9.2 Closest-features Algorithms

9.2.1 The V-Clip Algorithm

9.3 Hierarchical Polyhedron Representations

9.3.1 The Dobkin–Kirkpatrick Hierarchy

9.4 Linear and Quadratic Programming

Given two convex polyhedra, A and B, each expressed as the intersection of halfspaces, the convex polyhedron C that is their intersection volume is described (perhaps redundantly) by the intersection of all halfspaces from both A and B. A and B are therefore in collision if and only if there is a solution to the LP problem with the defining halfspaces of A and B as the linear constraints. Because any point common to both polyhedra will serve as a witness to their collision, the objective function can be chosen arbitrarily

Alternatively, the intersection problem can be expressed as an LP problem in the following way. Let the two polyhedra be given in terms of their vertices. Now a linear programming problem can be set up to determine whether there exist coefficients for a plane such that it forms a separating plane for the two polyhedra.

9.4.1.1 Fourier–Motzkin Elimination

Although Fourier–Motzkin elimination is both conceptually simple and straightforward to implement, a major drawback is the rapid increase of inequalities as variables are eliminated. Worst case, the number of inequalities is squared in each iteration, giving an exponential complexity. Despite the worst-case exponential complexity, Fourier–Motzkin elimination is still interesting (for small problems) in that the method is amenable to parallelization. Fourier–Motzkin elimination is closely related to a method for enumerating the vertices of a polyhedron, known as the double description method.

9.4.1.2 Seidel’s Algorithm

A simple method for solving linear programming problems in d variables and m inequality constraints is Seidel’s algorithm. Seidel’s algorithm has an expected running time of O(d!m).

9.4.2 Quadratic Programming

9.5 The Gilbert–Johnson–Keerthi Algorithm

9.5.4 Hill Climbing for Extreme Vertices

9.5.5 Exploiting Coherence by Vertex Caching

Because objects tend not to move much from frame to frame relative one another, a good choice for the initial point P would be the closest point to the other object as found on the previous frame.

When there is little frame-to-frame coherency, a better option might be to obtain the vector between the object centroids, compute supporting vertices on both objects with respect to the vector, and use these vertices as the starting points. This method can also be useful as a first-time initialization.

9.5.6 Rotated Objects Optimization

9.5.7 GJK for Moving Objects

Chapter 10 GPU-assisted Collision Detection

10.1 Interfacing with the GPU

10.1.1 Buffer Readbacks

10.1.2 Occlusion Queries

10.2 Testing Convex Objects

The basic idea behind these methods is to consider each render buffer pixel as a ray, perpendicular to the viewplane, cast toward the objects. When the ray intersects an object, the intersection can be described as an interval of first and last intersection with the ray.

It is worth noting that the presented test also serves as a conservativetest for concave objects A and B. If the test reports A and B as not intersecting, they are indeed not intersecting (within the accuracy of the rasterized approximation). However, if the test reports the concave objects as intersecting, they may or may not actually be intersecting in reality.

10.4 GPU-based Collision Filtering