Friday, 29 March 2013

Extracting tesselation from OpenGL Sample Implementation

What can be easier than ask your renderer to draw a polygon for you. However, that's not the case with OpenGL ES library. The most sophisticated object it can basically visualize is a triangle. So if you want a polygon you should compose it from lots of triangles. The process is known as tesselation or triangulation.

On most desktop systems there is a separate OpenGL-companion library named OpenGL Utility library (GLU), it is able to perform polygon tesselation. This library is also available for iPhone.

If your target system is known to have GLU you can link to this library and use tesselation functionality from it. See an example provided by Michael Fötsch, he linked to GLU for tesselation from his Direct3D application. If your target system does not have GLU you might consider writing your own tesselator or use one of the existing.

One of the best choices would be to extract tesselation functionality from OpenGL Sample Implementation.

It stood the test of time. Also, tesselation procedure from OpenGL Sample Implementation doesn't require external dependencies. You can just include sources in your project. Here are the steps how to do it for c++ project in Visual Studio.

Step 1.
Download OpenGL Sample Implementation. There are two versions there I have chosen the latest ogl-sample.20000807.tgz. We just need to isolate the tesselator from it. Create \libtess folder in your project's source directory. Copy all files from \ogl-sample.20000807\main\gfx\lib\glu\libtess to your \libtess folder.

Step 2.
Copy \ogl-sample.20000807\main\gfx\lib\glu\include\gluos.h to your peoject's \libtess as well.

Step 3.
Comment away the #include from tess.h and mesh.h in \libtess. This header brings a lot of dependencies we don't want. In mesh.h add #include "gluos.h" instead.

Step 4.
Now if you'll try to compile OGLTesselator you would probably see a lot of errors like

"error C2146: syntax error : missing ';' before identifier 'coords'".

This is due to a lot of missing OpenGL defines and typedefs. For instance, GLdouble define is not visible from mesh.h. These defines may be found in gl.h header file, however, this file is not in OpenGL Sample Implementation. You can find it in Windows SDK, also it is usually supplied with Visual Studio. This file contains a lot of declarations for functions unrelated to our task. So you might want to copy just the #defines and typedefs from this file. Put them to \libtess\gluos.h that you have just copied to \libtess dir.

Make sure that _WIN32 macro is disabled if you don't want windows.h dependencies, so that GLAPI and WINGDIAPI would be disabled.

Step 5.
Open tess.h and after
struct GLUtesselator {
typedef struct GLUtesselator GLUtesselator;
This is to enable GLUtesselator object to be declared without the struct keyword in libtess c-language files.

Step 6.
Now we have error C2371 related to undefined gluTess*() functions. Just after the above typedef in tess.h add these functions definitions (with c-linkage).
#ifdef __cplusplus
   extern "C" {
void GLAPI gluTessBeginPolygon(GLUtesselator* tess, void *data);

void GLAPI gluTessBeginContour(GLUtesselator *tess);

void GLAPI gluTessEndContour(GLUtesselator *tess);

void GLAPI gluTessEndPolygon(GLUtesselator *tess);

GLUtesselator * GLAPI gluNewTess(void);

void GLAPI 
gluTessCallback(GLUtesselator *tess, GLenum which, void (GLAPI *fn)());

void GLAPI 
gluTessProperty(GLUtesselator *tess, GLenum which, GLdouble value);

void GLAPI 
gluTessNormal(GLUtesselator *tess, GLdouble x, GLdouble y, GLdouble z);

void GLAPI 
gluTessVertex(GLUtesselator *tess, GLdouble coords[3], void *data);

void GLAPI gluDeleteTess(GLUtesselator *tess );

#ifdef __cplusplus
Now remove priority-heap.c (in \libtess) from your project. GLU tesselator build should succeed.

Step 7.
A simple test for tesselator, with a polygon forming the shape of letter 'E'.
#include "OGLTesselator.h" 
#include "Libtess\gluos.h"
#include "Libtess\tess.h"
#include <assert.h> 
#include <iostream>

GLenum g_ErrorCode = 0;

void VertexCallback(GLvoid* index)
 static int Count = 0;
 std::cout << (int)index << (++Count % 3 == 0 ? '\n' : ',');

void ErrorCallback(GLenum errorCode)
 g_ErrorCode = errorCode;

void EdgeFlagCallback(GLboolean flag) 
 // Indicates which edges lie on the polygon boundary 
 // (so to enable us to draw outlines), also 
 // if this callback is provided triangle fans and strips are
 // converted to independent triangles

void TesselatorTest()
 double data[] = {
  -128, -23, 0, 
  -128, 23, 0,
  -94, 23, 0,
  -94, 15, 0,
  -119, 15, 0,
  -119, 5, 0,
  -96, 5, 0,
  -96, -3, 0,
  -119, -3, 0,
  -119, -15, 0,
  -93, -15, 0,
  -93, -23, 0

 GLUtesselator* tesselator = gluNewTess();
 gluTessCallback(tesselator, GLU_TESS_VERTEX, 
 (GLvoid (GLAPI *) ()) &VertexCallback);
 gluTessCallback(tesselator, GLU_TESS_EDGE_FLAG,
 (GLvoid (GLAPI *) ())(&EdgeFlagCallback)); 
 gluTessCallback(tesselator, GLU_TESS_ERROR, 
  (GLvoid (GLAPI *) ()) &ErrorCallback);
 gluTessBeginPolygon(tesselator, NULL);

 for (int i = 0; i < 12; ++i) 
     gluTessVertex(tesselator, &data[i * 3], (void*)i);


 assert(g_ErrorCode == 0);