Shaky Crabs

[Julio Jerez]

there is an adjacent structure in the engine. It is use for the adjacent normal of static collsion shape and few other stuff.
class ndPolyhedra: public ndTree <ndEdge, ndEdgeKey>

anyway, Bird, yes still not good.

The fix I made does not really fix the problem, is fix two of problems
1- the mesh was rejecting tine and ill triangle,
2- the buffer that query the interesting faces, was too small because is was mass of the stack,

for year I have been making large ar large, it start with 32 face, the 64, 128, 256, now was 512.

with the marine rocks mesh, to collect the faces, it the code could not run a over 65 k triangles because it runs out of stack.

I loaded the mesh in max, and I see that the mesh has a very estrange scale with of lenght of 1.0e-4.
with the size of the convex I was using which is about 10 % of the entire size of the floor, a query collect tenth of thousands of faces.

I went to Max and reset the scale to be meters instead of a kilometer and save it.
now the query get around 10k faces.

this is still ridiculous, but the engine should handle it, so I made the change so that the temp data is not longer on the stack, instead they are thread local buffers kept in the scene.

that's that problem

the jitter problem we still have is related to the contact be inconsistent from frame to fame.

for that I have to implement the close approach part of eth collision that I have not gotten around

that is this part of the collision rotting that is comment out form 3,14
you will find in functions like

Code: Select all

void GetCollidingFaces(ndPolygonMeshDesc* const data) const
....
....
   if (data->m_doContinueCollisionTest)
   {
      ndAssert(0);
      //dFastRay ray(ndVector::m_zero, data->m_boxDistanceTravelInMeshSpace);
      //for (ndInt32 i = 0; i < faceCount; ++i)
      //{
      //   const ndInt32* const indexArray = &indices[faceIndexCount1];
      //   const ndVector& faceNormal = vertex[indexArray[4]];
      //   ndFloat32 dist = data->PolygonBoxRayDistance(faceNormal, 3, indexArray, stride, &vertex[0].m_x, ray);
      //   if (dist < ndFloat32(1.0f))
      //   {
      //      hitDistance[faceCount0] = dist;
      //      address[faceCount0] = faceIndexCount0;


I thought that I could probably get away without it, but that test you show me demonstrate that it does really need it.

so after I complete the change, I will re implement the closest approach contact.

in 3.14 that was done based of the deepest penetration, when a shape collides with a ground of faces, in deep penetration, is sort the array by penetration and reject the contact the did with lower penetration,

in 4.xx I removed that in favor of a more generic contact discriminator, that detect contact by the eigen values. this work quiet well but is fail bad with contacts with such wide range of penetration.

anyway after I get this global memory buffers, I will revisit and get that part with the test repro.

mean time, can you try decimating the mesh even more, maybe 100,000 or less face, and see if it
get to a stable setting,

[Bird]

mean time, can you try decimating the mesh even more, maybe 100,000 or less face, and see if it
get to a stable setting,

I went down to 70,000 triangles. It's not much different than 300,000. There's still some penetration and the pile does not settle.

[Julio Jerez]

yes, it is real bad.
I too made two different lods, a 10% and one a 1% of the original mesh, and the jitter error is still there.

this needs a better solution.

I made a repro, that if you sync you will see with a plane box without sleep and is dances all over the place.

ok I have some work to do.

[Julio Jerez]

one thing that show a sign of a big problem is that It seems contacts are produced outside the shape.
that's a big problem

Untitled1.png (435.02 KiB) Viewed 10862 times

I will see what is that all about, because before start thinkong new algorithm we need to be sure all the
known bugs are fixed.
a contact outsize the shape, is a big no no.
I also see lot of intermittent contacts, so that another big issue.

[Julio Jerez]

Yes, it is definitely generating contacts outside the shape.
That's quite, bad

I think this has to be related to some late changes, I do not remember being so bad.

Anyway, I have a consistent repro, so I work to get that fix them we move to the next challenge.

[Julio Jerez]

ok, I believe I found the problem and it explains why it is so bad.

it not hard to fix, but I will start tomorrow, sometime something that seem a solution turns out not to be when you are tired.

Edit:
Ah, I think I found what the problem is.
It is the tolerance in the polygon clipping routine.
In fact it could be in more than one place.

To me a small tolerance is a number like 1e-3
But with this mesh, even with the decimated one.
Some edges are like 100 time smaller than the tolerance.
Anyway, I am getting it fix.

[Julio Jerez]

ok, please sync an try again.

I try with the low and mid resolution mesh, so fart seems robust.
I did not do much more test, but please see if you get better results.

I would not try the high-res mesh.
try first the low (70k) them the mid (300k) and let us see how that goes.

[Julio Jerez]

I now test the mid res mesh and more shapes, so far so good.
I set the demo to show flat shaded shape because with a light is hard to see the insane resolution of that mesh.
The is not to be believe, and I am showing the mid resolution one.
that the kind of mess that people use to generate normal maps and even for that is too high.
I actually crash my version of Max few times, I get Low on memory, save you data waning.

it is hard to believe that the engine works at all with that kind of data.

[JoeJ]

there is an adjacent structure in the engine. It is use for the adjacent normal of static collsion shape and few other stuff.
class ndPolyhedra: public ndTree <ndEdge, ndEdgeKey>

Ah yes, i remember you use it to get the face normal across the edge.
And iirc, i could use the same index to get the face itself as well.
So adjacency is already there, and if not, i could just add some extra arrays if needed. Never mind.

[Bird]

ok, please sync an try again.

I try with the low and mid resolution mesh, so fart seems robust.
I did not do much more test, but please see if you get better results.

I would not try the high-res mesh.
try first the low (70k) them the mid (300k) and let us see how that goes.

Still some small penetrations in both 70k and 280k but now the piles settle quickly.

The full 1.3 million version is still very leaky

[Julio Jerez]

Those meshes seem to be generated by some fractal algorithms. A tail tale is when you close up, you can see tgat almost not to triangles sharing an edge form a convex cap.
There are like some brownian motion that a move in one direction is follow by a move in the opposite.

They can generated very untractable surfaces.

They offer no problem rendering because a renderer does
really process the mesh at runtime, the most problematic part for rendering is just clipping, and that is a simple operation since the clipp is against an alined plane.

For the physics on the other hand, there is lots of geometry procesing,, and when doing it with 32 bit floats, you have to set tolerances.

For 32 bit float the tolerance can not be epsilon because they may not have any effect.

So the problem with the very high resolution mesh is that there are triangle with edges smaller than 1e-4 of a unit.
And with those sizes the error introduce by tolerance is just too large.

Offline algorithm that do mesh manipulation use very small tolerances like 1e-15 which is around the 64 bit machine presition. That how they can operates on that kind of data.

For float 32, I amd using 1e-5 and some places 1e-4
But these tranches are hard coded, so using double will not help.

For these cases you are going to have to use they high resolution for visual and a decimated mesh for collision.

Another beneficial side effect of the decimated mesh, is that the polygon reduction toll tend to generate well behave mesh topogies, while the fractal algorithm are bases in ramdoness and generate more untractable topologies.

In the video bellow the decimated mesh is almost indistinguishable from the high resolution one
https://youtu.be/_IHPImuk5Fw

Can you make a video to see the penetration that you are seeing.

[Bird]

Can you make a video to see the penetration that you are seeing.

The 1st run has about 70,000 triangles, the 2nd run has about 280,000 triangles and the last is the original with about 1.3 million triangles

https://youtu.be/eJCM9l27Yc8

For these cases you are going to have to use they high resolution for visual and a decimated mesh for collision.

Yeah, that's what I figured. I'm trying to do the decimation on the fly in my app using InstantMeshes but can't get it working yet.

I wish I could use the decimated mesh for rendering .... that would be a lot better than sending 1.3 million triangles to the GPU.

[Julio Jerez]

Oh, yes that penetstion is normal, that's typical timestep and descrete collision.
The mesh is paper thin, in general real geometry has volume or thickness, and when it does not, them people are not suppose to see on the other side.

The only way to eliminate that is with ccd. But that a feature for next year.
A way to minimize it is with sepsteps.

Notice that newton collision system is not like others engines collision systems.
Newton collision work on intersection, so when two objects collide there is a minimum intersection, while other engine use collision margine.

Collision margine is much faster, but generates bad physic because contacts are generates procedually using heuristic. While intersection always produces geometric contacts from the geometry.

In the end the extra cost is not an issue because is totally negligible compared to the time in the solver resolution.

Anyway,
Thank for that repro, it helped a lot in fix multiple serios problems.
Keep them comming.

For now, I think this can be closed.

[Julio Jerez]

In tge last run.
It show the tolerance problem.
The code goes over the interesting mesh.
The find the best candidate for collision.

But the tiny triangle are totally steep because they are smaller that what the routine can handle.

It is not trivial to fix that with 32 bit presition. But there is not need to solve that problem when it is such an outlier.

In video Game artists spend they majority of thier time optimizing mesh for this kind of thing. Even in the movies
CGI geometry for background is fairly low res. The complex prop are the stuff in the foreground.

I am surprised Lightwave does not has a build in polygon reduction modifier.
I have max 2013, and it has two, one better than the other.
But both really bad at preserving uv, and any other Vertex attributes.

[Bird]

I am surprised Lightwave does not has a build in polygon reduction modifier.
I have max 2013, and it has two, one better than the other..

LW's Modeler does have several polygon reduction tools. That's how I decimated the marine_rock mesh.

But both really bad at preserving uv, and any other Vertex attributes

Yeah, that's the problem for rendering.

I usually use this tool inside my app for mesh reduction on the fly. But for some reason it cannot handle the marine_rock mesh
https://github.com/wjakob/instant-meshes