# tynet-lichat/shirakumo - IRC Chatlog

Search

17:46:11
selwyn
if i get the time between job applications - which is probable but not certain - i would like to tackle the sdf problem

17:52:56
|3b|
take a bunch of contours possibly with intersections (including self-intersections and overlapping line segments), and return a set of contours without those intersections (and ideally with consistent winding orders)

17:55:58
|3b|
(cubic beziers would be nice, but we can't parse the font files containing them yet anyway, and probably could approximate the cubics with quadratics if needed)

18:00:18
selwyn
hm. so you want to split the curves at intersections, remove overlapping segments, and return the resulting curves in a way consistent with the original winding?

18:01:49
|3b|
non-zero winding order is what tells you which overlapping parts should be replaced by filled or empty

18:03:26
|3b|
approximately, if you project a line from outside the set of contours to any interior point and look at places where that line crosses any contour edge, if the contour is going upwards add 1, if contour is going downwards subtract 1. if the total at the interior point is 0, that point is "outside" the final shape, otherwise it is "inside"

18:04:51
|3b|
https://docs.microsoft.com/en-us/typography/opentype/otspec184/ttch01#the-scan-converter <- drawing and more precise description

18:08:24
selwyn
if you have overlapping segments, then the winding number would have to change if you remove one of them

18:11:00
|3b|
because we need to calculate the distance from the boundary of the shape to arbitrary points. easiest way to do that (without rasterizing it at super high resolution and searching which is slow), is to find the distance to the contours

18:11:22
|3b|
if parts of the contours aren't boundaries of the shapes, we get the wrong answer whenever those parts are the "nearest" point

18:15:28
|3b|
yeah, minimum distance to any contour giving right answer is the goal (which is why shared points are OK, since the distance is the same)

18:16:13
|3b|
and getting sign right is why it would be nice to have things wound consistently, like exteriors clockwise and holes ccw, or the reverse

18:16:25
selwyn
well, i guess i will talk more about it when i have time to work on it, but i understand the problem now

18:20:20
|3b|
https://github.com/3b/sdf/tree/msdf is the msdf code, but cleaning up the contours could/should probably be separate

18:20:57
|3b|
not sure if the msdf code has anything worth trying to reuse for that or not, since it is probably still pretty messy

18:23:07
|3b|
and shouldn't be too hard to translate the shape data from sdf lib into whatever alternate form was easy to work with

18:23:25
|3b|
(and/or replace it, if you came up with something nicer, i still don't like what's there now :p)

18:25:48
|3b|
ideally, it should work with input in single-floats, since that's what we get from zpb-ttf

18:27:57
|3b|
but probably could get away with 16bit ints (and pretty sure 32bit int is enough)... can't quite tell how much precision you are actually supposed to be preserving when building up glyphs from pieces

18:30:22
|3b|
ACTION thinks since composite glyphs can be nested you can theoretically have arbitrarily high requirements if you are expected to preserve it, but there is also no requirement to actually support nesting them, so single layer might be 16.16 fixed point or so

18:47:56
selwyn
my gut feeling is that dealing with cubic bezier curves would be easier than trying to convert them to quadratic

18:49:20
|3b|
though at the point where you are doing numeric solutions anyway for 4, going to 9 might not matter

18:50:25
|3b|
ACTION 's point was more that "intersections is hard in general" while "approximating with a lower-degree curve is just coding and not very hard"

18:51:05
|3b|
so if limiting the intersections to quadratics makes that easier, it is probably a win

18:52:28
|3b|
ACTION hasn't implemented the sdf part of cubics either, so even less reason to care about them for the intersection part :)

18:52:35
selwyn
well, finding a good approximant to a cubic bezier curve using quadratic curves might be difficult

18:53:34
|3b|
or rather "good" doesn't have to be too strict in practice, so "chop it in half until the error is small enough" is fine

18:58:16
|3b|
and msdf could but doesn't currently bother trying to deal with inconsistent CW vs CCW, since that is ambiguous when there are overlaps

19:01:04
|3b|
msdf pretty much needs consistent CW/CCW ordering, since the version from the paper relies on being able to split contours into discontinuous pieces, so calculating them by winding number is hard

19:04:04
selwyn
i suppose that one could use gsll to solve numerically for roots of higher order polynomials

19:06:46
|3b|
if we wanted to ffi, could just bind msdfgen, or use skia for fixing contours like it does

19:08:13
|3b|
supposedly http://nishitalab.org/user/nis/cdrom/cad/CAGD90Curve.pdf is "better" than solving through polynomial zeros, since they don't always make very nice polynomials to start with

19:09:30
|3b|
ACTION isn't even sure an "exact" solution like you would get from a plynomial solver (or theoretically from that paper) is what we want

19:12:01
|3b|
like the current test case i've been stuck on since yesterday, i think the curves are effectively coincident to within double-float noise over a range of ~1e-7

19:13:08
|3b|
i know there are 2 other intersections, so could be 0 1 or 2 actual intersections in that range, but i can't tell without doing 'clever' things with rationals

19:14:41
|3b|
yeah, i guess polynomials would actually give the distance so make it easier to measure the interval, assuming it was stable enough

19:26:02
|3b|
and i meant "bisection in the context of finding intersections by solving polynomials" as opposed to "finding intersections by recursively bisecting curves and checking for overlap between the bounding boxes of the halves"

19:29:16
|3b|
and to clarify, the stuff about intervals isn't an external requirement, just something that might be useful for the way i was trying to solve the "clean up curves" problem

19:31:23
|3b|
ACTION 's plan is roughly "figure out how to intersect beziers" then "hook that into bentley-ottmann sweepline intersection finding" then "reconstruct the contours from the intersections"