|
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
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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)
int
wn_PnPoly( Point P, Point* V, int n )
{
int wn = 0;
for (int i=0; i<n; i++) { if (V[i].y <= P.y) { if (V[i+1].y > P.y) if (isLeft( V[i], V[i+1], P) > 0) ++wn; }
else { if (V[i+1].y <= P.y) if (isLeft( V[i], V[i+1], P) < 0) --wn; }
}
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 boundary crossing algorithm fails in this case.
Real programmers use butterflies
modified 5-Jul-21 15:17pm.
|
|
|
|
|
|
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
|
|
|
|
|
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<V.Length; j=i++)
{
Point pti = V[i];
Point ptj = V[j];
if (((pti.Y > 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
|
|
|
|
|
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. When I added a breakpoint I can see the letter 'B' has [84, 116, 136] as the contour endpoints in your letter 'B'.
See if this works:
Pseudocode:
1.) Looping through the list of points in the TTF file, add the next point to your polygon.
2.) If the index of the point is equal to the index of a 'contour end point' then break
3.) Close your polygon.
4.) If there are more points in the list goto step 1
Then I believe (if you wanted to continue using PNPOLY) that you can pass all those points to PNPOLY separated by a [0,0] vertex.
Good luck,
-David Delaune
|
|
|
|
|
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
|
|
|
|
|
Ha! Exactly like the kind of problem I had on my own polygon library! Good luck!
|
|
|
|
|
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
|
|
|
|
|
|
See the red "Got a programming question?" link at the top.
Not a good start as part of the community.
CI/CD = Continuous Impediment/Continuous Despair
|
|
|
|
|
I'm guessing the name means "Idiot finding out what I can get away with" - marketing dweebs don't care about accuracy ...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
What's not a secret signal is the stuff at the top of the page that you ignored.
Ask here: https://www.codeproject.com/Questions/ask.aspx[^]
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
No offence but everything about this is wrong. Posted in the wrong place, with the wrong formatting, using std::list is probably wrong (the C++ name for a list is std::vector ), including bits/stdc++.h is wrong, using namespace std is .. OK not exactly wrong but a bad practice, and putting your data directly in the code instead of loading it from a file or resource is also questionable.
|
|
|
|
|
a newbee at "I can scramble some code" to bring other to help me.
Press F1 for help or google it.
Greetings from Germany
|
|
|
|
|
|
See the red "Got a programming question?" link at the top.
CI/CD = Continuous Impediment/Continuous Despair
|
|
|
|
|
That's because the indentation is missing: that;'s a secret signal to the compiler to generate spurious errors to prevent your code from ever working until it's actually readable.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
STOP POSTING THIS HERE. READ THE TOP OF THE FORUM. REPORTED
Real programmers use butterflies
|
|
|
|
|
You are a student. A team leader, even a junior programmer, would know how to debug!
|
|
|
|