-
Notifications
You must be signed in to change notification settings - Fork 5
Real Time Collision Detection Notes
- barycentric coordinates are also called areal coordinates
-
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.
- P is a supporting point of C if for a given direction d it holds that
-
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.
works in both 2D and 3D
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.
-
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.
Desirable properties for bounding volumes include:
- ● Inexpensive intersection tests
- ● Tight fitting
- ● Inexpensive to compute
- ● Easy to rotate and transform
- ● Use little memory
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
principal component analysis (PCA)
Welzl’s algorithm
// TODO
// TODO
- sphere-swept points (SSPs): spheres
- sphere-swept lines (SSLs): capsules (capped cylinders or spherocylinders)
- sphere-swept rectangles (SSRs): lozenges
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).
method of alternating projection (MAP)
// TODO
- 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
// TODO
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.
It can also be shown that hierarchies of OBBs converge quadratically to match the bounded geometry, whereas AABBs and spheres converge only linearly.
- 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
- 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
front of the tree serves as witness to the disjointedness of the two objects
hierarchical spatial hash table
locational code: Morton order
childKey = (parentKey << 3) + childIndex
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).
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.
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.
A simple method for solving linear programming problems in
d
variables andm
inequality constraints is Seidel’s algorithm. Seidel’s algorithm has an expected running time ofO(d!m)
.
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.
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.