March 2014
Volume 29 Number 3
DirectX Factor : Triangles and TessellationThe 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 Direct2DTriangles 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 TrianglesI 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
void InterrogableTessellationSink::AddTriangles(_In_ const D2D1_TRIANGLE *triangles,
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 3DAfter 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 UniquelyFor 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->AddTriangles(&triangle, 1);
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->AddLine(triangle.point2);
geometrySink->AddLine(triangle.point3);
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
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->AddTriangles(triangles.data(), triangles.size());
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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.3