Deteriming convexity of a polygonal hull

Deteriming convexity of a polygonal hull

Post by Jeff Erickso » Sat, 14 Feb 1998 04:00:00




> 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!)

If you know already that the polyhedron is simple - no two faces
intersect - then this is enough; if every dot prodcut is positive, the
polyhedron is convex.  However, if all you're given is the list of
polygons and some adjacency information, it's possible for the
polyhedron to be LOCALLY convex, but not GLOBALLY convex.  To test for
global convexity, check that the bottommost vertex of the polyhedron is
on the correct side of every facet.  Again, this is just a dot product
calculation for each facet.

Say it with me, everyone --- Linear algebra is your friend.
Trigonometry is your enemy.
--
Jeff Erickson                         Center for Geometric Computing

http://www.cs.duke.edu/~jeffe                        Duke University

 
 
 

Deteriming convexity of a polygonal hull

Post by Ron Levi » Sun, 15 Feb 1998 04:00:00




>> 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.

Quote:>...
>Say it with me, everyone --- Linear algebra is your friend.
>Trigonometry is your enemy.

I'd say that lack of understanding of the most elementary facts of
vector algebra is your worst enemy

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
*****************************************************

 
 
 

Deteriming convexity of a polygonal hull

Post by Ron Levi » Sun, 15 Feb 1998 04:00:00



>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.
>The only problem with this is that the dot product of the normals only gives
>you information about angles from -90 to 90 (acos).

No, actually, the range of acos is 0 to 180 degrees corresponding to
the cos range of 1 to -1.  The angles between -90 and 90 degrees all
have cos >= 0.

Quote:> It would seem that a
>convex hull should have all adjacent polygon normals at angles of 180 or
>greater but quadrant information is lost in the acos.

Huh?

******************************************************
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
*****************************************************

 
 
 

Deteriming convexity of a polygonal hull

Post by John Nag » Sun, 15 Feb 1998 04:00:00





>>> 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.  This
will tell you if the entire figure is convex, but if it is not,
it won't help you find nonconvex edges.

    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.)

    Or you can just get a copy of Qhull and let it wrap your geometry in
a convex hull.

                                        John Nagle

 
 
 

Deteriming convexity of a polygonal hull

Post by Kenneth Sloa » Sun, 15 Feb 1998 04:00:00


I like the method presented by someone (sorry - I forget who).  This
method was new to me, but feels right.  Let me restate it (mostly to see
if I have it right!)

Convexity can be tested at each EDGE.  Each EDGE has two FACEs (call
them L and R).  For each FACE, we have a normal (by convention, facing
towards the OUTSIDE) - call them L.n and R.n.  We can also choose a
representative point for each FACE (this point must *not* be on the EDGE
we care about - and so should not be on any EDGE).  A good candidate
point is the average of all vertices.  Call these points L.p and R.p.
Now, for the EDGE, we can compute the vector E.v = (R.p - L.p).  (this
vector points from Left to Right across the EDGE).

The polyhedron is convex at this EDGE iff

                 (L.n DOT E.v) <= 0

That is, if the normal associated with the Left FACE points AWAY FROM
the Right FACE.

--

Computer and Information Sciences                       (205) 934-2213
University of Alabama at Birmingham                 FAX (205) 934-5473
Birmingham, AL 35294-1170   http://www.cis.uab.edu/info/faculty/sloan/

 
 
 

Deteriming convexity of a polygonal hull

Post by Jeff Erickso » Sun, 15 Feb 1998 04:00:00



> >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.
> Wrong.

Ho boy.  Let me wipe the egg off my face and try again.

To check whether two facets are locally convex, check that a vertex of
one facet is on the corerct side of the plane through the other.  This
IS a dot-product calculation, but not between two normal vectors.
Rather, if n is the outer normal of one facet, p is a vertex of that
facet, and q is a vertex of the other facet (but not on their common
edge), then the dot product n.(q-p) should be negative.

It's El Nino's fault.

Quote:> I'd say that lack of understanding of the most elementary facts of
> vector algebra is your worst enemy

...and using trigonometry is a symptom of the above.
--
Jeff Erickson                         Center for Geometric Computing

http://www.cs.duke.edu/~jeffe                        Duke University
 
 
 

Deteriming convexity of a polygonal hull

Post by Ron Levi » Sun, 15 Feb 1998 04:00:00






>>>> 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
*****************************************************

 
 
 

Deteriming convexity of a polygonal hull

Post by Ron Levi » Sun, 15 Feb 1998 04:00:00




>>    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.

Actually, the counter example I offer to refute John Nagle's claim is
a small modification that does not change the barycenter but does
change the convexity.

******************************************************
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
*****************************************************

 
 
 

Deteriming convexity of a polygonal hull

Post by John Nag » Mon, 16 Feb 1998 04:00:00




>>    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.

     You're right.  It's a necessary, but not sufficient, condition
for convexity.  So that's not really a very useful test.   Sorry.

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.

     Remember that the cross product is not commutative; a ^ b = -(b ^ a).
So if you process the faces in the opposite order, the sign of the
cross product changes.  As you point out, when you process the faces
in the opposite order, the sign of the edgevector also changes.  
These sign changes cancel, so the sign of k does in fact indicate
convexity or lack therof.

     This is closely related to the "right hand rule" for cross
products.  Think about what happens to the cross product vector
as the angle between the two vectors increases.  The direction
of the cross product vector inverts when the angle passes through
a multiple of pi.  

     Any questions?

                                        John Nagle

 
 
 

Deteriming convexity of a polygonal hull

Post by Ron Levi » Mon, 16 Feb 1998 04:00:00





>>>    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.

>     Remember that the cross product is not commutative; a ^ b = -(b ^ a).
>So if you process the faces in the opposite order, the sign of the
>cross product changes.  As you point out, when you process the faces
>in the opposite order, the sign of the edgevector also changes.  
>These sign changes cancel, so the sign of k does in fact indicate
>convexity or lack therof.
>...

Very good.  But you do indeed need to complete your prescription by
specifying that "edgevector"  has the sense it inherits from the
clockwise ordering of p2 (and not p1).

******************************************************
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
*****************************************************

 
 
 

Deteriming convexity of a polygonal hull

Post by hugo » Mon, 16 Feb 1998 04:00:00


You lot seem to be making a mountain out of a molehill. How many posts have there
been to this simple question? Not many have really helped solve the origional
problem. Especially Ron, who just seems to be in it for the argument, rather than
suggesting any real methods for determining the convexity of a hull.

    bagsy no flaming me back

        -hugo-

 
 
 

Deteriming convexity of a polygonal hull

Post by John Nag » Mon, 16 Feb 1998 04:00:00



>You lot seem to be making a mountain out of a molehill. How many posts
>have there been to this simple question? Not many have really helped
>solve the original problem. Especially Ron, who just seems to be in
>it for the argument, rather than suggesting any real methods for
>determining the convexity of a hull.

     Well, Ron did point out that my barycenter approach was wrong,
and we've now agreed that the cross-product method is correct,
after firming up the description.  So there's been progress.

     I suggest reading the documentation that comes with QHull if
you're really into this sort of thing.  There are a whole set of
numerical issues with convex hulls, most of which relate to figures
very close to convex.  If you triangulate the faces, you may create
coplanar faces.  If you don't, you'll probably have faces that
aren't perfectly flat.  Both cause problems with various uses of convex
hulls.

     What did the original poster actually want to do, anyway, once
they validated their convex hull?

                                        John Nagle

 
 
 

1. Deteriming size of texture

My program uses nehe's bitmap loading routine to
load textures right now. It seems to have a variable
AUX_RGBImageRec *image I searched google and
it says that this is part of GLaux.lib. I am interested in
its members ->sizex and ->sizey as perhaps a way to
get the size of the bitmap but my debugger cannot
evaluate the value after the bitmap is loaded and before
it is bound (which seems the proper place to me), it comes
up as:
"sizeX CXX0030: Error: expression cannot be evaluated"
how do i get that to a number of pixels?

Is there any documentation on AUX_RGBImageRec
anywhere so I can tell what type these members are?

Or perhaps there is a better way to go about it?

Thanx,
Christopher

2. I Need Wood!

3. Have: 3D convex hull, point p outside hull. Want: Closest point to p inside hull?

4. uudecode for mac?

5. Simple Convexity Working Group (preliminary report)

6. Display TIFs under MSDOS

7. convexity bibliography update

8. convexity bibliography sent

9. Bibliography on digital & computational convexity

10. 3D convexity

11. Convexity tests for polygons

12. Detecting convexity of an object?