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.

Kerning Tables and CoreText

I don't think I have ever worked on something type related without having, at some stage, to grub around in font tables. Cello, it turns out, is no different. The output file requires a subset of kerning pairs of the fonts used in the documents - to do this I need to get a set of all the kerning pairs that are defined a given font. Core Text won't give me the kerning pars but it has a function CTFontCopyTable that will give me, via a CFDataRef, a pointer to an arbitrary table in the font. All the fonts Core Text deals with are TrueType fonts, and those that are not (Type 1 postscript fonts) are cleverly packed up on the fly as synthetic true-type fonts. CTFontCopyTable takes an options flag that allows you to screen out synthetic tables - should you wish.

So to get the kerning table of a font you:

CFDataRef kerningTable =
 ::CTFontCopyTable(font, kCTFontTableKern, kCTFontTableOptionNoOptions);
const UInt8 *kerningTablePtr = ::CFDataGetBytePtr(kerningTable);

The format of the truetype fonts and font tables can be found here. Details of the kerning table can be found here.

There are four different formats of kerning tables. I plan initially to support Format0 only

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.

typename in templates - gcc errors

Pressing on I am working through the generator files. These are a set of files that generate the output. The biggest problem I found so far in these is some template definitions that tripped up gcc which requires a typename to be specified in some circumstances where visual c++ was quite happy. The following class - when complied on XCode

template <class T>
class Foo
{
public:
  Foo(const T&);
  std::list<T*>::iterator Bar();
};

Results in error: expected ';' before 'Bar'

Adding typename fixes the problem - so the gcc friendy Bar looks like this:

  typename std::list<T*>::iterator Bar();

As with many compiler errors the error message gave me little insight into the problem. I tracked down the solution looking through the boost libraries for code that returns an iterator.

Pargen for YACC and LEX

The YACC and LEX libraries that Cello links against come from Pargen. Pargen is a YACC and LEX distribution for use on Windows. Cello was supplied with the Pargen libraries without source. Fortunately Bumble Bee Software have the sources to their previous release of their Pargen library available for download. Checking the source headers against the headers that were included with the Cello code I can see that they are the same. The Pargen library compiled almost without problem.

Replacing GetKeys with CGEventSourceKeyState

Working through some of the ECMA (JavaScript) interpreter there is a line of code that tests for the escape key being held down in order to abort execution.

if ((::GetAsyncKeyState(VK_ESCAPE) & 0x8000))
{
  :
}

On the Mac the equivalent UI convention is the command-period. Looking at the world through old Carbon programmer eyes I would probably use GetKeys. In the brave new world of Cocoa replete with the Animal Farm bleat of "Cocoa good, Carbon bad" GetKeys is deprecated. I could use it but I'd rather not.

It took a little hunting but the replacement for GetKeys is CGEventSourceKeyState. This function will return if a given key (expressed as a virtual key code) is depressed. Virtual key codes are defined in HIToolbox/Events.h.

So the function drops out quite nicely:

bool IsCommandPeriodPressed()
{
  CGEventSourceStateID eventSource
    = kCGEventSourceStateCombinedSessionState;

  return ::CGEventSourceKeyState(eventSource, kVK_Command)
    && ::CGEventSourceKeyState(eventSource, kVK_ANSI_Period);
}

As a postscript, and for the avoidance of doubt, I have no beef with Cocoa; Cocoa is good and fun as well as being splendid bed-time beverage for children and adults alike. After all I will be using pure Cocoa for the Cello UI - it is just the Cocoa religion thing that is a bit scary.