Few questions
Oleh Derevenko
Oleh Derevenko
-- Yahoo ID: oleh_derevenko
-- ICQ: 36361783
Rodrigo Hernandez
>
> 1) What is the status of OPCODE and GIMPACT? Are not those external
> libraries developed independently which are merged from time to time
> to ODE? Can we commit changes in OPCODE and GIMPACT subfolders?
>
available, and there is no substitute project for OPCODE, it should be
ok to commit changes to OPCODE as
the changes won't likely be overwritten by a new version of the OPCODE
library.
GIMPACT is still under separate, independent development, so if you find
bugs in it and they have not been corrected by the official GIMPACT
maintainer, report them to them (him?).
The GIMPACT source is already old inside ODE, I believe it was
originally integrated by GIMPACT's author, we don't really have anyone
in charge of keeping these things current,
so unless someone volunteers to do it, we'll probably have to wait until
the original merger updates the code.
> 2) What is the definition of contact point and what sense should it
> carry? If objects just touch then OK, I can understand it: it is
> natural to generate a single point for one-point contact and
> three-four points shaped as some triangle or tetragon in case of area
> contact. However if objects penetrate, espacially in case of
> corner-corner or corner-edge penetration the direction of exit from
> penetration is undefined and there can't be any rule how the contact
> points should be chosen. What are the guidelines for contact point
> generation in collision checking functions in such cases?
> Well, I understand that physical simulations should not allow deep
> penetration and the problem becomes determinate as penetration depth
> decreases to zero. However it is still unclear what is the correct
> criterion for collision checking function for contact points
> generation if deep penetration is the case.
>
In ODE collision is detected once objects already penetrate, a contact
point is a point, a normal and a penetration magnitude, the point is a
3d location on the first object surface,
the normal is the direction in which the second (IIRC) object must be
moved in order to reduce penetration depth to zero and the penetration
magnitude is the amount the object
must be moved.
Spheres can do with only one contact point due to their nature, but for
boxes you need at least 3 to avoid wobbling as the contact point moves
from one place to another when you
have a face-face contact between 2 polyhedrons.
Setting a small time step (or rather a correct one for the dimensions of
your physical objects) is what keeps inter object penetration depth low.
Cheers!
Oleh Derevenko
>> libraries developed independently which are merged from time to time
>> to ODE? Can we commit changes in OPCODE and GIMPACT subfolders?
>>
> OPCODE is dead outside ODE, no new versions will probably ever be
>
> GIMPACT is still under separate, independent development, so if you find
> bugs in it and they have not been corrected by the official GIMPACT
> maintainer, report them to them (him?).
>> carry?
> point is a point, a normal and a penetration magnitude, the point is a
> 3d location on the first object surface,
> the normal is the direction in which the second (IIRC) object must be
> moved in order to reduce penetration depth to zero and the penetration
> magnitude is the amount the object must be moved.
Oleh Derevenko
-- ICQ: 36361783
Pierre Terdiman
> available, and there is no substitute project for OPCODE, it should be
> ok to commit changes to OPCODE as
> the changes won't likely be overwritten by a new version of the OPCODE
> library.
OPCODE was suspended while I was working at Novodex/Ageia, for obvious
reasons. But I'm not working there anymore. So I wouldn't rule out a new
version at some point.
- Pierre
Jon Watte
> 1) What is the status of OPCODE and GIMPACT? Are not those external
> libraries developed independently which are merged from time to time
> to ODE? Can we commit changes in OPCODE and GIMPACT subfolders?
OPCODE was abandoned a long time ago, as I wrote on this list last week.
The only living repository of OPCODE is within the ODE code base.
GIMPACT, I have less knowledge about.
>
> 2) What is the definition of contact point and what sense should it
> carry?
That's described pretty well in the manual. The main thing to understand
is that when calling dCollide(a,b), you will get contact points on the
surface of object b, and moving object a along the normal by the
penetration depth will resolve that penetration so the objects are
merely touching (zero depth).
Cheers,
/ h+
Jon Watte
> > the normal is the direction in which the second (IIRC) object must be
> > moved in order to reduce penetration depth to zero and the penetration
> > magnitude is the amount the object must be moved.
> This is a wrong approach as to my opinion. I thought about it last
> night and I had come to a conclusion that if a corner penetrates a
> surface, the force should be applied to it tangentially in direction
> to decrease angles between faces and align them.
You DO understand that ODE was written by a guy who had already done
many years of physics engines when he wrote it (10 years ago), right?
And that it's based on a few very successful and influential research
papers? If you think the constraint formulation is "wrong," then I
suggest you show the math for how your formulation would increase
stability of the system. (physical simulation is about getting as stable
as possible, with as little effort as possible)
> It seems to me that single but correctly chosen contact point for a
penetration should always be enough.
In effect, that's what taking the multiple contact points and running
them through a global solver is all about. Out of the global solver
comes the torques and forces that would be "optimal" as if there was one
"optimal" contact point. Unfortunately, there exists no closed form
solution to the problem, so given just a concave object pair, there's no
way of finding "the" single contact point. It gets even murkier when you
want to consider the resting case. Consider a cube resting on a plane --
you need at least three contacts to make the balance out correctly,
unless you can find the EXACTLY best point -- which is, again,
impossible in closed form when more than a single object pair interacts.
I think it's great that you're trying to learn about physical simulation
-- that's what I'm doing, too. However, most of your early learning
steps seem to be presented as "hey, THIS is all wrong, an MY WAY is
obviously much better..." which is probably the wrong way to go about it.
Cheers,
/ h+
Jon Watte
> OPCODE was suspended while I was working at Novodex/Ageia, for obvious
> reasons. But I'm not working there anymore. So I wouldn't rule out a new
> version at some point.
>
That's great news! There have been patches in the ODE version in the
meanwhile, so hopefully you'll be able to integrate those.
Cheers,
/ h+
Oleh Derevenko
From: "Jon Watte" <jwa...@gmail.com>
>
> You DO understand that ODE was written by a guy who had already done
> many years of physics engines when he wrote it (10 years ago), right?
> And that it's based on a few very successful and influential research
> papers? If you think the constraint formulation is "wrong," then I
> suggest you show the math for how your formulation would increase
> stability of the system. (physical simulation is about getting as stable
> as possible, with as little effort as possible)
>
> -- that's what I'm doing, too. However, most of your early learning
> steps seem to be presented as "hey, THIS is all wrong, an MY WAY is
> obviously much better..." which is probably the wrong way to go about it.
Well, I expected that answer. ;)
Yes, I understand everything. I'm sticking into the code that has been
working for years and starting to claim that it can't work. That looks silly
indeed.
Why does it work? If you use small step and do not allow deep penetration,
the exit direction does not matter very much. You just can choose any more
or less good direction and it will not affect the outcome of simulation. But
this is very slipepry situation. If the penetration gets deep you do not
have any choice. The exit direction can't be determined from geometry itself
as it depends on current velocity, acceleration and torques of the body. You
just can't say what direction the penetration should be compensated in
because you do not use enough input data for calculation. And the worst
thing is that you even can't return any error or fail an assertion check
because there is no criterion to say when penetration is deep and when it is
not deep enough yet. Because of this, the algorithm can't be considered
reliable. And even though chosing direction does not matter too much for
small penetrations and simulation seems to be working that's not a
scientific approach. That's alchemy or astrology.
If I want to implement my own cube-to-cube collision check (as it does not
seem very realistic to hope anybody could fix bugs in current
implementation), what exit direction should I chose and how many contact
points should I generate if I, for example, determine that the cubes
intersect like this ([-1;1]X[-1;1]X[-1;1] and [0;2]X[0;2]X[0;2], "X"
standing for Cartesian product)? The direction of reaction force depends on
which side cubes came from and what are their accelerations. And collision
checking function does not use that information.
Jon Watte
>
> If I want to implement my own cube-to-cube collision check (as it does not
> seem very realistic to hope anybody could fix bugs in current
> implementation), what exit direction should I chose and how many contact
> points should I generate if I, for example, determine that the cubes
> intersect like this ([-1;1]X[-1;1]X[-1;1] and [0;2]X[0;2]X[0;2], "X"
> standing for Cartesian product)? The direction of reaction force depends on
> which side cubes came from and what are their accelerations. And collision
> checking function does not use that information.
>
As I said, you should ideally return contact points along each
separating axis. If there is one separating axis that is obviously
shorter than the others, then returning only that will likely help with
penetration resolution, but not with stability in the resting case.
In general, you should/could test each feature (face, edge and vertex)
and return the shortest separating axis for each of the features that
intersect. That will usually result in good resting stability, while not
returning penetrations that are too deep or contra-effective.
Cheers,
/ h+
Oleh Derevenko
From: "Jon Watte" <jwa...@gmail.com>
Could you please explain in different words what is "separating axis"? I do
not understand that in English.
Jon Watte
> not deep enough yet. Because of this, the algorithm can't be considered
> reliable. And even though chosing direction does not matter too much for
> small penetrations and simulation seems to be working that's not a
> scientific approach. That's alchemy or astrology.
>
>
Are you saying: IF the intersection happens to be PERFECTLY symmetrical
along all three axes, then picking one of the three possible separating
axes is not a robust solution? It turns out that, for game physics
simulation, I think so. The vector could actually be off by a quanta
less than that representable by the least significant bit in the
floating point mantissa, and that divergence would cause it to shift in
one way or another. We might as well say that such quantum differences
always bias in a given direction. The chance that that will actually
happen in real life is 1 in every (1<<48) random intersections. For
games programming (which is the explicit target for ODE), the chances of
that mattering are nil, especially given that picking one of the
directions in a well-formed manner is actually consistent across both
machines and invocations -- you can even assert on it; it's a
well-defined rule.
> If I want to implement my own cube-to-cube collision check (as it does not
> seem very realistic to hope anybody could fix bugs in current
> implementation), what exit direction should I chose and how many contact
>
If there are bugs in the box/box code that bother you, and nobody else
is fixing them, wouldn't it be easier to fix them yourself rather than
writing one from scratch?
Anyway, if you have mutliple, equivalently good, points/depths/normals,
then one option is to return them all, and let the integrator average
them out for you. Another option is to average them yourself before you
return them. You might want to try it both ways, and see which one ends
up with the most stable results. The typical physics engine test program
is to build a pyramid of boxes, and see how tall you can make it before
internal imprecision and instability tears it apart.
Cheers,
/ h+
Jon Watte
>
> Could you please explain in different words what is "separating axis"? I do
> not understand that in English.
>
One of the basic principles of collision detection:
http://en.wikipedia.org/wiki/Separating_axis_theorem
Cheers,
/ h+
Pierre Terdiman
> the exit direction does not matter very much. You just can choose any more
> or less good direction and it will not affect the outcome of simulation.
It depends how you use the "exit direction", i.e. it depends on your contact
generation code (which might be shape specific). If this exit direction is
used to select, say contact polygons in a convex-vs-convex collision
routine, then the direction matters a lot. It is a bad idea to make
experiments on the box-vs-box case and extend the conclusions to
convex-vs-convex or more involved cases. What works for box-vs-box often
fails in those more advanced cases.
> The exit direction can't be determined from geometry itself
Yes it can. It's typically called the "MTD" = "Minimum Translation
Distance". Purely a geometrical thing.
> as it depends on current velocity, acceleration and torques of the body.
...but typical physics engines don't bother and just use the geometry. ODE
does that. Novodex/AGEIA does that. Etc.
>That's alchemy or astrology.
That's a good summary of rigid body simulation for games, really...
- Pierre
Oleh Derevenko
From: "Jon Watte"
> Oleh Derevenko wrote:
>> not deep enough yet. Because of this, the algorithm can't be considered
>> reliable. And even though chosing direction does not matter too much for
>> small penetrations and simulation seems to be working that's not a
>> scientific approach. That's alchemy or astrology.
>>
> Are you saying: IF the intersection happens to be PERFECTLY symmetrical
> along all three axes, then picking one of the three possible separating
> axes is not a robust solution?
It could be robust solution but it could be incorrect solution. Do you
remember my cube intersection [-1; 1] with [0; 2]? The way the cubes should
go further depends on where they came from. If upper cube came from positive
Z direction if should continue motion to Z-, X+, Y+. If it came from
Positive X direction it should continue to Z+, X-, Y+. You do not know in
what direction the object is to be shifted to be moved out of collision. It
is incorrect to just randomly chose any direction.
And this problem is not regarding to perfect symmetrical case only. Any
penetration compensation needs knowledge of where the objects came from. It
is not necessarily that the shortest way out is the correct way out.
>
>> If I want to implement my own cube-to-cube collision check (as it does
>> not
>> seem very realistic to hope anybody could fix bugs in current
>> implementation), what exit direction should I chose and how many contact
>>
>
> If there are bugs in the box/box code that bother you, and nobody else
> is fixing them, wouldn't it be easier to fix them yourself rather than
> writing one from scratch?
>
Can you understand anything in that code? I can't.
Oleh Derevenko
--ICQ: 36361783
Oleh Derevenko
From: "Jon Watte"
> As I said, you should ideally return contact points along each
> separating axis. If there is one separating axis that is obviously
> shorter than the others, then returning only that will likely help with
> penetration resolution, but not with stability in the resting case.
>
> In general, you should/could test each feature (face, edge and vertex)
> and return the shortest separating axis for each of the features that
> intersect. That will usually result in good resting stability, while not
> returning penetrations that are too deep or contra-effective.
>> Could you please explain in different words what is "separating axis"? I
>> do
>> not understand that in English.
>>
>
> One of the basic principles of collision detection:
>
> http://en.wikipedia.org/wiki/Separating_axis_theorem
OK. If I understand that article correctly, in 3D separating axis should be
called spearating plane.
What is meant by "return contact points along each separating axis"? Where
along it? How many of them? How to decide?
Also "you should/could test each feature (face, edge and vertex) and return
the shortest separating axis for each of the features that intersect". There
are 8 vertice, 12 edges and 6 faces. If we multiply all that we could get
rather big number of combinations. Do you mean I need to find the shortest
distance to exit among all the combinations (even between the features of
the different kinds)?
What is meant "shortest separating axis for each of the features"? Should I
select three shortest separating axes for vertice, edges and faces
independently? What's the logic? That looks like alchemy indeed.
Jon Watte
> It could be robust solution but it could be incorrect solution. Do you
> remember my cube intersection [-1; 1] with [0; 2]? The way the cubes should
> go further depends on where they came from. If upper cube came from positive
>
> And this problem is not regarding to perfect symmetrical case only. Any
> penetration compensation needs knowledge of where the objects came from. It
> is not necessarily that the shortest way out is the correct way out.
>
No game simulation library currently in use uses the velocity/direction
of the geometry when calculating intersections. The loop, as used by
Havok, PhysX, ODE, and all the others, is:
1. detect penetrations, which generates contact joints
2. calculate joint constraints
3. solve a large joint constraint system as a Linear Constraint Problem
4. integrate
The different systems may give different names to the concepts, but they
are all the same at the math level.
An older approach is to detect when the (moving) geometries first come
in contact, and not allow penetration at all, by stopping movement.
Thus, you will at all times assume non-penetrating objects. This has
problems with resting stability, though.
Now, the main direction that's coming out is "continuous collision
detection," where you attempt to keep objects out of penetration using
spiffier math. The library "Bullet" is implementing this method. If you
don't like the basic design approach of ODE, perhaps you should try that
library instead and see if it works better for your tastes.
>> If there are bugs in the box/box code that bother you, and nobody else
>> is fixing them, wouldn't it be easier to fix them yourself rather than
>> writing one from scratch?
>>
>>
> Can you understand anything in that code? I can't.
>
Yes, it looks like reasonable geometric code, similar to any other
box/box collision code. It's expressed in the "language" of the ODE
internals, which use macros rather than classes, but that's usually not
hard to see through. You can compare to the box/box code from "Real Time
Collision Detection" (Ericsson's book) or from www.geometrictools.com if
you want some reference points.
Cheers,
/ h+
Jon Watte
> OK. If I understand that article correctly, in 3D separating axis should be
> called spearating plane.
> What is meant by "return contact points along each separating axis"? Where
> along it? How many of them? How to decide?
>
>
No, that article was vague. I actually cleaned it up a little. The
separating AXIS is the dual of the plane. What the article called
separating axis in 2D is the separating line. The AXIS is the axis
which, when the objects are projected onto that axis, shows the objects
being separate. If there is no separating axis, then the penetration is
along the shallowest separating axis, and the penetration distance is
the length of the overlap on that axis. The contact normal is parallel
to that axis. Exactly where the contact point is, depends on the shapes.
If you start out with the baisc tenet that a body resting on another
under gravity should be stable, and the rules for contacts (which body
the point is on, what depth and normal means) then you can calculate it
for each case. There may be more than one correct solution for a given pair.
> Also "you should/could test each feature (face, edge and vertex) and return
> the shortest separating axis for each of the features that intersect". There
> are 8 vertice, 12 edges and 6 faces. If we multiply all that we could get
> rather big number of combinations. Do you mean I need to find the shortest
>
That's right! For boxes, the points typically don't matter, as long as
you correctly merge multiple coincident edge contacts. Also, the edges
mostly matter for where the contact points are; the actual directions
(for separating axes) are only 3 for each, plus the 3x3 for the
combinations, for a total of 15 directions to test.
> distance to exit among all the combinations (even between the features of
> the different kinds)?
> What is meant "shortest separating axis for each of the features"? Should I
> select three shortest separating axes for vertice, edges and faces
> independently? What's the logic? That looks like alchemy indeed.
>
Game physics simulation is imprecise. The trick is to choose rules that,
built upon the basic assumptions of the system (time-stepped,
penetration-based, matrix solver, etc), generates simulations that are
useful, which in turn means that they are stable, fast and realistic.
You can view this as the difference between engineering and science.
Physical simulation is very much an engineering discipline. You choose
an approximation that gives useful results within known limitations, and
you use it for those useful results within those known limitations.
Cheers,
/ h+
Oleh Derevenko
From: "Jon Watte"
>> Can you understand anything in that code? I can't.
>>
>
> Yes, it looks like reasonable geometric code, similar to any other
> box/box collision code.
So, can yo confirm if that point in my picture I sent here recently could be
a correct contact point? Well, I can suppose it is on separation axis but it
does not belong to any of cubes. Could contact points be generated outside
the penetration area? Maybe that's just a bad name and the whole confusion
comes from the fact that contact points should be called "separation
points"?