Collision Meshes

• Many game engines will allow (or require) the user to define a collision mesh for any object in the scene for which we need to detect the collision with other objects.
• The collision meshes are not displayed. They are only used to compute intersections with other objects instead of the polygons composing the object.
• The collision meshes are defined to make the computation easier: boxes, spheres, cylinders. The fastest test is the one you don't do.

Coplanar Polygons Intersection

• Two coplanar polygons intersect if at least one vertex from one is inside the other polygon, or if any two edges of the polygons intersect.
• Suppose we have a convex polygon and a point inside the polygon (center). Then an arbitrary point is inside the polygon if it's on the same side as the center of all the lines composing the polygon.
• Each polygon can be decomposed in triangles and the intersection computed for each couple of triangles.

Polygon Collision

Point Inside a Polygon

Edges Intersection

Both the vertex check and the edge check are O(n²), where n is the number of vertices in the highest polygon.

Two-Phase Algorithm

• In a scene with m objects, the algorithm must compute O(m²) intersection of pairs of objects.
• A two-phase algorithm eliminates most of the collision computations based on bounding boxes/spheres, etc. This is called the broad phase.
• For moving objects, one can compute the bounding box of the entire movement in the unit of time.
• To eliminate some of the intersections, a hierarchical tiling of the space can be used (quad tree), or a coordinate sorting. A hash table can be used to improve the sorting. This phase can be made almost O(m) (linear).

Narrow Phase Collision

• Analyzes more carefully pairs of coordinates that are not culled by the broad phase.
• Some of them would return the distance between non-intersecting objects that can be used in movement planning.
• Some optimizations are available.

Lin-Canny Algorithm

• Lin-Canny closest features algorithm determines the closest faces / edges / vertices between two polyhedral objects.
• It uses the Voronoi regions for each feature (see next slide). Let F be a feature and V(F) its Voronoi region.
• If A and B are the closest features of two polygons, and a and b the closest points in each feature, then a in V(B) and b in V(A).
• The algorithm iteratively reduces the current closest features.
• Alternatives exist that consider the coherence of the scene over time.

Other Algorithms

• V-Clip Algorithm - an improvement of the Lin-Canny algorithm, also using the Voronoi regions.
• (Gilbert, Johnson, Keerthi) - simplex-based algorithm. It considers the polyhedra as clouds of points and computes a simplex (point, bounded line, triangle, or tetrahedron) as a bounding region of the Minkowski difference polyhedron (or TCSO).
• The TCSO (transitional configuration space obstacle) is a collection of vectors obtained from the difference of points from the two polyhedra.TCSO = {b-a | a in A and b in B}.
• Public libraries for collision-detection are available, like I-Collide, V-Collide, QHull, ColDet.
• Collision detection in games: video

3D Intersections

• Plane equation:ax + by + cz + d = 0
• The two sides of the plane are defined by ax + by + cz + d < 0 ax + by + cz + d > 0
• Two points P and Q are on different sides of the plane if
  (aP_x + b P_y + c P_z + d)* (a Q_x + b Q_y + c Q_z + d) < 0

Crossing a Polygon

• First we must check that the origin O and the destination D are on different sides of the plane.
• Plane: ax + by + cz + d = 0
• Line segment:
  D = O + (t L_x, t L_y, t L_z),
  where L is the direction vector
• P the intersection point is defined as satisfying both the plane and the line segment equations.
• Then we must check that P is inside the polygon based on the equations described before.

Non-Coplanar Polygons

• Compute the intersection line based on the plane equations.
• Check if the line intersects any of the polygons.
• If it intersects both, then a point on this line must be on an edge of one polygon and at the same time inside the other one.

Box - Sphere

• Maximum distance
  max = r + sqrt(w² + h²)/2
• If d(c,p) > max, we don't need to check for collision.
• The collision threshold thr can be computed as:

  if a < b:
    thr = r + (h/2) cos a
  else
    thr = r + (w/2) / cos (90 - a)
         = r + (w/2) / sin a
  

• The easiest way is to transform the sphere into the frame of reference of the box.
  
• The sphere intersects this box of dimensions (w, h, d) if the distance between the center of the sphere (xc, yc, zc) and the center of the box (xb, yb, zb) is less than the side of the box plus the radius of the sphere.
  |xc - xb| < w/2 + r
  |yc - yb| < h/2 + r
  |zc - zb| < d/2 + r

Moving Past a Sphere

• When a box moves from A to B in one frame, it may collide with a sphere on the way.
• We have to project the center of the sphere on the movement line, and if the distance to the line is less than the max and P is between A and B, then we must compute the collision between the objects at the point P.
• The distance between C and a line of equation ax + bz + c = 0 is
  (a c_x + b c_z + d)/sqrt(a² + b²)

Motion and Collision

• When an object hits a surface with a certain velocity, it may bounce from the surface depending on the object elasticity.
  
• A perfectly elastic object bounces from a surface with a speed equal to its original speed, but in a direction symmetric with respect to the surface normal.
  

Imperfect Bouncing

• If the object is not perfectly elastic, then part of the energy resulting from the collision is absorbed.
• The speed can be decomposed in a vector tangent to the surface and one normal to the surface.
  
• The tangent component doesn't change.
• The normal component is partially absorbed by a factor e depending on the two surfaces.
  v_out = vt_out + vn_out = vt_in - e vn_in
  If |N|=1, then vn_in = N v_in (scalar product)
  vt_in = v_in - vn_in

Momentum

For a moving object, its momentum is defined by the mass times the speed:
p(t) = m v(t)

Newton

• An example of physics engine.
• Multi-platform, free, based on OpenGL. http://newtondynamics.com
• Popular in combination with some game engines Irlicht and Ogre.
• Based on the idea of defining objects - bodies - with some geometry, but also with collision geometry associated with them.

Program Structure

• All of the objects are created within a Newton World.
• Define physical properties of the objects. Some of these can be collision meshes, mass, joints and degrees of freedom.
• Add forces to them. Add torque.
• Update the whole system by calling a Solver.