Concave Polygons

Miscellaneous Topics
#1

I didn’t know where to put this as it is a general OpenGL question so here it is.

I am writing a program that will cheks the system hardware for OpenGL compatibility and accordingly loads either a Java2D or an OpenGL renderer, now my question is this, I am allowing the user to create a java.awt.Polygon and add it to the canvas to be rendered. in the Java2D version this is easy, but the user could very well define a concave polygon that will not look right in the OpenGL renderer. I tried using GL_LINE_LOOP, but it really needs to be filled. my question is this: Is there an algorythm that will let me create mutiple convex polygons from one arbitrary concave polygon? :-\

#2

http://www.amazon.co.uk/exec/obidos/ASIN/0521649765/ref=pd_bxgy_text_2_cp/026-6242347-9985264

#3

You can solve this problem fairly simply using the charmingly-named “Ear cutting” technique.

An ear is defined as a vertex of your polygon that, along with the two edges it is associated with, forms a triangle that : A) is on the interior of the polygon, and B) contains no other vertices of the polygon. Every polygon is guaranteed to contain at least two ears.

Testing for A) involves nothing more than making sure that the angle between the edges is acute (Note you have to know which direction you are iterating through the vertices)
Testing for B) involves 3 cross-products for every other vertex tested.

The approach is to simply iterate through the vertices and check each one for ear-iness. When you find one, it is safe to remove that vertex and store the resulting triangle for rendering.

There’s also a Tesselator utility in GLU or GLUT that might do what you want in a semi-automagical way, but I’ve never used it.

Hope this gets you started

#4

The Ear Cutting technique mentioned will produce different tesselations depending on which Vertex you start iterating on.

I find that the best tesselation involves adding edges of the smallest possible length.

You can improve on the Ear Cutting technique by iterating through all the verts checking for ear-iness, as well as measuring the new edge’s length. The ear with the smallest new edge should be the first ear to get cut. Rinse and repeat. There are more iterations and tests through the verts: (N)(N+1)/2 rather than N.

But you get a better result because the triangles end up closer to equilateral on average.

#5

Here’s some visuals of what I’m describing. First we have my heuristic, second we have the opposite of my heuristic (choosing the longest edges). Arbitrary iteration with no heuristic will of course produce something in between.

Also please note that when tesselating on a plane, it is sufficient to test if any verts lie within your Ear. If you are tesselating in 3d you need to check instead if any of the outer edges of the polygon intersect your Ear.

#6

Ok, I have decided to go with simple ear cutting for now and maybe jazz it up after I get it working. Now I am having trouble deciding if the angle is obtuse or not. Here is the function I use to get the angle:


private float getAngle(Point p1, Point p2, Point p3)
{
	float angle = 0, cosAngle = 0;
	Vector3f A = new Vector3f(p1.x - p2.x, p1.y - p2.y, 0);
	Vector3f B = new Vector3f(p3.x - p2.x, p3.y - p2.y, 0);
	
	cosAngle = Vector3f.dot(A, B) / (A.length() * B.length());
	
	angle = (float)(Math.acos(cosAngle) * (180/Math.PI));
	
	return angle;
}

The probelm is that is always retuns an angle of less that 180!
`
/
/
/ =135 deg.
|
|
|

 |
 |
 |   should = 270, but returns 135
/

/
/
/
`
How can I force it to measure the from a certain orientation? Or am I doing something else that’s just really wrong?! ???

#7

Ok, I figured it out!!! ;D

I need to find the normal of the two vectors and if the normal points in towards me (i.e. z is negative), then I have the angle I want, if it points away from me (i.e. z is positive) then I need to take 360-angle!!

Here is the updated code:


private float getAngle(Point p1, Point p2, Point p3)
{
	float angle = 0, cosAngle = 0;
	Vector3f A = new Vector3f(p1.x - p2.x, p1.y - p2.y, 0);
	Vector3f B = new Vector3f(p3.x - p2.x, p3.y - p2.y, 0);
	Vector3f AxB;
	
	cosAngle = Vector3f.dot(A, B) / (A.length() * B.length());
	
	angle = (float)(Math.acos(cosAngle) * (180/Math.PI));
	AxB = Vector3f.cross(A, B, null);
	if(AxB.z > 0) angle = 360f - angle;
	
	return angle;
}

Here are some pictures of what it did to different shapes!

This is the original shape that I was having trouble with.

Then I wanted a complicated shape to make sure it wan’t going to puke.

And I wanted to make sure that it did something sane on a simple shape.