Real-Time Physics Simulation Forum

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-31T20:35:42+00:00

I am glad you like those. Maybe I should give a breakdown talk how to model joints using constraints next year. Similar to the contact talk last year.

I had a look at a video of Supraleiter. This looks great! Good luck with your project!

Statistics: Posted by Dirk Gregorius — Sun May 31, 2015 8:35 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T23:48:44+00:00

By the way, your slides about Rubikon and physics generally, which I could find, were really a great help for me, to design my new physics engine with a right architecture this time, so that this physics engine now is not more faulty designed, in contrast to my last previous physics engines, which I've wrote since 2007.

My new physics engine should be otherwise complete so far, it has one-shot full contact manifold based base-shapes (Spheres, capsules, convex hulls, as you did described it in your slides), static triangle mesh BVH shapes (where the mid phase generates triangle convex hull shape broadphase contact pairs, in a efficient way, together with caching without unnecessary memallocs/memfrees), dynamic AABB tree broadphase, working island-based multithreading (except at the TOI stuff, since at least the Box2D-style approach must be strictly serial, but maybe I should try the Time Warp approach later, for to be able to parallelize it), QuickHull-inspired convex hull generation (with a optional option to limiting of count of the maximal convex hull points like at StanHull), raycasting, and so on, where really only one important thing is missing yet: joint constraints, but the first most important basic joint constraints should be implemented quickly, I think. At least, the almost empty joint constraint base class (for derivation to real joint constraint classes) is already implemented.

And then, I will remove my old (really super buggy) physics engine from my current game project Supraleiter, and replace it with my new physics engine. I hope that I can get with my new physics engine the wipeout-like ship physics behavior as fast as possible again so well back.

Statistics: Posted by BeRo — Sat May 30, 2015 11:48 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T22:12:54+00:00

Congratulations! I am glad you figured it out

Statistics: Posted by Dirk Gregorius — Sat May 30, 2015 10:12 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T19:03:13+00:00

So it seems, ihat i have found the real issue now. It was my GJK implementation, which was faulty (probably due to over optimization), so I've rewrote my GJK code from scratch now, with which my Bilateral advancement implementation seems to be working now. And as bonus, my new GJK code seems to be even up to 3x faster in my stress benchmarks.

Hopefully this fact just does not deceive, that it works now, but I will see it in later testing that it actually does always work properly. Keep your fingers crossed for me that it is indeed the case now

But to answer your question anyway:

I do it more or less as in Box2D, ie

GJK-Feature-initialization:

Code:

 // c-style pseudo code // Vertex-vertex Transform VerticesA[0] and VerticesB[0] into worldspace Axis = normalize(VerticesB[0] - VerticesA[0]); Mode = sfmVERTICESinWORLDSPACE; // Vertex-edge Transform VerticesA[0] into B local space  Axis = normalize(VerticesB[1] - VerticesB[0]); LocalPlane.Normal = normalize(cross(cross(Axis, VerticesA[0] - VerticesB[0]), Axis)); LocalPlane.Distance = -dot(Plane.Normal, VerticesB[0]); SeparationFunctionMode = sfmLOCALSPACEofB; // Vertex-face Transform VerticesA[0] and VerticesA[1] into B local space  Axis = normalize(cross(VerticesB[0] - VerticesB[1], VerticesB[2] - VerticesB[1])); LocalPlane.Normal = (dot(Plane.Normal, VerticesA[0]) < 0.0) ? -Axis : Axis; LocalPlane.Distance = -dot(Plane.Normal, VerticesB[0]); SeparationFunctionMode = sfmLOCALSPACEofB;. . . // Edge-Edge Transform VerticesB[0] and VerticesB[1] into A local space  eA = VerticesA[1] - VerticesA[0]; eB = VerticesB[1] - VerticesB[0]; Axis = normalize(cross(eA, eB)); LocalPlane.Normal = (dot(Plane.Normal, eB - eA) < 0.0) ? -Axis : Axis; LocalPlane.Distance = -dot(Plane.Normal, VerticesB[0]); SeparationFunctionMode = sfmLOCALSPACEofA;. . .

FindMinSeparation:

Code:

// real copy&pasted but by hand reformatted object-pascal code, since my personal object-pascal code-formatting-style is densefunction Evaluate : single; forward;function FindMinSeparation : single;begin  case SeparationFunctionMode of    sfmVERTICESinWORLDSPACE : begin      WitnessPoints[0] := Shapes[0].GetLocalFeatureSupportVertex(                                       Shapes[0].GetLocalFeatureSupportIndex(                                          Vector3TermMatrixMulTransposedBasis(Axis, Transforms[0])));      WitnessPoints[1] := Shapes[1].GetLocalFeatureSupportVertex(                                       Shapes[1].GetLocalFeatureSupportIndex(                                          Vector3TermMatrixMulTransposedBasis(Vector3Neg(Axis), Transforms[1])));    end;    sfmLOCALSPACEofA : begin      WitnessPoints[1] := Shapes[1].GetLocalFeatureSupportVertex(                                      Shapes[1].GetLocalFeatureSupportIndex(                                        Vector3Neg(                                          Vector3TermMatrixMulTransposedBasis(                                            Vector3TermMatrixMulBasis(Axis, Transforms[0]), Transforms[1]))));    end;    sfmLOCALSPACEofB : begin      WitnessPoints[0] := Shapes[0].GetLocalFeatureSupportVertex(                                      Shapes[0].GetLocalFeatureSupportIndex(                                        Vector3Neg(                                          Vector3TermMatrixMulTransposedBasis(                                            Vector3TermMatrixMulBasis(Axis, Transforms[1]), Transforms[0]))));    end;  end;  result := Evaluate;end;

Evaluate:

Code:

// also again real copy&pasted but by hand reformatted object-pascal codefunction Evaluate : single;begin  case SeparationFunctionMode of    sfmVERTICESinWORLDSPACE : begin      result := Vector3Dot(Axis,                           Vector3Sub(Vector3TermMatrixMul(WitnessPoints[1], Transforms[1]),                                      Vector3TermMatrixMul(WitnessPoints[0], Transforms[0])));    end;    sfmLOCALSPACEofA : begin      result := PlaneVectorDistance(LocalPlane,                          Vector3TermMatrixMulInverted(Vector3TermMatrixMul(WitnessPoints[1],                            Transforms[1]), Transforms[0]));    end;    sfmLOCALSPACEofB : begin      result := PlaneVectorDistance(LocalPlane,                          Vector3TermMatrixMulInverted(Vector3TermMatrixMul(WitnessPoints[0],                            Transforms[0]), Transforms[1]));    end;    else begin      result := 0.0;      Assert(false);    end;  end;end;

Statistics: Posted by BeRo — Sat May 30, 2015 7:03 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T18:16:24+00:00

I use variant 2. I don't understand variant 1. If you have Edge/Face or Face/Face every vertex of the edge/otherFace has the same distance to the reference face. I think averaging might be fine as well, but not sure if this solves any problem

How are you evaluating the separation function? In Box2D b2SeparationFunction::FindMinSeparation(). Maybe a specific example.

Statistics: Posted by Dirk Gregorius — Sat May 30, 2015 6:16 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T17:29:40+00:00

IIRC point most penetrating, since that is what we'll want to drive towards 0 penetration with the root solver.

Statistics: Posted by RandyGaul — Sat May 30, 2015 5:29 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-30T14:40:01+00:00

May I ask, how do you reduce these Edge/Face and Face/Face cases to a Vertex/Face case?

by picking the to-the-face-nearest Edge/OtherFace vertex as vertex?
or by picking simply the first (or a random) Edge/OtherFace vertex as vertex?
or by averaging the Edge/OtherFace vertices to a average Edge/OtherFace midpoint vertex?

I myself am doing so far the first here listed approach, but is it also a halfway correctly approach? But I could also imagine, that this approach would be unnecessary, because all vertices of the edge or other face are already on the same face plane side, since the shapes are not (yet) in a overlapping configuration, so that the second here listed approach can be used here also, right?

Statistics: Posted by BeRo — Sat May 30, 2015 2:40 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-29T20:57:26+00:00

I only have Vertex/Vertex, Vertex/Edge, Vertex/Face and Edge/Edge. Edge/Face and Face/Face are handled as Vertex/Face. This makes the dispatch easy.

No, I would not add this to GJK. I personally keep my GJK as simple and clean as possible. Especially since the dispatch is trivial.

Statistics: Posted by Dirk Gregorius — Fri May 29, 2015 8:57 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-29T19:28:13+00:00

I just enumerated the possibilities with some if-statements and a switch. Perhaps this might add some value to the discussion: http://pastebin.com/WAHSnRqw

Also Dirk, I'm curious if you know if anyone has ever placed feature extraction into GJK itself. It seemed to me to be a little silly to do this after GJK was finished, since it could be added into the internals of GJK without much fuss. I didn't try this, just an idea.

Statistics: Posted by RandyGaul — Fri May 29, 2015 7:28 pm

Re: Bilateral advancement 3D GJK feature extraction problems

2015-05-28T21:27:17+00:00

I look at the vertex count of the simplex and also the unique count as you describe:

Code:

int VertexCount = Cache.VertexCount.int UniqueCount1 = rnUniqueCount( Cache.VertexCount, Cache.Vertices1 );int UniqueCount2 = rnUniqueCount( Cache.VertexCount, Cache.Vertices2 );

Then I dispatch as follows:

Code:

if ( VertexCount == 1 ) -> Vertex/Vertexif ( VertexCount == 2 )    if ( UniqueCount1 == UniqueCount == 2 ) -> Edge/Edge    if ( UniqueCount1 == 1 ) -> Vertex/Edge    if ( UniqueCount2 == 1 ) -> Edge/Vertex    // ...

The tricky part is edge/edge. If you separation function is defined by two edges you need to be careful. You can use a fixed plane as in the vertex/vertex case. This is safe, but can be too slow. If you use the cross product of the edges you need to take special care that the edges don't cross over each and the normal direction flips. The edge/edge case makes the problem difficult since the function is not convex. You also need to make sure that the axis has the correct orientation. E.g. say you have vertices a1, a2 and b1, b2.

Code:

rnVector3 EdgeA = rnNormalize( VertexA2 - VertexA1 );rnVector3 EdgeB = rnNormalize( VertexB2 - VertexB1 );rnVector3 Axis = rnCross( EdgeA, EdgeB );if ( rnDot( VertexB1 - VertexA1, Axis ) < 0.0f ){Axis = -Axis;EdgeB = -EdgeB;}

Besides you also need to watch out for degenerate edge and faces. You want to catch this ideally in the resource compiler, but at least assert for a reasonable health topology.

HTH,
-Dirk

Statistics: Posted by Dirk Gregorius — Thu May 28, 2015 9:27 pm