Noob question: how to render a 2D concave polygon?

[CommanderKeith]

Hi,

I don't know how to fill concave polygons. I looked at how Kev Glass's Slick API does it, and it seems to triangulate/tesselate the polygon in software before rendering. But then some seem to use GLUT to triangulate automatically. I noticed that LWJGL 2.2.1 now has GLU Tesselator. Is that the best thing to use? Could someone show me some example code to fill a 2D concave polygon, say with these coordinates (which is a box with a chunk taken out of the top):

(100,100)
(200,100)
(200,200)
(150,150)
(100,200)

Thanks a lot  
Keith

[dronus]

This is actually a pro question 

You need to cut the polygon into convex parts, to have it rendered correctly.

Algorithms for that are slow or quite complicated.

If you don't want to rely on GLU and your polygons have few verticies (say <100), you can try "earcutting", the slowest but simplest method. One implementation could be found here: https://snr.freifunk.net/trac/vis/browser/VisClient/org/dronus/gl/Convexiser.java
Its quite simple to use:

List<Vector3f> polygon   ...has to contain all verticies of one concave polygon.

Convexiser c=new Convexiser();
List<List<Vector3f>> convexPolygons=c.convexise(polygon);

now convexPolygons contains several lists of verticies, each made up a triangle ready to render.


The GLU tesselation uses faster algorithms, but vast more overhead.  It resues verticies and builds tri-strips or fans, if useful. So if the count of verticies is high, it should perform better. But I have no idea if this would be 10, 100 or 1000 verticies.

[zik]

Hi,

If you don't want to rely on GLU and your polygons have few verticies (say <100), you can try "earcutting", the slowest but simplest method. One implementation could be found here: https://snr.freifunk.net/trac/vis/browser/VisClient/org/dronus/gl/Convexiser.java

I have try this one and it works fine in 99/100 case. For some polygons it fails. (I don't know why)

Where could I find an exemple on how to use GLUtesselator of lwjgl ?

[broumbroum]

you can use Java2D Shape's to find PathIterator's for using with this GLText package : http://lwjgl.org/forum/index.php/topic,3028.msg16668.html#msg16668
get the sample of code (attached in the first thread post) and it can be modified to handle various shapes; i.e. instead of reading the Shape from a Font glyph, load your own shape. But you'll still need methods got from the base GLText class.
Hope you find your way with it !

[broumbroum]

sorry previous GLText revision is obsolete. you need the last rev. wait a minute till I get it out from my scratch, plz...  
Here it is : http://lwjgl.org/forum/index.php/topic,3028.msg17389.html#msg17389
See how  GLUTesselator is handled, and how it must be added a GLUtessellatorCallbackAdapter to it.
you just have to use  a different Shape instance, as said before, but the adapter and the rest of code is meant to be ready to use.

[zik]

Thanks but I finally found myself. It works perfectly.
I have more than 1000 complexes statics polygons to render.

I use GLUTesselator to put them into a list with the function GL11.glNewList(). And when i need to render, i call them with GL11.glCallList().

I get no artefact and the render is very fast.

My problem was i didn't understand that i have to write myself the functions in the GLUtessellatorCallback... I thougth they should be ok by default.

[CommanderKeith]

Thanks a lot dronus, zik and broumbroum. Very helpful advice!