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 _______________________________________________ Freetype-devel mailing list Freetype-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/freetype-devel
