Graphics Reference
In-Depth Information
according to similar rules. For instance, if different types of primitives are used, such
as both triangles and quads as well as Bezier or NURBS surfaces, it makes sense to
test the polygons first before performing the more expensive tests involving surface
primitives.
It is also possible to arrange primitives to obtain extra culling information for
free. Say an OBB tree is built from a set of polygons representing a static world
that is collided with largely from above. The leaf OBBs of this tree are unlikely to
have polygons extending all the way into their topmost corner. Let the polygons
be rearranged so that the polygon with the highest vertex comes first in the list of
polygons. Then rearrange this polygon's vertices so that the topmost vertex comes
first in its set of vertices. Now the plane defined by the world
up
normal and the first
vertex stored in the leaf (which is in a known position) can be used to quickly cull
collisions with the OBB before other, more expensive, tests are performed.
Other possible arrangements include sorting vertices so that the two vertices form-
ing the longest edge come first, and placing the vertex first, which together with
the polygon centroid (which is easily computed from the stored vertices) forms the
bounding sphere of the polygon (the centroid being the sphere center and the vertex
defining the sphere radius).
6.6.6
On Recursion
Traversing of trees (binary or otherwise) is naturally expressed using recursion.
However, as was pointed out in Section 6.3.2, recursion is not the most effective
form in which to express the code. It suffers from a few other drawbacks. One prob-
lem is that exiting the recursion and immediately returning a value is not directly
supported in most languages. Using a flag variable to tell the code to exit is not just
an overly complicated and contrived solution but requires the recursion to “unwind”
all the way to the top.
The ideal solution is to rewrite any recursive code using explicit stacking, in the
manner described in Section 6.3.2. As the code is no longer recursive, it is possible
to exit the function at any time. Further benefits include the ability to interrupt and
resume the code at any point by simply saving away a few variable values. Having
an explicit stack pointer makes it easy to detect bugs in the traversal code that might
otherwise have caused an infinite recursion, and the code is overall easier to step
through during debugging. An explicit stack pointer also implicitly provides a stack
depth, making it easy to limit traversals to a specified maximum depth if so desired.
Not using recursion also avoids the overhead of recursive function calls. It is also
likely to use less stack space, as only one stack frame for the local variables is ever
created, reducing possible data cache trashing.
All of these considerations aside, during early development much can be said for
the benefits of using easy-to-read recursive code for quick prototyping and testing.
Fortunately, in both C and C++ there are alternatives to using nonrecursive code just
