Calculating convexity-- does this work?

[DOor]

Oh and I decided to compare my test with the 3DSmax reactor convexity test. For 90% of the tests we get the same results.


[EDIT] I think I just found the discrepancy. I was using floats to the nearest hundredth whereas Reactor was using much more precise floats. I stopped pruning my decimals and am now getting the same results as Reactor--

now, however, reactor says a cube exported from maya is concave. the angle calculated from my script reads 90.00000076 where that .00000076 causes a concavity. I guess my script works better than the Reactor convexity test.

[tbaypaul]

if you cross the two edges of a shared vertex of a single face...edge[0] X edge[1], then edge[1] X edge[2].........then take the dot product of those cross products and proceed in pairs to edge[i] X edge[i+1]. All the dot products will be either greater then 0 or less then 0 for all the edges....the very first "opposite" dot product value indicates a non-convex hull....this is assuming that your polygon is fairly planar and without holes....

Got this from "the Pleasures of Perp Dot Products" in Graphic Gems IV p.141....there is also "Testing the Convexity of a Polygon" p.7......

[gashworm]

Is there a reason why the polygon cleanup command wouldn't work? Using it to select all concave faces (polyCleanupArgList 3 { "0","1","1","0","0","1","0","0","0","1e-005","0","1e-005","0","1e-005","0","-1","0" };) you could then query the selection list (`ls -sl`) and if its empty continue with your export. that way the API does the heavy calculations instead of a mel script.

I've had a bit of a running battle with exporting meshes to a game engine and the fact that dae packers use a more crude way af triangulation than Maya. Since the data leaving maya will end up as triangles anyway the easiest solution is to trianglate everything in Maya before exporting to your game format. that way you can be assured that non convex polygons end up triangulated the right way.

[DOor]

@tbaypaul -- I see how that could work, but the problem with the edge method is that multiple edges branching from the same vert will cause this to become very slow.

@gashworm -- no, poly cleanup only detects concavity of the Face Components, not the convexity of the mesh's ShapeNode. The reason for this script is not for staticmeshes but rather for collision geometry for our breakable objects. For the most part it should be easy to Look at the collisions and make a visual check, but for some reason we still have artists moving verts the wrong way.


I know my script works. it does get slow with dense meshes. its not a big deal for the purpose we are using it for (very low poly collision geometry) but I am still working on a quicker method. here is another algorithm I heard about today:

well, if you want a very simple, not efficient algorithm, I had one idea.

For each triangle, check if all the other vertices are behind this triangle. If this holds true for all triangles, the polytope is convex. This check is simple to be made, pick the triangle normal n, any of the triangle vertices tv and other vertex v, then you get d = n.(v-tv). If d > 0, the polytope is concave. I didnt tested but makes sense, seems to work, but its very inefficient.


I thought about applying this but instead of checking each face with EVERY vert to instead check each face with the verts that make up the adjacent faces (kind of like what I do now.. except I just get the adjacent faces and use a point at their center)

[tbaypaul]

@tbaypaul -- I see how that could work, but the problem with the edge method is that multiple edges branching from the same vert

ah, I see, you are just testing for a "limit" of convexity on a poly object....I thought you testing "individual" polygon faces......big difference.....should have read a bit closer...

[DOor]

Ok so the new method I attempted seemed faster but I optimized my face method by getting ALL the face centers into a string array at the start of the script (rather than querying them as it ran-- this would mean querying center of adjacent faces multiple times.)

this has made the script run much faster, now I am just debating using the angle between the vectors to detect the concavity (as explained above) or using this new formula instead:

d = n * (pt2 - pt1); if d > 0 then there is concavity.

basically n is our normal vector still and pt1 and pt2 are the centers of each face (using the verts works too but it is slower as there are more verts than there are faces thus more calculating) the formula tells me if any of the faces are on the Wrong side of the face we are checking (by comparing it to the normal vector).


the speed increase of multiplying the vectors rather than finding the angle between them is not huge but now I am wondering which method will give me more accurate results.

[tbaypaul]

the speed increase of multiplying the vectors rather than finding the angle between them is not huge but now I am wondering which method will give me more accurate results.

They are one in the same.....the angle formula has the dot product, your....n*(pt2 - pt1)....in it.....

[AtrusDni]

Hey DOor, I have come across a similar issue and need to test whether or not the mesh is convex or concave. Would it be possible to post your script so I could dissect it?

[DOor]

Hey AtrusDni -- No problem. I added detectConcave.zip as an attachment.

The global procedure isConcave will return a boolean result (0 = all good, 1 = concavity detected). Most of the lines are commented but if you have any questions just let me know.

There are some lines commented out that I left in such as an adjustment for the precision of the test (right now I just drop all decimals, you could either use "floor" instead of "trunc" or you could leave 2 or 3 demicals for accuracy. I got better results just truncing all the decimals.)

gluck
elenerville

[AtrusDni]

Thanks a ton DOor! I will take a look at your code. I am working on a shatter script at the moment which uses the voronoi method to reconstruct the shattered shards of a mesh. I need to test whether a mesh is concave or convex because of the method im using to cut the shards. (uses a polycut command, then fill hole) but on concave meshes, sometimes after you cut the mesh, it will have multiple shells which maya cannot fill hole on. So if I can test for concave or convex mesh, it will determine if I need to boolean the mesh or go the faster route of just using poly cut.

Once I finish this part of the script, I think it will be complete and I will post the newer version into the "shatter help" topic. Thanks again!

[CGTalk Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.