Thanks Justin!
Yes, we plan to strike a balance between box size and accuracy. Its
important to note that the bounding boxes we will be trying to build will
model "solid-filled" space, which can (and will) span geometry. So for
example a wall might have 6 sides composed of pieces from 15 different
shapes, but we would detect that it was a large contiguous axis aligned box
which enclosed inaccessible space.
So we had two possible approaches. If we did our own implementation of
Bounds to handle a composite bounds, then yes we would implement something
along the lines of what you suggest.
But what if we cheated? What if we put non-renderable nodes into the same
branchgroup as the geometry, each with one of these bounding boxes? So if
we calculated 50 bounding boxes, then we would have 50 pickable, collidable
invisible nodes with these boxes. TYhis would turn over management of the
bounds searching over to java3d. Since they already have a mechanism for
spatially organizing bounds, I would suspect it would perform well...
I would like to know from the Sun guys if they think this would "break" the
java3d core.
Dave Yazel
-----Original Message-----
From: Justin Couch [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, June 05, 2001 10:10 AM
To: [EMAIL PROTECTED]
Subject: Re: [JAVA3D] Self-calculating bounds idea
"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".
===========================================================================
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".
