Collision Detection Technical Notes

In Vortex®, objects themselves do not actually collide, but rather a collision is detected when their associated collision geometries overlap. For performance, smoothness and stability, these geometries are typically simpler in shape and complexity than any possibly associated 3D model used for visualization.

When a collision is detected, a set of contact constraints is generated and considered in the solver, which then computes the collision force response necessary to prevent objects from penetrating, taking into account material properties such as stiffness, damping and friction coefficients found in the material table. When objects are moving fast, it is possible to flag them as fast-moving to avoid tunneling issues (i.e., the two rigid bodies going through each other).

The collision detection algorithm consists of a series of overlap tests, starting with fast, efficient, approximate tests, followed by progressively more accurate and less conservative algorithms. This procedure quickly eliminates as many pairs of potentially overlapping objects as possible before detailed and more costly intersection tests are performed on the remaining candidate pairs are performed, making the approach very efficient.

In the broad phase, fast, inexpensive tests eliminate potentially overlapping pairs of objects. This phase operates on bounding volumes and not on the exact collision shapes, which makes it very efficient.

As a result, the broad phase produces a list of geometry pairs which are potentially overlapping.

Then, in the narrow phase, more expensive and accurate intersection tests are performed for every pair. For mesh geometries, an additional middle phase further reduces the number of potentially colliding triangles. This avoids testing all triangles for collisions and greatly reduces the computational complexity. Custom spatial hashing data structures are employed for this purpose.

Collision Shapes (Collision Geometries)

Vortex supports a number of types of geometries, including the following:

• Primitives: plane, box, sphere, cylinder, capsule
• Convex meshes
• Meshes: general triangle meshes (optimized using OBB trees, or by hashing into a 2D grid), HeightField (regular grid, with different height), Level Set (or Distance Field) grid
• Composite geometries, which allow grouping together a set of other geometries.

Multiple geometries may be associated with a given part, each with its own relative transform to the part. By design, they will not collide with each other.

Typically the local Z-axis of the geometries has a special meaning: the cylinder and the capsule axis is the local Z-axis of the geometry. In the HeightField, the matrix of heights represents heights along the HeightField’s local Z-axis, and the UV Grid projects all triangles onto an internal grid data structure, aligned by default with the geometry’s local X-Y plane.

Broad Phase

Given a set of collision geometries, the broad phase will quickly determine which geometries potentially overlap by considering their axis aligned bounding boxes (AABB) (which are updated from the parts' positions at the start of the collision phase). As a result, it outputs a list of potentially overlapping pairs of geometries.

A number of techniques exist to avoid the O(n²) cost of a naive algorithm, such as hashing into grids, bounding volume hierarchies, etc. In Vortex, we use a highly optimized incremental axis sort algorithm based on the sweep and prune collision detection algorithm.

The AABBs of all geometries (except those in composite geometries, where the AABB of the composite is used) are projected on all three world axes. When an overlap of projections is detected for all three axes of given pair of AABBs, it is clear that the AABBs are in fact overlapping. The corresponding geometry pair is then reported as a potentially overlapping pair.

Parking

VxUniverse supports the ability to have geometries temporarily removed from collision detection.

There are two ways for temporarily removing (parking) collision geometries, both with different associated computational costs:

• Short term parking: In this approach, collision geometries are still in the simulation space but are disabled when parked (they are moved to the edge of the simulation space). This method has a small runtime cost as the collision geometries are still maintained in the collision detection, but the process of parking and re-enabling is very fast.
• Long term parking: In this approach, collision geometries are completely removed from the simulation space when parked. When re-enabled, the collision geometry is added to the simulation space. This method has no runtime cost, but performs slower during the operation of parking and re-enabling.

One application of this feature is to create a pool of collision geometries from which one can fetch geometries to be used at runtime. For example, one can maintain a set of “trees” close to a vehicle in a forest, by manually instantiating trees near a vehicle. This can be done by taking, positioning and unparking tree geometries from the pool.

Narrow Phase

Collision Geometries

The table of implemented interactions is as follows, where x represents a supported interaction:

Specific optimized overlap detection and contact generation code has been implemented for most interactions of these geometries.

Contact Generation

For each geometry pairs, a specific intersection algorithm is implemented to compute the contact points. A contact point is defined by a position, a normal vector and a scalar distance. The position defines the location of the contact, the normal vector provides the direction along which the two colliding surfaces can be separated, and the scalar distance represents the penetration depth of the colliding surfaces in the direction of the normal vector.

Contact Simplification

In order to improve performance, not all contact points are sent to the solver. Four contacts are sufficient for an interaction between two convex shapes. Moreover, sending too many contact points can have a negative impact on stability, due to over-constrained systems to solve.

For this reason, the number of contacts is reduced as shown in the following example.

Contact Tolerance

When two geometries overlap, in general, an overlap is reported only if it exceeds the contact tolerance. The sum of the tolerances of both geometries is used as the tolerance in the computation.

Middle Phase

For efficient computation of intersections with triangle meshes, an additional collision detection phase is executed which follows the broad phase. Consider for a moment that the AABB of a given triangle mesh geometry overlaps with some other geometry, making the geometries a potentially colliding pair in the broad phase. In order to calculate the exact intersection of the two geometries, one could now in a naive approach compute the intersections between each triangle in the mesh and the other geometry. For meshes with many triangles, this approach can be very time consuming and is therefore not appropriate for real-time simulation. Therefore, in order to avoid unnecessary computations, potentially colliding triangles are first identifie

d in a so-called middle phase. This middle phase varies depending on the mesh type.

HeightField

The triangles in a HeightField are uniformly arranged in a regular pattern on a 2D grid, varying in height along the local Z-axis, and having identical spatial extent on the X-Y plane of the HeightField. This pattern can be exploited to quickly identify potentially overlapping triangles by simply projecting the AABB of the colliding geometry onto the 2D grid and considering all
HeightField triangles as potentially overlapping which fall in to the projection of the AABB. This query operation has constant time complexity.

Note This efficiency comes with the limitation that height fields can not be used to represent any geometric shape as the height field triangles have predetermined X and Y coordinates.

UV Grid

The UV Grid is an efficient middle phase especially for terrains, because all triangles are put in a cell according to their 2D coordinates. The cell can be queried in O(1), then other subdivision hierarchies are in place to speed up the search in the current cell. This structure supports any kind of triangle mesh.

Bounding Volume Tree

The structure is the only mesh that is able to collide with itself. Thanks to an efficient tree structure we can query the triangles that collide with another convex or another Bounding Volume Tree. This structure supports any kind of triangle mesh.

Continuous Collision Detection

Continuous collision detection is done to avoid tunneling issues. That means, avoiding rigid bodies going through each other due to high speed and discrete time steps. To avoid tunneling issues, a collision geometry has a fast moving flag that can be activated. For each of these geometries, an additional treatment is done be during the collision detection.

During the broad phase, the AABB is extended depending on the linear and angular velocity. Thus, the new AABB has to find more collision pairs with other geometries.

In the narrow phase, those pairs are moved incrementally to determine if there is a collision between these two geometries. This search is processed in two steps: one rough movement that ensures not to miss the collision according to the thickness of the geometry and its speed, and another more detailed step which provides the time of impact with good precision.

Once the time of impact has been computed according to the angular and linear velocity and the angular and linear acceleration, contact points are created at the anticipated impact location. This approach effectively avoids "tunneling" issues, i.e., fast-moving objects passing through each other whereas they should collide.

Updating Geometries at Runtime

Primitives: Can be resized as needed.

HeightField: Heights can be changed at runtime via an update function.

Level Set: The 3D grid can be updated at runtime.

UV Grid: Can change vertex heights, but not move the vertices laterally. An update function needs to be called to update the internal height bounds and overall bounding box. Can also remove triangles without cost.

It is also possible to completely re-create the mesh, allowing the use of this data structure for receiving terrain data below a moving vehicle.