Sunday, February 15, 2009

Implementing OpenGL texture caching and bitmap image support in the Factor UI

Last time, I talked about how I implemented Unicode text rendering using Apple's Core Text API. In this blog entry I'll discuss some implementation details I omitted last time, and I'll also talk about a new feature I added a few days ago to the new_ui branch: support for bitmap images.

Note that Core Text is OS X-specific, and Factor will only use it on that platform; on other platforms, it will use Pango to render text (and maybe Uniscribe on Windows, leaving Pango for X11 only). The image support is cross-platform and indeed is entirely written in Factor.

A general cache abstraction

With Core Text, you never operate on strings of text directly, instead you construct a CTLine object and interrogate it for metrics, or ask it to render itself to a Core Graphics context. To avoid constructing CTLines over and over again, and to expose a straightforward API that only involves strings, the UI caches the CTLine objects. Using MEMO: or the cache combinator with a hashtable is insufficient here, since I don't want to retain every CTLine forever. Instead, I want each CTLine to be disposed and removed from the cache if it is not used for a fixed period of time.

To handle this use case, along with another one that I describe later on in this post, I implemented a simple cache abstraction.

The new cache vocabulary defines a new assoc type which wraps an existing assoc, and has a single configuration parameter, max-age:
TUPLE: cache-assoc assoc max-age disposed ;

: <cache-assoc> ( -- cache )
H{ } clone 10 f cache-assoc boa ;

INSTANCE: cache-assoc assoc

The values in the underlying assoc are all instances of cache-value:
TUPLE: cache-entry value age ;

: <cache-entry> ( value -- entry ) 0 cache-entry boa ; inline

The age of a value starts at zero, and is incremented at fixed intervals. Whenever a key is looked up in the cache, the age is reset to zero. Because I don't want to expose the user of a cache to these cache-entry tuples (they're just implementation detail), the cache-assoc type implements at* to unwrap the cache entry before returning the value to the user. Also note that I reset the age here:
M: cache-assoc at* assoc>> at* [ dup [ 0 >>age value>> ] when ] dip ;

Storing an entry into the cache first checks to see if the cache has been disposed of yet or not, and then wraps the value in a cache entry before passing it down to the underlying assoc:
M: cache-assoc set-at
[ check-disposed ] keep
[ <cache-entry> ] 2dip
assoc>> set-at ;

Converting a cache to an alist unwraps each value:
M: cache-assoc >alist assoc>> [ value>> ] { } assoc-map-as ;

The remaining important assoc methods simply delegate to the underlying assoc:
M: cache-assoc assoc-size assoc>> assoc-size ;

M: cache-assoc clear-assoc assoc>> clear-assoc ;

Caches also support one additional operation: disposal. When you call dispose on a cache, all values in the cache are disposed and the cache cannot be used again:
M: cache-entry dispose value>> dispose ;

M: cache-assoc dispose*
[ values dispose-each ] [ clear-assoc ] bi ;

This is the important part, that makes caches useful for managing external resources such as OpenGL textures.

Now, here is a word which ages each entry, and deletes those entries whose age exceeds the cache's max-age slot value. It uses the assoc-partition combinator, which splits an assoc into two, sorting key/value pairs based on whether they satisfy a predicate or not.
: purge-cache ( cache -- )
dup max-age>> '[
[ nip [ 1+ ] change-age age>> _ >= ] assoc-partition
[ values dispose-each ] dip
] change-assoc drop ;

I cheat a little here; because assoc-partition iterates over all key/value pairs exactly once, I can perform side effects in the predicate quotation; I increment the age and then immediately check if it exceeds the maximum. Note the use of '[ syntax with the _ directive, which places the max-age exactly where its needed without having to pass it around on the stack explicitly. The values which exceed the maximum age -- these make up the first return value of assoc-partition -- are all disposed of.

This cache vocabulary, which is currently in the new_ui branch and will be merged into the trunk soon, demonstrates the Factor equivalent of the "decorator" OO design pattern.


Doug Coleman has been working on a Factor library for working with bitmap images for quite some time; you can find it in the repository, in the images vocabulary. Recently it received a major facelift, as well as support for TIFF images (including LZW compression) in addition to Windows BMP. All of this is written entirely in Factor, and Doug also plans on supporting PNG, GIF and JPEG images, also with pure Factor code. When complete, this library will be quite a showcase for implementing complex algorithms in a concatenative language.

Also, Joe Groff designed some nice icons for the Factor UI. To make use of both of these great contributions, I wrote some code which caches images in OpenGL textures and renders these textures.

The load-image word in the images.loader vocabulary defines a data type for images:
TUPLE: image dim component-order bitmap ;

The component-order slot is one of a series of singletons,
R16G16B16 R32G32B32 R16G16B16A16 R32G32B32A32 ;

the dim slot is a pair of integers (the width and the height) and the bitmap slot is a byte array with the image data, where each pixel's size and format is determined by component-order.

OpenGL textures

In my last blog post, I showed some ad-hoc code for rendering a Core Graphics bitmap to a texture. I refactored this code to be independent of Core Graphics and Core Text, and put it in the opengl.textures vocabulary. There is a new texture data type:
TUPLE: texture texture display-list disposed ;

To create a texture from an image, I have to pass a format and a type to OpenGL. A generic word maps component order singletons into OpenGL constants; the implementation is incomplete, but it suffices for now:
GENERIC: component-order>format ( component-order -- format type )

M: RGBA component-order>format drop GL_RGBA GL_UNSIGNED_BYTE ;
M: ARGB component-order>format drop GL_BGRA_EXT GL_UNSIGNED_INT_8_8_8_8_REV ;
M: BGRA component-order>format drop GL_BGRA_EXT GL_UNSIGNED_INT_8_8_8_8 ;

Using this word, I implemented a <texture> constructor word, which creates an OpenGL texture from a bitmap image, and wraps the relevant data into a tuple:
: <texture> ( image -- texture )
[ dim>> ]
[ bitmap>> ]
[ component-order>> component-order>format ]
tri make-texture
] [ dim>> ] bi
over make-texture-display-list f texture boa ;

The code that wraps the glTexImage2D call, as well as creating a display list that renders a textured quad, is very similar to what I showed in my previous post, just slightly more general, so I won't reproduce it here.

To be useful cache keys, textures must be disposable:
M: texture dispose*
[ texture>> delete-texture ]
[ display-list>> delete-dlist ] bi ;

High-level abstraction for images

The ui.images vocabulary builds on top of the lower-level libraries: images, images.loader, opengl.textures and to provide an easy-to-use, simple, high-level interface for displaying icons in the UI.

The relevant data type is an image path, which is just a string wrapped in a tuple,
TUPLE: image-name path ;

C: <image-name> image-name

A fundamental word takes an image path, and loads the image that it names, if it has not been loaded already:
MEMO: cached-image ( image-name -- image ) path>> load-image ;

Note that I'm not using a cache-assoc to cache the bitmaps themselves. This is because bitmaps are objects in the Factor heap, not external resources, and so they don't have a dispose method, hence a simple MEMO: word suffices.

The next step is implementing the image texture cache. I added a new images slot to world gadgets. A world is the top-level gadget inside a native OS window, and since each world has its own OpenGL context, it is natural to associate the image texture cache with a world.

: image-texture-cache ( world -- texture-cache )
[ [ <cache-assoc> ] unless* ] change-images images>> ;


The image-texture-cache word assumes that there is a dynamically-scoped variable named world holding a world gadget. This is the case inside the dynamic extent of the draw-gadget word, and so textures can only be cached and looked up while a gadget is being rendered; a reasonable restriction.

The rendered-image word looks up a bitmap image texture in the cache, and adds it if its not already present:
: rendered-image ( path -- texture )
world get image-texture-cache [ cached-image <texture> ] cache ;

Note the two levels of caching here. First, it looks for an available texture associated with an image path. If there is no texture, it looks for a cached bitmap image and makes a texture from that. If there is no cached bitmap image, then cached-image loads it by calling load-image inside images.loader.

Now, drawing an image named by an image path is easy; this word draws the image at the origin, and code which wants to draw it at another position can simply translate the model view matrix first:
: draw-image ( image-name -- )
rendered-image display-list>> glCallList ;

Getting cached image dimensions is easy too, and does not involve the texture cache, only the bitmap cache:
: image-dim ( image-name -- dim )
cached-image dim>> ;

Caching rendered Core Text lines

In the last post, I presented the with-bitmap-context combinator in the core-graphics vocabulary which created a Core Graphics bitmap context, rendered to it by calling a quotation, and output a byte array when finished. I refactored this combinator and renamed it to make-bitmap-image. Instead of outputting a raw byte array, it creates an image tuple, which wraps the byte array together with dimensions and a component order. This means that anyone who doesn't care about portability and wishes to use the core-graphics vocabulary directly can do so very easily, and render graphics to an image object which works with a number of other Factor libraries.

Indeed, by changing the core-text code to call make-bitmap-image, I was able to very easily hook up texture caching for rendered lines of text.
: rendered-line ( font string -- texture )
world get text-handle>> [ cached-line image>> <texture> ] 2cache ;

M: core-text-renderer draw-string ( font string -- )
rendered-line display-list>> glCallList ;

Again, the user benefits because they don't have to concern themselves with "lines" (strings with layout) or GL textures; they just draw strings whenever and everything works out behind the scenes.

On code re-use

I'm a big fan of avoiding redundant data types in the Factor library. Over the years, parts of the Factor UI which were UI-specific have been split off, cleaned up and generalized. We now have some very nice vocabularies, such as colors, fonts and images which do not depend on OpenGL or the UI, and are hopefully general enough that no Factor programmer will have to re-invent the concepts of fonts, colors and bitmap images again.

Also, as much as possible of the Factor UI's rendering code is now abstracted off into sub-vocabularies of the opengl vocabulary; these define many utility words and types, and for instance something like opengl.textures can be used independently of the Factor UI, if you're doing OpenGL rendering with some other toolkit.

The introduction of the cache-assoc abstraction and generalized texture caching and bitmaps has simplified the Core Text text rendering backend considerably. It is now only a couple of hundred lines of code. This will make implementing a Pango backend easier.

Icons for definitions

To spruce up Factor's vocabulary browser and code completion, I cooked up a little vocabulary which, given a word or vocabulary, outputs an appropriate icon. For words, there are many types of icons corresponding to different types of words, and for vocabularies the icons distinguish loaded, unloaded and runnable vocabs.

The definitions.icons vocabulary defines a generic word:
GENERIC: definition-icon ( definition -- path )

Since all the icons are in a single directory, and in TIFF format, I define a utility word which takes an icon file name without the extension and outputs a full pathname:
: definition-icon-path ( string -- string' )
"resource:basis/definitions/icons/" prepend-path ".tiff" append ;

Now, I'd want to define a bunch of methods,
M: predicate-class definition-icon drop "class-predicate-word" definition-icon-path ;
M: generic definition-icon drop "generic-word" definition-icon-path ;
M: macro definition-icon drop "macro-word" definition-icon-path ;

However this is too verbose. The only really important part of each method line is the class name, and the icon name, without quotes. Everything else is boilerplate. Well, this is Factor, and we can factor it out. There are many different ways to do this. You can write a parsing word, or you can use my "functor" hack, which is just a syntax sugar for a particularly simple class of parsing words. Here is a solution using parsing words:

scan-word \ definition-icon create-method
scan '[ drop _ definition-icon-path ]
define ; parsing


And here is a solution using functors:

FUNCTOR: define-icon ( class icon -- ) WHERE
M: class definition-icon drop icon definition-icon-path ;

: ICON: scan-word scan define-icon ; parsing


The functor actually expands into code that is very similar to the parsing word. Both are straightforward. The main difference is that the parsing word has to explicitly call the run-time equivalents of M:; create-method and define.

Note that I wrap the parsing word in a compilation unit << ... >> so that it is compiled before the other words in the file. This allows the parsing word to be used in the same file where it is defined; otherwise usages of ICON: would attempt to call a parsing word that wasn't compiled yet, which throws an error.

Now new icons are very easy to define,
ICON: predicate-class class-predicate-word
ICON: generic generic-word
ICON: macro macro-word
ICON: parsing-word parsing-word
ICON: primitive primitive-word
ICON: symbol symbol-word
ICON: constant constant-word
ICON: word normal-word
ICON: vocab-link unopen-vocab

For vocabularies, the situation is simpler,
M: vocab definition-icon
vocab-main "runnable-vocab" "open-vocab" ? definition-icon-path ;

No comments: