"Yazel, David J." wrote:
>
> Could someone comment on the viability of this technique? How well would
> java3d handle a large number of small bounding boxes in their spatial tree?
> Would this be more efficient and faster than searching through the geometry?
Well, just looking at the very basics of the algorithms. The first point
you don't mention is the details of the bounding boxes. Are these
axis-aligned? (very important point). To me, the system seems to be a
progressive refinement type algorithm - as the boxes approach a size of
zero, they represent more accurately the underlying geometry. Is this a
correct statement?
So, let's assume the best case situation - axis aligned bounding boxes v
geometry.
In pure geometry intersections, you end up with o(n^2) for the colliding
polygons. That is, you have to test every polygon on one shape
intersecting with any polygon on another shape. This is a fairly hefty
computational requirement. Effectively you are computing a plain/plain
intersection although most will simplify this to a plain/box
intersection for speed.
If using the plain/box interesection test method (eg
http://www.gamasutra.com/features/19991018/Gomez_7.htm). Setup costs for
a single plane of the geometry is a normal calculation and the plain.
For each box that plain is tested against, there are 15 multiplies, 8
adds and a compare for each plain and then a distance calc from the box
center to the plain which doubles the above number of calculations.
If your object is just composed of a collection of tiny bounding boxes,
then the calculations are much less severe - particularly if axis
aligned. However, as your number of boxes increase (size for an
individual box decreases) then the computational cost becomes almost
identical to pure polygon intersections. Effectively your box is just a
polygon and so you pay the cost for it.
However, for efficiency, you might want to build bounding boxes into a
structured heirarchy just like j3d does internally. Build a big box for
the full geometry and then start building smaller boxes for each object
within the geometry. That is, we are using the basic culling tree
decision information that Java3D uses internally on a greater level of
detail. If you can keep those boxes axis-aligned, even better. Here's a
good series of rules:
http://www.education.siggraph.org/materials/HyperGraph/raytrace/rtaccel.htm
<QUOTE>
Kay & Kajiya give a list of properties for hierarchical bounding
volumes:
1. Subtrees should contain objects that are near each other and the
further down the tree the closer should be the objects.
2. The volume of each node should be minimal.
3. The sum of the volumes of of all bounding volumes should be minimal.
4. Greater attention should be placed on the nodes near the root since
pruning a branch near the root will remove more potential objects than
one farther down the tree.
5. The time spent constructing the hierarchy should be much less than
the time saved by using it.
</QUOTE>
Here is an article on implementing axis-aligned bounding box tests:
http://www.gamasutra.com/features/19991018/Gomez_3.htm
Basically a single test for two boxes is nine subtractions, nine adds,
and 18 compares. Note it is all subs and adds (even the compare is just
a subtraction) where the plain/box test uses multiplication so this will
be much faster.
--
Justin Couch http://www.vlc.com.au/~justin/
Freelance Java Consultant http://www.yumetech.com/
Author, Java 3D FAQ Maintainer http://www.j3d.org/
-------------------------------------------------------------------
"Humanism is dead. Animals think, feel; so do machines now.
Neither man nor woman is the measure of all things. Every organism
processes data according to its domain, its environment; you, with
all your brains, would be useless in a mouse's universe..."
- Greg Bear, Slant
-------------------------------------------------------------------
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
