GPU Text Rendering Overview

There are a few different ways to render text using the GPU. I’ll be discussing a few ways here. All these different ways represent general strategies - they can be mixed and matched. Also, this list may not be comprehensive, but I’ll only discuss the approaches that I’m familiar with. Also, note that I’m only interested in computing coverage here - not color.

First: a little background on text. Glyphs are just sequences of bezier paths (I’m ignoring “sbix” glyphs and things like that). I’m only interested in TrueType / OpenType fonts, so the form of the glyphs are given in the ‘glyf’ table or the ‘CFF ‘ table. The ‘glyf’ table only describes quadratic bezier curves, while the ‘CFF ‘ table can describe cubic bezier curves. At first, this may sound like a small difference, but it turns out that math involving cubic bezier curves is way more complicated than math involving quadratic bezier curves. (For example: finding the intersections of two cubic bezier curves involves finding roots of a 9th order polynomial - something which humanity is currently unable to compute in closed form.) Also, the winding-order is different for the two formats: the ‘glyf’ table encodes paths with a non-zero winding-order, while the ‘CFF ‘ table encodes paths with an even/odd winding-order. Subpaths are expected to intersect. This means that you can’t assume that the right-hand-side of a contour is always inside the glyph.

Texture Atlas

The first approach is kind of a hack. The text is still “rendered” on the CPU (the same way it has been done since the 70s), but the final image is uploaded into a texture atlas on the GPU. This approach actually makes the first use of a glyph slower (because of the additional upload step); however, subsequent uses of that glyph are much faster.

If a subsequent use of a glyph is slightly different in position (within a pixel) or size, there are a couple things you can do. If the position is different (one usage has its origin on the left edge of a pixel, and another usage has its origin in the middle), you might be able to get away with simply relying on the GPU’s texture filtering hardware to interpolate the result. If that isn’t good enough for you, you could snap the glyph origins to a few quanta within a pixel, and consider glyphs which differ in this snapped origin to be unique. This approach works similarly for varying glyph sizes - you can either rely on the texture filtering hardware to scale the glyph, or you could snap to a size quanta. (Or both!)

Signed Distance Field

Valve published a similar approach which they use in the Team Fortress 2 game. Recall how in the previous approach, the value of each texel is coverage of that texel. Valve’s approach uses the same idea, except that the value of each texel is a “signed distance field.” This means that the value of each texel is a signed distance of closest approach to the boundary of the curve (signed because “inside” values are negative). Using this approach causes bilinear filtering to provide higher-quality results (or, put another way, you can achieve comparable results with fewer texels).

A newer approach using signed distance fields has been implemented which uses additional color channels in the GPU texture to achieve higher-fidelity results.

Generated Geometry

The next approach is to generate geometry which matches the contours closely. GPUs can only render triangle geometry, so this means that this approach requires triangulating the input curve. One way to do this is to choose a constant triangle size. However, a better idea is to increase the triangle density in areas of high complexity, and to decrease the triangle density in areas of low complexity.

This means you want to subdivide the bezier curves finely where the curve is sharp, and loosely when the curve is loose. Luckily, the DeCasteljau method already does this! If you subdivide a Bezier curve with equal intervals using that method, the subdivision points will be closer together where the curve is sharp, and vice-versa.

Once you’ve done the subdivision, you can use a “Constrained Delaunay Triangulation” to actually run the triangulation. This is similar to a regular Delaunay triangulation, except that it can guarantee that particular edges are present in the triangulation. This means you can guarantee that no triangle will cross a contour. Therefore, each triangle can be considered to be entirely inside or entirely outside the glyph, and can be shaded accordingly.

Stencil Buffer Approach

If you don't want to run that triangulation, you can use the GPU’s stencil buffer (or equivalent) to calculate coverage instead. The idea is that you use the subdivision points to model the contours as a sequence of line segments. Then, you pick a point (let’s call it P) way off somewhere (it can be arbitrary), and, for every line segment, form a triangle with that line segment and that point P. When you do that, you’ll have lots of overlapping triangles.

You can then set up the stencil buffer to say “increment the texel’s counter if the triangle you’re shading has positive area, and decrement the texel’s counter if the triangle you’re shading has negative area” (where “negative area” and “positive area” refer to shading the “front” or “back” or the triangle, and is determined by if the points are submitted in a clockwise or counter-clockwise direction). If you shade all the triangles like this, all the overlapping triangles cancel out, and you're left with nonzero counters in all the places where the glyph lies. You can then set up the stencil buffer to say “only output a value if the stencil buffer has a nonzero value.” Note that this only works for font files which use a nonzero winding order.

This approach has the obvious performance/speed tradeoff of the subdivision density. The higher the density, the slower the rendering but the better-looking the results are. Also, you want the subdivision density to be proportional (somewhat) to the font size, since you want the subdivision density to be roughly equal in screen-space for all glyph rendered. Unfortunately, it’s difficult to use this approach to get high-quality rendering without super tiny triangles.

Loop-Blinn Method

In the first method, glyph coverage information was represented by a texture. In the third method, glyph coverage information was represented by geometry. Another method (called the Loop Blinn method) can represent glyph coverage information by using mathematical formulas. This method tries to represent a particular contour in a way that can be computed inside a fragment shader.

In particular, in order to draw a contour, you draw a single triangle which encompasses the entire contour. Inside the triangle, you define a scalar field where each point inside the triangle has a scalar value associated with it. You can create this scalar field in such a way that the following attributes hold:

• Scalar values which are negative are “inside” the contour, and scalar values which are positive are “outside” the contour
• Calculating the value of a scalar value in the field can be done in closed form by only knowing the relevant point’s location within the triangle, in addition to some interpolated information associated with the vertices of the triangle

This means that, given some vertex attributes, you can run some math in a pixel shader which will tell you if the shaded point is inside or outside the contour. So, for each contour, you consider a single triangle which includes the contour, and you then calculate some magic values to associate with each vertex of the triangle. Then, you shade that triangle with a fairly simple pixel shader which computes a closed-form equation to determine the coverage.

Note that the formulas involved with the Loop-Blinn method are much simpler for quadratic Bezier curves than for cubic Bezier curves. However, the general approach still works for cubic curves - the difference is that the formulas are bigger (and you need to perform an additional classification step).

Also note that this approach still can use the Constrained Delaunay Triangulation, because you still need to generate triangles that lie entirely within the bounds of the glyph. However, there is no need to do the heuristic subdivision like in the previous method; instead, all the triangles of the mesh are created from the control points of the contours themselves.

This means that the quality of the curves is defined by mathematical formulas, which means that it is effectively infinitely scalable. In fact, the information in the glyph contours can be losslessly converted to the information used for the Loop-Blinn method.

Overall, these methods are not monolithic things, and can be used in conjunction with one another. For example, you could use the stencil buffer approach to shade the insides of the glyph, but the Loop-Blinn method to shade the contours themselves (so that you don’t have to do any subdivision). These algorithms represent general approaches, and should be used as the basis for further thought (rather than simply coding them up wholesale).

Antialiasing with each of these methods is a pretty interesting discussion, but I’ll save that for another post.

CSS Box Model

Click for higher resolution.

Color Blending

Color blending is something which is done all the time. Your computer is doing it right now. Literally. However, it requires a little bit of thought to get it right.

There are four pieces involved when blending:

• Source color
• Coverage information (alpha)
• Destination color
• A working color space

We can all agree on what coverage is. You simply model each sample as a square, or rectangle, or circle, and decide on how much of that area is covered by the foreground. Therefore, it is fractional and unitless (because it’s a ratio). It can never be greater than 1 or less than 0. It is associated with the foreground because it represents the geometry in the foreground. You may have more than one value per sample (for example, if you are interested in each sub-pixel individually).

The working color space is the color space that our blending computations are performed in. This color space must be a linear color space. This means that, if you have a number which represents once channel of a color, and you double it, its distance from zero must also exactly double.

sRGB is not a linear color space. However, we can come up with a conceptual “linearized sRGB” color space which uses the same primaries as sRGB and same 0-point and 1-point, but uses linear interpolation between 0 and 1. Converting from sRGB into this new color space is simply raising each value to the 2.2 power. (The conversion is actually a little more complicated than that - it uses a peace-wise function - but we’re only discussing the conceptual model here.)

So, the first step is to convert all our colors into this working color space. Then, each blending operation is performed by taking a weighted average of the color primaries’ values, using the coverage information as a weight. Successive blending operations are performed back-to-front.

The formula for this weighted average is:

Source Primary * Source Alpha + Destination Primary * (1 - Source Alpha)

You can see that if the alpha is 0, the result is equal to the destination, and if the alpha is 1, the result is equal to the source. This is simply a linear interpolation between the two.

Now, it turns out that the requirement of rendering items from back-to-front is greatly constraining. It means that if we have a whole bunch of items to blend together, we can’t precompute the result of blending certain items together, and then blend those with a background. This is because the formula above is not associative.

However, a very similar formula is associative:

Source Primary + Destination Primary * (1 - Source Alpha)

The only difference between this formula and the original is the replacement of “Source Primary * Source Alpha” with “Source Primary.”

Well, let’s come up with a new concept, called a “premultiplied color.” This is the same thing as a regular color, except the values in the primaries’ channels have already been multiplied by the alpha of the color. This is possible because the color primaries’ values and the alpha channel have the same lifetime, so we can perform the multiplication at the time when this object is created.

Well, we can see that if we use these objects in the associative formula, we get the same answer as before (because the new “Source Primary” is equal to the old “Source Primary” times the Source Alpha; this multiplication is performed inside the “Premultiplied Color” object). However, we get the benefit of using an associative formula.

Therefore, with premultiplied colors, you can blend in any order. It’s worth noting that using premultiplied colors is not a requirement - if you blend out-of-order with premultiplied colors, you will get the exact same result as if you had blended back-to-front with non-premultiplied colors. This also means that you can start blending out-of-order, but if you notice that you have blended all the deepest items, you can transition to non-premultiplied blending halfway through all your blending operations. The answer will be the same.

By contrast, using a linear working color space is a hard requirement. If you don’t do this, your math will yield values which are meaningless. Once you’re done with all your blending, you usually want to write out the output in a well-known colorspace (such as sRGB), which means you usually have to un-linearize the result just before output.

Because of this, linearization / unlinearization should be the first and last steps. Premultiplication and unpremultiplication should be the second and second-to-last steps (if they are used at all). Premultiplication is optional and you can even unpremultiply halfway through your calculations if some conditions are met.

Note that linearizing / unlinearizing sRGB can have some pretty dramatic results. For example, if you blend pure black and pure white (technically “sRGB black” and “sRGB white”) with 50% alpha, you end up with your (resulting sRGB) primaries having values of 74%, nowhere near the 50% you would get if you performed the same calculation (incorrectly) in the non-linear sRGB space.

UTF-16 Surrogate Calculator

Codepoint (hex):

UTF-16:

High surrogate (hex):
Low surrogate (hex):

Codepoint:

Antialiasing of Core Graphics and Direct2D

Methods of writing Windows apps

Win32

In the beginning, there was just Win32. This is a C-based API which has been around since Windows 95. In this API, UI widgets (such as buttons) were known as “Windows” (represented in code as HWND) and windows could have windows inside of them. There was no concept of automatic layout; instead, each window had to be explicitly placed and sized by the programmer.

When you have a window, you can create a “device context” which is associated with that window. This device context is what we now would call a 2D drawing context, and it has API functions which let you draw lines and circles and text and that kind of stuff. All these drawing operations were performed on the CPU by a library named “GDI.”

Interactivity was fairly primitive. Applications would create their own runloop. Each turn of the runloop calls GetMessage(), which corresponds with an event that occurred. However, because some messages need to be handled by the system, the runloop just turns around and delivers the event back to the system. Before doing this, you register a callback function which the system will invoke when it wants to. This is where you are told things like “you should paint your contents now” or “the user pressed a key on the keyboard.” Because each message has an enum type, this callback function will switch over the type, and react to all the messages it understands.

This API is 20 years old, and should not be used for new projects. However, it is still supported today on current Windows operating systems.

Microsoft Foundation Classes (MFC) was the next suggested method of writing Windows apps. This is a C++ wrapper around the Win32 API; it was a new way of doing what people were already doing. Similar to Win32, it shouldn't be used anymore.

.NET

.NET represents a new approach to Windows desktop software development. There is a new language, a new object model, a new ABI, garbage collection, etc. There are two ways that .NET applications could be used to make graphical applications: WinForms and WPF. WinForms simply internally uses the Win32 API, and therefore isn’t very interesting.

WPF, however, represents a clean break from Win32 GUI programming. This API doesn’t use GDI for drawing, doesn’t use HWNDs, and doesn't require manual layout. Instead, development starts with a declarative language called XAML. This is an XML-based language where regions of the screen are represented as elements in XAML. Each element has an associated .NET class (in the System.Windows namespace) which allows you to do everything in code that the XAML file does. These elements aren’t HWNDs; instead, they are their own unrelated type.

Because HWNDs aren’t involved, drawing isn’t done with GDI. Instead, it is done entire on top of Direct3D, which means that the drawing routines are hardware accelerated. It also means that WPF controls look different from their GDI counterparts; a WPF app is recognizable.

WinRT

WinRT is the suggested method of creating a GUI application. WinRT’s GUI model is set up similarly to WPF, except that it has an entirely new set of elements (which reside in the Windows.UI namespace). It still employs XAML for representing elements in a declarative form.

For drawing a specific control, WinRT uses Direct2D, a hardware-accelerated drawing library. This library is conceptually on top of Direct3D, but it is also available for arbitrary developer use.

Once an individual element is drawn, multiple elements are composited together using Windows Composition. This library allows for creating a retained-mode hardware-accelerated tree of visual objects. This API is internally used to composite all the controls in the window. It even has a public API so you can interact with the composition tree directly.

As opposed to Win32, WinRT has an application model. You don’t have to write your own event loop with WinRT. Applications are implemented as a subclass of Windows::ApplicationModel::Core::IFrameworkView. This class has 5 functions which the application overrides in order to react to lifecycle events. The event loop is implemented in CoreApplication::Run, which takes an IFrameworkViewSource, which is a factory for IFrameworkViews.

Event handling is performed explicitly. Class definitions in C++/CX have properties, methods, and events. If you want to react to an event, you simply construct an Windows::Foundation::EventHandler object, and use the += operator to attach it to the object’s event field. The EventHandler object is a wrapper around a function pointer or a lambda. As an example, UIElement has a “PointerMoved” event.

Layout is achieved by encapsulating different layout algorithms inside different controls. For example, there is a Windows::UI::XAML::Controls::Grid control, which arranges its contents in a grid. Different controls arrange their contents according to their own internal algorithms. The most basic example is the Canvas class, which allows the programmer to explicitly lay out its child controls (so you’re not limited by the classes that come with the library).

Inside these callbacks, you can modify any part of the XAML tree you want in order to change the rendering of your app. From code, the way you identify elements in the XAML tree is pretty interesting. Each XAML file is represented in native code by a class which extends Windows::UI::Xaml::Controls::Page. When you build your project, the XAML file is used to create an auto generated header. Nodes in the XAML file can have a “name” attribute, which represents the name that native code would refer to the node as. The auto generated header contains each of these variables of the right type and name. Then, the auto generated header’s content is mixed into your Page subclass by using the support for “partial” classes. This allows the class declaration to be defined in two files; the conceptual class is the union of the two classes. Therefore, these auto generated variables automatically become class members, and are therefore in scope for all the methods of the class. In the end, this means that you don’t have to do any typing; you just immediately have access to your nodes by name.

Once you have access to the elements, you can change any of their properties, run any of their methods, and listen for any of their events.

Binary Compatibility of Windows Programs

COM

Around 1993, there was an issue around binary compatibility of object-oriented programs. The problem is that callers and callees must agree on the internal layout of structs in memory. This means, however, that if a callee is updated (as libraries often are) and changes this memory layout, the program will not behave as expected.

Microsoft came up with a solution to this problem by creating an “object model” (named “COM”) which objects that traverse library boundaries should adhere to. The object model has a few rules:

• Objects must not have any data that is exposed. Therefore, the only thing publicly available from an object is functions to call on the object.
• The object’s functions are represented in memory as an array of pointers to functions. The order of this array matches the order that the functions are declared in source code.

Therefore, given these requirements, everybody can agree on how to interact with objects; all interactions with the objects must go through the object’s functions, and everyone agrees on where the functions exist.

You may recognize this design as an “interface.” The function array is a vtable. Therefore, mapping this idea to C and C++ is very natural. Because the only things that exist in the objects is a vtable, there are no problems with padding or alignment of data members or anything like that. Inheritance is implemented by simply adding more function pointers on to the end of the array.

This memory layout also means that many languages can interact with these COM objects.

There are two more interesting pieces to this object model: there are 3 functions that every object must implement. This can be thought of as the root of the inheritance hierarchy. In C++, this base class is known as IUnknown. The three functions are:

• AddRef()
• QueryInterface()
• Release()

AddRef() and Release() are for reference counting; every COM object is reference counted using these functions.

QueryInterface() is pretty interesting. It is a way of converting one object into another type. The idea is that all COM types have an associated ID number. When you call QueryInterface(), you pass in an identifier of a type that you want. If the object knows how to represent itself as that type, it returns an interface of the correct type. Therefore, it’s sort of like a dynamic_cast, except that the source and destination types don’t have to be related at all. This is actually a really powerful concept, because it provides a mechanism for interoperability between APIs. A new library can be released, and its objects might want to support being used as the objects in another library; this can naturally be achieved by supporting QueryInterface().

In every COM library I’ve used, functions use out params instead of return values. Instead, they return an HRESULT error code. Therefore, it’s common to see every call to a COM object wrapped in a block which checks the return code.

.NET

Around 10 years later, Java was becoming popular. One of Java’s goals was to allow programs to run on any machine without requiring recompilation. It achieved this goal by compiling to a “virtual machine” bytecode. Then, at runtime, an interpreter would run the bytecode.

This approach means that all memory accesses and function calls operate through an interpreter, so the interpreter can make sure that nothing bad happens (for example: a program can never segfault). It also means that the virtual machine is free to implement any object model it wants; all object accesses pass through it, so it is free to, for example, move objects around in memory whenever it wants. This naturally leads to a garbage-collected language, where the garbage collector is implemented in the virtual machine.

(Now, I’d like to make an aside about this “managed code” business. It isn’t really true that all Java programs are interpreted; the virtual machine will JIT the program and point the program counter into the JITted code. Whenever the interpreter needs to do some work, it just makes the generated bytecode call back into its own code. Therefore, nothing is being done here that couldn’t be done with a simple software library. Indeed; this managed “runtime” is the same fundamental idea as the raw C “runtime”; it’s just that many operations which would be raw instructions in C are instead implemented as function calls into the runtime. If you are diligent about all your object accesses, you can make your C++ program garbage collected. “Managed code” doesn’t really mean anything mechanical; instead, it is a way of thinking about the runtime model of your program.)

Microsoft wanted to be able to use this model of “managed code” in their own apps, so they invented a system quite similar to Java’s. You would compile your apps to a “CLI” form, which is a platform-agnostic spec describing a virtual machine. Then, the Microsoft CLR interprets and runs your program. A new language (C#) was invented which nicely maps all its concepts to CLI concepts.

There are a couple extra benefits of having a well-specified intermediary form. One is that there can be multiple languages which compile to your CLI. Indeed, Microsoft has many languages which can be compiled to the CLI, such as F# and VB.NET. Another benefit is that the standard library can exist in the runtime, which means that all of those languages can call into the standard library for free. Each language doesn’t need its own standard library.

A pretty interesting benefit of this virtual machine is that it solves the binary compatibility problem. The fundamental problem with binary compatibility is that one library might reach inside an object vended by another library; with a virtual machine, that “reaching” must go through the runtime. The runtime can then make sure that everything will work correctly. So, we now have another solution for the binary compatibility problem.

C++/CLI

Remember how I mentioned earlier how that this concept of “runtime” is really just a library of functions that you should call when you want to do things (like call a function or access a property of an object)? Well, C++ supports linking with libraries… there is no reason why one shouldn’t be able to call into these runtime libraries from a C++ program.

The difficulty, however, is being diligent with your accesses. Every time you do anything with one of these “managed” objects, you must call through the runtime. This is a classic case of where the language can help you; you could imagine augmenting C++ to be able to naturally represent the concept of a managed object, and enforcing all interactions with such objects to be done through the runtime.

This is exactly what C++/CLI is. It is a superset of the C++ language, and it understands what managed objects are. These managed objects are fundamentally different from C++ objects; they are represented using different syntax. For example, when you create a managed object, you use the keyword “gcnew” instead of “new”, in order to remind you that these objects are garbage collected. A reference to a managed object uses the ^ character instead of the * character. Creating a reference to a managed object is done with the % character instead of the & character. These new types are a supplement to the language; all the regular C++ stuff still exists. This way, the compiler forces you to interact with the CLI runtime in the correct way.

Windows Runtime

The currently accepted way to write Windows programs is using the Windows Runtime (WinRT). You may think that WinRT is a runtime just like the .NET runtime discussed above; however, this isn’t quite right. WinRT objects are integrated with the .NET runtime, and are considered “managed” in the same way that .NET objects are considered “managed.” However, they aren’t binary compatible with .NET objects; you can’t interact with WinRT objects using the same functions you use to interact with .NET objects.

Therefore, C++/CLI doesn’t work for WinRT objects. Instead, a similarly-looking language, C++/CX, was invented to interact with these WinRT objects. It keeps some of the syntax from C++/CLI (such as ^ and %) but replaces others (such as “ref new” instead of “gcnew”).