Subject: Problem with TTF to PS

From: "L.S.Ng" <[email-masked]>
Date: Mon, 6 Jun 1994 10:29:50 BST

Soon after I released ttf2ps.c version 1.0, I rerun and burn-in test.

To my dismay, I discover one major bug. It is about the limit of path.

In most PostScript interpretters, there exists a certain limit on each
type of graphical objects. Path is composed of curves and lines. The
number of points to define a path cannot exceed 1500, as mentioned in
PostScript Language Reference Manual Appendix B.

In version 1.0 of ttf2ps, I treated each Chinese character as one single
path. The PS interpretter I used, Ghostscript, just give up on the
5201-st Chinese Big5 character. This is the character 'Xiang3'
(ringing). (The number 5201 based on 0 as the first character of Big5
'One' in Chinese)

I concluded that some Chinese characters are too complicated to be
treated as one path.  There are too many data points to be treated as
one single path.  So it is neccessary to decompose them.  The solution
is to make each unconnected radical a path.  So a typical character is
made up of several path.

Theory

It is fortunate that TTF has such information. TTF defines out-contour
as clockwise and in-contour as anti-clockwise.

Out-contours are paths that enclosed an area within which it is painted
black.  In-contours are surrounded by one out-contours and within an
in-contour the area should be left white.  Each out-contour can have
several in-contours.  For example, the character O has one out and in, I
has onely one out.  The Chinese character 'Sun' has one out and two ins.
(Only Chinese characters are so complicated and yet beautiful!! This is
part of the fun working with Chinese fonts!!)

It is observed that no out-contours will intersect each other. So every
out-contour is effectively unconnected. So I concluded that each
out-contour constitute an unconnected radical.

Clockwise means the data points are define in a clockwise sense. e.g. if
a square is defined as (0,0), (0,1), (1,1), (1,0), it is a clockwise
square; (0,0), (1,0), (1,1), (0,1) will be a anticlockwise square.

The area of a clockwise loop (i.e.  closed path) is effectively negative
by convention and positive for anticlockwise loop.  Such convention is
derived from Cartesian Geometry.  Consider the simplest loop, a triagle.
The area of an arbitrary triangle is ( a b sin @ / 2 ) where a and b are
the length of either two sides and @ is the angle between.  However( a b
sin @ ) is also the magnitude of the vector product of the vector a and
vector b.  So we can use the vector product to find the area.  The
vector product will be simply perpendicular to both a and b, i.e.  if a
and b is on xy-plane, then the product is parallel to z-axis.  Usually
the sign of the product is ignored as far as area is concern.  However,
if a and b are chosen such that @ is anticlockwise, the sign will be
positive.  This rule can be extended to any close loops.  Hence the
meaning of positive and negative area of a loop.

The second point is that all in-contours must be enclosed by one
out-contour.

So the modified algorithm will be:

For each outcontour,
    find all incontours it encloses
    group all of them as one path

To determine if an incontour is inside a certain outcontour, it is
necessary to prove all points of the incontour is inside the outcontour.
However, it is sufficient to prove all points are 'in' IF ONE POINT IS
INSIDE. So the problem reduces to determining if one point of the
incontour is inside a outcontour.

Various algorithm can be used. I simply used the 'additive area rule'.
This is to say that if a point is inside a loop, if we draw another loop
so as to touch the point inside, the resultant loop will have a smaller
area than the original. i.e. An area has been subtracted. If it is
outside, then the area will be larger, i.e. the test point adds to the
area. e.g. Consider a square with 4 corners as their data points. If we
put a point in the middle, and redraw a loop that joints all the 4
corner points and the middle point, the shape is now a square minus a
triangle. Hence the area is reduced. If the point is outside, the
resultant shape will be a square plus a triangle.

Obviously the simple 'additive area rule' breaks down if a badly behaved
shape is drawn. e.g. Consider a square ABCD and a point N, where N is
outside ABCD, and nearest to side AB. A well behaved shape will be
ANBCD. A badly behaved shape will be ABCND.

So the nearest data point (hence the nearest side) to the test point
must be found before applying the 'additive area rule'.  If found, the
small triangular area made by the test point with the nearest side will
be clockwise (negative area) if it is inside provided we make the test
point the third point of the triangle.  If it is outside, the triangle
will be anti-clockwise (positive area).

Comments welcome.

Liangsheng Wu