Text Effects - Debugging

Having implemented the Accessor class getting the base class and the first text effect to compile was reasonably easy. The first text effect is a glyph substitution effect where glyphs in text are replaced with random glyphs in a simple animation.

After fixing a couple of crashes the output appeared to more or less work. To test the effect more thoroughly I overlaid the text with the effect applied (a single word) on top of the same text without the effect — this allows me to check things like positioning and character spacing. Doing this and publishing revealed that the text was positioned wrongly and had a vertical offset — so there is a bug.

After quite a few years of chasing bugs a method that often really helps me is to stop and think about it and see if you can figure out how it is misbehaving. Are there different — maybe better test cases that will tell you more about the problem.

So on to this offset — is it a one off offset (say the position of the text box) that is causing the problem or is it something that is incorrect with the calculation of the baseline. Knowing this will allow me to more tightly narrow my focus. There are a lot of numbers flying about in Cello and being able to look in the right area is going to be much less painful.

To test this I made two lines of test (two paragraphs with one word) in the PC version of Cello and published. If you look at the results below:



So from this it looks like the offset increases with successive lines. My guess is that the problem is somewhere in the calculation of the baseline or bounding rectangle of the text — both of which have logic to flip from CG style coordinates to QD style coordinates.

CoreText - flipped coordinates and glyph curves.

Text output is requires partial fonts to be included in the file format. This is done by having the glyph outlines embedded in the file. As described earlier I am using Core Text to get the glyph outlines (see). Unfortunately (looking at the output) the outlines are flipped.

This particular problem is caused by CoreGraphics (Quartz) having a flipped y-axis, so zero is at the bottom rather that the top. This can be corrected by passing an appropriate transform (flipping allong the baseline) through to CTFontCreatePathForGlyph. This snippet calculates an appropriate flipped transform.

sFlipTransform = CGAffineTransformIdentity;
sFlipTransform = CGAffineTransformScale
(sFlipTransform, 1, -1);

Which results in the glyphs being correctly orientated.

CoreText and Typographic Bounds

[build 44] Having got the simple file with text to open the next stage was to get the brute to publish. The first attempt at publishing yielded nothing - white space. Looking at the debug log that dumps the published movie it was because the text object that was published was empty i.e. had no text.

The primary cause of this was due the conversion of floating point to integer values. Within Cello all object coordinates and dimensions are expressed as integers - Core Text, like CoreGraphics, is floating point. The issue here is that Cello has auto hight boxes whose height is based on the typographic bounds of the text. So a height of 31.2 was being truncated to 31. Giving a CTFramesetter anything less than the typographic height of the first line when it creates the CTFrame results in a frame with no lines of text. So no text. I found a report of a similar problem here.

Following a fix to a crash in some very early asci->uft8 code I wrote before I started writing unit tests Cello publishes it's first text.
The glyphs are not in the right positions and everything is inverted (coordinate space in Quartz is flipped so this kind of problem is not uncommon or unexpected) but it is not that far away.

Converting Quartz Paths - MoveTo, LineTo, CurveTo

Cello has it's own support for curves - internally it has support for cubic and quadratic splines, as well as lines - the equivalent to what exists in CoreGraphics (Quartz) and generally in vector graphics systems. Within Cello there are classes that represent multi contoured splines and the attendant trickery to draw and manipulate them. They are of significance to me now as the existing Cello code requires the geometry of glyphs in its own internal format. So I needed to write conversion functions from a CGPaths to Cello's internal format.

Cello's curve format is unusual so writing the conversion has taken a little time. Most graphic systems that I have come across describe things in the form of, moveto, lineto and curveto. The idea being that "from where the pen is do this". Cello seems to be the other way round. Instead the curve verbs appear to be of the form linefrom, curvefrom, and movefrom.

My approach to writing the conversion has been first lift some existing code that converts the output of the D-Type font scalar (which is similar to the way that CoreGraphics thinks of curves) and to write a converter from Cello's internal format back to a CGPath. Again for this I could lift some code from Cello's output - again in the output the format paths are similar to CoreGraphics. Using the to and from converters it was possible to write Unit Tests to make sure that an original path is the same as a path converted, and then converted back. CFEqual will let you know if two paths are equal or not.

CPTAssert(::CFEqual(origPath, shape.AsPath()));

Converting and then back converting to, demonstrably, the same thing gives some idea of correctness but it does not guarantee that what you have done is correct, it just asserts that these two components are consistent. When I can look at the glyph shapes in the final output format I will be able to check this.

Reading Bitmap Objects III

[build 0034] It looks like I have come to the end of DIBs and CGImages - well that is as far as the file format and file generation goes. The final part was, much as I suspected, mainly leg-work.

Below is one of the final parts of my testing - showing transparency working correctly in the output file. The GIF transparency has the characteristic halo as it only supports 0% or 100% transparency.Testing the file generation had a few wrinkles - the file format caters for 8-Bit indexed bitmaps, but I was only able to get the Image IO file import to yield 16bit indexed bitmaps. So in order to test this properly I added code that would convert the 16 bit indexed to 8-bit indexed. In the end the extra leg-work was well worth the effort - the unit tests that I added to check the conversion threw into open some underlying issues that I had in some of the other conversion routines.

Prior to moving on to the next part, I shall probably start looking at text and glyphs, I added a small number of sample files to the Unit Tests of the project - to assert that a file, with images, when written is the same as when it was first read (I create these test files in the PC version of Cello) - the idea is to get an early call on any regression in this area.

Saving JPEGs with Image IO

[build 0031] JPEGs now work again.

Fixing the problems in the JPEG images fell out in the wash. It looked like a byte ordering problem combined with a pixel size problem (which would explain the vertical striping) - but I did not look into it. Instead I used Image IO to generate the JPEG. The save, using Image IO, fell out in four or five lines of code. Using Image IO means that the OS will handle all the byte order, pixel order, packing etc - all I need to do is to feed it a CGImageRef. As all bitmaps in the OSX version of Cello are now CGImages this is natural. Also as a tiny fringe benefit using Image IO also means that I have been able to remove the JPEG library from the project build, so the file count and build time are modestly improved.

All that remains, to put the issue of bitmaps to rest, is to work through the remaining problems with the other bitmap formats that are not encoded as JPEG. This would seem to be more of a handle turning exercise - there is code missing for the 16-bit indexed bitmap and there may be byte/pixel ordering issues for the 32 bit. Byte/pixel ordering issues happen because the original code expects certain byte orders and I need to move this over to using the more general pixel unpacking code that now exists in the project.

DIBS and CGImage - The price of progress

[build 0030] Sometimes the price of progress is that things stop working. Not much works in Cello but the JPEG based part of the export now no longer works.

For the past couple of weeks I have been working out the underlying problems with bitmaps, DIBs and CGImages. I abandoned my approach of getting the melding the CGImage implementation to be more like the MFC Dibs and instead more-or-less changed the DIB class so that it was a thin wrapper around a CG image. This was what I originally intended to do but early on the path of lest resistance seemed to be else where.

I don't think getting the JPEG export to work properly will be a big deal and on from that the other graphics formats.

More Bitmaps - DIBS and CGImage

[build 0029] I have been working on bitmaps and bit images and the whole thing is slowly coming more into shape. The issue that I have been having with bitmaps is that fundamentally the bitmaps that are imported into Cello using Image IO as a CGImage are richer and more complex than those represented by DIBS. A CGImage has notions of byte order (big and little endian) and different data packing. Below is a classic example of the sort of an endian problems that you can get.Additionaly there are wrinkles such as GIF images and PNGs with a color table are imported as indexed 16 bit colors. One byte is an index into the color table the other is transparency. Also internally Cello wants to deal with non premultiplied alpha, where as the export needs the alpha pre multiplied.

In with all of this I have discovered that it is possible to get a direct copy of the pixel data of a CGImage - using CGImageGetDataProvider.

With all of this I have changed my approach a little. I have added a CGBitmapInfo to the OSX version of the MFC bitmap header so that I have an idea of byte order and packing. I have also written, and tested, some templated pixel accessors so I can easily access the various channel packing orders.

All of this needs to be integrated with the existing image export so there is still a fair way to go before the image side of things is wound up.

CGImage & ImageIO - converting premultiplied alpha

The final part of the DIB (bitmap) equation is reading images. Cello has classes for reading and writing PNG, JPEG and a few formats including PaintShop Pro that are prevalent on windows. The change that I have made here is to use Image IO. Image IO will let you read all the most common formats - and also has support for RAW images (as spat by many digital cameras) amongst other things.

ImageIO is really easy to use you just need to give it something - a URL or a Data provider or whatever and it will turn it into a CGImage. The only issue with CGImage is that it is not possible to get to at the pixel data. In Cello there is a fair amount of code that manipulates pixels directly - so I have to facilitate this.

A solution is to draw the image onto a bitmap where you own the pixels - CGBitmapContextCreate will create a bitmap context and the following code fragment will draw it.

   CGRect drawRect = ::CGRectMake(0, 0, width, height);
   ::CGContextTranslateCTM(context.get(), 0.0, float(height));
   ::CGContextScaleCTM(context.get(), 1.0, -1.0 );
   ::CGContextDrawImage(context.get(), drawRect, theImage);

In this there are a couple of wrinkles.

• CGBitmapContextCreate won't work on an indexed bitmap. So all the images will be converted to either RGB32 or RGBA32. I don't see this as a big deal.
• CGBitmapContextCreate will only work with premultiplied alpha. Cello assumes the alpha is not premultiplied. The easiest thing to do is to wholesale convert the bitmap to nom-premultiplied alpha after the fact.

The code for this is reasonably straight-forward:

inline UInt32 Unpremultiply(UInt32 c, Float32 inverseAlpha)
{
UInt32 result = UInt32(Float32(c) * inverseAlpha);
result = std::min(result, 255);
return result;
}

void BitmapClass::UnpremultiplyRGBA()
{
UInt8* pRow = reinterpret_cast(m_pBits);
for (int row = m_height; row > 0; --row)
{
    UInt32* pPixel = reinterpret_cast(pRow);
    for (int column = m_width; column > 0; --column)
    {
        UInt32 alpha = GetAValue(*pPixel);
        if (alpha)
        {
            Float32 inverseAlpha = 255.0/alpha;

            UInt32 red = Unpremultiply(GetRValue(*pPixel), inverseAlpha);
            UInt32 green = Unpremultiply(GetGValue(*pPixel), inverseAlpha);
            UInt32 blue = Unpremultiply(GetBValue(*pPixel), inverseAlpha);

            *pPixel = RGBA(red, green, blue, alpha);
        }
        else
            *pPixel = 0;
        ++pPixel;
    }
    pRow += m_iByteWidth;
}
}

It is, of course, entirely non-optimized - but as this will happen as a single hit when an image is read I don't see it as being any kind of bottle neck. If it turns out to soak up time and that this is a problem I will attack it later.

DIB to CGImage - the washing up

I changed the plans and in the end kept the class that manage the DIBs almost unchanged. The DIB class, within Cello, represents a bitmap with a physical bit-image. Give or take the fact that it can handle native compressed bit-images it handles the concept that an image is a bunch of bits and possibly a color table. A CGImage is very similar except that you can't get to the bit-image. You can make a CGImage where you can get to the bits if wrap the the bit image in a CFDataProvider. So the natural thing seemed to keep the DIB class more or less as it was but to provide a way off creating one from a CGImage.

The key change that I have made to the DIB class is to change the way that pixels are stored; I have moved from using a raw pointer for the pixels to boost::shared_array. The boost::shared_array is an array with an owner count - and it means that it is possible to deal with joint ownership. The point being that data provider needs to have ownership of the data it is providing (the pixels) as does the DIB class.

The other part of the equation is the colour palette its self. A colour palette is a list of colours - little more. In Cello there is a class that represents this list of colours as a list of RGBQUAD from which it can create the HPALETTE etc required for MFC bitmaps. I have changed the colour palette class so that it is now a thin wrapper around a CGColorSpace. You can still access a representation of it as a list of RGBQUAD - this is required for other things in Cello such as the ditherer. Changing this code and writing the attendant unit test was quite straight forward. I use boost::intrusive_ptr to manage the CFColorSpaceRef, and boost::shared_array to manage representation (cache) of RGBQUAD. In retrospect I think it would have been better not to have made this change and instead to have just provided a way of converting into a CGColorSpace. It would have been a smaller change.

Moving DIBs (device-independent bitmaps) to CGImage

The biggest remaining clot of link errors (probably about 30 or so) relate to Cello's handing of Bitmaps. There are a handful of classes, many parts of which of which are commented out or omitted from compilation, that deal with bitmaps. Hanging on to this are classes and libraries that deal with reading and writing images to and from physical files. Central to all of this is the class that manages the DIB which I have discovered is a device-independent bitmap. The wikipedia article is an excellent introduction and explained why, when I was reviewing the code, I saw code and logic that dealt with vertically flipping images (it seems that DIBs are an inverted format). There is also a fair amount of wrangling to move DIBs (which represents an actual bit image) between images.

My plan here is to replace the DIBs and indeed the image classes with a thin wrapper around CGImage. Apple's ImageIO framework provides a homogenous way to read and write these images in a variety of file-formats.

Cubics & Quadratics - Approximation results

I spent a few hours going through the Font Forge files to get a grip on how much work it would be to use it in Cello. My suspicion is that the code in Font Forge will produce better results in converting Cubics to Quadratics for fonts, simply because Fount Forge is dedicated to this kind of work and George Williams (the author) has obviously put a lot of work and consideration into the approximation - which specifically looks for various things like points of inflection when breaking the curve, and detecting Cubics that have been converted from Quadratics - something which happens with fonts.

Looking through the Font Forge code it does seem possible to map CGPaths onto the Splines and SplineSets - but it will be a bit of a fiddle to get it all working. On he other hand getting the existing Cello classes to work with CGPaths is actually quite straight forward. These classes are all written in C++ and the conversion is fairly trivial.

There is a huge amount to do so I am going with the path of least resistance. As the project progresses I can always open the Font Forge option again. It is something I would like to revisit as there is a huge amount of interesting stuff dedicated to the manipulation of splines in Font Forge.

I would personally recommend checking out the Font Forge FAQ for some great answers to questions. I particularly liked Why isn't Font Forge written in C++ - George Williams has written a great piece of software, is giving it away lock, stock and build instructions to whoever wants it for whatever purpose - it is there enjoy it.

To test the conversion of Cubics into Quadratics I took the Apple PathDemo sample code, that is in the installed with xcode in the developer folder, and made some changes. This sample code will, amongst other things, draw random paths - so the changes are quite small. I also added some code that will draw the on-curve points so that I can get an idea of the complexity of the new paths. Probably the biggest thing is Cello has it's own definitions points, lines, splines etc - and you need to satisfy the a reasonable spread of dependencies before you can use the magic ShapeVectorApproximator class.

Here are a couple of screen-shots from the test program. The grey thick line is the Cubic and the thin green one is the Quadratic.
The Quadratic on curve points are drawn in blue and the Cubic in red - so you can eaisly see that there are quite a few more cubic segments in the approximation.

If you look carefully in the image below you can see areas where the approximation breaks down and the green line strays outside of the grey - it should be in the exact centre.

Glyphs to Paths - Cubics & Quadratics in CoreText

Sometimes the world is a bit more upside down than you might initially perceive - Cello's output file format requires its curves to be described as Quadratics rather than Cubics. So I need to convert any Cubic paths that I get from CoreText to Quadratics.

Converting from Quadratics to Cubics is far less straight forward than the other way around. Cubics can only be approximated by Quadratics they can not be exactly converted. This sort of conversion is something that I have had to deal with in the past - it is not the sort of maths that I can pull off from first principles - so I have been working out with Google.

The best explanation of Cubics & Quadratic conversion that I have found is in the Font Forge (an open source font editor) website and can be found here. The section Converting Postscript to TrueType explains very clearly the issues that are involved in the conversion - check it out!

In doing the actual conversion after grubbing arround it would seem that I have a few options.

1. Font Forge - As a font editor Font Forge does this conversion. Looking through the sources this happens in a file called SplineOrder2.c. Of the implementations of the conversion this is by far the biggest and I conjecture might be the one best suited to converting fonts. The license for the software is a modified BSD license (a very permissive license) so I could use it. Font Forge has its own representation for curves so my CGPath would need to be converted.
   
2. Cello - Elsewhere Cello converts Cubics to Quadratics. The curves are in it's own internal path representation.
3. GXLibrary - When QuickDraw GX was released the SDK had a library (supplied as source code) that includes a conversion from Cubics to Quadratics. The source can be found in CubicLibrary.c. The conversion is all based on GX data stuctures and fixed point maths.

Glyphs to Paths - Quadratics & Cubics in CoreText

Pressing on with the conversion of the file that deals with glyphs I need to obtain the path that represents a glyph. CoreText provides the function CTFontCreatePathForGlyph that returns a CGPath of an individual glyph. The final thing to do then is to convert the path to the output format.

Core Graphics provides a function CGPathApply that will apply a user defined function to each element a part is composed of. So your user function is applied to al the moveto, lineto and curveto operations that make up the path.

To make getting to the path elements a little easier in C++ I have written a visitor class. The class is quite trivial, little more than a switch statement, that calls through to virtual moveto, lineto and curveto methods that can be overridden. Another way of doing this would be to write an iterator.

A slight complication is that the CGPath can contain both cubic and quadratic curves. In the target file format all curves are cubic. This means that any QuadCurveToPoint calls have to be converted to the cubic CurveToPoint. I am not yet in the position to test any of this - but I think it is reasonable to assume that there is a high probability that some font outlines may be expressed in quadratic curves - simply because quadratic curves are the native curve type of TrueType fonts. I would expect the Postscript (Type-1 fonts and friends) to appear as quadratics as that is the native curve type of these fonts.

Converting the QuadCurveToPoint so that it calls through to CurveToPoint is not too bad. The key thing is to have the previous end-point - and the rest is maths. I did not work out the maths that does this conversion myself - but it is something that I have had to use before. The function (or method) drops out quite simply. A link to some maths that seems strangely consistent with my old notes can be fond here.

void CGPathVisitor::QuadCurveToPoint(const CGPoint &q1, const CGPoint &q2)
{
CGPoint    c0 = m_lastPt; // last point

CGPoint c1 = { c0.x + 2.0 * (q1.x - c0.x) / 3.0,
c0.y + 2.0 * (q1.y - c0.y) / 3.0 };
CGPoint c2 = { q2.x + 2.0 * (q1.x - q2.x) / 3.0,
q2.y + 2.0 * (q1.y - q2.y) / 3.0 };
CGPoint c3 = q2;

this->CurveToPoint(c1, c2, c3);
}

I have not tested this code yet - if there are problems with it I will come back and correct this post.

Fonts and Font Scalars - from D-Type to CoreText

I have come to the part of Cello where I need to start dealing with text and fonts. Detailed information about glyphs, metrics, kerning pairs, glyph outlines etc. all need to be known in order to generate the final output file.

The Windows (MFC) version of Cello uses the D-Type font engine (scalar). Looking at D-Type it looks pretty good, and it is available for OSX. I do not, however, plan to use it - instead I will use CoreText. Core Text is Apple's new type technology. Released in Leopard (10.5) it replaces ATSUI which has entered the holding area that technologies enter before deprecation. I plan to use CoreText for a variety of reasons - the main one is that it integrates directly and naturally with CoreGraphics (Quartz) Apple's graphics technology. I plan to do all the drawing with CoreGraphics so using the complementary companion technology makes sense. I have experience of mashing and melding disperate graphics engines and font scalars and the like together and it is a whole lot easier to have a single imaging model.

The CoreText API looks clean and easy to understand. It is built on top of standard Core Foundation objects like CFDictionary as well as introducing it's own new types like CTFont. As with other Core Foundation technologies it toll-free-bridges onto equivalent cocoa NS types. This will make the inevitable protrusions into Cocoa for the UI straightforward to deal with.