Numerical issues with GJK for large triangle areas

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Numerical issues with GJK for large triangle areas

Post by irlanrobson »

I've noticed that my GJK implementation is suffering from numerical issues for a 3-simplex early out (e.g. the closest point is on a triangle), where the shapes involved are a sphere and a triangle.

What made me notice this was a vertical stack of 10 spheres falling over the following static triangle: v1 = (-50.0, 1.0, -50.0), v2 = (0.0, 1.0, 50.0), v3 = (50.0, 1.0, -50.0).

So, I tested a sphere of radius = 1 located at c = (-5.0, 2.0..n, 0.0) over the same triangle, and noticed the solver was fuzzy in the z-axis canonical direction. Then shifted the spheres to c = (0.0, 2.0, 0.0) and the stack became stable. This was expected of course, because the barycentric for this c does not suffer much from precision issues. The same problem is reduced as long as the sphere over the triangle is close to the triangle centroid.

Is there currently any work around for this problem or we still do need to limit the size of triangles (of course coming from meshes) in our games?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Numerical issues with GJK for large triangle areas

Post by Dirk Gregorius »

How does the support function of sphere looks like?
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: Numerical issues with GJK for large triangle areas

Post by irlanrobson »

The support point is just the sphere center.

I'm pretty sure the implementation is correct as it is has been working very well since implemented. I just need to know if this is a common numerical problem for GJK (large shape sizes). I've read about this in the forums some weeks ago but can't remember exaclty where.

If I replace the triangle mesh with a hull of the same size (but the face being a quad now) this problem doesn't occurs.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Numerical issues with GJK for large triangle areas

Post by Dirk Gregorius »

Looks like a bug to me. I have no numerical issues at that scale.
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: Numerical issues with GJK for large triangle areas

Post by irlanrobson »

Okay, I tested the stack on a hull and now with the sphere stack starting from a different location, and looks like a numerical problem due to GJK barycentrics. If anyone is able to reproduce this same setup and post back the results I'd greatly appreciate and set this thread as solved.

Box (Hull)

Position = (0.0, 0.0, 0.0)
Density = 0.0 kg m^3
Friction = 1.0
Dimensions = 100 x 1 x 100 m^3 / Scale = (50, 1, 50)

Sphere 1

Position = (-30.0, 2.05, 10.0)
Density = 1 kg m^3
Friction = 1.0
Radius = 1.0 m

Sphere 2

Position = (-30.0, 4.55, 10.0)
Density = 1 kg m^3
Friction = 1.0
Radius = 1.0 m

Frequency = 60 Hz
Sleeping = 0
Warm Starting = 1
Vel. Iters = 8
Pos. Iters. = 2
Gravity = 9.8 m/s^2

After ~20 s Sphere 2 should start sliding along the z axis and the stack fall.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Numerical issues with GJK for large triangle areas

Post by Dirk Gregorius »

I am not sure I understand what the problem is. Are you saying that the closest point returned from GJK is not *exactly* projecting under the lowest sphere center and that the tiny offset due to numerical imprecision is making your sphere stack fall over?
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: Numerical issues with GJK for large triangle areas

Post by irlanrobson »

Yeah. Obviously if the contact point doesn't align with the center of mass of Sphere 1 because of rouding errors being accumulated when projecting its center on the triangle, and if Sphere 2 does, then the latter will start sliding after some significant amount of time has passed.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Numerical issues with GJK for large triangle areas

Post by Dirk Gregorius »

I am not sure if I would consider this a bug and spend time trying to fix this.
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: Numerical issues with GJK for large triangle areas

Post by irlanrobson »

Yeah, same thing here. Thanks.
Post Reply