Triangulating and Extruding Arbitrary Polygons

by Michael Fötsch
May 6, 2001

This article was originally published on geocities.com/foetsch.

Contents

1. Abstract
2. Introduction
3. Converting Text to Polygons
   1. An Overview of GDI Paths
   2. Using GDI Paths
4. The GLU Tesselation Functions
   1. The Tesselation Object
   2. Passing Vertices to the Tesselator
   3. Working with the Tesselation Callbacks
      1. The GLU_TESS_EDGE_FLAG Callback
      2. The GLU_TESS_VERTEX Callback
      3. The GLU_TESS_COMBINE Callback
5. Adding Depth to a Polygon
   1. Creating the Back Surface
   2. Creating the Side Faces
   3. Calculating the Vertex Normals
      1. Sidenote: Vector Maths
   4. Adding Texture Coordinates
6. Final Words

Abstract

This article demonstrates how you can take advantage of OpenGL Utility (GLU) functions to triangulate polygons for use in Direct3D applications. In this tutorial, we'll generate meshes from arbitrary polygons (convex as well as concave polygons and polygons with holes), including the polygons that make up TrueType fonts. In addition, we'll explore an easy way to retrieve the glyph outlines of text strings--by using the GetPath GDI function.

The article comes with a Direct3D 8 sample application (135 KB).

This article assumes good knowledge of C++, Direct3D, and general Windows programming. It might be convenient to have the sample project opened in your development environment while reading the article.

Introduction

Just recently I was searching the Internet for some ready-to-use polygon triangulation code--or at least a good tutorial. I didn't find either. Some of the sites offer explanations, others have code that supports convex polygons only. Others have code that doesn't support polygons with holes. After searching for a few hours I gave up and decided to invent my own algorithm. This isn't exactly a quick solution, but I thought it might be fun. It wasn't.

Then I remembered that I had read about polygon triangulation in the OpenGL docs. I wondered whether I could manage to combine Direct3D and OpenGL functionality. And you know what--it worked.

This tutorial is for all those who prefer finding on the Internet to searching the Net. This article is divided into the following sections:

1. Converting Text into Polygons--In this section, we'll discuss the merits of the GDI Path functions. We'll use these functions to retrieve the polygons that make up TrueType text.
2. The GLU Tesselation Functions--In this section, I'll give you a detailed explanation of the built-in triangulation mechanism of OpenGL.
3. Adding Depth to a Polygon--In this section, we'll extrude the flat mesh that we created in the preceding step. The resulting mesh will have texture coordinates and the normal vectors for a smooth surface.

Converting Text to Polygons

One of the most common uses for polygon triagulation and extrusion is producing 3D text meshes. And producing 3D text is exactly what we'll be doing in this tutorial. First, we'll use the functions of the Windows GDI to draw the text into a so-called GDI path. We'll then use a path function to convert the Bézier curves in the font into straight-line segments. Next, we'll retrieve the list of polygon vertices.

As it turns out, text isn't the only output that can be converted into polygons this way. The described procedure works with the output of many other GDI primitive drawing functions as well. More on this later.

An Overview of GDI Paths

The easiest way of getting things done is having someone else do it. In our case, that someone is the GDI. Although you could use the GetGlyphOutline function to retrieve the glyph outlines of a TrueType font, this isn't really fun. Fortunately, when reading the Windows 2000 Graphics API Black Book by Damon Chandler (a book that I can recommend, not only because I wrote the DirectDraw part of it!), I came across the GDI path functions. These functions make retrieving the glyph outlines of TrueType fonts a lot easier. A path is a special type of GDI graphic object that records a series of drawing routines. Once recorded, you can edit the path, draw its outline, or fill its interior. By using paths, you can assemble fancy shapes of simple primitives. Text is just such a fancy shape, made up of lines and Bézier curves.

Some text as rendered by the GDI directly (top)
and rendered manually from its path representation (bottom)

Using GDI Paths

To begin recording GDI drawing routines, you open a path bracket by calling the BeginPath function. To stop recording, you call the EndPath function. Between these function calls, you can record a number of GDI functions, including TextOut, ExtTextOut, MoveToEx, LineTo, PolyBezier, Polygon, and others. (Windows 2000 supports a few more functions within a path bracket than does Windows 95.)

The following code draws some text into a path:

// hDC is a handle to a device context (can be an off-screen
device context)

// open a path bracket
BeginPath(hDC);

// print some text
TextOut(hDC, 0, 0, "Some text", 9);

// close the path bracket
EndPath(hDC);

Note: Before you call the TextOut function, make sure that a TrueType font is selected into the device context. The quality of the resulting mesh depends on the size of the currently selected font. A font with a size of 16 pixels, for example, results in a mesh that is approximately 16 units high and that has a relatively low polygon count. A font with a size of 100 pixels, on the other hand, results in a higher polygon count.

At this point, the path contains a series of polygons, each consisting of lines and curves. There should be 11 polygons in the path, one for each character in the string "Some text" and three for the holes in the letters "o" and "e".

A polygon consisting of several contours

Before we can triangulate the polygons, we should get rid of the curves. This can be done with a simple call to the FlattenPath function:

// convert Bézier curves in the path to straight lines
FlattenPath(hDC);

It's that easy. Next, we want to retrieve the list of polygon vertices. The GetPath function does just that. The function is declared as follows:

int GetPath(
    HDC hdc,          // handle to device context
    LPPOINT lpPoints, // pointer to array receiving path vertices
    LPBYTE lpTypes,   // pointer to array of path vertex types
    int nSize         // count of points defining path
);

When you set the lpPoints and lpTypes parameters to NULL, the GetPath function returns the number of vertices in the path. You can use this return value to allocate the arrays for the vertex data and for the vertex type data. The following code demonstrates this:

LPPOINT p_points = NULL;
LPBYTE p_types = NULL;

try
{
    // determine the number of endpoints in the path
    const int num_points = GetPath(hDC, NULL, NULL, 0);

    if (num_points > 0)
    {
        // allocate memory for the point data and for the vertex types
        p_points = new POINT[num_points];
        p_types = new BYTE[num_points];

        // get the path's description
        GetPath(hDC, p_points, p_types, num_points);

        // ...
    }
}
catch (...)
{
    SAFE_DELETE_ARRAY(p_points);
    SAFE_DELETE_ARRAY(p_types);
}

Note: The coordinates of the points are specified in the device context's coordinate space. Usually, this means that the positive y-axis points down. In Direct3D applications, it's usually the other way round. Before you use the point data that is returned by the GetPath function with Direct3D, remember to multiply the y coordinates by -1. Otherwise, the meshes will appear upside down.

When the GetPath function returns successfully, the p_points array contains num_points POINT structures. The entries of the p_types array specify how these POINT structures should be interpreted. Possible values are PT_MOVETO, PT_LINETO, or PT_BEZIERTO. (Because we used the FlattenPath function to convert the Bézier curves, the PT_BEZIERTO flag will not be reported.) In addition, the PT_LINETO and PT_BEZIERTO flags can be combined with the PT_CLOSEFIGURE flag.

When drawing the path contents manually, the PT_ flags specify which GDI function you must call. PT_MOVETO stands for the MoveTo function, PT_LINETO stands for the LineTo function, and PT_BEZIERTO stands for the BezierTo function. When the PT_CLOSEFIGURE flag is set, the figure is closed by drawing another line to the point corresponding to the last PT_MOVETO.

As I mentioned earlier, a path usually contains several polygons at the same time. Holes in polygons are polygons themselves. This is also how we're going to pass the polygons to the GLU tesselation functions. Following GLU terminology, I'll refer to the entire contents of a path as polygon, and to the single polygons as contours. In the sample application, I'm using STL vectors (std::vector) to store the contents of a path. The class Contour is defined as a vector of POINT structures, and a PathPolygon is defined as a vector of Contour objects:

#include <vector>

class Contour : public std::vector<POINT>
class PathPolygon : public std::vector<Contour>

The following code fills a PathPolygon object with the path data. The PT_MOVETO flag marks the beginning of a new contour.

Contour contour;

// go through the endpoints
for (int i = 0; i < num_points; i++)
{
    // if this endpoint starts a new contour
    if (p_types[i] == PT_MOVETO)
    {
        // add the previous contour if it's not empty
        if (contour.size() > 0)
        {
            pathPolygon.push_back(contour);
        }

        // start a new contour
        contour.clear();
    }

    // add this endpoint to the contour
    contour.push_back(p_points[i]);
}

// add the last contour
if (contour.size() > 0)
{
    pathPolygon.push_back(contour);
}

At this point, the text has been converted into a bunch of polygons. However, not all of these polygons are convex, some of them have holes, and some might even be self-intersecting. In short, it's completely impossible to render these polygons with Direct3D. In the next section, we'll use the OpenGL Utility (GLU) library to convert the contours into a list of triangles.

The GLU Tesselation Functions

A concave polygon with one hole (left) and the same polygon after tesselation (right)

The OpenGL Utility (GLU) library is part of the OpenGL specification. This means that every Windows machine has a copy of the glu32.dll file. The GLU functions are implemented in software and don't require an OpenGL rendering context, i.e., they're independent of the graphics driver. Therefore, GLU is the only component of OpenGL that you can use together with Direct3D. This being said, let's take a closer look at the GLU tesselation functions.

The Tesselation Object

In the GLU library, tesselation is managed by tesselation objects. You retrieve a handle to such an object by calling the gluNewTess function. When you're done working with the object, free the resources by calling the gluDeleteTess function:

#include <gl/glu.h>

// create tesselation object
GLUtesselator* tess = gluNewTess();

if (tess == NULL)
{
    throw std::runtime_error("Creation of tesselation object
        failed.");
}

// ...

// destroy the tesselation object
gluDeleteTess(tess);

Passing Vertices to the Tesselator

The process of passing vertices to the tesselation object and performing the triangulation can be divided into five steps:

1. gluTessBeginPolygon begins a new polygon.
2. gluTessBeginContour begins a new contour. Recall that a polygon can be made up of several contours. Holes within polygons are passed as separate contours as well.
3. gluTessVertex is called repeatedly to pass the vertices to the tesselator.
4. gluTessEndContour ends the contour. If there are more contours in the polygon, continue at Step 2.
5. gluTessEndPolygon instructs the GLU library to begin with the triangulation.

Calling the gluTessBeginPolygon and gluTessBeginContour functions is straightforward. Both functions take a handle to a tesslation object as their first parameter. The second parameter of the gluTessBeginPolygon function is an opaque void pointer. This pointer is used similarly to the lpContext parameters that were used in previous versions of Direct3D for the enumeration functions. The value of the parameter is passed to the callback functions and can be used, for example, to pass an object's this pointer to a callback function that is a static member of the object. We'll discuss the GLU tesselation callbacks shortly.

The only parameter of the gluTessBeginContour function is the handle to the tesselation object.

Note: In earlier versions of OpenGL, one used the gluNextContour function instead of gluTessBeginContour and gluTessEndContour. The gluNextContour function looks quite promising, as it takes a parameter that specifies whether the contour is an exterior contour or an interior contour, i.e., a hole within a contour, and whether the vertices are defined in counterclockwise order or in clockwise order . However, don't bother calculating whether a contour is exterior or interior. The gluNextContour function is obsolete and is simply mapped to a call to gluTessEndContour followed by a call to gluTessBeginContour in OpenGL 1.2.

The gluTessVertex function is declared as follows:

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

The first parameter, tess, is the handle to the tesselation object. The second parameter, coords, is a pointer to an array of three doubles specifying the vertex coordinates. Note that you can pass a pointer to any custom vertex structure, as long as the first entries contain the x, y, and z coordinates of the vertex as double-precision floating-point values.

The third parameter, data, is an opaque pointer that is passed to the vertex callback as is. While the coords parameter is used to pass the position of the vertex to the GLU tesselator, you can use the data parameter to identify the vertex after the triangulation took place. The accompanying sample application, for example, stores the vertex data in a vector of custom vertex structures. In addition to the vertex position, these structures store a normal vector and a pair of texture coordinates. To be able to refer to this additonal information from the callback functions, the sample code passes the index of the vertex within the vertex vector as the data parameter. This is demonstrated in the following code:

// Vertices is a std::vector of custom vertex structures
// vertex_num is an index into this vector

gluTessVertex(tess,
              reinterpret_cast<double*>(&Vertices[vertex_num]),
              reinterpret_cast<void*>(vertex_num));

The gluTessEndContour and gluTessEndPolygon functions take the handle to the tesselation object as their only parameter. After you call the gluTessEndPolygon function, the triangulation process starts. The resulting triangles are passed back to the caller by means of callback functions. These callbacks are discussed in the following section.

Working with the Tesselation Callbacks

The GLU library defines a number of callback functions that are invoked during tesselation to resolve intersections of polygon edges and after the tesselation to pass back the resulting triangles to the caller. In this section, we'll discuss these callback functions in detail.

Callback functions are user-defined, i.e., they are implemented in your application. You register your callbacks with GLU by passing their addresses to the gluTessCallback function. The gluTessCallback function is declared as follows:

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

The which parameter specifies which callback you wish to register. The fn parameter is a pointer to the callback function itself. The following callback functions are defined:

void __stdcall begin(GLenum type);

void __stdcall beginData(GLenum type,
    void* polygon_data
);

void __stdcall end();

void __stdcall endData(void* polygon_data);

void __stdcall vertex(void* vertex_data);

void __stdcall vertexData(void* vertex_data,
    void* polygon_data
);

void __stdcall edgeFlag(GLboolean flag);

void __stdcall edgeFlagData(GLboolean flag,
    void* polygon_data
);

void __stdcall combine(GLdouble coords[3],
    void* vertex_data[4],
    GLfloat weight[4],
    void** outData
);

void __stdcall combineData(GLdouble coords[3],
    void* vertex_data[4],
    GLfloat weight[4],
    void** outData,
    void* polygon_data
);

void __stdcall error(GLenum errno);

void __stdcall errorData(GLenum errno,
    void* polygon_data
);

Most of the GLU tesselation callbacks are self-explanatory and trivial to implement. Those that require a little more explanation are discussed in the following sections. (For a full example of how the callbacks are used, see the accompanying sample project.)

The GLU_TESS_EDGE_FLAG Callback

Bounding and non-bounding edges within a triangulated polygon

The GLU_TESS_EDGE_FLAG callback is useful within OpenGL programs when you want to draw the outline of a triangulated polygon. The callback is invoked with a flag that specifies whether the edges that are defined by the following vertices are boundary edges or not. (A boundary edge is an edge that separates the polygon interior from the polygon exterior.) Edge flags can't be reported for triangle fans and triangle strips. Therefore, when you register a GLU_TESS_EDGE_FLAG (or GLU_TESS_EDGE_FLAG_DATA) callback, the GLU library converts all triangle strips and triangle fans to simple triangle lists. For simplicity, we take this approach in our sample application. The callback is implemented as follows:

void __stdcall EdgeFlagDataCB(GLboolean flag,
    void* lpContext)
{
    // empty
}

And registered with the following function call: (tess is a handle to a tesselation object)

typedef void (__stdcall *GluTessCallbackType)();

gluTessCallback(tess,
    GLU_TESS_EDGE_FLAG_DATA,
    reinterpret_cast<GluTessCallbackType>(EdgeFlagDataCB)
);

The GLU_TESS_VERTEX Callback

The GLU_TESS_VERTEX callback is invoked after the triangulation is completed, i.e., some time after you call gluTessEndPolygon. With every call, you receive the vertex identifier that you passed to the gluTessVertex function when sending vertices to the tesselator. For example, let's say the following four gluTessVertex calls were used to specify a rectangle:

gluTessVertex(tess, vertex[0], 0);
gluTessVertex(tess, vertex[1], 1);
gluTessVertex(tess, vertex[2], 2);
gluTessVertex(tess, vertex[3], 3);

The elements of the vertex array are, in turn, arrays of 3 double-precision floating-point numbers. These numbers contain the three-dimensional coordinates of the vertex. The vertices are passed to the gluTessVertex function as its second parameter. The third parameter is an identifier that you can use later on to uniquely identify the vertices when the GLU_TESS_VERTEX (or GLU_TESS_VERTEX_DATA) callback is invoked. The callback might be defined as follows:

void __stdcall VertexCB(unsigned int vertexIndex)
{
    // vertexIndex gives the index of the vertex
    //within the array of vertices
}

When the above rectangle is triangulated, the callback might be invoked by the GLU library as follows:

// first triangle
VertexCB(0);
VertexCB(1);
VertexCB(2);
// second triangle
VertexCB(0);
VertexCB(2);
VertexCB(3);

Of course, you could pass any value as the third parameter to the gluTessVertex function, for example a pointer to the vertex data itself. However, in the sample application I'm using indexed primitives: The vertex data is stored in a Direct3D vertex buffer, and I have the vertex index passed to the GLU_TESS_VERTEX callback to fill the corresponding index buffer.

The GLU_TESS_COMBINE Callback

Let's begin our discussion of the GLU_TESS_COMBINE callback with a recap of the GLU_TESS_VERTEX callback. For each vertex in the mesh, the GLU_TESS_VERTEX callback receives the data that you passed to the gluTessVertex callback. In our example, we had the GLU library pass back the index of the vertex within our own vertex array. But what if, during triangulation, new vertices must be created? This can happen when some edges of the polygon are self-intersecting, for example. The tesselator knows where the new vertex must be inserted, but it doesn't know what to pass to the GLU_TESS_VERTEX callback. The solution: The library asks your program to assign an identifier to the newly created vertex. This gives you a chance to insert the vertex into your internal vertex array (which could be a Direct3D vertex buffer, for instance) and, if need be, to assign texture coordinates or a color to the vertex.

A self-intersecting polygon

The generic prototype of the GLU_TESS_COMBINE callback looks like this: (The GLU_TESS_COMBINE_DATA callback adds a void* paramter)

void __stdcall combine(GLdouble coords[3],
    void* vertex_data[4],
    GLfloat weight[4],
    void** outData
);

The first parameter, coords, specifies the coordinates of the new vertex as calculated by the GLU library. This array is not for you to modify but for your information only. The vertex_data parameter is an array that contains the identifiers of the four vertices that surround the new vertex. The entries of this array are interpreted in exactly the same way as the parameter to the GLU_TESS_VERTEX function, i.e., the values are what you passed to the gluTessVertex function when specifying the four vertices.

The next parameter, weight, points to an array that stores information about how much influence the four vertices in the vertex_data array have on the newly created vertex. This is useful, for example, to assign texture coordinates or a color to the new vertex. The four floats in the weight array always add up to 1.0. To assign texture coordinates to the newly created vertex that are an interpolation of the texture coordinates of the four surrounding vertices, you could write code like the following:

void __stdcall CombineCB(GLdouble coords[3],
    unsigned int vertexData[4],
    GLfloat weight[4],
    unsigned int* outData)
{
    // construct new vertex with the specified coordinates
    MyVertexType new_vertex = MyVertexType(coords);

    // interpolate texture coordinates
    new_vertex.u = my_vertex_array[vertexData[0]].u * weight[0] +
        my_vertex_array[vertexData[1]].u * weight[1] +
        my_vertex_array[vertexData[2]].u * weight[2] +
        my_vertex_array[vertexData[3]].u * weight[3];
    new_vertex.v = my_vertex_array[vertexData[0]].v * weight[0] +
        my_vertex_array[vertexData[1]].v * weight[1] +
        my_vertex_array[vertexData[2]].v * weight[2] +
        my_vertex_array[vertexData[3]].v * weight[3];

    // store the new vertex in our vertex buffer
    unsigned int index =
        insert_vertex_into_vertex_buffer(new_vertex);

    // tell the GLU library how to refer to the new vertex in calls to
    // the GLU_TESS_VERTEX callback by storing the index at outData
    *outData = index;

}

First, a new vertex with the specified coordinates is constructed. In the above code snippet, we assume that the structure MyVertexType has a constructor that takes the coordinates from an array of three GLdouble values. Next, we calculate the U and V texture coordinates by interpolating the vertex coordinates of the four surrounding vertices. Then we insert the new vertex into our vertex buffer and store its index at the location pointed to by the outData parameter. This value will be used by the GLU library in subsequent calls to the GLU_TESS_VERTEX (or GLU_TESS_VERTEX_DATA) callback to refer to this vertex.

To see how all these concepts fit together, please refer to the accompanying sample code. The tesselation is performed in the PathExtruder class that is implemented in the files PathExtruder.h and PathExtruder.cpp.

Adding Depth to a Polygon

After converting a polygon into a list of triangles with the help of the GLU tesselation functions, the polygon is still flat. In this section, we'll discuss how to add depth to the flat mesh, i.e., how to extrude the polygon. Conceptually, extrusion is very simple: The result of the GLU tesselation is the front surface of the body. The back suface can be created by rotating the front surface 180° around the y-axis and translating it a few units along the z-axis. Then, one has to add the side faces, which is achieved by connecting the vertices of the front surface with the vertices of the back surface.

Creating the Back Surface

To create the back surface, simply duplicate the vertices of the front surface, i.e., the vertices of the mesh that the GLU tesselator produced. Increase the z-coordinates of the new vertices by a few units, depending on how much you wish to extrude the polygon. If your vertex structure contains a normal vector (as the one in the sample application does), don't forget to have the normals of the new vertices point to the opposite direction. You can do this by multiplying the z-coordinate of the normal vector by -1.0. Next, you must add new indices for the back surface. To do this, duplicate the indices for the front surface and add an offset that equals the number of vertices reserved for the front surface. For each triangle ABC, make sure to swap indices B and C so that the winding of the back surface triangles is becomes clockwise again. The following code snippet demonstrates this whole process:

// create back surface

// create vertices
for (int v = 0; v < num_front_face_vertices; v++)
{
    MyVertexStruct new_vertex = my_vertex_array[v];
    new_vertex.z += 50.0;   // make body 50 units deep
    new_vertex.nz *= -1.0;  // adjust normal vector

    insert_vertex_into_vertex_buffer(new_vertex);
}

// create indices

for (int t = 0; t < num_front_face_triangles; t++)
{
    insert_index_into_index_buffer(front_face_indices[t * 3] +
        num_front_face_vertices);
    insert_index_into_index_buffer(front_face_indices[t * 3 + 2] +
        num_front_face_vertices);
    insert_index_into_index_buffer(front_face_indices[t * 3 + 1] +
        num_front_face_vertices);
}

Creating the Side Faces

Recall that we used the GDI path functions to convert some text into a series of contours. If you kept a copy of these contours, you can now use them to easily build the side faces of the extruded polygon. For this, you simply have to go through the points in each of the contour. For each point, you create two vertices--one with a z-coordinate that equals the z-coordinate of the front surface of the extruded polygon and one with a z-coordinate that equals the z-coordinate of the back surface of the extruded polygon. Creating new vertices is necessary because they will have different normal vectors than the front and back surface vertices.

After creating the vertices, you create two triangles by inserting indices into the index buffer. The first triangle is defined by the front vertex of this contour point, the back vertex of this contour point, and the front vertex of the next contour point, in this order. The second triangle is defined by the front vertex of the next contour point, the back vertex of this contour point, and the back vertex of the next contour point.

Please note that the vertices of the next contour point are not yet contained in the vertex buffer when you insert the indices. These vertices will be created when you process the next point in the contour.

For an example of how this could be done, see the accompanying sample application.

Calculating the Vertex Normals

For a mesh to be useful it needs a set of vertex normals. We already have the normals for the front and back surfaces. They were easy enough to produce. Producing the normals for the side faces is a bit less easy, but it isn't rocket science either. (Or do you need normal vectors for rocket science as well?)

To produce smooth edges, the normal vector of a given vertex must be the average of the normal vectors of the edges that meet at that vertex. This is essentially the same as the normalized sum of the edge normals. However, if you treat all edges as smooth, the result will look completely fake. Therefore, we need to implement some intelligence that automatically detects whether an edge should be smooth or not. For our purposes, we treat edges that meet at an angle between 135° and 225° as smooth. If the angle between two edges is less than 135° or more than 225°, the vertex between these edges is duplicated. The first vertex is assigned the normal of the first edge, the second vertex is assigned the normal of the second edge.

Left: Angles less than 135° designate a sharp edge
Center: Angles between 135° and 225° designate a smooth edge
Right: Angles greater than 225° designate a sharp edge

To summarize, these are the required steps:

1. Calculate the angle between the edges that meet at this contour point.
2. If the angle is between 135° and 225°, continue at Step 4.
3. This is a sharp edge. Create two vertices for this contour point. Set the normal of the first vertex to the normal of the previous contour edge. Set the normal of the second vertex to the normal of this contour edge.
4. This is a smooth edge. Create one vertex for this contour point. Calculate the normal of the previous contour edge. Calculate the normal of this contour edge. Set the normal of the vertex to the average of the two edge normal.

You can find the formulae for calculating such things as the angle between two vectors in the following sidenote. For a coding example, please see the sample project.

Adding Texture Coordinates

Adding texture coordinates to the resulting mesh is straightforward. As you know, texture coordinates range from 0.0 to 1.0, where 0.0 designates the left/upper edge of the texture bitmap and 1.0 designates the right/lower edge of the texture bitmap. To project a texture onto the front surface of the mesh, first calculate the width and the height of the triangulated polygon. The following code demonstrates this:

double min_x = my_vertex_array[0].x;
double max_x = min_x;
double min_y = my_vertex_array[0].y;
double max_y = min_y;

// go through the vertices
for (int i = 0; i < num_vertices; i++)
{
    if (my_vertex_array[i].x < min_x)
    { min_x = my_vertex_array[i].x; }
    if (my_vertex_array[i].x > max_x)
    { max_x = my_vertex_array[i].x; }
    if (my_vertex_array[i].y < min_y)
    { min_y = my_vertex_array[i].y; }
    if (my_vertex_array[i].y > max_y)
    { max_y = my_vertex_array[i].y; }
}

double width = max_x - min_x;
double height = max_y - min_y;

When a vertex at x = 0.0 has the texture coordinate u = 0.0 and a vertex at x = 100.0 has the texture coordinate u = 1.0, then a vertex at x = 50.0, which is at the center of the mesh, should have the texture coordinate u = 0.5. In a more general form, this can be written as:

my_vertex_array[i].u = my_vertex_array[i].x - min_x * (1.0 / width);
my_vertex_array[i].v = my_vertex_array[i].y - min_y * (1.0 / height);

Following this scheme, the following code snippet applies texture coordinates to all vertices in the mesh:

const double u_per_x = 1.0 / width;
const double v_per_y = 1.0 / height;

for (int i = 0; i < num_vertices; i++)
{
    my_vertex_array[i].u = my_vertex_array[i].x - min_x * u_per_x;
    my_vertex_array[i].v = my_vertex_array[i].y - min_y * v_per_y;
}

Final Words

That's it. We have just created a 3D text mesh, complete with texture coordinates and a smooth surface. The GDI converted the TrueType text into a series of polygons for us. The OpenGL Utility library performed the triangulation for us. All we had to do was call a few functions, add a few vertices, and calculate some normal vectors. That's what I call a quick solution!

I hope you can make use of the techniques presented in this article. Feel free to experiment with the code. If you liked this tutorial, point your friends to this site. If you have any questions, suggestions, or comments, send me an e-mail at foetsch@crosswinds.net.