Sign in to follow this  

Inflat/Deflate convex shape for gjk core shapes

Recommended Posts

Hi people, I've been working on my physics engine. I recently do a performance testing of each integration steps (broadphase, narrowphase, solver, etc), and found out that the narrowphase took the most out of execution time. I thought it was reasonable because I simply use EPA to generate contact point. Now most presentation of physics for games that I read suggest using gjk + core shapes to generate contact point. I already have the gjk part implemented nice and sound. Now, how do I inflate/deflate the convex shapes though? scaling by its center would result in non-uniform scale, that is, the distance of the "inflated" to the core shape is non-uniform. Here's a picture showing the non-uniform scaling problem.

 

inflate_convex.pngthe green box is the core shape, the red one is the inflated shape, scaled up to 1,5x. but now the distance between the core and the inflated one is non uniform (Here, dX should equal dY!). I've been thinking of how to solve this, but to no avail. How would I generate the inflated shape based on the core shape + margin?

Share this post


Link to post
Share on other sites

In order to inflate/deflate the shape you need to push the face planes outside/inside. Then you have to rebuild a new hull from these planes. There exist a couple of algorithms to compute a polygonal mesh from a set of planes but I like doing this in dual space the most. Sounds complicated, but is very easy:

 

1) For each face divide the normal by the plane offset plus/minus your margin and save that point

2) Build the convex hull of these points (this is dual)

3) We now need to go back to primary space and do exactly the same (essentially build the dual of the dual). For each face of the dual divide the face normal by the plane offset (no adjustment this time) and save that point

4) Build the convex hull of these new points which is your inflated/deflated shape 

 

There is one gotcha though. The origin must be contained in the initial hull. Since you have the vertices this is trivial and you can simply shift the shape and reapply the inverse translation after you are done.

 

Don't get worried about the fancy naming. It is very simple and if you draw it for a simple shape you can see very easily how this works. 

 

HTH,

-Dirk

Share this post


Link to post
Share on other sites

Uh... Hi Mr. Gregorious, happy new year!! Btw I can't seem to follow the dual space thingy. I've been reading the article at wikipedia, but aaghh, I just don't understand. I can push the faces inside by specified margin, this will result in faces that is overlapping with each other, as shown in these pictures:

 

cl1.pngcl2.pngthe red is the original convex shape, the light blue one is with the face "pushed in" along its normal as far as the specified margin. Is this what you mean at step 1? I reckon you meant to push the faces back by dividing the normal plane +/- margin? but at step 2 you said to build convex hull? doesn't that mean step 1 should produce clouds of points? ugh, I got confused....can you maybe...show some pictures? sorry if I bother you.

Share this post


Link to post
Share on other sites
My algorithm for inflating the shape involves linear algebra, and consists of extruding the vertex such that the extruded vector dotted with the normal of all the faces that share threat vertex yields the inflated distance.

So, if a vertex has is shared by two faces with vertex normals n1 and n2 corresponding to these faces (face1 and face2), then the algorithm I solve is as follows.

( Alpha * n1 + Beta * n2 ) dot n1 = dist
( Alpha * n1 + Beta * n2 ) dot n2 = dist

Rearrange it and we get:
[ n1 . n1, n2 . n1 ] * [ Alpha = [ dist, dist ]
[ n2 . n1, n2 . n2 ] Beta ]


After I've solved the matrix, my new extruded point is vertex position + Alpha * n1 + Beta * n2.

Share this post


Link to post
Share on other sites

Mr. Vernon, Happy New Year to you as well! :)

 

Say we have convex hull. You can describe a convex hull as a polygonal mesh or as a set of planes. If you have a polygonal mesh you also have the set of planes (you can construct them from the face vertices or store them directly). The other way around this is not true. If you have only a set of planes you don't have any vertices or topology (faces and edges). The method I suggest is that we take the face planes and push them inside by the margin. Once we have done this we lost any vertices and connectivity. Essentially what you are showing in your images above. So we need to recover the vertices and topology. There are methods which clip any three planes and reconstruct vertices and faces from there, but these methods are very complex and numerical sensitive. If you look for Quake brushes or BSP you will find algorithms which can do this.

 

A better way to recover the polygonal mesh is the dual space approach I suggested above. Of course you can build a convex hull of  a set of points. What is less known is that you can use the same algorithm to also build the convex hull of a set of planes. You can even clip convex hulls by planes this way. This is what the dual space approach does I show above. I assume you have convex hull builder or you use QHull: https://github.com/qhull/qhull

 

The all you need to do is essentially:

// First pass to build dual and shift planes
std::vector< Vector3 > dual_vertices;
for ( all faces f of hull )
{
    Plane plane = f->plane;
    Vector3 vertex = plane.n / ( plane.d - margin ); // Only subtract margin in the first pass
    dual_vertices.push_back( vertex );
}

// Build the dual hull
Hull dual = BuildHull( dual_vertices);

// Second pass to recover new shrunk hull in primary space
std::vector< Vector3 > primary_vertices;
for ( all faces f of dual )
{
    Plane plane = f->plane;
    Vector3 vertex = plane.n / plane.d;
    primary_vertices.push_back( vertex );
}

// Recover hull in primary space which is the shrunken hull
Hull primary = BuildHull( primary_vertices );

The math *theory* might be non-trivial, but the algorithm itself is very easy. 

 

HTH,

-Dirk

 

PS:

I also gave a presentation on QHull which might be a good read in this context: http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

After tinkering a bit, I implemented iterative solution for this problem, and it worked nice! but perhaps non optimal, but since it's an offload process, it's fine. Anyway, here it is showing the "core shapes" + pure gjk for contact generation (at around 34 seconds mark)

https://www.youtube.com/watch?v=9D90eVB9Sg4

 

My algorithm for inflating the shape involves linear algebra, and consists of extruding the vertex such that the extruded vector dotted with the normal of all the faces that share threat vertex yields the inflated distance.

So, if a vertex has is shared by two faces with vertex normals n1 and n2 corresponding to these faces (face1 and face2), then the algorithm I solve is as follows.

( Alpha * n1 + Beta * n2 ) dot n1 = dist
( Alpha * n1 + Beta * n2 ) dot n2 = dist

Rearrange it and we get:
[ n1 . n1, n2 . n1 ] * [ Alpha = [ dist, dist ]
[ n2 . n1, n2 . n2 ] Beta ]


After I've solved the matrix, my new extruded point is vertex position + Alpha * n1 + Beta * n2.

Thanks for the reply! after toying a bit, I implemented the iterative version of this. Basically, each vertex has to satisfy a series of linear equation, and then I solve it using gauss seidel iteration.

 

Mr. Vernon, Happy New Year to you as well! :)

 

Say we have convex hull. You can describe a convex hull as a polygonal mesh or as a set of planes. If you have a polygonal mesh you also have the set of planes (you can construct them from the face vertices or store them directly). The other way around this is not true. If you have only a set of planes you don't have any vertices or topology (faces and edges). The method I suggest is that we take the face planes and push them inside by the margin. Once we have done this we lost any vertices and connectivity. Essentially what you are showing in your images above. So we need to recover the vertices and topology. There are methods which clip any three planes and reconstruct vertices and faces from there, but these methods are very complex and numerical sensitive. If you look for Quake brushes or BSP you will find algorithms which can do this.

 

A better way to recover the polygonal mesh is the dual space approach I suggested above. Of course you can build a convex hull of  a set of points. What is less known is that you can use the same algorithm to also build the convex hull of a set of planes. You can even clip convex hulls by planes this way. This is what the dual space approach does I show above. I assume you have convex hull builder or you use QHull: https://github.com/qhull/qhull

 

The all you need to do is essentially:

// First pass to build dual and shift planes
std::vector< Vector3 > dual_vertices;
for ( all faces f of hull )
{
    Plane plane = f->plane;
    Vector3 vertex = plane.n / ( plane.d - margin ); // Only subtract margin in the first pass
    dual_vertices.push_back( vertex );
}

// Build the dual hull
Hull dual = BuildHull( dual_vertices);

// Second pass to recover new shrunk hull in primary space
std::vector< Vector3 > primary_vertices;
for ( all faces f of dual )
{
    Plane plane = f->plane;
    Vector3 vertex = plane.n / plane.d;
    primary_vertices.push_back( vertex );
}

// Recover hull in primary space which is the shrunken hull
Hull primary = BuildHull( primary_vertices );

The math *theory* might be non-trivial, but the algorithm itself is very easy. 

 

HTH,

-Dirk

 

PS:

I also gave a presentation on QHull which might be a good read in this context: http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf

The quick hull!! it really helps tremendously in visualizing the CSO. Thanks for the share. But in the end, I yield to iterative solution, I'm gonna read your solution thoroughly later though!

 

Thank you for the link! gonna read em.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this