Sign in to follow this  
My_Mind_Is_Going

determining if a group of polygons forms a convex region

Recommended Posts

I'm trying to figure out a test to tell if a list of polygons form a convex region. This is part of some BSP stuff I'm doing so the region in question isn't necessarily closed. It seems like as a brute force approach I can just dot the normal of each polygon with the normal of every other one and make sure the dot products all have the same sign (i.e. all normals are either pointing inward or outward). Does anyone know if this approach is correct? This is being done offline so I'm not really concerned with efficiency. Thanks.

Share this post


Link to post
Share on other sites
Martin    194
What you need to do is calculate the plane equation of each triangle then check that all your other vertices are behind that plane

This doesn't tell you that you have a complete closed convex hull, but does tell you that the triangles you have at least partially formed a convex hull

Share this post


Link to post
Share on other sites
Zipster    2365
If you calculate the convex hull of the polygons (using something like the quickhull algorithm), each polygon should be coincident with a side of the hull. As an added bonus, you can also figure out where you are missing polygons on the hull.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this