Concave Polygon Triangulation

[Razor89]

Hey!

I was wondering if someone might be able to help me with a little problem of mine?

I am in the midst of writing an OpenGL application to load maps (aka levels) from
the Jedi Engine by LucasArts, used in Dark Forces and Outlaws, and everything was going
great until I had to draw the floors and ceilings of the sectors, allow me to elaborate:

A sector is a simply, often concave, polygon connected by a series of points to form the
sector and since OpenGL cannot render concave polygons, only convex ones, I have to triangulate
the sector myself and for the life of me I cant figure it out.

Ive posted on some forums and even email Ken Silverman, the creator of the Build Engine from Duke Nukem 3D,
and he recommended what is called Trapezoidalization and told me to look at the source code of his polymost renderer
so I tried it and it didnt work.
People also suggested I use the gluTess* functions however for some bizzare reason they wont work for me.

So to the point: Do any you know how to triangulate a polygon that can be concave?

The triangulation will have to handle floating point numbers and possibly
very small numbers.

Thanks,
Jimmy.

 

[MrPaul]

gluTess*

Ive used OpenGL extensively with unmanaged C++, but not with any managed language, so this thread is written as if you are using unmanaged C++.

I would recommend persisting with the gluTess* functions as they are easy to use and reliable once you get them working. In general your code should follow these steps:

1. Create a new tessellation object with gluNewTess
2. Use gluTessCallback to specify callback functions
3. Specify tessellation properties using gluTessProperty
4. Create and render polygons
5. Delete tessellation object with gluDeleteTess

There are 12 possible callback functions you can implement, but you probably wont need them all. Since youre only trying to tessellate concave polygons, not complex polygons containing holes or intersecting edges, you will probably only need to implement the BEGIN, END, and VERTEX callbacks, although I would recommend also implementing an ERROR callback.

At the simplest level, you can use the functions glBegin and glEnd as the callbacks for BEGIN and END, and then code your VERTEX function to call glTexCoord*, glColor*, glNormal* etc, and glVertex*, depending on the type of vertices you are using.

Example, untested code:

GLUtesselator* tessObj;

//Create tessellator object
tessObj = gluNewTess();

//Assign callbacks
gluTessCallback(tessObj, GLU_TESS_BEGIN, beginCallback);
gluTessCallback(tessObj, GLU_TESS_END, endCallback);
gluTessCallback(tessObj, GLU_TESS_VERTEX, vertexCallback);

//Callbacks
void CALLBACK beginCallback(GLenum mode)
{
    glBegin(mode);
}
void CALLBACK endCallback()
{
    glEnd();
}
void CALLBACK vertexCallback(GLvoid* vertex)
{
    //Call various gl* functions depending on whats expected in vertex
}

For step 4, you define polygons between gluTessBeginPolygon and gluTessEndPolygon, each polygon consisting of contours defined between gluTessBeginContour and gluTessEndContour. Contour vertices are defined using gluTessVertex. In this case, you probably need only one polygon containing only one contour:

gluTessBeginPolygon(tessObj, NULL);
gluTessBeginContour(tessObj);

//Specify vertices here

gluTessEndContour(tessObj);
gluTessEndPolygon(tessObj);

The gluTessVertex function is defined as follows:

void gluTessVertex(GLUtesselator* tessobj, GLdouble coords[3], void* vertex_data);

vertex_data contains your vertex coordinates, normals, colour data, etc, and is not used in the tessellation process (so could in fact contain anything). The coords parameter is what is used by the tessellator to break the contour up into renderable primitives. Note that the last vertex is automatically connected to the first.

Ive assumed here that your polygons are only concave - if they contain holes or intersecting edges, you will need multiple contours and should specify a winding rule and a normal vector.

Good luck