Using Tessellation to Cut Multiple Holes

Using tessellation I am able to cuts holes out of a polygon provided that:

  1. Holes do not intersect with any edges.

  2. Holes do not intersect with other holes (which I guess are edges?).

My problem is that I want to be able to cut multiple holes out of a polygon, these holes could overlap with each other as well as the edges of the main polygon.

Here is some sample code which cuts 2 intersecting holes out a a simple rectangle. If I cut either one of the “inner” shapes out it works fine, however with both it fails to draw anything at all. Do I need more callbacks??? An I missing the point here?


void RenderShapes()
GLUtriangulatorObj * tess;

static GLdouble	outside[4][3] = {
	{ -5, -5, 0, },
	{ +5, -5, 0, },
	{ +5, +5, 0, },
	{ -5, +5, 0, }

static GLdouble	inside[4][3] = {
	{ -2, -1, 0, },
	{ +2, -1, 0, },
	{ +2, +1, 0, },
	{ -2, +1, 0, }

static GLdouble	inside2[4][3] = {
	{ -1, -2, 0, },
	{ +1, -2, 0, },
	{ +1, +2, 0, },
	{ -1, +2, 0, }

glClearColor(1.0, 1.0, 1.0, 0.0);

glTranslatef(0.0, 0.0, -10.0);
glColor3f(0.0, 0.0, 1.0);

// ** create tessellation object and register callbacks **
tess = gluNewTess();
gluTessCallback(tess, GLU_BEGIN,	glBegin);
gluTessCallback(tess, GLU_VERTEX,	glVertex3dv);
gluTessCallback(tess, GLU_END,		glEnd);

// ** draw outside **
	gluTessVertex(tess, outside[0], outside[0]);
	gluTessVertex(tess, outside[1], outside[1]);
	gluTessVertex(tess, outside[2], outside[2]);
	gluTessVertex(tess, outside[3], outside[3]);

// ** draw inside 1 **
gluNextContour(tess, GLU_INTERIOR);
	gluTessVertex(tess, inside[0], inside[0]);
	gluTessVertex(tess, inside[1], inside[1]);
	gluTessVertex(tess, inside[2], inside[2]);
	gluTessVertex(tess, inside[3], inside[3]);

// ** draw inside 2 **
gluNextContour(tess, GLU_INTERIOR);
	gluTessVertex(tess, inside2[0], inside2[0]);
	gluTessVertex(tess, inside2[1], inside2[1]);
	gluTessVertex(tess, inside2[2], inside2[2]);
	gluTessVertex(tess, inside2[3], inside2[3]);



Sorry I don’t get it, you just said that holes cannot intersect and you want to know why your code with intersecting holes does not work ?

Do I missunderstand you 100% here ?


The point is that I want to be able to do it when they do intersect.

Also I have since realised that I will need to use a combine callback.

Check out the options you can pass to gluTessProperty.

Yes its helping, I am so close!!

Basically but adding a combine callback to the above code and setting the winding rule to GLU_TESS_WINDING_ABS_GEQ_TWO I get the exact inverse of what I want (I simply get a combination of all of holes as a solid).

The best way to illustrate this problem is with this game scenario:

A game map has specified width and height dimensions as it is look down 3D and not FPS. Therefore it does not use the traditional “carve the level out of rock” approach (i.e. nothing is at a location unless you draw it). Instead you start with a rectangular base sector (say height 0) and you draw over sectors on top. The base sector is simply a single faced rectangle on the Z plane.

When adding a floor sector of the same height or a lowered sector (like a pond or river) a hole would need to be cut in the base sector for it to be visible.

It is quite possible that sectors may overlap or touch the edge of the base sector, therefore the “hole cut out code” needs to be able to deal with this. The “holes” could be anywhere, as they can touch the edge of the base they could even chop it up into many polys.

Is it possible to either:

  1. Cut out loads of holes and end up with a combination of all the holes (no islands!).
  2. Cut out each internal contour one at a time, i.e. cut out and then feed the result poly back into the tessellator (that would be neat).


To illustrate this further I have uploaded a couple of screenshots.

This screenshot is with the base sector rendered, lower sectors like water are not visible due to a lack of holes…

This screenshot is without the base sector rendered, water is visible but no base sector (obviously)…