Thanks Doug!
My day is just getting better and better!
I didn't really expect many responses during JavaOne.
David Yazel
-----Original Message-----
From: Doug Twilleager [mailto:[EMAIL PROTECTED]]
Sent: Tuesday, June 05, 2001 2:14 PM
To: [EMAIL PROTECTED]
Subject: Re: [JAVA3D] Self-calculating bounds idea
Non-visible geometry is still pickable. It also does not get sent
to the state sorting structure so there is no cost there. Letting
the Java 3D spacial structure handle these objects should work
pretty well. But, as usual, it depends upon the performance and
flexibility needs of the application. In this case, I don't see
any problems.
Doug Twilleager
Java 3D Team
Sun Microsystems
>Delivered-To: [EMAIL PROTECTED]
>MIME-Version: 1.0
>Subject: Re: [JAVA3D] Self-calculating bounds idea
>To: [EMAIL PROTECTED]
>
>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".
===========================================================================
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".
