Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (714) Games in Android Showcase (214) games submitted by our members Games in WIP (787) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Concave Polygons  (Read 3034 times) 0 Members and 1 Guest are viewing this topic.
cborders

Junior Devvie

 « Posted 2005-09-29 16:03:08 »

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?
Mark Thornton

Senior Devvie

 « Reply #1 - Posted 2005-09-29 20:52:42 »

ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #2 - Posted 2005-09-30 09:54:51 »

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
anarchotron

Junior Devvie

...precious bodily fluids.

 « Reply #3 - Posted 2005-09-30 15:52:16 »

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.

anarchotron

Junior Devvie

...precious bodily fluids.

 « Reply #4 - Posted 2005-09-30 16:17:38 »

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

Junior Devvie

 « Reply #5 - Posted 2005-10-03 16:03:47 »

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:
 1  2  3  4  5  6  7  8  9  10  11  12 `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?!
cborders

Junior Devvie

 « Reply #6 - Posted 2005-10-03 16:34:54 »

Ok, I figured it out!!!

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:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 `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.
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Rule (55 views) 2017-03-19 12:43:22 Rule (48 views) 2017-03-19 12:42:17 Rule (59 views) 2017-03-19 12:36:21 theagentd (63 views) 2017-03-16 05:07:07 theagentd (69 views) 2017-03-15 22:37:06 theagentd (65 views) 2017-03-15 22:32:18 theagentd (63 views) 2017-03-15 22:31:11 ral0r2 (126 views) 2017-03-03 11:52:41 ral0r2 (124 views) 2017-03-03 11:42:24 Archive (311 views) 2017-02-27 19:41:49
 basil_ 19x philfrei 13x Apo 11x dime26 10x Archive 9x FrozenShade 9x bornander 7x KaiHH 7x FabulousFellini 7x SteveSmith 7x princec 7x Spasi 6x Riven 6x CJC 6x orangepascal 5x Ecumene 5x
 List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05SF/X Librariesby SkyAphid2017-03-02 06:38:56SF/X Librariesby SkyAphid2017-03-02 06:38:32SF/X Librariesby SkyAphid2017-03-02 06:38:05SF/X Librariesby SkyAphid2017-03-02 06:37:51
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org