Different jitter on different shape types?

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Different jitter on different shape types?

Post by pico » Mon Jan 07, 2008 9:21 am

Hi,

i use applyImpulse to move a rigid body made of a btBoxShape.
I experience the following problem:

When i move this body over a static btBoxShape then it moves very smoothly.
When i move this body over a static btBvhTriangleMeshShape then there is alot of jitter.

The static btBvhTriangleMeshShape looks exactly like the static btBoxShape.
I tried to disable friction, but the jitter is still there.

Any help would be much appreciated.

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Different jitter on different shape types?

Post by pico » Sat Jan 12, 2008 11:31 am

Does no one experience this behaviour?

Does anyone use a box as collision shape without the described jitter problems?

Any help on this topic would be great!

thanks

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Sat Jan 12, 2008 2:42 pm

Contact point generation for convex vs mesh is a complex thing. I am just experiencing this myself.

Erwin:
How does Bullet deal with convex vs mesh? Do you create a manifold for each triangle that collides with the convex shape simply using GJK/EPA? Do you use any heuristics to remove redundant and/or even bad manifolds? Do you have any contact point reduction like described in GPG 4?


Cheers,
-Dirk

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Different jitter on different shape types?

Post by Erwin Coumans » Sat Jan 12, 2008 5:44 pm

pico wrote: When i move this body over a static btBoxShape then it moves very smoothly.
When i move this body over a static btBvhTriangleMeshShape then there is alot of jitter.
The static btBvhTriangleMeshShape looks exactly like the static btBoxShape.
I tried to disable friction, but the jitter is still there.
There shouldn't be any difference. Can you reproduce this in a Bullet demo, so we can check it out?
Dirk Gregorius wrote:Contact point generation for convex vs mesh is a complex thing. I am just experiencing this myself.
How does Bullet deal with convex vs mesh? Do you create a manifold for each triangle that collides with the convex shape simply using GJK/EPA? Do you use any heuristics to remove redundant and/or even bad manifolds? Do you have any contact point reduction like described in GPG 4?
Bullet uses one contact manifold between convex vs mesh, and it performs contact point reduction to keep 4 points at most. Contact manifolds per-triangle was used in the past, but a single manifold is sufficient as long as you always keep the point with deepest penetration.
You can check it out in the Bullet ConcaveDemo.

A full chapter of my upcoming book is spend on contact methods, including point caching and point reduction.
Erwin

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Sat Jan 12, 2008 6:23 pm

So btBvhTriangleMeshShape is required to be convex or can it be even a surface mesh without volume?

If the mesh can be any shape ( e.g. concave with volume or surface without volume ) than I doubt that one simple persistent manifold is sufficient for good contact point generation. Even Havok came up with a new welding heuristic in version 5.0. So why so much effort with pre-processing to generate welding information if a persistent manifold like in Bullet is sufficient? Ageia seems to break all meshes into convex pieces as Pierre stated here on the forum. Finally I know from a lot of studios that they restrict their artists only to use convex shapes to approximate the level geometry since meshes can make so many problems. Sorry, but one single demo is by no means a prove that this approach works in all scenarios - it is a start. BTW: Four one shot manifolds I didn't find any difference in keeping the deepest point in the convex hull approximation. I think Erin made the same experience.

I glad to hear that you make this whole topic in your book. Have you made any progress already? What is the estimate on a release?

Here is a link which shortly touches the problems on mesh contacts as well. It would be interesting how the incremental manifold deals with the "cliff" problem. I can imagine that it is not as bad as using clipping:

http://www.box2d.org/forum/viewtopic.ph ... a&start=10

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Different jitter on different shape types?

Post by Erwin Coumans » Sat Jan 12, 2008 7:46 pm

Dirk Gregorius wrote:So btBvhTriangleMeshShape is required to be convex or can it be even a surface mesh without volume? If the mesh can be any shape ( e.g. concave with volume or surface without volume ) than I doubt that one simple persistent manifold is sufficient for good contact point generation.
Yes, many 3D games use static (non-moving) concave triangle meshes for the landscape, environment and buildings, and btBvhTriangleMeshShape can be used for this. And 4 contact points are enough in practice.
Even Havok came up with a new welding heuristic in version 5.0. So why so much effort with pre-processing to generate welding information if a persistent manifold like in Bullet is sufficient? Ageia seems to break all meshes into convex pieces as Pierre stated here on the forum. Finally I know from a lot of studios that they restrict their artists only to use convex shapes to approximate the level geometry since meshes can make so many problems. Sorry, but one single demo is by no means a prove that this approach works in all scenarios - it is a start. BTW: Four one shot manifolds I didn't find any difference in keeping the deepest point in the convex hull approximation. I think Erin made the same experience.
Having worked for both Havok, and on the PhysX engine, I can tell those workaround are fixes for hitting interior edges. Some of those fixes cause the 'cliff' problem.

It is not likely that this is related to the jitter mentioned by the original poster, so it is better to split the topic, and start/continue another topic on how to avoid hitting interior edges of a triangle mesh, if that is your main concern.

It is likely another issue that we are dealing with, so let's find out and reproduce it in a Bullet demo.
Hope this helps,
Erwin

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Sat Jan 12, 2008 8:57 pm

I thought the jitter was related to hitting internal edges, but it might be another problem. I get out of this discussion and start a new thread...


-Dirk

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Different jitter on different shape types?

Post by pico » Sun Jan 13, 2008 11:15 am

Erwin Coumans wrote:
pico wrote: When i move this body over a static btBoxShape then it moves very smoothly.
When i move this body over a static btBvhTriangleMeshShape then there is alot of jitter.
There shouldn't be any difference. Can you reproduce this in a Bullet demo, so we can check it out?
Hi Erwin,

i modified the "ConcavePhysicsDemo.cpp" to show the effect. There are now two boxes. After some seconds they start to move.

- The upper box moves on a static box ground.
- The 2nd moves on a perfectly flat triangleMeshShape.

I suggest to make the openGl window fullscreen to see the effect more easily.

Now watch the boxes move. The first box moves without 'jumping' on the Y axis. The 2nd 'jumps' on random positions.
Please note that you have to restart the simulation several times with "space" to see this effect.
I often need several restarts until the effect happens really badly.

It seems the effect only happens when the box crosses a triangle edge.
Attachments
ConcavePhysicsDemo.zip
(4.18 KiB) Downloaded 230 times

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Sun Jan 13, 2008 1:56 pm

I can see the effect and I wouldn't call this jitter. My guess would be that it is related to the contact point generation. Either you get bad normals (e.g. hitting internal edges) or (less likely) there are some issues with the contact cache since I could imagine that due to the sliding some points might fall out of the distance threshold. I doubt that the later is the reason since I would guess you would see the same issues with the other box in this case as well.

User avatar
Erwin Coumans
Site Admin
Posts: 4193
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Different jitter on different shape types?

Post by Erwin Coumans » Mon Jan 14, 2008 3:07 am

pico wrote: It seems the effect only happens when the box crosses a triangle edge.
In that case, the sliding box is hitting an internal edge indeed.

We can add some option/workaround for static triangle meshes, to always return the triangle normal. This will eliminate the effect of hitting internal triangle edges, at the cost of some side effect. It might help you.

I'll add it to the todo, and try to add it before next release,
Thanks,
Erwin

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Different jitter on different shape types?

Post by pico » Mon Jan 14, 2008 9:29 am

Dirk Gregorius wrote:I can see the effect and I wouldn't call this jitter.
You are right, in this example its not visible as jitter. However, in my actual game i have more complex static meshes which are much denser. Also my cam is more close. There it is noticeable as strong jittering.

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Different jitter on different shape types?

Post by pico » Mon Jan 14, 2008 9:39 am

Erwin Coumans wrote:
pico wrote: It seems the effect only happens when the box crosses a triangle edge.
In that case, the sliding box is hitting an internal edge indeed.

We can add some option/workaround for static triangle meshes, to always return the triangle normal. This will eliminate the effect of hitting internal triangle edges, at the cost of some side effect. It might help you.

I'll add it to the todo, and try to add it before next release,
Thanks,
Erwin
I had exactly the same box/edge collision problem in my own physics engine. It became recognizeable with larger velocity/gravity ratios.
My fix was to dismiss any static edge collisions when the considered static edge was connectected to another triangle. I think this should fix this issue without any side effects.

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Mon Jan 14, 2008 10:14 am

If one vertex is exactly over an edge you would dismiss this contact point as well - just because the closest point is on an edge? Also note that when a box bottom face is parallel to the triangle any point on the triangle realizes a closest point. Even worse GJK usually returns a closest point on a vertex or edge in this case. How can you dismiss internal triangles without any other geometric heuristics and expect no side effects?

Is there any trick I overlook?

pico
Posts: 229
Joined: Sun Sep 30, 2007 7:58 am

Re: Different jitter on different shape types?

Post by pico » Mon Jan 14, 2008 3:31 pm

Dirk Gregorius wrote:If one vertex is exactly over an edge you would dismiss this contact point as well - just because the closest point is on an edge? Also note that when a box bottom face is parallel to the triangle any point on the triangle realizes a closest point. Even worse GJK usually returns a closest point on a vertex or edge in this case. How can you dismiss internal triangles without any other geometric heuristics and expect no side effects?

Is there any trick I overlook?
You are right, that alone doesn't cure the problem. I did that code some years back so my memory is a bit dusty. There was an additional step examining the normal at that edge (averaged from the connected faces), the normal of a possible 2nd collision point on the face and some comparisons with the velocity of the other body. Although it worked great there i guess its too hacky on a larger scale.

Dirk Gregorius
Posts: 874
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Different jitter on different shape types?

Post by Dirk Gregorius » Mon Jan 14, 2008 3:59 pm

I just thought about this in 2D shortly. My guess is that we can maybe dismiss normals that are not in the Voronoi region of the shared vertex. If this would work it shouldn't be to difficult and expensive to compute a reasonable normal angle/cone offline.
Voronoi.png
Voronoi.png (5.5 KiB) Viewed 9345 times
I shortly try to sketch the basic idea. As soon as the box comes in proximity with the second (right) edge we get flat normals that should be dismissed. Since the found (red) normal is not in the plausible (green) region we discard it. It is just a simple idea, but it should be extendable to vertex and edge regions in 3D. Unfortunately it doesn't help me with my problem, since I use one shot manifolds and triangle normals :-) and this seems more appropriate for incremental manifolds using closest points and shallow penetration.

BTW: Note that for flat edges (triangles that share the same normal) the feasible region correctly becomes only the face normal and all bad/flat normal would be disgarded. In the example the "up" vector. The should't be any problems with "cliffs" as well.


Erwin, feel free to move this to a separate thread if you like.

Post Reply