Incorrect collision normal in sphere/triangle mesh collision

Post Reply
hiker
Posts: 83
Joined: Tue Oct 24, 2006 11:52 pm
Location: Australia
Contact:

Incorrect collision normal in sphere/triangle mesh collision

Post by hiker »

Hi,

in our game supertuxkart we've recently added a soccer mode. But during testing we discovered that now and again the ball would suddenly jump up a bit. The ground is a totally flat rectangle (>90x170 units) made out of 8x8 triangles (originally we used 2 triangles, but I seemed to remember some issues with large triangles in bullet, so we subdivded the plane - but it made no difference).

Debugging showed that this appears to happen during the constraint impulse solver, and is ultimately caused by bullet reporting a collision normal that is not (0,1,0), but slightly rotated e.g. (-0.191352 0.981521 0.00000). What happens later is that this normal is multiplied by the velocity of the object (ball) in btSequentialImpulseConstraintSolver::setupContactConstraint:

Code: Select all

			btVector3 vel1 = rb0 ? rb0->getVelocityInLocalPoint(rel_pos1) : btVector3(0,0,0);
			btVector3 vel2 = rb1 ? rb1->getVelocityInLocalPoint(rel_pos2) : btVector3(0,0,0);
			vel  = vel1 - vel2;
			rel_vel = cp.m_normalWorldOnB.dot(vel);
If the velocity of the ball in the direction of the incorrect normal (in the example above X direction) is high, the resulting value of rel_vel is too high, causing too big an impulse to be applied in btSequentialImpulseConstraintSolver::resolveSingleConstraintRowLowerLimit. This impulse is applied in the direction of the normal, which is mostly up --> the ball jumps up.

The incorrect normal is computed in SpheretriangleDetector::collide():

Code: Select all

...
if (hasContact) {
    btVector3 contactToCentre = sphereCenter - contactPoint;
    btScalar distanceSqr = contactToCentre.length2();

    if (distanceSqr < radiusWithThreshold*radiusWithThreshold)
    {
        if (distanceSqr>SIMD_EPSILON)
        {
            btScalar distance = btSqrt(distanceSqr);
            resultNormal = contactToCentre;                // Incorrect normal here!
            resultNormal.normalize();

            // FIX???   resultNormal = normal;
            point = contactPoint;
            depth = -(radius-distance);
        } else
        {
            btScalar distance = 0.f;
            resultNormal = normal;
            point = contactPoint;
            depth = -radius;
        }
        return true;
    }
In case that distanceSqr>SIMD_EPSILON a new normal is computed as difference between the centre of the sphere and the collision point, which is in general not in the up direction of the triangle mesh.

A simple fix seems to be (as shown above) to set resultNormal to 'normal' (which is in our case (0, 1, 0)), but I am not sure what kind of side effect this could have.

Note that we are using a quite old version of bullet (2.79), but updating bullet is not a trivial issue for us (due to some modifications we have applied). I had a quick look at 2.83, and while a lot of source code has changed, the basic behaviour (i.e. computing the normal, multiplying with speed and applying the impulse) appears to be the same.

Can anyone with a better understanding shed some light on this issue? Is there a better fix then the one above? Or should we update to a current bullet version?

We see the same issue when using a puck (cylinder), but I haven't had time to debug this.

Any help appreciated!

Cheers,
Joerg
benelot
Posts: 350
Joined: Sat Jul 04, 2015 10:33 am
Location: Bern, Switzerland
Contact:

Re: Incorrect collision normal in sphere/triangle mesh colli

Post by benelot »

Sounds like a cool game! Is it open source? Concerning your issue, it sounds strange to just hardcode the contact normal, as it might be the base for the reflection of the ball on the ground and if you ever do triangle collision with the cars, then the cars as well. In fact, the slight deviations of your contact point are typical numerical errors, and it is interesting that you can observe them in the behavior of the game. Anyway, you might want to use btStaticPlaneShape, making the normal always correct. Anything preventing you from using this?

Did you do many changes to the bullet code base? You might want to consider porting to the newer release, just to keep up with the future. Otherwise, if you are happy with your performance, stay with it!
hiker
Posts: 83
Joined: Tue Oct 24, 2006 11:52 pm
Location: Australia
Contact:

Re: Incorrect collision normal in sphere/triangle mesh colli

Post by hiker »

Hi Benelot,

thank you for your quick answer!
benelot wrote:Sounds like a cool game! Is it open source?
Yes, please check http://supertuxkart.net (we have just done a new RC: https://sourceforge.net/projects/supert ... art/0.9.2/)

Concerning your issue, it sounds strange to just hardcode the contact normal,
Well, not really 'hardcode' - I use the normal from the triangle (instead of the connection-line between the two bodies). By now I have verified that the cylinder (puck) has the same issue, and the same fix (using the normal of the triangle) solves the problem for us. I have a slightly modified patch now (I test that the triangle body has indeed mass 0), so my change should not affect any collision between dynamic triangle meshes (though we don't have them anyway, all our dynamic objects are simple shapes like cone, spheres, boxes). You can see my patch here:

https://github.com/supertuxkart/stk-cod ... e/fix-2522

It's basically the same patch applied at two locations (once for sphere triangle collision, the other for convex vs triangle). I admit it is VERY ugly code, since I have to include some dynamics code into the collision handling (in order to get the mass). A proper fix would be to include a flag from a calling subroutine (where we still have dynamical bodies) to trigger the different normal computation in the collision handling, or perhaps detect in the first place if a static body is involved and handle this case separately?. But since that would be a lot of code changes, I don't want to do this work ;)
as it might be the base for the reflection of the ball on the ground and if you ever do triangle collision with the cars, then the cars as well.
I think that should be ok now, since only tracks would be static bodies.
In fact, the slight deviations of your contact point are typical numerical errors,
Not sure about your usage of 'numerical errors' - the error is not a floating point error, but a problem with the way of how the collision is handled. That can of course be because bullet is a simulation (or because there is a bug ;) Maybe it's just that in case of a static body using the connection between the two contact points is not correct since the static body is not pushed away?? But I can certainly see that if the incorrect normal is used and the speed of the object happens to be big in the 'incorrect' direction, a too large impulse is applied. Maybe if the solver would iterate longer the effect might be reduced). Just to be sure, we are not talking of a slight 'wobbling'. One of our devs made a video of it:
https://www.youtube.com/watch?v=e2SkBWH ... tu.be&t=40
Completely unmotivated the puck is suddenly pushed up higher than the kart. Admittedly it is rare that it happens that rarey, but if the velocity just happens to be large in the right direction when the normal is incorrect, the effects can be rather huge. I see that the impulse applied by the collision impulse solved causes a vertical speed of 2m/s. We actually removed the puck from our next release because it looks so bad (ball has the same effect, but at least it looks a bit more natural, people accept that a ball can bounce a bit ;) ).
and it is interesting that you can observe them in the behavior of the game. Anyway, you might want to use btStaticPlaneShape, making the normal always correct. Anything preventing you from using this?
First of all, I am not sure that this would actually solve the problem - I admit I only had a very quick look, but it appears that the static plane creates two triangle to do the collision (in btStaticPlaneShape::processAllTriangles), so I am not convinced that it is worth the effort to test this ;)

Secondly (and for us more important): it doesn't work with our pipeline. We export the whole track (including AI information and other meta information like material) from blender, and in general we don't have that flat planes to make it worth handling this as a special case. In fact, I have seen 'bowling balls' (powerups in the game) jumping up unexpectedly for a long time, and always assumed it's just our tracks being not smooth enough. Now I strongly suspect that this is actually the same issue.
Did you do many changes to the bullet code base? You might want to consider porting to the newer release, just to keep up with the future. Otherwise, if you are happy with your performance, stay with it!
We are happy with the performance, so as long as we don't hit real problem we don't intend to update (being a small team we just don't have the time to keep all our libs up-to-date).

We did apply a few changes (we basically have a somewhat modified version of the raycast vehicle: https://github.com/supertuxkart/stk-cod ... btKart.cpp). We:
  • added function to apply additional impulses (for special handling triggered by game play, not physics)
  • support 'cushioning' of falls (we detect when a kart is falling and would hit the ground too hard for the suspension, so that actually the chassis would hit the ground) and in this case apply an additional upward impulse to prevent this from happening.
  • have code to keep karts upright (as much as possible)
  • improved jumping a bit (if a kart should have only one wheel on the ground before it finally takes off, this will add a rotation to the kart causing is to land facing in the wrong direction. And while this might be real, it's not fun playing ;) So we ... just pretend that always both wheels on one axle are on or off ground ;) ).
  • added some bug fixes (e.g. https://github.com/supertuxkart/stk-cod ... dfd2c5fe7d which afaik was never accepted/integrated into bullet).
Cheers,
Joerg
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Incorrect collision normal in sphere/triangle mesh colli

Post by Flix »

hiker wrote:It's basically the same patch applied at two locations (once for sphere triangle collision, the other for convex vs triangle).
Then I guess it affects spheres made with one btMultiSphereShape too, isn't t?

In any case I think it's better if you post a issue to the bullet3 issue section (https://github.com/bulletphysics/bullet3/issues) referencing this post.

It is not clear to me if you've made the fallback for dynamic bodies because it works better or just to stay on the "safe side" (I have to understand better the collision algorithm to understand it): as you said, the separation between Bullet Collision and Bullet Dynamics could make applying your patch more difficult.

[Edit (Based by the comments in your patch):] maybe the problem arises when two adjacent triangles are planar more than when the triangle is static, isn't it? But in that cases shouldn't the ball collide with more than one triangle and the sum of their "tangent contributes" be zero ? And by using a single big triangle for the field could solve this problem...

It's an important issue IMO because a lot of people uses Bullet to make sport simulations with balls on planar surfaces... maybe just having a hook to replace the collision normal without modifying the Bullet source code could be useful.

P.S.: I played it some year ago and your game was one of the best free games available for Linux at that time (and the music was addictive)! Many compliments.
hiker
Posts: 83
Joined: Tue Oct 24, 2006 11:52 pm
Location: Australia
Contact:

Re: Incorrect collision normal in sphere/triangle mesh colli

Post by hiker »

Hi,

thanks for your answer!
Flix wrote:
hiker wrote:It's basically the same patch applied at two locations (once for sphere triangle collision, the other for convex vs triangle).
Then I guess it affects spheres made with one btMultiSphereShape too, isn't t?
Indeed. See attached graph (didn't have time for a video) showing the Y (up) direction, and speed in x and y direction.
multisphere.jpg
multisphere.jpg (41.08 KiB) Viewed 17430 times
At the left (frame 160) it shows the collision of the kart with the ball, then the unexpected jump at frame 210 (there is another collision just at the end, which is when the ball hit the fence around the soccer field).
In any case I think it's better if you post a issue to the bullet3 issue section (https://github.com/bulletphysics/bullet3/issues) referencing this post.
Will do, I was/am hoping to get a confirmation that it is indeed a bug, and not perhaps a restriction of the physics simulation.
It is not clear to me if you've made the fallback for dynamic bodies because it works better or just to stay on the "safe side" (I have to understand better the collision algorithm to understand it): as you said, the separation between Bullet Collision and Bullet Dynamics could make applying your patch more difficult.
Yes, it was only to reduce potential side effects, at least in our case I know that this will only affect a collision with the track.
And it definitely needs a better fix: either (if in case of collisions with a static body) this needs to be handled differently, or ... no idea ;)
[Edit (Based by the comments in your patch):] maybe the problem arises when two adjacent triangles are planar more than when the triangle is static, isn't it? But in that cases shouldn't the ball collide with more than one triangle and the sum of their "tangent contributes" be zero ? And by using a single big triangle for the field could solve this problem...
We first observed the problem when we had one plane with two triangles only, and the incorrect normals were not on the boundary. The incorrect normal happens (at least in the sphere case) the connection between the contact points is not parallel to the normal of the ground - so I guess whenever the sphere is slightly 'in' the triangle.
It's an important issue IMO because a lot of people uses Bullet to make sport simulations with balls on planar surfaces... maybe just having a hook to replace the collision normal without modifying the Bullet source code could be useful.
Yes, that would work, too. I am actually surprised that no one has seen this before - so, perhaps we are doing something wrong ;)

P.S.: I played it some year ago and your game was one of the best free games available for Linux at that time (and the music was addictive)! Many compliments.
Thanks a lot! Feel free to have a look at our current 0.9.2 release candidate (link in a previous post here in this thread).

Cheers,
Joerg
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Incorrect collision normal in sphere/triangle mesh colli

Post by Flix »

Thanks for taking the time to test the btMultisphereShape too :) .

P.S. To make your patch depend on Bullet Collisions only, btCollisionObject.h should have a isStaticOrKinematicObject() method that just depends on its own collision flags.
It could be used instead of checking the mass (and should be faster).

Code: Select all

	SIMD_FORCE_INLINE bool		isStaticOrKinematicObject() const
	{
		return (m_collisionFlags & (CF_KINEMATIC_OBJECT | CF_STATIC_OBJECT)) != 0 ;
	}
Post Reply