Game Development Reference
In-Depth Information
Our SAT-based method can only work with a pair of convex objects. Concave
objects would need to be subdivided into convex pieces. The approximate contact-
manifold method is also good only for convex pairs of objects. Concave shapes
will generate a manifold for each convex subshape pair. That may amount to a lot
of contacts. An additional contact-optimizing pass may eliminate a lot of them.
The narrow phase of collision detection is concerned with finding the contact
point or points between a pair of objects. Narrow phase follows broad phase
and is computationally much more intensive than broad phase. On the flip side,
narrow phase is very easily parallelizable. It arguably scales better than both
the preceding broad phase and the following dynamic solver. The output of the
narrow phase goes to the dynamics solver and consists of one or more contacts
between the pair of objects. It is the last stage where the shapes of colliding
objects matter: the dynamics solver will only look at the contact points, without
giving any thought to the object's shape.
Narrow phase collision detection deals with two objects in close vicinity,
sometimes penetrating. Depending on our approach, we may allow penetration
universally (i.e., require all objects to penetrate by a small margin) or disallow it
(e.g., require all objects to have a small distance between them). Effectively, our
strategy will change the shape of the objects, either “imploding” them or extrud-
ing and beveling them.
If we require all objects to penetrate, we don't need to compute the exact
distance between them if they don't penetrate. We may still want to generate
contacts with “negative penetration” speculatively for the velocity solver to be
more stable in subsequent iterations or for the positional solver to prevent them
from penetrating. If the velocity solver knows objects are about to collide, it can
reduce the relative speed in anticipation of impact, speculatively. It's a hack, and
friction should not be applied in such a case. The penetration solver may use a
contact with negative penetration as a safeguard against making objects penetrate
each other to prevent penetration with other objects.
4.3.2 Constraint Solver
Sometimes, after a contact manifold is completely generated, it consists of more
points than necessary for stable simulation. The sampling algorithm from Sec-
tion 4.6.7 partly takes care of that, but if we sample many directions or use the
direct method of support-shape computation as in Section 4.6.3, we still may end
up with more points than necessary. It may be desirable to remove some points
from the manifold.
We care about spending time to reduce the contact points because extra con-
tact points that don't add much to the simulation quality may add to the simulation