sunLoadingImage
whowedImag
decoration left 1
decoration left 2
transhome
transprojects
transgallery
transarticles
decoration rigth
English
Українська
Show/Hide search bar
black cat logo variable logo
[26 Jan 2013]

Triangulation of contours of True Type symbol with GLU library

Previous tutorials show how to get contours of symbols from True Type font and how to form text string from individual symbols. You can render contours with line segments, but not as filled shapes. To render filled text you have to triangulate contours for each symbol (as on the following image). Process to form text strings from triangulated symbols is same as for contours of symbols.
Rendered triangulated symbols:
You can use GLU library to triangulate contours. It is well suited for triangulation of convex and concave polygons, and also for polygons with holes. Triangulation process starts with creation and initialization of GLUtesselator. Then you have to start polygon. In our example polygon is a symbol, and contains all contours of a symbol. So you have to add all contours to polygon. And each contour is represented by vertices. When you filled triangulator with data you can start actual triangulation and get triangles.
Include glu32.lib to project dependencies. And include following headers:
#include <Windows.h>
#include "gl\glu.h"
Function triangulateSymbolContours() triangulates contours of a symbol. First it creates helper object for triangulation and fills it with contours and vertices. When all information about contours is saved to triangulator object, call to endTriangulation() triggeres actual triangulation in helper object. That's all. Result of triangulation is array of vertices, where each three vertices represent a triangle.
void triangulateSymbolContours(
      const std::vector<std::vector<glm::vec2>> & contours,
      std::vector<glm::vec2> & vertices)
{
   // no need to triangulate empty shape
   if(contours.size()>0)
   {
      Triangulator triangulator;
      triangulator.beginTriangulation();

      // add each contour to triangulator helper
      for(uint i=0; i<contours.size(); i++)
      {
         // add only not empty contours
         if(contours[i].size()>0)
         {
            triangulator.beginContour();
            // add each vertex to triangulator helper
            for(uint j=0; j<contours[i].size(); j+=2)
            {
               triangulator.addVertex(glm::vec2(contours[i][j], contours[i][j+1]));
            }
            triangulator.endContour();
         }
      }
      завершини ініціалізацію і почати тріангуляцію
      triangulator.endTriangulation();

      Повернути результати тріангуляції
      vertices = triangulator.results();
   }
}
Helper class for triangulation:
class Triangulator
{
public:
   // Constructor
   Triangulator();
   // Destructor
   ~Triangulator();

   // Start initialization of triangulation
   void beginTriangulation();
   // Start new contour
   void beginContour();
   // Add vertex to current contour
   void addVertex(const glm::vec2 & vertex);
   // End current contour
   void endContour();
   // Ends initialization and triangulates saved contours
   void endTriangulation();

   // return result (each three vertices - triangle)
   std::vector<glm::vec2> results() const;

private:
   GLUtesselator * triangulator;
   std::unique_ptr<TessContext> context;
};
Implementation of triangulation helper class:
// this CALLBACK define is required for GLU library
#ifndef CALLBACK
#define CALLBACK __stdcall
#endif

// helper for triangulator (context of triangulator)
struct TessContext
{
   // temporal list to store data for triangulation
   std::list<std::unique_ptr<GLdouble[]>> input;
   // array of indices (each three indices represents triangle)
   std::vector<uint> indices;
   // array of vertices
   std::vector<float> result;

   // triangulation runtime data
   GLenum currentPrimitiveType;
   uint currentIndex;
   bool isFirstVertex;
   uint firstVertexIndex;
   bool isSecondVertex;
   uint secondVertexIndex;

   TessContext()
      : currentPrimitiveType(GL_NONE)
      , currentIndex(0)
      , isFirstVertex(false)
      , isSecondVertex(false)
   {
   }
};

// Constructor
Triangulator::Triangulator()
   : triangulator(nullptr)
{
}

// Destructor
Triangulator::~Triangulator()
{
   // remove GLU triangulator
   if(triangulator)
   {
      gluDeleteTess(triangulator);
   }
}

// called when triangulator starts new primitive
void CALLBACK tessBegin(GLenum type, TessContext * ctx);
// called when triangulator outputs new vertex
void CALLBACK tessVertex(GLvoid *, TessContext * ctx);

// PS: previous functions have behavior similar to immediate mode functions glVertex, glBegin, glEnd from older versions of OpenGL

// Initializes triangulation
void Triangulator::beginTriangulation()
{
   // create new GLU triangulation object
   if(triangulator)
   {
      gluDeleteTess(triangulator);
   }
   triangulator = gluNewTess();

   // set callback functions for triangulator
   gluTessCallback(triangulator, GLU_TESS_BEGIN_DATA,
                  (void (CALLBACK*)())tessBegin);
   gluTessCallback(triangulator, GLU_TESS_VERTEX_DATA,
                   (void (CALLBACK*)())tessVertex);

   // set normal that is used by default
   // it point in direction of Z axis, as we work in XY plane
   gluTessNormal(triangulator, 0, 0, 1);

   // create and set context for triangulator - context is object
   // that is visible to triangulator during triangulation
   context = std::unique_ptr<TessContext>(new TessContext);
   gluTessBeginPolygon(triangulator, context.get());
}

// starts new contour
void Triangulator::beginContour()
{
   gluTessBeginContour(triangulator);
}

// adds new vertex to current contour
void Triangulator::addVertex(const glm::vec2 & vertex)
{
   GLdouble * tInput = new GLdouble[3];
   tInput[0] = vertex.x;
   tInput[1] = vertex.y;
   tInput[2] = 0;
   context->input.push_back(std::unique_ptr<GLdouble[]>(tInput));

   gluTessVertex(triangulator, tInput, tInput);
}

// ends current contour
void Triangulator::endContour()
{
   gluTessEndContour(triangulator);
}

// triangulates saved contours and removes GLU triangulator
void Triangulator::endTriangulation()
{
   gluTessEndPolygon(triangulator);

   if(triangulator)
   {
      gluDeleteTess(triangulator);
      triangulator = nullptr;
   }
}

// get results of triangulation
std::vector<glm::vec2> Triangulator::results() const
{
   std::vector<glm::vec2> out;

   std::vector<float> & res = context->result;
   uint num = context->indices.size();

   // get each vertex by index
   for(uint i=0; i<num; i++)
   {
      uint index = context->indices[i];
      out.push_back(glm::vec2(res[index*2], res[index*2+1]));
   }

   return std::move(out);
}

// called when triangulator starts new primitive
// sets type of primitive, and that nor first,
// nor second vertices aren't set
void CALLBACK tessBegin(GLenum type, TessContext * ctx)
{
   ctx->currentPrimitiveType = type;
   ctx->isFirstVertex = false;
   ctx->isSecondVertex = false;
}

// called when triangulator adds new vertex to results
void CALLBACK tessVertex(GLvoid * data, TessContext * ctx)
{
   // new vertex
   GLdouble * coord = (GLdouble*)data;
   ctx->result.push_back((float)coord[0]);
   ctx->result.push_back((float)coord[1]);

   // save results - depends on type of primitive
   if(ctx->currentPrimitiveType == GL_TRIANGLES)
   {
      ctx->indices.push_back(ctx->currentIndex++);
   }
   else if(ctx->currentPrimitiveType == GL_TRIANGLE_FAN)
   {
      if(ctx->isSecondVertex)
      {
         // new triangle
         ctx->indices.push_back(ctx->firstVertexIndex);
         ctx->indices.push_back(ctx->secondVertexIndex);
         ctx->indices.push_back(ctx->currentIndex);

         // index of next vertex
         ctx->secondVertexIndex = ctx->currentIndex++;
      }
      else if(ctx->isFirstVertex)
      {
         // second vertex in triangle
         ctx->isSecondVertex = true;
         ctx->secondVertexIndex = ctx->currentIndex++;
      }
      else
      {
         // first vertex in triangle
         ctx->isFirstVertex = true;
         ctx->firstVertexIndex = ctx->currentIndex++;
      }
   }
   else if(ctx->currentPrimitiveType == GL_TRIANGLE_STRIP)
   {
      if(ctx->isSecondVertex)
      {
         // new triangle
         ctx->indices.push_back(ctx->firstVertexIndex);
         ctx->indices.push_back(ctx->secondVertexIndex);
         ctx->indices.push_back(ctx->currentIndex);

         // to next vertex
         ctx->firstVertexIndex = ctx->secondVertexIndex;
         ctx->secondVertexIndex = ctx->currentIndex++;
      }
      else if(ctx->isFirstVertex)
      {
         // second vertex in triangle
         ctx->isSecondVertex = true;
         ctx->secondVertexIndex = ctx->currentIndex++;
      }
      else
      {
         // first vertex in triangle
         ctx->isFirstVertex = true;
         ctx->firstVertexIndex = ctx->currentIndex++;
      }
   }
}



Sun and Black Cat- Igor Dykhta (igor dykhta email) © 2007-2014