Hi Kelvin & Doug (& all you other fine Sun Engineers);
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)
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?
* 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?
* 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.
* 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?). 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.
* 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.
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
===========================================================================
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".
