PxGeometryQuery::overlap/computePeneration failure case

[Zeblote]

I (or rather, players) have found a specific combination of convexes that causes overlap and computePeneration to return incorrect values. It is a rather cursed arrangement of shapes. Here is a recreation in blender.

These shapes cannot be separated by the planes of any of their faces. Compute peneration between them returns a value of exactly 0.449912 units. With some experimentation, I have determined that to be the following length:

Is this a bug or a limitation of the algorithm?

Can we do anything else to get an accurate result for these shapes?

[Zeblote]

It was a combination of two bugs. This fix gives me correct results for any shapes tested so far: https://github.com/Zeblote/PhysX/commit/e503c76357cb3775ea3ffa0497b6e1367dc3f64a

The problems: 1) The loop over edges in buildPartialHull made no sense and was skipping some of the edges. For example, with your method, for a polygon with 3 edges it would check edges between vertices 0->2, 2->0, 0->1. I've fixed the loop so now it properly tests 2->0, 0->1, 1->2 circle. 2) testEdgeNormal only checked for min overlap in one direction (poly1 higher than poly0 on axis) but special cases exist where you must also check in the other direction.

cc @PierreTerdiman because I see comments from you in the affected code

[PierreTerdiman]

Thanks. My name is in there but only because I modified the code at some point. I'll track down the original authors and check with them what's going on in that code.

[PierreTerdiman]

Would you have the vertex data for these two shapes, by any chance?

[Zeblote]

I should be able to dump the convexes and transforms from the game, will post them here in a bit

[kstorey-nvidia]

Thanks for reporting the issue. Looking forward to seeing the repro vertices. We've already found in some convex-mesh cases where we needed to consider both max0-min1 and max1 - min0, so I fully expect this will be required here as well.

However, I'm not clear about what was wrong with the original loop:

for (PxU32 iStart = 0, iEnd = PxU32(polygon.mNbVerts - 1); iStart < polygon.mNbVerts; iEnd = iStart++)

Running this through my head with a polygon with 3 vertices, I think this should produce the following states: iStart = 0, iEnd = 2 iStart = 1, iEnd = 0 iStart = 2, iEnd = 1

I haven't stepped through the code yet to confirm it does this, but I don't see how it gets us 0->2 then 2->0 because iEnd is assigned to iStart++.

Thanks

Kier

[kstorey-nvidia]

OK. I understand, the issue is that we should load iEnd rather than iStart into v0, and load iStart into v1. The loop itself is correct, but there is an incorrect optimization that tries to load only one vector.

[Zeblote]

Yeah, if changed to use both iStart and iEnd inside the loop it would make sense. Combined with reusing the vertex from the last iteration it doesn't, because then you get the effect where the second iteration reuses the iEnd from the last loop as the first index, so 2 -> 0.

I think my version that keeps the reuse and simplifies the loop is more readable / easy to understand, though.

[kstorey-nvidia]

Agree. I've made the same change locally. We don't need the iEnd index anymore unless we are loading both vertices inside the loop.

We don't have a regression test case where this code fails yet. I suspect this is because we use GJK/EPA in the contact gen, with this code only being used in the cases where the GJK/EPA code hits a degenerate case. This GJK/EPA implementation is pretty robust so we very rarely hit this code. The computePenetration code is probably the only code that hits this logic frequently.

[Zeblote]

I am using computePenetration to determine whether players are allowed to place bricks at a position. Bricks have integer positions on a grid and axis aligned rotations. I need it to guaranteed always return the exact same result for the same pair of bricks regardless of whether it's at pos = 0 or pos = 500000 or rotated.

So it will look up bricks that overlap the integer bounds in a custom data structure, then transform the query shape to be relative to the existing shape (still using integers only) and then call computePenetration, allowing it to be placed if penetration <= some epsilon value for all discovered bricks.

So this code runs millions of times for me - lots of room to discover edge cases and bugs!

I can't use overlap because there's a chance it may return true for two opposing wedges that touch each other but don't intersect by any meaningful distance. It seems like overlap actually uses a totall different algorithm.

[Zeblote]

A player reported a new failure case between two cursed wedges that my changes don't fix. So it's not done yet.

I still need to find some time to extract these and post them here.