freetype-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[ft-devel] On contour directions and fill rules (was Re: [patch] embolde


From: Behdad Esfahbod
Subject: [ft-devel] On contour directions and fill rules (was Re: [patch] emboldening rework v1)
Date: Thu, 19 Apr 2012 14:08:26 -0400
User-agent: Mozilla/5.0 (X11; U; Linux i686 (x86_64); en-US; rv:1.9.2.28) Gecko/20120306 Thunderbird/3.1.20

Ok, I *was* seriously misguided.  I think I understand things now.  Let me
summarize for posterity.  What puzzled me before is that I came across fonts
that have both TrueType orientation and Type1 orientation in the same glyph
(but separate from eachother), and FreeType handles them fine.  It didn't
occur to me until now that separate parts of the glyph can have different
winding direction and that's fine for a nonzero-winding fill rule.

So, each glyph outline is a collection of contours.  Each contour has a
direction: clockwise or counter-clockwise.  The contour direction can be
determined in a few ways.  Finding an extreme point and probing the edge
angles is one.  Using the signed area is another.

Now there are different fill rules:

- Even-odd rule: from any point, draw a halfline in any desired direction, add
1 every time the halfline crosses a contour.  Fill if total number is odd,
don't fill otherwise.

- Non-zero winding rule: from any point, draw a halfline in any desired
direction, add +1 or -1 every time the halfline crosses a contour, depending
on the direction of the crossing.  Fill if total number is nonzero, don't fill
otherwise.

Now.  *if* the outline is not self-intersecting and doesn't have degenerate
contours, then filling a glyph designed to be filled with nonzero winding rule
with the even-odd rule generates the same outcome.

A degenerate contour is one that does not change the rendering if removed.
For example, if you have a clockwise circle, and another clockwise circle
fully inside it, the second circle is degenerate because the rendering is one
fully filled circle with or without it.  With this assumption, one can show
that the halfline to infinity ought to flip between in and out at each
crossing, hence this being the same as the even-odd rule, and the contours
being crossed are CW/CCW alternatively.

Now, if we are dealing with such nice glyphs, and the outer outlines all have
the same direction, then we can use simpler filling rules.  For example, for
such well-formed TrueType outlines, you can have a fill-right rule:

- Fill-right rule: find the closest outline, fill if the point is to the right
of the outline, don't fill otherwise.

So, that's what mainly confused me.  Because my rasterizer is in fact a
fill-right rule.

Now there are three if's so far:

- There are no degenerate contours.  I'm just going to assume this.  Have not
seen any in the wild so far.

- All outer contours have the same direction.  I've seem many glyphs in the
wild violating this.  Letter "A' in MonsieurLaDoulaise-Regular.ttf from Google
Font Directory is just one example.  The good news is, this can be detected
and fixed.  And I'm going to fix my code to do that.

- No self-intersection.  Now, when one says self-intersecting, one has to
qualify.  I was under the impression that assuming outlines are not
self-intersecting was a safe assumption.  However, I'm convinced now that this
is absolutely false assumption.  I'm convinced otherwise now.  I'd say
assuming that each *contour* is non-self-intersecting is safe, but I'm going
to guess that many well-constructed font will have overlapping contours for
the "c-cedilla" character.  Any font creating that glyph as a composite glyph
is going to have this problem.  There are two different contours, both
clockwise, that partially intersect.  And filling this with fill-right or
even-odd is plain wrong.  Only non-zero winding rule can render this
correctly.  And now I guess these cases are exactly why non-zero winding was
chosen over even-odd originally.

And indeed, my rasterizer cannot handle ccedilla in Droid Sans Regular right
now.  One way to fix it I guess would be to detect those and render the two
outlines as if they were separate glyphs.  Needs more work, more math, and
some graph algorithms to separate the contours into separate subglyphs...  Not
impossible, though clumsy...


That's it.  Ok, now wouldn't be fair to not reveal my rasterizer after all
this talk.  It's a project I've been working on for a while, and many
interested parties already know about it.  I was holding off announcing
publicly until a driver issue in mesa could be fixed.  There's a patchset for
that now, so I'll go ahead and announce the project right after this email.  I
will also be presenting it at LGM and GUADEC.


Cheers!
behdad



reply via email to

[Prev in Thread] Current Thread [Next in Thread]