Details on collision detection
d.carbonaro
where can I find more information about the collision detection module
of ODE?
I know that ODE uses Axis Aligned Bounding Box but I need more for
exemple about the different spaces (Simple Space or Hash Space)..
The is ODE manual the only way?
Thanks
Daniele
d.carbonaro
Is an exact analytic collision detection implemeted between primitives
(spheres,boxes etc. )?
Does ODE apply the AABB check recursively,or?
Thanks
Daniele
Jon Watte
> Is an exact analytic collision detection implemeted between primitives
> (spheres,boxes etc. )?
> Does ODE apply the AABB check recursively,or?
>
ODE is a penetration based solver, not a swept penetration avoiding solver.
So, no, and no.
Sincerely,
jw
d.carbonaro
Can you give me some links where I can read more?
Daniele
Progger
source code of ode is the best source you can get information from I
suppose.
If not, so use the manual:
http://opende.sourceforge.net/mediawiki-1.6.10/index.php/Manual_%28Concepts%29#Collision_handling
http://opende.sourceforge.net/mediawiki-1.6.10/index.php/Manual_%28Collision_Detection%29
d.carbonaro
That's not clear on the manual..
Another question is: Does ODE use OPCODE in the default setting?
On Mar 25, 12:53 pm, Progger <a.schre...@gmx.net> wrote:
> Do you intend to create your own collision detection mudule? If so the
> source code of ode is the best source you can get information from I
> suppose.
Daniel K. O.
> Can you give me some links where I can read more?
I believe all information you can get without reading the source code is
in the manual. Here's an overal sumary of what you'll find after reading
a bit of code:
For broad-phase collision detection there are 3 (now 4) data structures,
that determine potential intersections between geoms' AABBs:
dSimpleSpace, dQuadTreeSpace, dHashSpace (and now dSAPSpace).
The dSimpleSpace structure is just a list that tests all O(n^2) pairs of
geoms for intersections, and is very fast for a small number of geoms.
The dQuadTreeSpace, as the name suggests, places the geoms into a
QuadTree. Geoms are placed in the smallest tree cell that contains the
geom's AABB. For every populated cell, collision is detected by testing
all cell geoms against each other (O(n^2)) and against geoms in the
parent cell. Thus it's more efficient when geoms are more evenly
distributed, and not clumped together.
The dHashSpace structure is a hash table for AABBs. Depending on the
AABB size, it is "decomposed" into smaller "pieces", each inserted
separately in the hash table. The collision detection is done by
iterating through the "pieces", and performing queries on the hash
table. (The quoted words I used probably are not standard nomenclature
on hash spaces, it's what I came up to describe from what I know about
the source code.)
The dSAPSpace structure is based on the Sweep And Prune algorithm.
Terdiman wrote a good article about this, so I won't try to describe it:
http://www.codercorner.com/blog/?p=11
After the broad-phase collision detection, collideAABBs() (see
collision_space_internal.h) is called for the geoms, where category bits
are tested, then comes a standard AABB test, and an extra (optional)
geom-specific AABB test is done (useful for non-convex shapes, like
trimeshes). After that, the user-provided dNearCallback is invoked, and
if the user calls dCollide(), comes the expensive narrow-phase collision
detection.
Which in ODE is done with specialized code for each pair of geom types;
there's a big matrix, indexed by the geom type, that stores function
pointers. This is hard to maintain (almost half of ODE code is for
collision detection); Bullet, for example, has a more elegant approach,
through the GJK algorithm. Adding a new geom to ODE requires writing
collision detection code for every geom that already exists; adding a
new geom to Bullet requires just a single support function (for the GJK
algorithm).
Triangle meshes are handled with specialized code (not only on ODE, but
on Bullet too); the triangles are usually stored in their own
specialized data structure, to figure out which triangles are
potentially colliding. By default ODE uses OPCODE for this (which is
known to be very fast).
About your question on analytic collision detection: ODE only detects
collisions after there's already penetration, as John said. After this
is detected, movement constraints are created between the bodies, and
the collision is "solved" by letting the LCP algorithm figure out to
solve the system with those constraints, trying to not let things get
"worse" (like letting the bodies penetrate further). "Solving" the
system means figuring out what the next velocities should be, for all
bodies; the velocities are then integrated (currently through a first
order method).
--
Daniel K. O.
"The only way to succeed is to build success yourself"
d.carbonaro
Thanks !!!
Daniele
Jon Watte
The Baraff paper is a good start. Also, the ODE documentation PDF file
(found on www.ode.org) is a good start.
Sincerely,
jw
Jon Watte
Daniel,
Can you put this in the FAQ? It'll probably help any n00b who comes
along and doesn't know how this kind of game physics system works. I
think it's a great summary!
Sincerely,
jw
Daniel K. O.
> Daniel,
>
> Can you put this in the FAQ? It'll probably help any n00b who comes
> along and doesn't know how this kind of game physics system works. I
> think it's a great summary!
I put the text on the wiki:
http://opende.sourceforge.net/mediawiki-1.6.10/index.php/How_Collision_Detection_Works
It's currently linked from the Heap page. I don't know where in the FAQ
I should put it.