Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Concave Polygons  (Read 1823 times)
0 Members and 1 Guest are viewing this topic.
Offline cborders

Junior Member





« Posted 2005-09-29 18: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?  Undecided
Offline Mark Thornton

Senior Member





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

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

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #2 - Posted 2005-09-30 11: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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline anarchotron

Junior Member




...precious bodily fluids.


« Reply #3 - Posted 2005-09-30 17: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.





Offline anarchotron

Junior Member




...precious bodily fluids.


« Reply #4 - Posted 2005-09-30 18: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.
Offline cborders

Junior Member





« Reply #5 - Posted 2005-10-03 18: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?! Huh
Offline cborders

Junior Member





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

Ok, I figured it out!!!  Grin

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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Riven (15 views)
2014-07-29 18:09:19

Riven (10 views)
2014-07-29 18:08:52

Dwinin (10 views)
2014-07-29 10:59:34

E.R. Fleming (28 views)
2014-07-29 03:07:13

E.R. Fleming (10 views)
2014-07-29 03:06:25

pw (40 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (27 views)
2014-07-23 21:07:15

Riven (29 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!