Graphics Reference
In-Depth Information
critical component could be costly. In evaluating the ease of implementation it is of
interest to look at not just the overall algorithm complexity but how many and what
type of special cases are involved, how many tweaking variables are involved (such as
numerical tolerances), and other limitations that might affect the development time.
Several additional issues relate to the use of the collision detection system. For
example, how general is the system? Can it handle objects of largely varying sizes?
Can it also answer range queries? How much time is required in the build process
to construct the collision-related data structures? For the latter question, while the
time spent in preprocessing is irrelevant for runtime performance it is still impor-
tant in the design and production phase. Model changes are frequent throughout
development, and long preprocessing times both lessen productivity and hinder
experimentation. Some of these problems can be alleviated by allowing for a faster,
less optimized data structure construction during development and a slower but more
optimal construction for non-debug builds.
2.7.1
Debugging a Collision Detection System
Just like all code, collision detection systems are susceptible to errors. Finding these
errors can sometimes be both difficult and time consuming. Steps can be taken during
development to make this debugging process less painful. Some good ideas include:
Keep a cyclic buffer of the arguments to the
n
last collision queries, correspond-
ing to up to a few seconds' worth of data (or more). Then, when something
goes visually wrong, the program can be paused and the data can be out-
put for further analysis, such as stepping through the calls with the saved
arguments. The logged data may also provide useful information when
assert
s
trigger.
●
Provide means to visualize the collision geometry. For example, you might visu-
alize tested faces, their collision attributes, and any hierarchies and groupings
of the faces. Additionally, visualize the collision queries themselves, prefer-
ably with the history provided by the cyclic buffer mentioned earlier. This
visualization provides a context that makes it easy to spot bad collision queries.
●
Implement a simple reference algorithm (such as a brute-force algorithm that
tests all objects or all polygons against each other) and run the reference algo-
rithm in parallel with the more sophisticated algorithm. If the results differ,
there is a problem (in all likelihood with the more advanced algorithm).
●
Maintain a test suite of queries, and run the collision code against the test
suite when the code changes. Code of geometric nature tends to have many
special cases, and having a set of comprehensive tests helps in trapping prob-
lems early. Whenever a bug is found, add test cases to detect if it is ever
reintroduced.
●
