Hi Karen,
>
>Let me start out by apologizing for probably being the cause of the barrage
>of email you guys have had to deal with over the past couple of days.
>Lesson learned! I will VERY carefully word my emails from this point on.
>Let me say that I'm impressed with how fast you guys get back to people with
>prompt, helpful and courteous responses.
>
>I almost hate to ask the next question, but I must. Part of my problem is
>that I come from the world of Robot Graphical Simulation, Collision
>Detection / Distance calculation and Path planning. I know next to nothing
>about games programming. Furthermore, I am not yet familiar enough with
>the Java 3D API to understand the language most of the people on the J3d.org
>mailing list are using. This is due to the fact that I'm evaluating which
>platform I should use. I can't justify spending too much time learning API
>details. I just need to know how the algorithm used in Java3D compares with
>the existing collision detection / distance calculation algorithms out
>there. (i.e. the basic approach it takes).
>
>Some I'm aware of are:
>
>V-Collide ( Lin, Manocha & others)
>I-Collide (Cohen, Lin, Manocha, & Ponamgi)
>Q-Collide (Kelvin Chung (is this you Kelvin?), Wang)
Yes, this is my research 4 1/2 years ago.
http://www.cs.hku.hk/~tlchung/research.html
>OBB-Tree (Lin, Manocha)
>QuickCD (Klosowski)
>KDS (Basch, Erickson, Guibas, Hershberger & Zhang)
>
>There are a host of others I won't mention.
>
>We've implemented V-Collide in a small C++ / OpenGL simulator & it seems to
>work well for a 7-DOF Canadian Space Agency Robot we built (although, I
>admit, we didn't extensively use or test it).
>
>We have extensively used a higher-end commercial simulator library called
>ACT (by Alma, www.alma.fr) based on OpenGL which has excellent distance
>computation (& as a result collision detection, prediction, and path
>planning) capabilities. I used to have a paper written by one of the
>developers (Bernard Faverjon), but I have since misplaced it. This approach
>included hierarchical bounding boxes & I've (since losing the paper)
>forgotten the finer details. The algorithm computes the shortest distance
>between a given programmer-selected entity and any other object in the
>environment. I also implemented directed distance computations in ACT for
>a programmer-selected object and any other object in the environment. We
>used the directed distance computations for real-time on-line distance
>sensor simulation (i.e. we used the simulator on-line to generate simulated
>sensor info as input to our robot controller). The reason I'm mentioning
>all this junk is that if I had some means of comparing what Java 3D's
>approach is closest to, I'd have a pretty good idea of its capablities w.r.t
>my type of application. By the way, if I'd have my "druthers", I'd prefer
>to have an algorithm that actually returns the shortest and/or directed
>distance between a programmer-selected object and of the other objects in
>the environment, than an algorithm that simply returns any or all collisions
>in the environment. Having said this, I know the problem is VERY
>non-trivial.
>
>Now, if you're not too bored to continue, let me explain where I'm unclear
>about what your algorithm does. Doug, you mentioned that the following
>about Java 3D's algorithm.
>
>"we currently use a spacially organized tree structure for all of our
>geometric operations. So, a collision test is fairly quick, although it
>depends upon how well the tree is balanced, how many objects are moving, how
>many collision "triggers" are pending, etc..."
>
>* Is the tree you are referring to the scene graph with it's bounding
>box info? Kelvin mentioned a hierarchical tree. Do you simply peruse the
>scene graph or create another hierarchical tree?
We parse the scene graph Shape3D and create another axis-align
Bounding box tree for use in picking, collision and culling.
>* Do you compute distances between bounding entities in order to
>determine which entities in the tree to check for collision? If so, what
>type of bounding entities are computed by the software (e.g. box, sphere,
>convex hull). w.r.t. boxes, are they are aligned in a way that minimizes
>their size and increases the accuracy of reporting collisions?
No, we did not take advantage of time coherance between frames and
store the distance between bounding entities.
>* At a given time, are collision checks performed for all moveable
>objects or do you perform some form of optimization that allows you to
>ignore moveable objects that are far away from all other objects.
Collision is performed when WakeupOnCollisionXXX() is used. The
target (usually Shape3D) specify is query against the bounding box
tree every frame using its bounds. If the bounds of target did
intersect some other bounds in the bounding box tree. Collision
is return for USE_BOUNDS. Otherwise, for USE_GEOMETRY, current
implemetation do a brute force O(n^2) check for each triangle.
So the first pass is pretty quick but the second pass is very
slow.
>* Do you use optimized collision checks for complex polyhedric surface
>objects (e.g. if I have two polyhedra each consisting of 2000 polygons, is
>the collision check between them optimized in any way?).
We optimize for many object in a scene graph and for USE_BOUNDS cases
but not complex polydera (for USE_GEOMETRY)
> I believe I got an
>email regarding this saying that you could specify USE_BOUNDS (i.e. I'm
>presuming bounding boxes), or USE_GEOMETRY. In the USE_GEOMETRY case, a
>brute force method would be used. USE_BOUNDS would be OK for cases where
>collision is not immanent, but USE_GEOMETRY would eventually become
>necessary in order to report the collision accuratly. I guess this means
>that if I have a very complex polyhedric surface, I'll have to split it up
>into multiple Shape3D nodes at creation time. Do you have any utilities to
>do this? I suppose if one can determine the correspondence between how the
>individual polygons are stored in memory vs. where they are physically
>located one could do this.
I don't think we have this utility.
>* Is Java 3D's collision checking similar to that implemented in
>Q-Collide? (assuming that Kelvin is the Kelvin Chung behing Q-Collide). If
>so, how, does it compare to V-Collide's approach.
No, the algorithm in Q-Collide (which works for convex shape only)
did not implement in Java3D.
V-Collide build an OBB-Tree for the complex polyhedra model, thus
it can support Concave shape.
Q-Collide did not build any hierachical tree for the complex
polyhedra model. Thus use less memory and startup time.
It makes use of both time and space coherance
for Convex model to quickly eliminate non-interface object
in expected constant time. But it can't deal with Concave shape.
To handle concave shape, we can found the convex hull of
it and employ this algorithm as additonal layer to
report non intersect object before another algorithm
like OBB tree is used for concave object.
>
>There may be some questions I haven't asked due to lack of understanding
>what your approach is. I'd appreciate a brief algorithm description.
>
>That'll be all for now,
>
>Cheers,
>
>Karen Dias, ISE
>
>
Thanks.
- Kelvin
------------------
Java 3D Team
Sun Microsystems Inc.
===========================================================================
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".
