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”).

Vertical Text

To start off, latin scripts are generally not written vertically. For example, let’s say you’re writing on the spine of a book. Usually, you wouldn’t stack the letters on top of each other; instead you would lay the book down horizontally and then write on the spine. In this situation, you’re simply writing horizontally on a canvas which has been rotated.

However, many East Asian scripts are written vertically. In this case, the characters are stacked on top of each other. Laying out text like this is a little different than laying it out horizontally.

You’re probably familiar with the concept of each character having an advance, which represents the displacement from one character to the next. Well, this displacement vector is different if you’re stacking letters on top of each other. In particular, there are two different kinds of advances: horizontal advances and vertical advances. With CoreText, CTFontGetAdvancesForGlyphs() takes a CTFontOrientation parameter, where you can specify if you want horizontal advances or vertical advances.

In general, the pen starts out horizontally centered above the letter, and the vertical advance takes you to a place that is horizontally centered below the letter.

This is actually the same concept as a “baseline”, where pen keeps returning to the same line after each character. The difference is that this baseline is in the middle of the letters, rather than underneath (some of) them. This is known as an “ideographic baseline,” which is distinct from the “alphabetic baseline” we are used to. A font file can define where these (and more) baselines should occur in the ‘bsln’ or ‘BASE’ table.

However, when you tell a glyph to draw at a particular point, that local origin isn’t at these pen locations.

Therefore, if you are going to draw a glyph, you need some way of going from this pen location to the glyph’s local origin. With CoreText, you can do this with the API function CTFontGetVerticalTranslationsForGlyphs().

So that should be enough to lay out a line of pure text, but in Web content, you may have stacked letters in the same line as non stacked letters (for example: an English word in a Chinese sentence). Laying out these two situations correctly is possible because of the relationship between the alphabetic baseline and the ideographic baseline.

Keep in mind baselines progress in the direction of the line, not the characters. The ideographic baseline and the alphabetic baseline are parallel to each other. The font's ascent and descent tell you how much space the letters take up orthogonally to the baseline. Therefore, in vertical text, the ascent measures to the right of the baseline and the descent measures to the left of the baseline, even though the letters are stacked.

A Deeper Look at OpenType and TrueType Font Features

Font Features are a way to provide arbitrary changes to a sequence of glyphs. Text layout happens in a couple steps:

1. Codepoints get mapped, one-to-one, to glyphs. This turns your string into a sequence of glyph IDs. Each of these glyph IDs is associated with an “advance” which is a 2D vector from the origin of each glyph to the next.
2. Font features run arbitrary modifications on the sequence of glyphs and advances
3. Each glyph is rendered at its respective location.

The two popular font file formats, TrueType and OpenType, have many things in common. They both share the same notion of how to map code points to glyphs. They both share the notion that a glyph is represented a a sequence of Bezier paths laid tail-to-front. However, the two file formats model font features in very different ways.

OpenType

OpenType’s model is simpler, so let’s start there. OpenType encapsulates font features into two tables, GPOS and GSUB. GPOS is for glyph positioning, and GSUB is for glyph substitution. Both of these tables actually share the same overall structure. The shared structure is as follows:

• The table is represented by a collection of “scripts.”
• A “script” is represented by a collection of “language systems.”
• A “language system” is represented by a collection of “features.”
• A “feature” is represented by a collection of “lookups.”
• A “lookup” is represented by a collection of typed tables.

The only difference between the GPOS and GSUB tables is the last step - these typed tables. For positioning, these typed tables describe things like “adjust the positions of the following glyphs by the following amounts” or “move the following pairs of glyphs closer together.” For substitution, the typed tables describe things like “replace the following glyphs with these other glyphs” or “match this pattern of glyphs and replace it with this other pattern of glyphs.” The form of these tables is specific to the positioning or substitution you are trying to achieve.

Each of the typed tables has an associated “coverage” table. This simply holds a set of glyphs that the typed table acts upon. When the software is laying out some glyphs, if none of the glyphs appear in the coverage table, the software can safely ignore that typed table.

Everything else is shared between GPOS and GSUB, and is just an aggregation of the level below it. Each “feature” has a four-letter code associated with it, such as “liga” or “smcp.” These codes are reported in the program UI, and the user is allowed to switch on or off each of these codes independently. If the user switched off a particular code, the stuff inside that feature’s “lookup” tables is not performed. The lookup tables are performed one by one, in the order the file describes.

Scripts and language systems each have their own four-character tags associated with them. The reason for the distinction is that many different languages may share the same script. For example, both English and Spanish share the Latin script. Because the languages and scripts are expected to have very different glyph patterns, separating out the features into these buckets seems like a good idea. Also, there is a default script tag and a default language system. Microsoft keeps a registry of all of the scripts and language systems, as well as their associated 4-character tags.

TrueType

TrueType font features are completely different. In particular, there are many tables, each with a specialized purpose. For example, instead of the general “GPOS” table, there is a much more specific “kern” (or “kerx”) table, which is only designed for kerning glyphs. Similarly, there is a separate, more-specific, “opbd” table for the optical bounds of the font. Many of the OpenType features have corresponding specific-purpose tables inside TrueType. These tables do not provide the same flexibility as the GPOS table.

However, unlike most of the TrueType tables, the “morx” table is quite general. Conceptually, it describes the same sort of things that the OpenType GSUB table describes. However, its model of font features is very different.

The “morx” table doesn’t mess around with any of that “script” and “language system” stuff. Instead, the table is represented by a collection of “chains.” Each chain is comprised of a collection of typed subtables. These typed subtables describe things like “Rearrange this sequence of glyphs according to these predefined rules” or “insert a specific glyph into the middle of this particular glyph sequence.”

The rest of the chain is devoted to describing which typed subtables should be performed.
Similar to before, each chain gets a coverage table. However, in addition, there is a pretty interesting mechanism to determine which features cause which typed subtable to be performed.

Inside the chain, a sequence of bitwise operations is described, which results in a particular bitfield. Each typed subtable in the chain also has an associated bitfield. If the bitwise and of those two values is nonzero, then the typed subtable is applied.

That sequence of bitwise operations is where individual features come into play. Instead of representing a particular feature as a four-character tag, like in OpenType, TrueType represents a feature as a tuple of (feature type, feature selector). The font describes a sequence of features and corresponding bit masks to be ANDed / ORed. When a feature is enabled in the application’s UI, its associated bitwise operations are performed. When the feature is disabled, its associated bitwise operations are not performed.

The software starts with a known bit pattern. It then runs through the sequence. For each item in the sequence, if its associated font feature is enabled, it performs the appropriate bitwise operations. When it’s done, the result is a particular bit pattern value.

Each of the typed subtables also has an associated pattern value. If the bitwise AND of the calculated bit pattern and a subtable’s bit pattern is nonzero, then the table is performed.

Exclusive and Default Features

In OpenType, the font file has no way of expressing that certain features conflict or that certain features should be on by default. Each feature is simply represented by a four-character tag, and it is either enabled or disabled. The software may (or may not) decide to enable certain features by default based entirely on the semantics of the feature itself (not based on the font file). For example, the OpenType feature “rlig” is mean for “required ligatures” and is generally enabled by default.

The representation of a font feature in TrueType conveys more information than an OpenType font feature. In TrueType, a feature is represented by a tuple of a “type” and a “selector.” For a particular “type,” there will be a variety of different selectors which are relevant. Many selectors are only relevant to a particular type. An example would be “type”: “kLigaturesType” and “selector”: “kHistoricalLigaturesOnSelector”. Another example would be “type”: “kCharacterShapeType” and “selector”: “kTraditionalCharactersSelector”.

There is a fairly interesting difference between these two examples, though. The first type, kLigaturesType, and “on” and “off” selectors. The second type, kCharacterShapeType, doesn’t. This means that kCharacterShape is what is known as an “exclusive” type, where setting a value for it overrides all other values for it. On the other hand, kLigaturesType is a nonexclusive type, so you can set both kRareLigaturesOnSelector and kCommonLigaturesOnSelector for it. For all the feature types your font knows about, you can declare whether they are exclusive or nonexclusive in the font’s ‘feat’ table, and the software will behave accordingly.

In addition, you can mark a feature as on by default if you set the chain’s default flags to intersect with the feature’s enable flags. Logically, this makes sense - if the feature turns on something which is already on, then that feature should be on by default. However, because the feature is on by default, the software might decide not to show it in the list of available font features. This makes sense for something like required ligatures; turning that feature off would make the font completely illegible, so the software shouldn’t even give the user that option. This behavior allows the font file to determine which features get turned on by default, rather than the software making a guess.

This also means that, for all your exclusive features, you need to designate one selector as the default, even if that selector doesn't actually trigger any typed subtables to be performed. Again, this logically makes sense, and allows you to perform some shaping by default.