March 2014

Volume 29 Number 3

# DirectX Factor : Triangles and Tessellation

Charles Petzold

The triangle is the most basic two-dimensional figure. It’s nothing more than three points connected by three lines, and if you try to make it any simpler, it collapses into a single dimension. On the other hand, any other type of polygon can be decomposed into a collection of triangles.

Even in three dimensions, a triangle is always flat. Indeed, one way to define a plane in 3D space is with three non-collinear points, and that’s a triangle. A square in 3D space isn’t guaranteed to be flat because the fourth point might not be in the same plane as the other three. But that square can be divided into two triangles, each of which is flat, although not necessarily on the same plane.

In 3D graphics programming, triangles form the surfaces of solid figures, starting with the simplest of all three-dimensional figures, the triangular pyramid, or tetrahedron. Assembling a seemingly solid figure from triangle “building blocks” is the most fundamental process in 3D computer graphics. Of course, the surfaces of real-world objects are often curved, but if you make the triangles small enough, they can approximate curved surfaces to a degree sufficient to fool the human eye.

The illusion of curvature is enhanced by exploiting another characteristic of triangles: If the three vertices of a triangle are associated with three different values—for example, three different colors or three different geometric vectors—these values can be interpolated over the surface of the triangle and used to color that surface. This is how triangles are shaded to mimic the reflection of light seen in real-world objects.

## Triangles in Direct2D

Triangles are ubiquitous in 3D computer graphics. Much of the work performed by a modern graphics processing unit (GPU) involves rendering triangles, so of course Direct3D programming involves working with triangles to define solid figures.

In contrast, triangles aren’t found at all in most 2D graphics programming interfaces, where the most common two-dimensional primitives are lines, curves, rectangles and ellipses. So it’s somewhat surprising to find triangles pop up in a rather obscure corner of Direct2D. Or maybe it’s really not that surprising: Because Direct2D is built on top of Direct3D, it seems reasonable for Direct2D to take advantage of the triangle support in Direct3D and the GPU.

The triangle structure defined in Direct2D is simple:

``````struct D2D1_TRIANGLE
{
D2D1_POINT_2F point1;
D2D1_POINT_2F point2;
D2D1_POINT_2F point3;
};
``````

As far as I can determine, this structure is used in Direct2D only in connection with a “mesh,” which is a collection of triangles stored in an object of type ID2D1Mesh. The ID2D1RenderTarget (from which ID2D1DeviceContext derives) supports a method named CreateMesh that creates such an object:

``````ID2D1Mesh * mesh;
deviceContext->CreateMesh(&mesh);
``````

(To keep things simple, I’m not showing the use of ComPtr or checking HRESULT values in these brief code examples.) The ID2D1Mesh interface defines a single method named Open. This method returns an object of type ID2D1TessellationSink:

``````ID2D1TessellationSink * tessellationSink;
mesh->Open(&tessellationSink);
``````

In general, “tessellation” refers to the process of covering a surface with a mosaic pattern, but the term is used somewhat differently in Direct2D and Direct3D programming. In Direct2D, tessellation is the process of decomposing a two-dimensional area into triangles.

The ID2D1TessellationSink interface has just two methods: Add­Triangles (which adds a collection of D2D1_TRIANGLE objects to the collection) and Close, which makes the mesh object immutable.

Although your program can call AddTriangles itself, often it will pass the ID2D1TessellationSink object to the Tessellate method defined by the ID2D1Geometry interface:

``````geometry->Tessellate(IdentityMatrix(), tessellationSink);
tessellationSink->Close();
``````

The Tessellate method generates triangles that cover the areas enclosed by the geometry. After you call the Close method, the sink can be discarded and you’re left with an ID2D1Mesh object. The process of generating the contents of an ID2D1Mesh object using an ID2D1TessellationSink is similar to defining an ID2D1Path­Geometry using an ID2D1GeometrySink.

You can then render this ID2D1Mesh object using the FillMesh method of ID2D1RenderTarget. A brush governs how the mesh is colored:

``````deviceContext->FillMesh(mesh, brush);
``````

Keep in mind that these mesh triangles define an area and not an outline of an area. There is no DrawMesh method.

FillMesh has a limitation: Anti-aliasing can’t be enabled when FillMesh is called. Precede FillMesh with a call to SetAntialiasMode:

``````deviceContext->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);
``````

You might wonder: What’s the point? Why not just call FillGeometry on the original geometry object? The visuals should be the same (aside from the anti-aliasing). But there’s actually a profound difference between ID2D1Geometry and ID2D1Mesh objects that’s revealed by how you create these two objects.

Geometries are mostly just collections of coordinate points, so geometries are device-independent objects. You can create various types of geometries by calling methods defined by ID2D1Factory.

A mesh is a collection of triangles, which are just triplets of coordinate points, so a mesh should be a device-independent object as well. But you create an ID2D1Mesh object by calling a method defined by ID2D1RenderTarget. This means the mesh is a device-dependent object, like a brush.

This tells you the triangles that comprise the mesh are stored in a device-dependent manner, most likely in a form suitable for processing by the GPU, or actually on the GPU. And this means that FillMesh should execute much faster than FillGeometry for the equivalent figure.

Shall we test that hypothesis?

Among the downloadable code for this article is a program named MeshTest that creates a path geometry for a 201-point star, and slowly rotates it while calculating and displaying the frame rate. When the program is compiled in Debug mode for the x86 and runs on my Surface Pro, I get a frame rate of less than 30 frames per second (FPS) when rendering the path geometry (even if the geometry is outlined to eliminate overlapping areas and flattened to eliminate curves), but the frame rate leaps up to 60FPS when rendering the mesh.

Conclusion: For complex geometries, it makes sense to convert them to meshes for rendering. If the need to disable anti-aliasing to render this mesh is a deal-breaker, you might want to check out ID2D1GeometryRealization, introduced in Windows 8.1. This combines the performance of ID2D1Mesh but allows anti-aliasing. Keep in mind meshes and geometry realizations must be recreated if the display device is recreated, just as with other device-dependent resources such as brushes.

## Examining the Triangles

I was curious about the triangles generated by the tessellation process. Could they actually be visualized? The ID2D1Mesh object doesn’t allow you to access the triangles that comprise the mesh, but it’s possible to write your own class that implements the ID2D1TessellationSink interface, and pass an instance of that class to the Tessellate method.

I called my ID2D1TessellationSink implementation Interrogable­TessellationSink, and it turned out to be embarrassingly simple. It contains a private data member for storing triangle objects:

``````std::vector<D2D1_TRIANGLE> m_triangles;
``````

Most of the code is dedicated to implementing the IUnknown interface. Figure 1 shows the code required to implement the two ID2D1TessellationSink methods and obtain the resultant triangles.

Figure 1 The Relevant Code of InterrogableTessellationSink

``````// ID2D1TessellationSink methods
UINT trianglesCount)
{
for (UINT i = 0; i < trianglesCount; i++)
{
m_triangles.push_back(triangles[i]);
}
}
HRESULT InterrogableTessellationSink::Close()
{
// Assume the class accessing the tessellation sink knows what it's doing
return S_OK;
}
// Method for this implementation
std::vector<D2D1_TRIANGLE> InterrogableTessellationSink::GetTriangles()
{
return m_triangles;
}
``````

I incorporated this class in a project named Tessellation­Visualization. The program creates geometries of various sorts—everything from a simple rectangle geometry to geometries generated from text glyphs—and uses InterrogableTessellationSink to obtain the collection of triangles created by the Tessellate method. Each triangle is then converted into an ID2D1PathGeometry object consisting of three straight lines. These path geometries are then rendered using DrawGeometry.

As you might expect, an ID2D1RectangleGeometry is tessellated into just two triangles, but the other geometries are more interesting. Figure 2 shows the triangles that comprise an ID2D1Rounded­RectangleGeometry.

Figure 2 A Rounded Rectangle Decomposed into Triangles

This isn’t the way a human being would tessellate the rounded rectangle. A human being would probably divide the rounded rectangle into five rectangles and four quarter-circles, and tessellate each of those figures separately. In particular, a human would slice the four quarter-circles into pie wedges.

In other words, a human being would define several more points in the interior of the geometry to aid in the tessellation. But the tessellation algorithm defined by the geometry object doesn’t use any points beyond those created by the flattening of the geometry.

Figure 3 shows two characters rendered with the Pescadero font decomposed into triangles.

Figure 3 Text Decomposed into Triangles

I was also curious about the order in which these triangles were generated, and by clicking the Gradient Fill option at the bottom left of the window, you can find out. When this option is checked, the program calls FillGeometry for each of the triangle geometries. A solid color brush is passed to FillGeometry but the color depends on the triangle’s index in the collection.

What you’ll find is that the FillGeometry option renders something akin to a top-down gradient brush, which means that triangles are stored in the collection in a visual top-down order. It appears the tessellation algorithm attempts to maximize the width of horizontal scan lines in the triangles, which probably maximizes the rendering performance.

Although I clearly recognize the wisdom of this approach, I must confess I was a little disappointed. I was hoping that a widened Bézier curve (for example) might be tessellated beginning at one end of the line and continuing to the other, so the triangles could be rendered with a gradient from one end to the other, which is not a type of gradient commonly seen in a DirectX program! But this was not to be.

Interestingly, I needed to turn off anti-aliasing before the FillGeometry calls in TessellationVisualization or faint lines appeared between the rendered triangles. These faint lines result from the anti-aliasing algorithm, which involves partially transparent pixels that don’t become opaque when overlapped. This leads me to suspect that using anti-aliasing with FillMesh isn’t a hardware or software limitation, but a restriction mandated to avoid visual anomalies.

## Triangles in 2D and 3D

After working just a little while with ID2D1Mesh objects, I began visualizing all two-dimensional areas as mosaics of triangles. This mindset is normal when doing 3D programming, but I had never extended such a triangle-centric vision to the 2D world.

The documentation of the Tessellate method indicates the generated triangles are “clockwise-wound,” which means that the point1, point2 and point3 members of the D2D1_TRIANGLE structure are ordered in a clockwise direction. This isn’t very useful information when using these triangles in 2D graphics programming, but it becomes quite important in the 3D world, where the ordering of the points in a triangle usually indicates the front or back of the figure.

Of course, I’m very interested in using these two-dimensional tessellated triangles to break through the third dimension, where triangles are most comfortably at home. But I don’t want to be in such a rush that I neglect to explore some interesting effects with tessellated triangles in two dimensions.

## Coloring Triangles Uniquely

For me, the biggest thrill in graphics programming is creating images on the computer screen of a sort I’ve never seen before, and I don’t think I’ve ever seen text tessellated into triangles whose colors change in a random manner. This happens in a program I call SparklingText.

Keep in mind that both FillGeometry and FillMesh involve only a single brush, so if you need to render hundreds of triangles with different colors, you’ll need hundreds of FillGeometry or FillMesh calls, each rendering a single triangle. Which is more efficient? A FillGeometry call to render an ID2D1PathGeometry that consists of three straight lines? Or a FillMesh call with an ID2D1Mesh containing a single triangle?

I assumed that FillMesh would be more efficient than FillGeometry only if the mesh contained multiple triangles, and it would be slower for one triangle, so I originally wrote the program to generate path geometries from the tessellated triangles. Only later did I add a CheckBox labeled “Use a Mesh for each triangle instead of a PathGeometry” and incorporated that logic as well.

The strategy in the SparklingTextRenderer class of SparklingText is to use the GetGlyphRunOutline method of ID2D1FontFace to obtain a path geometry for the character outlines. The program then calls the Tessellate method on this geometry with the InterrogableGeometrySink to get a collection of D2D1_TRIANGLE objects. These are then converted into path geometries or meshes (depending on the CheckBox value) and stored in one of two vector collections named m_triangleGeometries and m_triangleMeshes.

Figure 4 shows a pertinent chunk of the Tessellate method that fills these collections, and the Render method that renders the resultant triangles. As usual, HRESULT-checking has been removed to simplify the code listings.

Figure 4 Tessellation and Rendering Code in SparklingTextRenderer

``````void SparklingTextRenderer::Tessellate()
{
...
// Tessellate geometry into triangles
ComPtr<InterrogableTessellationSink> tessellationSink =
new InterrogableTessellationSink();
pathGeometry->Tessellate(IdentityMatrix(), tessellationSink.Get());
std::vector<D2D1_TRIANGLE> triangles = tessellationSink->GetTriangles();
if (m_useMeshesNotGeometries)
{
// Generate a separate mesh from each triangle
ID2D1DeviceContext* context = m_deviceResources->GetD2DDeviceContext();
for (D2D1_TRIANGLE triangle : triangles)
{
ComPtr<ID2D1Mesh> triangleMesh;
context->CreateMesh(&triangleMesh);
ComPtr<ID2D1TessellationSink> sink;
triangleMesh->Open(&sink);
sink->Close();
m_triangleMeshes.push_back(triangleMesh);
}
}
else
{
// Generate a path geometry from each triangle
for (D2D1_TRIANGLE triangle : triangles)
{
ComPtr<ID2D1PathGeometry> triangleGeometry;
d2dFactory->CreatePathGeometry(&triangleGeometry);
ComPtr<ID2D1GeometrySink> geometrySink;
triangleGeometry->Open(&geometrySink);
geometrySink->BeginFigure(triangle.point1, D2D1_FIGURE_BEGIN_FILLED);
geometrySink->EndFigure(D2D1_FIGURE_END_CLOSED);
geometrySink->Close();
m_triangleGeometries.push_back(triangleGeometry);
}
}
}
void SparklingTextRenderer::Render()
{
...
Matrix3x2F centerMatrix = D2D1::Matrix3x2F::Translation(
(logicalSize.Width - (m_geometryBounds.right + m_geometryBounds.left)) / 2,
(logicalSize.Height - (m_geometryBounds.bottom + m_geometryBounds.top)) / 2);
context->SetTransform(centerMatrix *
m_deviceResources->GetOrientationTransform2D());
context->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);
if (m_useMeshesNotGeometries)
{
for (ComPtr<ID2D1Mesh>& triangleMesh : m_triangleMeshes)
{
float gray = (rand() % 1000) * 0.001f;
m_solidBrush->SetColor(ColorF(gray, gray, gray));
context->FillMesh(triangleMesh.Get(), m_solidBrush.Get());
}
}
else
{
for (ComPtr<ID2D1PathGeometry>& triangleGeometry : m_triangleGeometries)
{
float gray = (rand() % 1000) * 0.001f;
m_solidBrush->SetColor(ColorF(gray, gray, gray));
context->FillGeometry(triangleGeometry.Get(), m_solidBrush.Get());
}
}
...
}
``````

Based on the video frame rate (which the program displays), my Surface Pro renders the meshes faster than the path geometries, despite the fact that each mesh contains just a single triangle.

The animation of the colors is unnervingly reminiscent of a scintillating migraine aura, so you might want to exercise some caution when viewing it. Figure 5 shows a still image from the program, which should be much safer.

Figure 5 The SparklingText Display

## Moving the Tessellated Triangles

The remaining two programs use a strategy similar to SparklingText to generate a collection of triangles to form glyph outlines, but then move the little triangles around the screen.

For OutThereAndBackAgain, I envisioned text that would fly apart into its composite triangles, which would then come back to form the text again. Figure 6 shows this process at 3 percent into the flying-apart animation.

The CreateWindowSizeDependentResources method in the OutThereAndBackAgainRenderer class assembles information about each triangle in a structure I call TriangleInfo. This structure contains a single-triangle ID2D1Mesh object, as well as information necessary to take that triangle on a journey outward and back again. This journey takes advantage of a feature of geometries you can use independently of rendering. The ComputeLength method in ID2D1Geometry returns the total length of a geometry, while ComputePointAtLength returns a point on the curve and a tangent to the curve at any length. From that information you can derive translate and rotate matrices.

As you can see in Figure 6, I used a gradient brush for the text so that triangles of slightly different colors would cross paths and intermingle a bit. Even though I’m using only one brush, the desired effect requires the Render method to call SetTransform and FillMesh for every single-triangle mesh. The gradient brush is applied as if the mesh were in its original position prior to the transform.

Figure 6 A Still from the OutThereAndBackAgain Program

I wondered if it would be efficient for the Update method to transform all the individual triangles “manually” with calls to the TransformPoint method of the Matrix3x2F class, and to consolidate these in a single ID2D1Mesh object, which would then be rendered with a single FillMesh call. I added an option for that, and sure enough, it was faster. I woudn’t have imagined that creating an ID2D1Mesh in each Update call would work well, but it does. The visuals are slightly different, however: The gradient brush is applied to the transformed triangles in the mesh, so there’s no intermingling of colors.

## Text Morphing?

Suppose you tessellate the glyph outline geometries of two text strings—for example, the words “DirectX” and “Factor” that make up the name of this column—and pair up the triangles for interpolation. An animation could then be defined that transforms one word into the other. It’s not exactly a morphing effect, but I don’t know what else to call it.

Figure 7 shows the effect midway between the two words, and with a little imagination you can almost make out either “DirectX” or “Factor” in the image.

Figure 7 The TextMorphing Display

Optimally, each pair of morphing triangles should be spatially close, but minimizing the distances between all the pairs of triangles is akin to the Traveling Salesman Problem. I took a relatively simpler approach by sorting the two collections of triangles by the X coordinates of the triangle center, and then separating the collections into groups representing ranges of X coordinates, and sorting those by the Y coordinates. Of course, the two triangle collections are different sizes, so some triangles in the word “Factor” correspond to two triangles in the word “DirectX.”

Figure 8 shows the interpolation logic in Update and the rendering logic in Render.

Figure 8 Update and Render in TextMorphing

``````void TextMorphingRenderer::Update(DX::StepTimer const& timer)
{
...
// Calculate an interpolation factor
float t = (float)fmod(timer.GetTotalSeconds(), 10) / 10;
t = std::cos(t * 2 * 3.14159f);     // 1 to 0 to -1 to 0 to 1
t = (1 - t) / 2;                    // 0 to 1 to 0
// Two functions for interpolation
std::function<D2D1_POINT_2F(D2D1_POINT_2F, D2D1_POINT_2F, float)>
InterpolatePoint =
[](D2D1_POINT_2F pt0, D2D1_POINT_2F pt1, float t)
{
return Point2F((1 - t) * pt0.x + t * pt1.x,
(1 - t) * pt0.y + t * pt1.y);
};
std::function<D2D1_TRIANGLE(D2D1_TRIANGLE, D2D1_TRIANGLE, float)>
InterpolateTriangle =
[InterpolatePoint](D2D1_TRIANGLE tri0, D2D1_TRIANGLE tri1, float t)
{
D2D1_TRIANGLE triangle;
triangle.point1 = InterpolatePoint(tri0.point1, tri1.point1, t);
triangle.point2 = InterpolatePoint(tri0.point2, tri1.point2, t);
triangle.point3 = InterpolatePoint(tri0.point3, tri1.point3, t);
return triangle;
};
// Interpolate the triangles
int count = m_triangleInfos.size();
std::vector<D2D1_TRIANGLE> triangles(count);
for (int index = 0; index < count; index++)
{
triangles.at(index) =
InterpolateTriangle(m_triangleInfos.at(index).triangle[0],
m_triangleInfos.at(index).triangle[1], t);
}
// Create a mesh with the interpolated triangles
m_deviceResources->GetD2DDeviceContext()->CreateMesh(&m_textMesh);
ComPtr<ID2D1TessellationSink> tessellationSink;
m_textMesh->Open(&tessellationSink);
tessellationSink->Close();
}
// Renders a frame to the screen
void TextMorphingRenderer::Render()
{
...
if (m_textMesh != nullptr)
{
Matrix3x2F centerMatrix = D2D1::Matrix3x2F::Translation(
(logicalSize.Width - (m_geometryBounds.right + m_geometryBounds.left)) / 2,
(logicalSize.Height - (m_geometryBounds.bottom + m_geometryBounds.top)) / 2);
context->SetTransform(centerMatrix *
m_deviceResources->GetOrientationTransform2D());
context->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);
context->FillMesh(m_textMesh.Get(), m_blueBrush.Get());
}
...
}
``````

With that, I think I’ve satisfied my curiosity about 2D triangles and I’m ready to give those triangles a third dimension.

Charles Petzold is a longtime contributor to MSDN Magazine and the author of “Programming Windows, 6th edition” (Microsoft Press, 2012),  a book about writing applications for Windows 8. His Web site is charlespetzold.com.

Thanks to the following Microsoft technical experts for reviewing this article: Jim Galasyn and Mike Riches