GIMPACT problems

[Tilmann]

I've been looking at the gimpact problems, e.g. seen when running
demo_heightfield and dropping a mesh (press 'm').
I think I made some progress regarding the problem that the mesh sinks
into the ground (plane) after bouncing off the heightfield.

So the interesting workaround I found is:
Change the method recomputeAABB() in collicion_kernel.h to stop
checking the gflags.

void recomputeAABB() {
// if (gflags & GEOM_AABB_BAD) {
// our aabb functions assume final_posr is up to date
recomputePosr();
computeAABB();
gflags &= ~GEOM_AABB_BAD;
// }
}

The result problem (when waiting for gflags to become bad) is that the
AABB used in GIMPACT is not updated never collides with the plane
(checked in gim_trimesh_plane_collision(..) ). Actually, it does
collide, but only much later after it sunk in deeply. I'm not sure why
so much later it decides to finally update the AABB. Does it maybe
wait until it leaves the AABB of the heightfield?

I also found that dGeomMoved() (collision_space.cpp) is never called
on the TriMesh after creation. It is only repeatedly called for the
Ray used by the heightfield collider.

The workaround is obviously not a good solution, and I have no idea
why dGeomMoved() is never called (or is that intended?).
I'm a bit stuck now, could maybe someone shed some light on this? Any
suggestions?

Many thanks,
Tilmann

=============
www.ode4j.org
=============

[Daniel K. O.]

Tilmann escreveu:

> I also found that dGeomMoved() (collision_space.cpp) is never called
> on the TriMesh after creation. It is only repeatedly called for the
> Ray used by the heightfield collider.

dGeomMoved() is called unconditionally for *every* geom attached to a
body (see util.cpp). If you are sure it's not being called for the
trimesh (which I assume is attached to a body) then the only explanation
is a memory corruption coming from somewhere else. You might have to
fire up a debugger and/or a memory analyzer like valgrind, see if there
are any invalid memory accesses. It's probably in the gimpact-specific
code, as opcode seems to not be affected.

--
Daniel K. O.
"The only way to succeed is to build success yourself"

[Tilmann Zäschke]

Thanks for the suggestion.

But I don't think that is the case, because the same problem occurs in
my Java port of ODE/GIMPACT, and I believe Java is largely immune
against memory corruption. Above that, the problem disappears (and
dGeomMoved() is called again) once the trimesh gets away from the
heightfield (this may be coincidence(?)).
I was more thinking that the heigthfield collider may substitute the
trimesh-geom with the ray-geom that it creates for collision, for
performance reasons, could that be the case? I couldn't find any peace
of code that does that, however.

Tilmann

[Tilmann Zäschke]

I just got my first bounce from the tose guy:

tose....@gmail.com

Cheers,
Tilmann

[Tilmann Zäschke]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Okay, it seems I made a mistake regarding dGeomMoved(), it is indeed
called. I also checked that a body is attached.

That leaves the curios behaviour that the problem is fixed when
recalculating the AABB even if the objects is not 'bad'.
Any ideas?

Thanks,
Tilmann

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iEYEARECAAYFAktYnOoACgkQ6CnElG/gOPd0uQCgwdUBLjn4YKm4VUDKCFK1QtlF
PwEAoNBACASfnvuAmbnngaU0dzFvKqxS
=PUj0
-----END PGP SIGNATURE-----

[Daniel K. O.]

2010/1/21 Tilmann Zäschke <zaes...@gmx.de>:

> Okay, it seems I made a mistake regarding dGeomMoved(), it is indeed
> called. I also checked that a body is attached.
>
> That leaves the curios behaviour that the problem is fixed when
> recalculating the AABB even if the objects is not 'bad'.
> Any ideas?

Well, then I don't know what your test case is. I was testing on the
heightfield demo; just forcing the AABB recomputation isn't enough to
keep GIMPACT trimesh from falling through. Additionally, the
heightfield code does some changes directly on the geom's transforms,
so that's a bit suspicious too. Are you sure the AABB is problematic
when the collision fails? The OPCODE's AABBs are not as tight, maybe
it suffers from the same problem depending on the dimensions involved.

[Tilmann Zäschke]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks for looking into this :-)

I just check it again, my test case is demo_heightfield in ode 0.11.1,
using GIMPACT (--with-trimes=gimpact). I tried both DOUBLE and SINGLE,
no other options.
I'm on Linux 64bit, using gcc 4.3.2, if that matters.

Just to avoid misunderstandings, the bunny will think partly through
the heightfield (it doesn't do that in my Java port, so I don't mind).
I'm interested in the part once it bounced of the heightfield and hits
the Plane.

Normally the Bunny topples over, sinks almost completely into the plane,
then resurfaces and stabilizes.
Removing the 'if' statement in recomputeAABB() prevents it from sinking
(visibly) into the plane. It still stabilizes in a somewhat unrealistic
position though.

Otherwise the code is not modified.

If you can't see it, let me know whether you a different platform.
Maybe it's a 32/64bit issue???

Cheers,
Tilmann

Daniel K. O. wrote:
> 2010/1/21 Tilmann Z�schke <zaes...@gmx.de>:

>> Okay, it seems I made a mistake regarding dGeomMoved(), it is indeed
>> called. I also checked that a body is attached.
>>
>> That leaves the curios behaviour that the problem is fixed when
>> recalculating the AABB even if the objects is not 'bad'.
>> Any ideas?
>
> Well, then I don't know what your test case is. I was testing on the
> heightfield demo; just forcing the AABB recomputation isn't enough to
> keep GIMPACT trimesh from falling through. Additionally, the
> heightfield code does some changes directly on the geom's transforms,
> so that's a bit suspicious too. Are you sure the AABB is problematic
> when the collision fails? The OPCODE's AABBs are not as tight, maybe
> it suffers from the same problem depending on the dimensions involved.
>
>

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iEYEARECAAYFAktY2ecACgkQ6CnElG/gOPdUeQCgpaWSNSemDHY8OvzB1wjYvpmH
qvsAoJ03swSj/wnSj/xNEYQJAkx2qZ62
=+/rn
-----END PGP SIGNATURE-----

[Tilmann Zäschke]

I believe I found the problem.
I'm now using the latest from SVN (not that it made a difference to me),
I'm still on 64bit, double-precision and GIMPACT.

Just as a reminder, the fix does not prevent the bunny (press 'm' in
demo_heightfield) from going through the heightfield. But it prevents
the Bunny from submerging into the ground after it bounced off the
heightfield.

A simple fix (not very performant and somewhat dirty) is to insert the
following three lines into heightfield.cpp (lines 1817-1819, latest from
SVN):

#if dTRIMESH_GIMPACT
o2->computeAABB();
#endif

Explanation:
The dCollideHeightfield(...) function changes pos,R,aabb and flags of
a colliding object to some temporary values. It then calls (line 1741)
the computeAABB() method.

// Rebuild AABB for O2
if (reComputeAABB)
o2->computeAABB();

In the lines above the proposed (dirty?) fix, it tries to revert the
temporary change and overwrites pos,R,aabb, and flags with backup values.

The problem in GIMPACT (I don't know about OPCODE) is, that
computeAABB() also changes the AABB stored internally in GIMPACT.
But the attempt to revert the changes only restores the AABB in the
Geom, not the one in GIMPACT. Hence GIMPACT uses the wrong AABB in the
next collision, until it is calculated again.

Some possible ways of fixing this are:
- backup the GIMPACT-AABB as well and restore it later.
- do not call computeAABB() in 1741, calculate the temporary in a
different way, e.g. by transforming the existing AABB with the same
matrix that would turn POS into the tempPOS and R into tempR (the
temporary values)
- call computeAABB() after restoring the values (but that may have
impact on performance)
- Possibly unreasonable effort: Avoid transforming 'o2' at all,
but transform the plane of the heightfield (see my question below).

Question: To be honest, I do not understand why the colliding objects
are moved around at all. Could someone shed some light on this and maybe
explain why this is done (e.g. instead of transforming the plane,
which is probably less effort)?

Also, shall I provide a patch?

Any comments are appreciated.
Thanks,
Tilmann

[Oleh Derevenko]

Hi,

For this "dirty" variant I doubt the patch file is necessary. If you decide
to make a complete "legal" fix, the patch would be appreciated of course.

Oleh Derevenko
-- Skype with underscore

[Tilmann Zäschke]

Oh, and obviously, a better version of the (dirty?) fix would look like
this, limiting the application to TriMesh classes:

#if dTRIMESH_GIMPACT
if (o2->type==dTriMeshClass)
o2->computeAABB();
#endif

Tilmann

[Daniel K. O.]

Tilmann Z�schke escreveu:

> I believe I found the problem.
> I'm now using the latest from SVN (not that it made a difference to me),
> I'm still on 64bit, double-precision and GIMPACT.

Ok, I can see it happening here too.

> The problem in GIMPACT (I don't know about OPCODE) is, that
> computeAABB() also changes the AABB stored internally in GIMPACT.
> But the attempt to revert the changes only restores the AABB in the
> Geom, not the one in GIMPACT. Hence GIMPACT uses the wrong AABB in the
> next collision, until it is calculated again.

It seems the heightfield code is at fault here. GIMPACT only receives
position and orientation updates during the AABB computation. As the
geom was "moved" for the collision test, it should make sure the geom is
"moved back" to the original position.

> Some possible ways of fixing this are:
> - backup the GIMPACT-AABB as well and restore it later.

The issue might not be GIMPACT-specific. Any external collision
detection library that you try to plug in might suffer from this.

> - do not call computeAABB() in 1741, calculate the temporary in a
> different way, e.g. by transforming the existing AABB with the same
> matrix that would turn POS into the tempPOS and R into tempR (the
> temporary values)

I think the proper fix here is that we should have an computeOBB() that
receives an arbitrary transform. By default it can return the AABB's
AABB, according with the new orientation, and the geoms would override it.

> Question: To be honest, I do not understand why the colliding objects
> are moved around at all. Could someone shed some light on this and maybe
> explain why this is done (e.g. instead of transforming the plane,
> which is probably less effort)?

If the heightfield has an arbitrary orientation, how can you figure out
which cells you should test? One simple way is to have the BB of the
geom aligned with the heightfield (so you can enumerate these cells with
2 nested loops). It's also possible to just project the AABB's to the
heightfield plane, but it requires more code, and is probably less
efficient.

[Tilmann Zäschke]

I had an idea, would it be that bad to use bounding-sphere instead of
bounding-boxes? At least for the purpose of colliding with heightfield.

I can see spheres are quite bad in approximating lengthy geoms. But
for other geoms (cylinders, pyramids,.. ) they are not much worse than
boxes, and for others (short capsules, spheres, rock-shaped
trimeshes,...) they probably fit even better than boxes.
They are probably hard to calculate for geoms like trimeshes, but the
real advantage would be that they would be invariant over the lifetime
of a geom, independent of it's rotation, only depending on the position.
So I could imagine in case of the heightfield collider, which does a lot
of AABB rotation, they might perform better than boxes?

In the meanwhile, I will have a look at implementing the computeOBB().

[Tilmann Zäschke]

I had a look, and I think using computeOBB() would not really work,
because the temporary transformed geoms are send to the different
plane-colliders, which need more than just a modified AABB, but the
completely
transformed geom.

How to make this work:

a)
Do initial checking with a temporary AABB (OBB) in
dCollideHeightfield(..), but then refactor
dxHeightfield::dCollideHeightfieldZone(...) to call the colliders with
the un-transformed geom and a transformed plane instead.

OR

b)
Alternatively, the refactor dCollideHeightfield(..) to use
dGeomSetPosition() and dGeomSetRotation() for the temporary
transformation, instead of directly accessing the variables. This is
somewhat expensive, but would make sure that the geom-objects know about
the updates.

I think a) would be a bit more work, but may result in faster code.

Any comments?

Cheers,
Tilmann

[Daniel K. O.]

2010/1/28 Tilmann Zäschke <tilma...@gmx.de>:

> b)
> Alternatively, the refactor dCollideHeightfield(..) to use
> dGeomSetPosition() and dGeomSetRotation() for the temporary
> transformation, instead of directly accessing the variables. This is
> somewhat expensive, but would make sure that the geom-objects know about
> the updates.

But these functions would also trigger space updates, which are locked
during the broad phase. A work-around is doable, but I believe a) is
the proper way to do it.

[Tilmann Zäschke]

Okay, I finally found time to start implementing the oriented BB for
heigthfield.

I have a question though, I noticed the following in heigthfield.cpp
1728-1729:

dMultiply1_331( pos1, terrain->final_posr->R, pos0 );
dMultiply1_333( R1, terrain->final_posr->R, o2->final_posr->R );

However dxGeom.computePosr() in collision_kernel.cpp (421-425) the pos
is calculated by also adding the bodies' position.

dMultiply0_331 (final_posr->pos,body->posr.R,offset_posr->pos);
final_posr->pos[0] += body->posr.pos[0];
final_posr->pos[1] += body->posr.pos[1];
final_posr->pos[2] += body->posr.pos[2];
dMultiply0_333 (final_posr->R,body->posr.R,offset_posr->R);

Excuse my ignorance, but could it be that one of the above is not
correct? Shouldn't the heigthfield consider the bodies position as well?

Cheers,
Tilmann

On 28/01/10 21:32, Daniel K. O. wrote:
> 2010/1/28 Tilmann Z�schke <tilma...@gmx.de>:

[Tilmann Zäschke]

Hi,

I have created a patch (ID 2963676):
https://sourceforge.net/tracker/?func=detail&aid=2963676&group_id=24884&atid=382801

For me it fixes the problem of the trimesh sinking into the ground after
bouncing off the heightfield.

It touches a number of files, mostly the heightfield collider, but also
many geometry classes for which it made sense to implement a dedicated
oriented bounding box function.

Please let me know what you think.

Best regards,
Tilmann

[Tilmann Zäschke]

Dear all,
a while ago I submitted a patch to fix the that GIMPACT trimeshes get
their AABB skewed while in the proximity of a heightfield (see attached
post).

The patch has not been accepted yet and has received some criticism,
mainly because it affects multiple files and the change to the
heightfield collider is significant, meaning that the patch may be
difficult to test. While the nature of the changes should only affect
the heightfield collider, I can see that thorough tests are not straight
forward.

So my questions are:
- are the any proposals for a simpler solution?
- is anyone willing to test the changes?
- what can be done to ensure that this (or another) patch gets accepted?

Thanks,
Tilmann

=============
www.ode4j.org
=============

--
You received this message because you are subscribed to the Google Groups "ode-users" group.
To post to this group, send email to ode-...@googlegroups.com.
To unsubscribe from this group, send email to ode-users+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ode-users?hl=en.

[Martijn Buijs]

Tilmann Zäschke wrote:
> Dear all,
> a while ago I submitted a patch to fix the that GIMPACT trimeshes get
> their AABB skewed while in the proximity of a heightfield (see attached
> post).
>
> The patch has not been accepted yet and has received some criticism,
> mainly because it affects multiple files and the change to the
> heightfield collider is significant, meaning that the patch may be
> difficult to test. While the nature of the changes should only affect
> the heightfield collider, I can see that thorough tests are not straight
> forward.
>
> So my questions are:
> - are the any proposals for a simpler solution?
> - is anyone willing to test the changes?
> - what can be done to ensure that this (or another) patch gets accepted?
>
> Thanks,
> Tilmann

I will look at this this week, and test in our game.

If I understand it right, did this bug cause the geom inside the heightfield AABB to have it's AABB
altered? If so, this could explain an old heightield bug that I and others were never able to fix.

I think it's this one:
http://sourceforge.net/tracker/?func=detail&aid=1662574&group_id=24884&atid=382799

Did this bug also affect geoms other than trimesh? Also, were you able to reproduce the same issue
with OPCODE trimesh?

/Martijn

[Tilmann Zäschke]

I think the bug you mention is not related to my bug.
I believe it only affects collision of an object that is inside the
heightfield's AABB with other objects _except_ the heightfield.
It also only affects objects that store spacial information other than
the fields defined in dxGeom (position, rotation and aabb).

For example, GIMPACT trimeshes are affected because they store a second
AABB inside their data structure.

Description of what is going on:
================================
The heightfield collider transforms any object in its AABB into the
coordinate system of each (not each, but all relevant) triangle, which
is represented by a horizontal plane. This simplifies AABB colission
checking with each triangle/plane.
To do this transformation, it sets position, rotation and AABB to
temporary values (storing the previous values in a backup variable).
Then it performs the collision. Then it restores position, rotation and
AABB from the backed up values. Finished.

The problem is that it only restores position, rotation and AABB, which
are stored in dxGeom. Any other variables (like the internal AABB in
GIMPACT) which may be updated during collision checking, are not restored.

My solution is to avoid setting and restoring internal values of each
geom, but instead add a method to each geom (and a generic method in
dxGeom) that returns a transformed AABB, which can be used for efficient
collision checking.

In the patch I describe an example where a GIMPACT-trimesh (bunny)
bounces off the heightfield and then sinks into the ground, because the
AABB is still skewed from the previous collision with the heightfield.
But as soon as the bunny-AABB leaves the heightfield AABB, the collision
works fine and the bunny pops to the surface of the ground plane (easy
to repeat in demo_heightfield, just press 'm' and wait).

Some rules:
a) This bug should affect any collision where at least one geom's AABB
intersects with the AABB of the height field.
b) It does not affect collision with the hieghtfield itself.
c) It does not affect geoms that use only the pos/R/AABB declared in dxGeom.


So far I only saw the problem with GIMPACT trimeshes, but it may also
arise with user geoms. I think most other geoms in ODE fall under rule c).

I should also mention that this bug does not address the faulty
collision between GIMPACT trimeshes and a heightfield (i.e. no collision
occurs).

I realized that I haven't submitted a formal bug, only a patch with a
bug-description. Should I also raise a bug report?


To test the bug, there is also a flag in heightfield.cpp (line 28),
which allows enabling and disabling the patch.

Cheers,
Tilmann

=============
www.ode4j.org
=============

> If I understand it right, did this bug cause the geom inside the
> heightfield AABB to have it's AABB altered? If so, this could explain an
> old heightield bug that I and others were never able to fix.
>
> I think it's this one:
>
http://sourceforge.net/tracker/?func=detail&aid=1662574&group_id=24884&atid=382799
>
>
> Did this bug also affect geoms other than trimesh? Also, were you able
> to reproduce the same issue with OPCODE trimesh?

[Martijn Buijs]

Ok, I have looked at this briefly only, because another bug interferes with my testing:

https://sourceforge.net/tracker/index.php?func=detail&aid=2214773&group_id=24884&atid=382799

Perhaps you have an idea where I look if I want to fix that one? Perhaps it is even tangentially
related. The symptoms are: missing contacts, contacts where there shouldn't be any, while some other
contacts are semi-accurate, but rare. Rays works fine, as does switching to OPCODE.

As for the patch, I'd have to agree with Oleh that the source of the problem lies in the
trimesh-heightfield collision code. I'm not convinced that a fix should touch the code of other
primitives, especially since there are no problem if there's no heightfield present in the simulation.

IMO dHeightfield needs a thorough re-write or should be removed altogether.

[Tilmann Zaeschke]

>
https://sourceforge.net/tracker/index.php?func=detail&aid=2214773&group_id=24884&atid=382799

Hmm, that doesn't ring a bell. Unfortunately, I'm not that familiar with
GIMPACT, so I would have to start debugging like anyone else.
But it's good to know. I'm rather busy at the moment with other things
(weeks or even months), but I need to look into GIMPACT anyway at some
point to solve some other problems I found in my Java port of GIMPACT.

Regarding the patch:
I agree with you that the fix should be done in the trimesh-heightfield
collision code.
Indeed, the patch touches the other primitives as well, but not as a fix
to existing code, it only adds a new function. The idea is that this new
function may have some general use. For example it would allow other
UserGeoms with their own AABB to work properly with heightfields. It
would also improve encapsulation, which I think is never a bad thing.

When we discussed the possible solution a while ago, I made another
proposal (somewhat dirty) that is much shorter and would look like this
(inserted in heigthfield.cpp 1817-1819):

#if dTRIMESH_GIMPACT
if (o2->type==dTriMeshClass) //I just made up this line, but I guess it should compile
o2->computeAABB();
#endif

This fix should work as well, but it would slow down GIMPACT users
(Gentoo/Ubuntu users? and every one that is not happy with the OPCODE
license),s because of the additional AABB calculation. Also it would not
take care of any future geoms that may have their own AABB stored.
This was basically the reason why we did not choose this solution when
we discussed it the last time (January, I believe).

But if the agreement now leans towards this short version, then so be it.
But In that case it would be nice to have the opinion of at least one
developer that actually uses GIMPACT (I understand you and Oleh are
using OPCODE?).
Are there any other opinions / ideas out there?

Thanks,
Tilmann

[Oleh Derevenko]

Hi

 

----- Original Message -----

From: "Tilmann Zaeschke"

When we discussed the possible solution a while ago, I made another
proposal (somewhat dirty) that is much shorter and would look like this
(inserted in heigthfield.cpp 1817-1819):

#if dTRIMESH_GIMPACT
if (o2->type==dTriMeshClass) //I just made up this line, but I guess it should compile
         o2->computeAABB();
#endif

This fix should work as well, but it would slow down GIMPACT users
(Gentoo/Ubuntu users? and every one that is not happy with the OPCODE
license),s because of the additional AABB calculation. Also it would not
take care of any future geoms that may have their own AABB stored.
This was basically the reason why we did not choose this solution when
we discussed it the last time (January, I believe).

But if the agreement now leans towards this short version, then so be it.
But In that case it would be nice to have the opinion of at least one
developer that actually uses GIMPACT (I understand you and Oleh are
using OPCODE?).
Are there any other opinions / ideas out there?

----- EoOM -----

 

My idea is the one that I've expressed in the comment for the patch.

In my opinion the rotation for o2 should be eliminated altogether and heightfield should not be rotated either.  The heightfield surface is just the set of planes each of them having a very simple constraint on contact points to be located in axis aligned right-angled triangle (well in coordinates of heightfield or in coordinates of the plane - I'm not sure what is the correct approach here but either way should not be difficult). As far as I know, the plane-object collision checking does not require object rotation. So, why the heightfield does?

Ff the main difficulty is because the existing plane-object colliders need to be reused, then, instead of rotating object it could be possible to pass space transformation matrix+vector as the optional parameter to collider functions and account them in end-formulas if they are present. In any case, don't try to convince me that trimesh (whether it is GIMPACT or OPCODE) can't check collisions with plane that is arbitrarily rotated.

Oleh Derevenko
-- Skype with underscore

--

[Tilmann Zaeschke]

On 26.04.2010 09:42, Oleh Derevenko wrote:

My idea is the one that I've expressed in the comment for the patch.

In my opinion the rotation for o2 should be eliminated altogether and heightfield should not be rotated either.  The heightfield surface is just the set of planes each of them having a very simple constraint on contact points to be located in axis aligned right-angled triangle (well in coordinates of heightfield or in coordinates of the plane - I'm not sure what is the correct approach here but either way should not be difficult). As far as I know, the plane-object collision checking does not require object rotation. So, why the heightfield does?

Ff the main difficulty is because the existing plane-object colliders need to be reused, then, instead of rotating object it could be possible to pass space transformation matrix+vector as the optional parameter to collider functions and account them in end-formulas if they are present. In any case, don't try to convince me that trimesh (whether it is GIMPACT or OPCODE) can't check collisions with plane that is arbitrarily rotated.

Thanks for the feedback.
I didn't write the heightfield collider, but I believe the explanation is as follows (as I also commented on the patch):
Leaving the planes flat and instead turning the object allows for very fast collision checking of an AABB with an horizontal plane, it doesn't get much faster than that (and you don't get any false positives). Of course rotating the geom is expensive, so this only pays off if the object is much larger than a single triangle, and thus rotating multiple triangles can be avoided.
This is my opinion why the code is at it is. But I'm not sure this is the best solution, I simply don't know.
The disadvantages of this approach are:
- It helps only if the geoms are considerably bigger than the average triangle
- It actually hurts performance if the geom is very expensive to turn, for example as complex as a trimesh
- It requires a lot of complex collision code
- Fixing the GIMPACT problem becomes ugly (that is why we are having this discussion).

If we assume that the heigthfield is rarely or never rotated or translated during its lifetime, then we could buffer the rotated planes or coordinates, making the whole thing faster (and simpler?). I understand that is also what Oleh proposes.
Here the disadvantage is that the initial pre-check via AABB vs Plane is not as accurate and will deliver false positives, resulting in more calls to the actual collider code.

I think Oleh's proposal makes sense and I would support it. However I do not know why the code was implemented the way it is now, maybe it is a lot cleverer than I can fathom.

Martijn, is it correct that you wrote the collider originally? Could you shed some light on this?

Thanks,
Tilmann

[Oleh Derevenko]

----- Original Message -----

From: Tilmann Zaeschke

To: ode-...@googlegroups.com

Sent: Tuesday, April 27, 2010 12:10 AM

Subject: Re: [ode-users] GIMPACT problems

On 26.04.2010 09:42, Oleh Derevenko wrote:

My idea is the one that I've expressed in the comment for the patch.

In my opinion the rotation for o2 should be eliminated altogether and heightfield should not be rotated either.  The heightfield surface is just the set of planes each of them having a very simple constraint on contact points to be located in axis aligned right-angled triangle (well in coordinates of heightfield or in coordinates of the plane - I'm not sure what is the correct approach here but either way should not be difficult). As far as I know, the plane-object collision checking does not require object rotation. So, why the heightfield does?

Ff the main difficulty is because the existing plane-object colliders need to be reused, then, instead of rotating object it could be possible to pass space transformation matrix+vector as the optional parameter to collider functions and account them in end-formulas if they are present. In any case, don't try to convince me that trimesh (whether it is GIMPACT or OPCODE) can't check collisions with plane that is arbitrarily rotated.

Thanks for the feedback.
I didn't write the heightfield collider, but I believe the explanation is as follows (as I also commented on the patch):
Leaving the planes flat and instead turning the object allows for very fast collision checking of an AABB with an horizontal plane, it doesn't get much faster than that (and you don't get any false positives).

Checking for boundaries of triangles and bottom plane is not difficult even if heightfield is rotated. Well, there are a little bit more computations but still, it's a linear formula. Also, if to take into consideration that heightfield is usually hardly ever rotated the optimized checking code could be selected that will result in the very same simple comparison of one coordinate value in most cases.

I suppose Martijn has originally sticked with transiting to heightfield space just because it was the simplest way, the first thing that has come into mind. Am I wrong?

Oleh Derevenko
-- Skype with underscore

--

[Martijn Buijs]

Oleh Derevenko wrote:
> Checking for boundaries of triangles and bottom plane is not difficult
> even if heightfield is rotated. Well, there are a little bit more
> computations but still, it's a linear formula. Also, if to take into
> consideration that heightfield is usually hardly ever rotated the
> optimized checking code could be selected that will result in the very
> same simple comparison of one coordinate value in most cases.
> I suppose Martijn has originally sticked with transiting to heightfield
> space just because it was the simplest way, the first thing that has
> come into mind. Am I wrong?
>
> Oleh Derevenko
> -- Skype with underscore

Tilmann Zaeschke wrote:
> Martijn, is it correct that you wrote the collider originally? Could you
> shed some light on this?

dHeightfield was based on an existing patch known as "terrain and cone" by Benoit Chaperot. It had a
dTerrainY and dTerrainZ collider (mainly written for his offroad moto-cross game, cones were used
for wheels). As their name indicated, there were two terrain geom implementations, coded for Y-up
and Z-up respectively.
I took the dTerrainY variation, clean up the code, removed some unnecessary limitations and added
support for various heixel formats + GetHeight callback. So I merely improved the API interface, I
never touched the collision code itself. Back then, dHeightfield was fairly simple and robust.

At some point I abandoned ODE, and others was decided that the dHeightfield geom was 'too different'
from other geoms. Changes were made, so that the origin is at the center, and geom rotation support
was added to so it could work with Z-up coordinate systems. Later an optimization was added that
cached triangles under the g2 AABB (termed 'heightfield zone' in the code comments), constructing a
list of triangles/planes etc to merge neighboring co-planar triangles.

These last few changes were apparently not thoroughly tested. The 'zone' optimization in particular
introduced a very hard to trace bug (contacts missing near grid edge corners). The original
'optimization patch' code included a margin to work around this issue, so I think even the author
himself didn't know how to solve it.
In one attempt to fix the bug, Oleh removed this workaround while trying other things, so arguably
the dHeightfield geom is in an even less usable state than it did before.

So, that's roughly the history of the dHeightfield patch.

Perhaps, for trimesh-heightfield, one can replace the ray/plane/depth function pointer mechanism
with specific heightfield vs trimesh collision code. IMO, there's was also a lot of code
complication introduced with the rotation & origin changes. At the time I objected, because it would
needlessly complicate the code; and indeed a handful of bugs caused by this were found (to credit,
the known bugs were fixed eventually).

For a start, one should remove arbitrary rotation support (only allow axis aligned heightfield
orientations) and remove the need for DHEIGHTFIELD_CORNER_ORIGIN to clean up the code. Still you'll
have to accept that dHeightfield will still be bug-ridden and generally not very useful. Even
ray-heightfield has problems (long rays test against every triangle inside the ray AABB!), so I
can't think of a single facet of dHeighfield that has no serious shortcomings.

I've been trying to find the time/motivation to re-write dHeightfield, based on the original
dHeightfield patch I submitted, with optional Quad-Tree optimization, and support for
diamond-triangle layout. But I haven't gotten anywhere in the last few years. :(

(FYI: I actually use dHeightfield in our project (with bug workarounds), but as you guessed I'm not
happy with it. We have high resolution heightmaps so dTrimesh is not an option because of memory cost.)

/Martijn

[Oleh Derevenko]

By the way, where is that copy of object rotation matrix in GIMPACT? Can't it just store constant pointer to the matrix in object so that it remained up to date?

Oleh Derevenko
-- Skype with underscore

 

 

[Martijn Buijs]

Oleh Derevenko wrote:
> By the way, where is that copy of object rotation matrix in GIMPACT?
> Can't it just store constant pointer to the matrix in object so that it
> remained up to date?
>
> Oleh Derevenko
> -- Skype with underscore

I'd love to know this too! I spend some time looking for the code where the rotation is passed from
ODE to GIMPACT, but couldn't find it easily. I suspect something may get mixed up in there.

/Martijn

[Tilmann Zäschke]

The rotation matrix is stored together with a translation vector in a
4x4 matrix in GIMPACT/gim_trimesh.h (line 158: mat4f m_transform; ).

So buffering the rotation matrix would be possible, but require some
hacking.

The bigger problem is the AABB.The AABB is always updated when the
rotation is updated. The AABB is stored together all the AABBs for each
triangle. They are stored in a struct called GIM_AABB_SET, which is
protected by a complex (too complex for my mind) memory locking
mechanism, which stores references to the GIM_AABB_SET in different
places and exchanges them in a complex manner. In fact it was so complex
that I wrote that part from scratch (without the locking) when I
translated GIMPACT to Java, because I couldn't understand it and
couldn't get it to work either.

Anyway, when the rotation is updated, all AABBs are updated. And this
GIM_AABB_SET is directly used by the colliders.

So there are two problems here:
- Whoever wanted to use temporary rotation/AABBs would need to
understand when and how this locking and pointer swizzling works.
- I believe that leaves the problem that all the AABBs in the
GIM_AABB_SET would need to be recalculated, which costs time and extra
storage space (one AABB per triangle).



Further information about GIM_AABB_SET:
The file GIMPACT/gim_trimesh.h declares "GIM_AABB_SET m_aabbset" in line
154.
GIM_AABB_SET is defined in GIMPACT/gim_boxpruning.h. It contains a list
of all AABBs of all triangles. The method
gim_aabbset_calc_global_bound() returns the enclosing AABB.


Bottomline, I would prefer if we could leave that part of GIMPACT alone
and rather implement a different solution.
Btw, how about introducing the old heigthfield code as a new geom, for
example OrthogonalHeightField? Limiting the rotation would not only make
the code simpler, but probably also speed up collision. If people really
need arbitrary rotation, they can still use the current implementation.

[Oleh Derevenko]

----- Original Message -----

From: "Tilmann Zäschke"

Sent: Monday, May 03, 2010 8:48 PM

Subject: Re: [ode-users] GIMPACT problems

Anyway, when the rotation is updated, all AABBs are updated. And this
GIM_AABB_SET is directly used by the colliders.

So there are two problems here:
- Whoever wanted to use temporary rotation/AABBs would need to
understand when and how this locking and pointer swizzling works.
- I believe that leaves the problem that all the AABBs in the
GIM_AABB_SET would need to be recalculated, which costs time and extra
storage space (one AABB per triangle).

That's a serious matter. :(

 

Oleh Derevenko
-- Skype with underscore

--

[Jon Watte]

Reality check: Does anyone think that this micro-optimization would show up on any profiler anywhere?

It seems to me that you're introducing a bunch of usage problems, and all you're gaining for it is a few instructions that won't actually impact anything.

Copying the matrix as appropriate when asked for seems cheap enough. Why not leave well enough alone, and work on things that matter? (like heightfield, cylinder, etc)

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.

[Tilmann]

> Reality check: Does anyone think that this micro-optimization would
> show up on any profiler anywhere?
> It seems to me that you're introducing a bunch of usage problems, and
> all you're gaining for it is a few instructions that won't actually
> impact anything.
> Copying the matrix as appropriate when asked for seems cheap enough.
> Why not leave well enough alone, and work on things that matter? (like
> heightfield, cylinder, etc)

I'm not sure I understand what you mean.
My intention here is to fix a bug in GIMPACT-heigthfield collision.

Indeed I proposed to remove rotation from the heigthfield, or add a
version without rotation, which would also be faster. But that would
only be an additional benefit besides fixing that bug.

Could I clarify the situation? Or did I misunderstand you?

Cheers,
Tilmann

[Martijn Buijs]

Jon Watte wrote:
> Reality check: Does anyone think that this micro-optimization would show
> up on any profiler anywhere?
> It seems to me that you're introducing a bunch of usage problems, and
> all you're gaining for it is a few instructions that won't actually
> impact anything.
> Copying the matrix as appropriate when asked for seems cheap enough. Why
> not leave well enough alone, and work on things that matter? (like
> heightfield, cylinder, etc)
>
> Sincerely,
>
> jw

The intent is not optimization, but reducing code complexity, ultimately to fix a bug.

To me, heightfields that can be rotated to arbitrary orientations (non-axis aligned) are as useful
as plane geoms attached to bodies.

/Martijn

[Jon Watte]

Plane geoms are also not orientable, and thus can also not attach to bodies. In fact, I have a hard time understanding what a discrete rigid body means, mathematically, when considered as attached to an infinite geometry...

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.

[Martijn Buijs]

Jon Watte wrote:
> Plane geoms are also not orientable

That doesn't mean there isn't a use for it. Say you want to simulate certain rebel infiltrators
getting crushed in a star destroyer's thrash compactor. Create aligned planes, attach bodies with
locked rotation, piston joints, have fun squashing wookies.

> , and thus can also not attach to bodies. In fact, I have a hard time understanding what a discrete rigid body means, mathematically, when considered as attached to an infinite geometry...

That's what I meant. It is far fetched. In the rare case someone needs it, he has the source code
and can add it for himself. Publish it as patch, perfect. But don't merge uncommented, rushed code
that adds code complexity and introduces bugs, for some enhancement the average user rarely, if
ever, needs. :)

[Jon Watte]

Say you want to simulate certain rebel infiltrators getting crushed in a star destroyer's thrash compactor

A trash compactor is finite in size. Perfect use for a box?

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable.