My opengl polygon tessellator. Works great! Unfortunately, I still haven't figured out how to get code pasted properly. Grrrr. Blogger is not off to a good start for me.

Anyway, it nicely demonstrates how to do opengl polygon tessellation in C++ and retrieve the triangles later. The Point_2, Polygon_2 and Polygon_with_holes_2 are CGAL typedefs, the others are simple stl typedefs.

I was just playing around and comparing triangulations.

Update Feb 20, 2007: I added the webcpp css to the template, so it looks better.

class Tessellator
{
private:
 typedef         vector<Point_2*>          Point_2_Vec;
 typedef         pair<GLenum, Point_2_Vec> Poly;
 typedef         vector<Poly>              PolyVec;

 GLUtesselator*  m_tessellator;
 PolyVec         m_polygons;
 Point_2_Vec     m_all_vertices;

 static void vertexCallback(Point_2* point, Tessellator* tess)
 {
   Poly&         poly      = tess->m_polygons.back();
   Point_2_Vec&  vertices  = poly.second;
   vertices.push_back(point);
 }

 static void beginCallback(GLenum type, Tessellator* tess)
 {
   tess->m_polygons.push_back(Poly(type, Point_2_Vec()));
 }

 static void combineCallback(GLdouble coords[3], Point_2*[4], GLfloat[4], Point_2** outData, Tessellator* tess)
 {
   Point_2_Vec& vertices = tess->m_all_vertices;
   vertices.push_back(new Point_2(coords[0], coords[1]));
   *outData = vertices.back();
 }

 static void errorCallback(GLenum code)
 {
   const GLubyte* error_msg = gluErrorString(code);
   cout << "opengl error: " << error_msg;
 }

 void  _glTessPoly(Polygon_2& poly)
 {
   gluTessBeginContour(m_tessellator);
   for (Polygon_2::Vertex_const_iterator vertex_it = poly.vertices_begin(); vertex_it != poly.vertices_end(); vertex_it++)
   {
     Point_2* p = new Point_2(*vertex_it);
     m_all_vertices.push_back(p);
     GLdouble v[3] = { to_double(p->x()), to_double(p->y()), 0.0 };
     gluTessVertex(m_tessellator, v, p);
   }
   gluTessEndContour(m_tessellator);
 }

public:
 Tessellator(const Polygon_with_holes_2& poly): m_tessellator(gluNewTess())
 {
   gluTessProperty(m_tessellator, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_POSITIVE);

   gluTessCallback(m_tessellator, GLU_TESS_VERTEX_DATA,  (_GLUfuncptr)Tessellator::vertexCallback);
   gluTessCallback(m_tessellator, GLU_TESS_BEGIN_DATA,   (_GLUfuncptr)Tessellator::beginCallback);
   gluTessCallback(m_tessellator, GLU_TESS_COMBINE_DATA, (_GLUfuncptr)Tessellator::combineCallback);
   gluTessCallback(m_tessellator, GLU_TESS_ERROR,        (_GLUfuncptr)Tessellator::errorCallback);

   gluTessBeginPolygon(m_tessellator, this);
     Polygon_2 outer = simplify_polygon(poly.outer_boundary());
     _glTessPoly(outer);
     for (Polygon_with_holes_2::Hole_const_iterator hole_it = poly.holes_begin(); hole_it != poly.holes_end(); hole_it++)
     {
       Polygon_2 hole = simplify_polygon(*hole_it);
       _glTessPoly(hole);
     }
   gluTessEndPolygon(m_tessellator);
 }

 virtual ~Tessellator()
 {
   gluDeleteTess(m_tessellator);
   for (Point_2_Vec::const_iterator it = m_all_vertices.begin(); it != m_all_vertices.end(); it++)
     delete *it;
 }

private:
 void _collect_triangle_fan(const Point_2_Vec& points, list<Polygon_2>& triangles)
 {
   Point_2_Vec::const_iterator it = points.begin();
   Point_2* center   = *it++;
   Point_2* previous = *it++;
   for (; it != points.end(); it++)
   {
     Polygon_2 new_poly;
     new_poly.push_back(*center);
     new_poly.push_back(*previous);
     new_poly.push_back(**it);
     triangles.push_back(new_poly);
     previous = *it;
   }
 }

 void _collect_triangle_strip(const Point_2_Vec& points, list<Polygon_2>& triangles)
 {
   Point_2_Vec::const_iterator it = points.begin();
   Point_2* first  = *it++;
   Point_2* second = *it++;
   bool switcher = true;
   for (; it != points.end(); it++)
   {
     Polygon_2 new_poly;
     new_poly.push_back(*first);
     new_poly.push_back(*second);
     new_poly.push_back(**it);
     triangles.push_back(new_poly);
     if (switcher) // keep them counterclockwise
       first   = *it;
     else
       second  = *it;
     switcher = not switcher;
   }
 }

 void _collect_triangles(const Point_2_Vec& points, list<Polygon_2>& triangles)
 {
   for (Point_2_Vec::const_iterator it = points.begin(); it != points.end();)
   {
     Polygon_2 new_poly;
     new_poly.push_back(**it++);
     new_poly.push_back(**it++);
     new_poly.push_back(**it++);
     triangles.push_back(new_poly);
   }
 }

public:
 void collect(list<Polygon_2>& triangles)
 {
   for (PolyVec::const_iterator poly_it = m_polygons.begin(); poly_it != m_polygons.end(); poly_it++)
   {
     const Poly& poly = *poly_it;
     switch (poly.first)
     {
       case GL_TRIANGLE_FAN:
         _collect_triangle_fan(poly.second, triangles);
         break;
       case GL_TRIANGLE_STRIP:
         _collect_triangle_strip(poly.second, triangles);
         break;
       case GL_TRIANGLES:
         _collect_triangles(poly.second, triangles);
         break;
       case GL_LINE_LOOP:
         throw runtime_error("Tessellator does not support GL_LINE_LOOP");
         break;
       default:
         throw runtime_error("Tessellator cannot handle this geometry type");
     }
   }
 }
};