Polygon filling, and TTF mess

[honey the codewitch]

No I think missed it in the fray as I was neck deep in half a dozen different things. I'll follow the link. Thanks!

Real programmers use butterflies

[honey the codewitch]

I just looked at that wiki entry you pointed me to. It looks like that would solve it but I don't know how to do it yet. Sally forth! Onward to google! Thank you so much for your comment. I didn't mean to ignore your tip from before, I think I just got buried. :)

Real programmers use butterflies

[Lost User]

You are welcome,

honey the codewitch wrote:

Thank you so much for your comment.

I couldn't help but notice that you checked in the sample code from wikipedia nearly verbatim. Your intersects_poly[^] function is a copy-paste from the even–odd rule[^] article that we discussed last month. Looks like it was checked in ~15 minutes after we discussed polygon intersections. The nonzero-rule[^] will require either a frame buffer or some clever math to determine stroke direction. Best Wishes, -David Delaune

[honey the codewitch]

yeah, that was my starting point. I'll end up modifying it. I intend to modify it anyway to use horizontal run-lengths to speed up drawing.

Real programmers use butterflies

[honey the codewitch]

I don't necessarily have read/a framebuffer on all my devices, but I do have it on e-paper devices. However, in order to make this work for all devices I'll need to probably need to do that clever math, or draw the characters to an intermediary bitmap, which I don't want to do since then memory usage is tied to character size and I run into issues where characters somewhat overlap or otherwise connect with each other (think a cursive font) - because what I've noticed is characters in TTF can overhang their effective bounding box. I'm wondering - if I draw in order, can't i determine the stroke direction by looking at previous points? I guess I need to understand the algorithm better.

Real programmers use butterflies

[Super Lloyd]

Ha! Exactly like the kind of problem I had on my own polygon library! Good luck! :)

A new .NET Serializer All in one Menu-Ribbon Bar Taking over the world since 1371!

[Lost User]

Well, Might be easier to find using the math term. I guess only software engineers would call it 'The non-zero rule.' The math terminology you are looking for is contour winding numbers[^]. Winding number - Wikipedia[^] I don't expect that you would be interested in this... but the same algorithm software engineers call 'the non-zero rule ' is the same algorithm Ed Witten used in the 1990's for exploring Calabi–Yau manifolds[^]. Today that work is known as T-duality[^]. There are hundreds C/C++ of examples of this algorithm on the internet. Just google for 'winding number algorithm'. Best Wishes, -David Delaune

[honey the codewitch]

I found this: Point in polygon - Wikiwand[^] Which led me here: Geometry Algorithms TOC[^] Which led me to some code, but I think i'm looking at the wrong routine because when I implemented theirs I get the same dodgy result I do when I use .NET's FillPolygon() or when I use my own even-odd method in C++ (picture of the result in the original post)

// wn_PnPoly(): winding number test for a point in a polygon
// Input: P = a point,
// V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
// Return: wn = the winding number (=0 only when P is outside)
int
wn_PnPoly( Point P, Point* V, int n )
{
int wn = 0; // the winding number counter

// loop through all edges of the polygon
for (int i=0; i P.y)      // an upward crossing
             if (isLeft( V\[i\], V\[i+1\], P) > 0)  // P left of  edge
                 ++wn;            // have  a valid up intersect
    }
    else {                        // start y > P.y (no test needed)
        if (V\[i+1\].y  <= P.y)     // a downward crossing
             if (isLeft( V\[i\], V\[i+1\], P) < 0)  // P right of  edge
                 --wn;            // have  a valid down intersect
    }
}
return wn;

}

That's from the book, but I reimplemented it in C# with my C# version of my TTF renderer, so I'm still digging, but I've maybe made some progress.. ETA: I should note while you may not be familiar with this variant of the winding algorithm depending on the last time you had to do this, in the first link it's covered here:

Quote:

There is a significant speed-up (known since 2001) of the winding number algorithm. It uses signed crossings, based on whether each crossing is left-to-right or right-to-left. Details and C++ code are given at the link in the following annotation .[6] Angles are not used, and no trigonometry is involved. The code is as fast as the simple boundary crossing algorithm. Further, it gives the correct answer for nonsimple polygons, whereas the boundar

[Lost User]

Hmmm, That code looks correct to me. If you upload something I can compile on Windows then I can take a look sometime this week. Actually I have an another idea. Can you try using the PNPOLY algorithm W. Randolph Franklin[^] came up with? PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF)[^] I've never used it, but I've read about it in several journals. Also... if you have a copy of Mathematica then you can test these algorithms[^] and then export/convert them to the C programming language[^]. Best Wishes, -David Delaune

[honey the codewitch]

Here's a link to a repo in C#. I have something in C++ but you'll be buried in abstractions if I share it. GitHub - codewitch-honey-crisis/Ttf[^] The pertinent code is all in Main.cs _poly contains a list of points to draw. Because of the needs of the winding algorithm, I close the polygon as the final point (it points to the same point as the first point). That happens in Main's constructor. The constructor takes a glyph that I've loaded from a ttf and turns it into a bunch of "GlyphPoint" entries, which the ctor turns into Point objects. There's an extra member on GlyphPoint but I'm not using it in this case. It's for rounding the edges of the polygons.

Real programmers use butterflies

[honey the codewitch]

I got the exact same result with the PNPOLY algorithm. I'm starting to think there's some kind of problem with how I'm building the final points of my glyph? I don't know. *scratches head* I'm kind of clueless right now.

    static bool IsInsidePolygon2(Point P, Point\[\] V)
    {
        int i, j;
        bool c = false;
        for(i=0,j=V.Length-1;i P.Y) != (ptj.Y > P.Y)) &&
             (P.X < (ptj.X - pti.X) \* (P.Y - pti.Y) / (ptj.Y - pti.Y) + pti.X))
                c = !c;
        }
        return c;
    }

Real programmers use butterflies

[honey the codewitch]

You know, I don't think that's the problem now that I've tried 3 different polygon fill algos and got the same result. It's not because the poly is overlapping. There's something wrong with how it's being terminated to begin with but I'm not sure what. I've used even/odd, non-zero-rule/winding, and PNPOLY and the latter two deal with overlapping polygons (i'm not 100% certain about PNPOLY but i think it does) It's super frustrating because the TTF format is complicated, and loading those glyphs wasn't easy.

Real programmers use butterflies

[Lost User]

Good morning, Ok, I took a brief look at your code and believe that I have identified the problem. In your Main() function[^] you are naively loading alll of the polygon points and simply passing that to your 'point in polygon' function. That would only work for simple polygons. Some comments: 1.) TrueType patents have expired but were previously held by Apple. So you should refer to the Apple reference documents[^]. 2.) I see that the Apple reference docs state that the TTF file format is specificially designed for the non-zero winding algorithm[^] so maybe you should go back to using that. Although I don't think it would be a problem to continue working with PNPOLY, the PNPOLY algorithm simply requires a [0,0] between each contour/hole. I actually think it might be less work if you keep using PNPOLY. 3.) You need to read the Contours section of the TrueType reference manual[^], it specifically says that the letter 'B' contains three distinct closed shapes, each being a contour. 4.) It looks like you already have some code for using contours. In your OpenFont.Glyph.cs[^] code I can see that you are already using ContourEndpoints. Contours[^] I can see that your TTF parser seems to correctly identify the three contours. Whe

[honey the codewitch]

I found a better way that also does anti-aliasing. I ... figured out some things, including what you're saying, but there's more. In the end it involves sorting and tracking edges, and doing something the code I'm referencing (public domain! yay!) calls "xor winding" - it doesn't use pure xor though - it uses a flag (invert) anyway I'm working through it because it renders to bitmaps and I want to render directly to a drawing surface (even if that surface is a bitmap! but also if it's a display)

Real programmers use butterflies