[comp.graphics] Test for object concavity

mmiller@manyjars.SRC.Honeywell.COM (Mike Miller) (03/01/90)

Here's a problem I've been struggling with:

We have a 3-d object described by a linked list of edges.
We are trying to determine if the object is simply convex; in
order to do so, we have found a couple of tests which will
(we hope) find all non-simply convex objects.

What we have come up with so far is this:

The first test finds those cases where it is impossible to define
a plane which groups all the vectors from one vertex to its 
neighbors on the same side of the plane:

for all vertices
    find the sum of the vectors from the vertex to all adjacent
        vertices (the edge vectors)
for all vertices
    find the dot product of the resultant with each of the
        edge vectors
    if any of the dot products are negative, the object is
        not simply convex

since this test fails for some sets of edges, we have defined 
a second test which checks for inflection points on the
surface: 

for all vertices
    find the dot product of the resultant with the resultants
        at each adjacent vertex
    if any of the dot products are negative, the object is not
        simply convex.

We realize that this test is trivial if we can define each facet
of the object such that its normal points either into or out of
the object.  Unfortunately, there is no guarantee of that in our
data structure.

If anyone can spot a flaw in our reasoning or suggest a better
method, please EMail.

Any help will be greatly appreciated.  We will summarize and post
if we get enough useful suggestions.

Thanks       -Mike Miller