| 4.3. Octrees for dynamic worlds | ||
|---|---|---|
 | Chapter 4. Octrees |  |
In version 1.6.0 of the engine, the octree structures were much improved to make them suitable for dynamic scenes. The crucial idea is to use a 2-level hierarchy of octrees (instead of a single octree).
Each shape has it's own triangle octree, build and stored in local shape coordinates (
TShape.OctreeTriangles). Since everything inside this octree is stored in local coordinates, nothing has to be updated when merely the transformation of this shape changes (it's moved, rotated and such). When the local geometry changes, the octree still has to be rebuild — but now it's only the octree for this particular shape, octrees of other shapes don't change.There's also a single octree of all scene shapes. Shapes are stored there in world coordinates. Each change of geometry causes the rebuild of this octree, but this is a small octree, so rebuilding it is usually very fast.
When making a collision query, for example when testing whether a ray (given in world coordinates) intersects the scene, we start with a normal collision in the shape octree. At the leaves, we have a list of shapes potentially intersecting this ray. To test ray with each shape, we transform the ray into shape's local coordinates (this means we need to keep an inverted matrix of shape transformation, to convert from world space into local space). Then the ray in local coordinates is checked for collisions with triangle octree inside the shape. After the testing, we need to transform the returned intersection (if found) back into world coordinates.
I dare to say that this works pretty excellent. Traversing the shape
octree must be done efficiently, just like traversing triangles octree
— in fact, we simply have TBaseTrianglesOctree
class that implements the non-leaf traversing algorithms for both tree
kinds. Triangle/shape octrees only have to handle what happens in leaf
octree nodes. Both octrees use the mailbox
technique to avoid checking the same item more than
once during one collision query. For triangle octree mailboxes
save the number of direct triangle vs ray/segment tests.
For shape octree they save the number of shape vs ray/segment
tests (so we will have less queries to local shape octrees,
which is quite important saving, this makes query time more than 2 times
faster on some scenes).
As noted, we need to know the transformations and
inverted transformations of the shapes, to freely switch between world
and local coordinate space. For normal transformations (Transform
node in VRML >= 2.0) we simply calculate the inverted matrix along
with the normal matrix when traversing VRML/X3D graph, so when doing collision
query we have both matrices ready to use. For arbitrary 4x4 matrix
transformations (MatrixTransform node, standard in VRML 1.0,
and added as an extension to VRML >= 2.0) we have to actually calculate
matrix inversion. Careful reader will spot here potential problems:
What if the matrix is not reversible? What if there's a scale with zero factor, for example a scale
(1, 1, 0)that projects shape onto Z=0 plane?Well, then we'll have a problem... this is simply not solved now, and as far as I know it would just require special treatment (which is quite difficult, since there may be many such difficult transforms along the traversing way).
A minor problem is with arbitrary matrices, as they may change a point into a direction or the other way around (as we work with homogeneous coordinates, each 3D point is actually a 4D vector with non-zero 4th component; each 3D direction is a 4D vector with 4th component zero). This is simply detected and no collision assumed — we can't do anything more sensible for these cases actually. That's why I really like the fact that VRML >= 2.0 removed
MatrixTransformfrom the standard — forcing authors to express transformations in terms of onlyTransformnode is a Good Idea.Another problem is when we check for collisions with axis-aligned box or sphere. How to transform an axis-aligned box or sphere by a matrix?
An axis-aligned box should turn into an oriented box by a mere rotation. If we also take into account scaling along the arbitrary axis, you get something that doesn't even have to be a box. It's a 6-DOP, that is a set of 3 pairs of parallel planes. There are known routines to detect collisions with such thing, but admittedly they are a little more involved and, what's more important, much slower than routines dealing with simple axis-aligned box.
A sphere under an arbitrary transformation will turn into an ellipsoid. Ellipsoid is a sphere with (possibly) non-uniform scale along an arbitrary 3D axis. To make collisions with it you usually just un-rotate and un-scale the other object (like triangle) and then make normal intersection with a sphere. Again, this is doable, but is also slower (than normal, untransformed, sphere routines).
So what's our solution? Just ignore the whole issue. Transform axis-aligned box into another axis-aligned box, possibly enlarging it by the way. Convert sphere into axis-aligned box, and then transform this into possibly even larger axis-aligned box. This way we input an axis-aligned box into local sphere's octree. While this looks like a lame solution, it's also simple and fast. Practice shows that it's “lameness” is totally not noticeable on real 3D scenes. That's because boxes and spheres are used mainly as bounding volumes for player and creatures. So the fact that they grow slightly larger during collision detection is not noticeable in practice.
Still, implementing it better, at least using ellipsoids is of course planned some day. It just doesn't seem desperately needed now.
The goal is to implement one day a really dynamic octree, to avoid rebuilding the shape octree at all. For details, see the paper Dynamic Irregular Octrees (from the page http://www.cs.nmsu.edu/CSWS/php/techReports.php?rpt_year=2003) by Joshua Shagam and Joseph J. Pfeiffer. A short summary of the idea:
First of all, updating the octree can be done simply by deleting and re-inserting the octree item.
During delete and insertion you should try to keep the octree balanced, so leafs may be split or merged to keep octree limits (
maxDepth,leafCapacityin our implementation) satisfied. Inserting is of course already implemented (that's how we construct the octree), the delete operation must be done.To make the deletion possible in a reasonable time, you have to keep each item only once in the octree. This means that some items will not be placed at octree leaves, instead they will be “stuck” at the lowest possible internal node.
Note that this will also make the “mailbox” idea useless, as the only function of “mailbox” is to save the computation when items are duplicated many times in the octree.
The fact that some items get “stuck” at internal nodes is generally a bad thing. We want to move items as deep as possible, to gain from octree traversing. Otherwise the whole idea of octree becomes useless.
To counter this, we make the octree node planes optional. Since a plane may be “deactivated”, some items may be allowed to go deeper into the octree.
| |  | |
| 4.2. How octree works |  | 4.4. Similar data structures |