Bilateral advancement 3D GJK feature extraction problems
-
- Posts: 8
- Joined: Fri Apr 17, 2015 5:50 am
- Location: Moenchengladbach, Germany
Bilateral advancement 3D GJK feature extraction problems
Now my second question regarding CCD, where now the first SAT question was answered here
The second question is, what at my bilateral advancement implementation is wrong (doesn't work correctly), may especially the GJK feature extraction code part of it, where I believe, that because the problem lies in it. The optional alternative question would be, if somewhere there is an open source 3D bilateral advancement reference implementation with complete correct working GJK feature extraction etc., since Box2D has only a implementation for the 2D case.
My GJK-based conservative advancement implementation as a comparison debugging algorithm works almost flawlessly (except in some rare cases), but BA is more optimal than CA, so that I do want get my BA implementation correctly working.
My almost working conservative advancement code => http://pastebin.com/RkDUU6EK (Video with it in action with a 15 Hz physics rate as test case: https://www.youtube.com/watch?v=jZpN5DvXdRs)
My not working bilateral advancement code => http://pastebin.com/G2y7KkR8 (Video with it in action with a 15 Hz physics rate as test case: https://www.youtube.com/watch?v=YVzDtKzJzVI)
My GJK code in two variants (one without simplex support vertex ID storing for CA, and one with simplex support vertex ID storing for BA) => http://pastebin.com/Lr5nxbXu
I will push my physics engine as open source on GitHub under a BSD/MIT-style license, so far when the physics engine is ready and when the physics engine is used successfully in my game called Supraleiter (for more infos => https://www.youtube.com/playlist?list=P ... nsC4UoaC4-).
Thank you in advance
The second question is, what at my bilateral advancement implementation is wrong (doesn't work correctly), may especially the GJK feature extraction code part of it, where I believe, that because the problem lies in it. The optional alternative question would be, if somewhere there is an open source 3D bilateral advancement reference implementation with complete correct working GJK feature extraction etc., since Box2D has only a implementation for the 2D case.
My GJK-based conservative advancement implementation as a comparison debugging algorithm works almost flawlessly (except in some rare cases), but BA is more optimal than CA, so that I do want get my BA implementation correctly working.
My almost working conservative advancement code => http://pastebin.com/RkDUU6EK (Video with it in action with a 15 Hz physics rate as test case: https://www.youtube.com/watch?v=jZpN5DvXdRs)
My not working bilateral advancement code => http://pastebin.com/G2y7KkR8 (Video with it in action with a 15 Hz physics rate as test case: https://www.youtube.com/watch?v=YVzDtKzJzVI)
My GJK code in two variants (one without simplex support vertex ID storing for CA, and one with simplex support vertex ID storing for BA) => http://pastebin.com/Lr5nxbXu
I will push my physics engine as open source on GitHub under a BSD/MIT-style license, so far when the physics engine is ready and when the physics engine is used successfully in my game called Supraleiter (for more infos => https://www.youtube.com/playlist?list=P ... nsC4UoaC4-).
Thank you in advance
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
Do you expect us to read your code and find the bug for you? If you ask some concrete question I might be able to help.
-
- Posts: 8
- Joined: Fri Apr 17, 2015 5:50 am
- Location: Moenchengladbach, Germany
Re: Bilateral advancement 3D GJK feature extraction problems
No, but I thought the basic question would be clear.
Primary, what is the correct way to extract the features of a 3D GJK simplex, ie Vertex-Vertex, Edge-Vertex, Face-Edge, Face-Vertex, for usage in Bilateral Advancement.
I'm already storing the vertex indices (in addition to the normal 3D vectors, for to avoid relookups of support vertices from arrays) of the found support points in the simplex, where I do the following then in my Bilateral Advancement implementation for to extracting the features from the GJK termination-state simplex:
1. if all support vertex indices are respectively equal on A and B in the simplex with a typical size of one point => Vertex-Vertex feature
2. if two support vertex indices are different on A but all equal on B in the simplex with a typical size of two points => Edge-Vertex feature
3. if two support vertex indices are different on B but all equal on A in the simplex with a typical size of two points => Vertex-Edge feature
4. if three support vertex indices are different on A but all equal on B in the simplex with a typical size of three points => Face-Vertex feature
5. if three support vertex indices are different on B but all equal on A in the simplex with a typical size of three points => Vertex-Face feature
6. if three support vertex indices are different on A and two different on B in the simplex with a typical size of three points => Face-Edge feature
7. if three support vertex indices are different on B and two different on A in the simplex with a typical size of three points => Edge-Face feature
8. if all three support vertex indices are different on A and B in a simplex with the typical size of three points => Face-Face feature
9. if the simplex has four points => ignore and abort
but my GJK simplex feature extraction implementation does not seem to be working, at least not at my Bilateral Advancement implementation, which otherwise follows the Box2D implementation.
So is it the correct way for to extract the features from a GJK termination-state simplex in the 3D case?
More specific questions will follow, when this first part by the question is answered.
Primary, what is the correct way to extract the features of a 3D GJK simplex, ie Vertex-Vertex, Edge-Vertex, Face-Edge, Face-Vertex, for usage in Bilateral Advancement.
I'm already storing the vertex indices (in addition to the normal 3D vectors, for to avoid relookups of support vertices from arrays) of the found support points in the simplex, where I do the following then in my Bilateral Advancement implementation for to extracting the features from the GJK termination-state simplex:
1. if all support vertex indices are respectively equal on A and B in the simplex with a typical size of one point => Vertex-Vertex feature
2. if two support vertex indices are different on A but all equal on B in the simplex with a typical size of two points => Edge-Vertex feature
3. if two support vertex indices are different on B but all equal on A in the simplex with a typical size of two points => Vertex-Edge feature
4. if three support vertex indices are different on A but all equal on B in the simplex with a typical size of three points => Face-Vertex feature
5. if three support vertex indices are different on B but all equal on A in the simplex with a typical size of three points => Vertex-Face feature
6. if three support vertex indices are different on A and two different on B in the simplex with a typical size of three points => Face-Edge feature
7. if three support vertex indices are different on B and two different on A in the simplex with a typical size of three points => Edge-Face feature
8. if all three support vertex indices are different on A and B in a simplex with the typical size of three points => Face-Face feature
9. if the simplex has four points => ignore and abort
but my GJK simplex feature extraction implementation does not seem to be working, at least not at my Bilateral Advancement implementation, which otherwise follows the Box2D implementation.
So is it the correct way for to extract the features from a GJK termination-state simplex in the 3D case?
More specific questions will follow, when this first part by the question is answered.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
I look at the vertex count of the simplex and also the unique count as you describe:
Then I dispatch as follows:
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.
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
Code: Select all
int VertexCount = Cache.VertexCount.
int UniqueCount1 = rnUniqueCount( Cache.VertexCount, Cache.Vertices1 );
int UniqueCount2 = rnUniqueCount( Cache.VertexCount, Cache.Vertices2 );
Code: Select all
if ( VertexCount == 1 ) -> Vertex/Vertex
if ( VertexCount == 2 )
if ( UniqueCount1 == UniqueCount == 2 ) -> Edge/Edge
if ( UniqueCount1 == 1 ) -> Vertex/Edge
if ( UniqueCount2 == 1 ) -> Edge/Vertex
// ...
Code: Select all
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;
}
HTH,
-Dirk
-
- Posts: 43
- Joined: Mon May 20, 2013 8:01 am
- Location: Redmond, WA
Re: Bilateral advancement 3D GJK feature extraction problems
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.
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.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
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.
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.
-
- Posts: 8
- Joined: Fri Apr 17, 2015 5:50 am
- Location: Moenchengladbach, Germany
Re: Bilateral advancement 3D GJK feature extraction problems
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?
-
- Posts: 43
- Joined: Mon May 20, 2013 8:01 am
- Location: Redmond, WA
Re: Bilateral advancement 3D GJK feature extraction problems
IIRC point most penetrating, since that is what we'll want to drive towards 0 penetration with the root solver.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
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.
How are you evaluating the separation function? In Box2D b2SeparationFunction::FindMinSeparation(). Maybe a specific example.
-
- Posts: 8
- Joined: Fri Apr 17, 2015 5:50 am
- Location: Moenchengladbach, Germany
Re: Bilateral advancement 3D GJK feature extraction problems
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:
FindMinSeparation:
Evaluate:
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: Select all
// 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;
. . .
Code: Select all
// real copy&pasted but by hand reformatted object-pascal code, since my personal object-pascal code-formatting-style is dense
function 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;
Code: Select all
// also again real copy&pasted but by hand reformatted object-pascal code
function 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;
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
Congratulations! I am glad you figured it out
-
- Posts: 8
- Joined: Fri Apr 17, 2015 5:50 am
- Location: Moenchengladbach, Germany
Re: Bilateral advancement 3D GJK feature extraction problems
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.
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.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bilateral advancement 3D GJK feature extraction problems
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!
I had a look at a video of Supraleiter. This looks great! Good luck with your project!