Testing For Concave Mesh

#1 If any collision mesh you were using was concave, you'd get an error message. If you post a screenshot of what you're doing, it might be easier to say whats wrong.

#2 True, but that raises an interesting question. How DO you tell if a mesh is concave/convex?

I can think of one way, but seems Terribly Inefficient:

For every triangle:
Every vertex should be co-planer or "behind" that triangle's plane.

I'm pretty sure that would work, but it's O(n^2). Yuck. Is there a better way? Computing dot-products isn't all that expensive, but still...

#3 Just a thought

for every triangle:
   calulate its normal Tn
   for every neithbour triangle
        calculate its normal Nn
        if angle between  Tn and Nn < 180 degrees
             break ; its concave

Have no idea if it works or if its better ;)

#4 Given some pre-computed adjacency information, that sounds like it would be much more efficient. O(n) instead of O(n^2). Generating the adjacency information however sounds like a O(n^2) operation... So if you already had it, great. If not? Not so much.

It just occured to my WHY convex collisions are more efficient. A point is inside the convex object if it is behind all the triangles' planes. That's still a O(n) test though. I suppose you could break the object up into its own BSP tree to speed things along... but I thought BSP's only decomposed things down to convex objects anyway... Humph.

--Mark

"It's all so clear to me now" --Ren Hoek, "Space Madness"

#5 Heheh,...Roland... Had the same idea myself : )

@Mark : DTS objects allow concave meshes - that's why you should limit the mount of DTS shapes on screen at the same time and use LOD on them.

If youre talking about DIF shapes, the the method described by Roland could be really good, just get the normals of adjacent planes and see if they cross. If so, you have a concave that's ilegal and wont export. This could be easely done at export time, and not at run time, making it much more efficient.

#6 ..the above guys said it in code already! ...
here it is in the simplest terms i have heard it

"if a face continued on would it cut into the one beside it?"

a shape is convex aslong as it doesnt have 2 adjacent (side-by-side) faces at an angle greater then 180 degrees... or less then depending on which way you look at it

2 faces flat beside each other is ok... even 1 degree of dip and its convex...
there can be issues with invisible edges needing turning from time to time but thats generally for sphere collision objects

(sorry if you knew all the above!)


my little titbit is try using plain ol boxes, no skewing.. see if you have the same problem
if you dont atleast you know its the skewing thats the problem
simple..no?