Game Development Reference
In-Depth Information
I've assumed that standard sorting and list manipulation routines are available,
along with some extra methods I've used to hide the actual updates for the sake of
brevity (we saw the code for these earlier).
Performance
There are tens of variations of this kind of ordering system and lots of different ways
to sort, keep lists, and perform updates. I implemented six different methods while
experimenting for this topic.
The best performance gain was achieved using the method just described. Un-
fortunately it was very minor. For frames with few contacts, and using some of the
more general optimization techniques described in chapter 16, the performance of
the linked list version is considerably worse than the naïve approach. With many tens
of contacts, among a set of tightly packed objects, 6 itbecomesmoreefficient.Forsev-
eral hundred contacts among tightly packed objects, it becomes significantly faster.
For the simulations I come across in the games I'm involved with, it simply isn't
worth the extra development effort. I'd rather not have the extra pointers hanging
around in the contact and rigid-body data structures. You may come across situ-
ations where the scale of the physics you are working with makes it essential. For
anything in game development it is essential to profile your code before trying to
optimize it.
14.5
S UMMARY
Collision resolution involves some of the most complex mathematics we've met so
far. For a single contact we do it in two steps: resolving the interpenetration between
objects and turning their closing velocity into rebounding velocity.
The velocity resolution algorithm involves working out the effect of applying an
impulse to the contact point. This can then be used to work out the impulse that will
generate the desired effect. The result is a single impulse value that modifies both the
linear and angular velocity of each object involved.
Unlike the velocity resolution algorithm, penetration resolution does not corre-
spond to a physical process (since rigid objects cannot interpenetrate in reality). Be-
cause of this, there are lots of different approaches to get visibly believable behavior.
In this chapter we implemented an approach derived from the same compression and
impulse mathematics used for velocity resolution.
Resolving one contact alone isn't much use. To resolve the complete set of con-
tacts, we used two similar algorithms: one to resolve all penetrations and the second
to resolve all velocities. Each algorithm considered collisions in order of their severity
(i.e., penetration depth or closing velocity). The worst collision was resolved in isola-
6. The significance of tightly packed objects will become apparent in chapter 16: if objects are not tightly
packed, then it is possible to consider contacts in smaller batches, which is much more efficient.