>>>> I'm trying to find a good way to determine if a polygonal hull

>>>> (quads or tris) is convex or not.

>>>> I first thought about comparing the angle between adjacent polygon

>>>> normals.

>>>This is exactly the right approach, except that you do NOT want to

>>>actually compute angles. Instead, you should just compute the dot

>>>product of the outer normal vectors of every pair of adjacent facets.

>>>If any dot product is negative, the polyhedron is not convex. (The

>>>inner normals will also work, but be consistent!)

>>Wrong. It is quite easy to construct a convex polyhedron in which the

>>normals of some adjacent face pairs have negative dot product. For

>>example a wedge in which one of the inner dihedral angles is less than

>>90 degrees.

> That's correct.

> One easy solution is to compute the barycenter (the average of

>all the vertices) and make sure it is inside every face.

I don't think this is correct either. True, if the barycenter is on

the out side of some face plane then the polyhedron is indeed

nonconvex, BUT I can easily visualize a nonconvex polyhedron for which

the barycenter of the vertices is on the in side of every face plane.

For example, take a cube and modify it by replacing each square face

with four triangles each with a base edge equal to an edge of the cube

face and having a common apical vertex which is a point displaced

slightly inward from the center of that cube face.

Generally, you cannot tell a lot about the global properties (such as

convexity) of a polyhedron from moments (such as barycenter) of the

vertices, because you can always modify the polyhedron by adding lots

of vertices in different small regions, thus drastically changing

moments without affecting the global properties.

Quote:>...

> If you really need to check edges for convexity, you can use

>the fact that the cross product of two plane normals is a vector

>collinear with the line formed by the intersection of the two planes.

>If you have all your edges uniformly ordered

>(i.e. all faces can be traced "clockwise"), and edge vectors for

>all edges,

> k = (p1normal ^ p2normal) * edgevector;

>will give you a value which will be negative for concave edges.

>(Here, "^" is the cross product and "*" is the dot product.)

This doesn't make sense to me either, because (in a non-pathological

polyhedron, such as a manifold) each edge belongs to two faces and is

oppositely oriented by the "clockwise" ordering of the two faces it

belongs to. Your formula does not tell me which of the two senses of

"edgevector" to use. They are equally valid but will give different

signs to k.

Ron

******************************************************

Dorian Research, Inc.

Berkeley, CA

(510)-704-9115

http://www.dorianresearch.com

Everything should be made as simple as possible,

but not simpler.

--Albert Einstein

*****************************************************