Newton 2.0x Archemedia Open Beta

[rvangaal]

Here's my results:

- calling NewtonTreeCollisionEndBuild(geom,maxAspect,0); and saving the tree gives different results depending on 'maxAspect'; one time I had 1200Kb, then 1700Kb. It was consistent but depends on the aspect. Did you add splitting of polygons if they had a large aspect ratio? Older tree saves for this track were ~500Kb for unoptimized, 250K for optimized.
- using optimize still gave problems unfortunately. I should try to paint the collision tree triangle normals to see if that isn't the problem. Unoptimized the tree still collides fine.

Strange...

[Julio Jerez]

you say that and unoptimize mesh when form 500kb to 1200Kb? what aspect ratio did you pass?

the aspect ratio is independent of optimization. so unoptimized meshes will also be splitted to meet the specified aspec ratio.
if you do not want face to be cliiped, you can pass as large aspect ratio, a value bigger than 1000 will do.

you say the optimized mesh still fail, I do not undertand can you post a video of the area when the bug happens?
I tested the mesh you sent me with several shapes and I did not see the bug.

do you think you can send me and executable that I can run to test this, maybe it something else?

[JernejL]

what value for aspect ratio should we use for it to work as before? what does the ratio mean? (so i can add the new info it to wiki)

[Julio Jerez]

what value for aspect ratio should we use for it to work as before? what does the ratio mean? (so i can add the new info it to wiki)

if you pass a value larger than 1000, and it will bypass it.
any value will be clamped betwenn 10 and 1000,
10 will make bloaded the mesh, 100 or bigger seems to be a good value.

the ratio is a measured of how oblong the face is.
It is calculated as the ratio bewteen the largest axis divided by the shortest axis of the OBB of the face.

[Julio Jerez]

I am thinking about the and the more I think the less I like the idea of the aspect ratio.
Delfy and rvangaal pleas ignore 2.20
This saturday I will re work that as fallow.
I will save the max face size as data member of each face. then in the contact solver I will add a Bin click routine that will make sure excessive parts of a face are clipped with the face is teacher from the collision tree.

I have sevaral reason for this.
-The nopnbe of bad face is always realisably small.
- Clipping is always proportional to the face area, and sine face can be very large, this leads to very large trees wish increases the queries time unnecessarily.
- I so not have a good metric to determine a good aspect ratio, and fix aspect ratio can still leave faces that can be too big compares to a small colliding shape, and also too large compared to large colliding face.
a Bin clipping can adjust routine to the side of the colliding shape and the face size

- an Bin clipping routine will be much faster than letting large faces in the collision tree.
the reason for this is that contact solver is a Gradient decent algorithm. basically it build a partial convex hull of the two faces,
by using the Minkousky difference of two convex shape
Minkousky difference of two convex shape is another convex shapes, so searching for a contact is nothing but a steeper decent search in a convex shape.
Here is the problem, when the sizes of the two shape are very different, say one is very big and the other is very large,
and if the very large have a very too oblond, what you get is a shape with very large flat faces,
the minkousky sum is very close to the shape of the large collision shape and it should be convex,
however the problems is that since the other shape is too small the contributions to the resulting mink convex are also very small.

The vertices of the Mink shape are created by subtractiing very large values from very small values,
and because of the lost of precision it just happen that the steeper decent rules breaks down,
by this I mean there are surfaces in the Mink shape that are not longer flat convex,
instead they have small perturbation and the search terminate in a local minima.
When the search terminate in a local minima we get what Rvangaal is seeing, a collision penetration or even an explosion.

However this is not the worse, the worse is that the collision becomes many time over slower.
This is because the combined Mink shape have very litle gradients and each step in the search for the lowest
point do not make good progress, it just decend a to a vertex that is just a little lower than the previous.

To make and comparison for two normal shapes the inner look for the closest point that about 6 to 11 iterations
when the two shapes collide the first time, after that if the faces move very litle from the previous frame it takes from
2 to 6 iterations, a box resting on a plane usually find the minimum in 1 or 2 iterations after the first collision.

when the aspect ratio is over 100, then the number of iteration goes as high as 128,
and this is because the inner loop bail out at that number and from there is uses and alternate algorithm.
when minum point is found found it is usually 40, 60, or even 80 iterations, and ther is not quaretee thsi si a teh lower point,
it could be a local minimal.

so if I can clip the face using a Bin that originates at the center of the colliding shape parallel
to the face normal and cut the polygon around, then this will guarantee that the two faces will be more or less equal sized,
and the steeper decent method will terminate in less than 10 iterations.
It is my believe that this will make the collision system way more reliable.

I am taking 2.20 down.

[JernejL]

Julio: just because we are currently talking about collision trees, is there any chance we could get to adjust the face optimization tollerance values? there's few cases where straight contigous flat polygons do not get optimized and merged - for example a straight slope made of separate quads, but going along same plane, i can provide a screenshot if you wish.

[Julio Jerez]

I have seem that too, and soem tiem I wonder if I can make better parttions.

... for example a straight slope made of separate quads, but going along same plane, i can provide a screenshot if you wish.

can you show screen shot yes.

The problem is that tolerances for collision are very, struct. tow face many be coplanar with normal sthat only difren in less than one ten of a degree.
however that small deviation of the plane normal may cause that point in one extreme of the plane many not lie in the average plane normal of the combined face.
if we allow for a tolarance anithing bigger than almost the machine precisi It may get better convex paratition mesh but bad collision faces.

Anyway let me work of these three problem I am fixing now and let us see if we can work on that after.
I remember there were some bug before and we got mush better mesh, so maybe we can do the same again.

[JernejL]

It is hard to see so i marked the entire area, while the map is made of cubes of different shapes totally flat ground is very well optimized by newton, however the straight sloped areas like this don't optimize properly, you can see it did optimize the vertical strips, the side triangle, but not the entire top surface (marked red), which is essentially flat plane.

It's optimized well enough for me, but it would be really nice if sloped areas could be improved.

[Julio Jerez]

yes I agree, after I implement the beam clipping there will be not more problems with face size limit, so we can optimize out to the maximun.

[Julio Jerez]

Here's my results:

- calling NewtonTreeCollisionEndBuild(geom,maxAspect,0); and saving the tree gives different results depending on 'maxAspect'; one time I had 1200Kb, then 1700Kb. It was consistent but depends on the aspect. Did you add splitting of polygons if they had a large aspect ratio? Older tree saves for this track were ~500Kb for unoptimized, 250K for optimized.
- using optimize still gave problems unfortunately. I should try to paint the collision tree triangle normals to see if that isn't the problem. Unoptimized the tree still collides fine.

Strange...

Ok Rvangaal, I made teh change and I believe it is very good now. I think collison with big faces is more stable and the end application do not have to do anything.
You do need to re serialize any previuslly saved collision trees.

The reason I know is that this is much better solution is that, in my debug build I did not see any call to the Fallback solver solution with the test mesh you sent my.
The collision solver managed to get the contacts in the primary solver. Plus the number of passes was always kept under 10.
The good thing is that regular and small size faces do not get affected by this optimization at all, so all in all is a big win in all count.
I hope this solves that dreaded bug, that was bodering me for a long time.

[JernejL]

I got the 2.20, it also loaded original serialized trimeshes without re-serializing, and new serializing seems to work a bit faster now aswell, but i see no improvements in optimizing sloped flat surfaces.

[Julio Jerez]

The optimization of convex shpe is not in yet, I am leaving that for 2.21
I am focus on the speed of building to down and bottom up collision trees, the correct contact calculation when collision tree have large faces, and see if teh contact direction are consistent when calculation cotact with compound and trees.
after that I will check out the glich in the optimization fo make lareg convex faces.
that vestion 2.20 only have the the correct contact calculation when collision tree have large faces, whic is teh most critical of thos ebugs.

also even the pre serialize tree load and work, you should re-serialize them form the source the new feature take place.
by this I mean rebuild the mesh using Create, begin, add face, end

[rvangaal]

Ok, thanks. I still seem to have the problem here, but I'll have to look into that later, perhaps I'm not feeding triangles correctly.
I have a week on a trip now so more later...

[Julio Jerez]

I do not think you are passing the triangle wrong, because that does not explain why the other levels with more regular meshes are working.
It may be something else also related to large faces. Maybe ray casting or convex cast. Faces with extreme aspect ratio are plain nasty to deal with.
If you still have the problems, I think the best way to debug it, is by me having a test demo I can play to see where the crash is happening.

The fix that clips large faces, is a good one it mades the engine more robust, stable, and even run faster when those large faces are encountered.
It does that at zero cost when colliding with small faces, and it does not add extra memory to the mesh.
when I made the fix I verified that the contact solver find the contacts with large faces 100% in all test I runned with your sample mesh.
Without clipping faces it fails in almost 1 out of 30 checks and it uses the Contact fallback solver to recover, It is the fallbak contact solver that fail sometime.

can you send me a running demo so that I can see what could it be?

[rvangaal]

One thing I noticed today while investigating NaNs appearing in body vs tree collisions, is that I at some point added a double-sided face triangle for each unculled triangle. In code:

if(triangle is not culled)
{
add regular triangle to collision mesh
flip triangle
add flipped triangle to collision mesh
}

This gives the problem that when hitting the collision mesh with my car collision mesh, things go bad and I get NaN in my car's body position (obtained from Newton). Probably a zero somewhere in calculating the distance between the 2 colliding triangle, which are at exactly the same location.
Detecting that situation might be useful. Also, while optimizing the collision tree, if you could detect triangles that are in the same spot (3 vertices matching another 3 vertices, not necessarily in the same order though!) that would help in finding these problems.

Not adding the flipped triangle to the collision mesh fixes the NaN problem. I'm going to try adding a small offset over the triangle's normal (to avoid our 3D modeler having to redo the track to make volumes).