Support for Fillrule.NonZero in addition to current FillRule.EvenOdd?

[Fribur]

When doing Boolean operations on polygons, it is often essential to be able to select different fillrules: Non-Zero, Even-Odd, Positive, Negative, which is derived from the winding number (nice visual in Clipper2 documentation).

I got a use case with Variable Fonts: pretty much all of them have glyphs defined via self-overlapping outlines. The overlaps are to be considered "overlaps", and not "holes". I can accomplish this by setting the Fillrule in Clipper2 to FillRule.NonZero or Fillrule.Negative (Clipper2 supports all 4 FillRules mentioned above, most graphics libraries support at least FillRule.Even-Odd and FillRule.Non-Zero).

It looks like Polybool only supports FillRule.Even-Odd? Is it in principle possible to add FillRule.NonZero functionality to PolyBool, e.g. by defining new selection rules or new annotation rules? Or is it simply not possible via this approach? If possible, I would appreciate a hint how, and I might give it a stab to implement this.

[velipso]

I suspect the main algorithm will still work, but the rules for whether a segment is filled above or below will need to be updated.

The fill logic is here (iirc):

polybool/src/Intersecter.ts

Lines 589 to 614 in a46c3a2

	let toggle: boolean; // are we a toggling edge?
	if (ev.seg.myFill.below === null) {
	// if we are new then we toggle if we're part of a closed path
	toggle = ev.seg.closed;
	} else {
	// we are a segment that has previous knowledge from a division
	// calculate toggle
	toggle = ev.seg.myFill.above !== ev.seg.myFill.below;
	}
	// next, calculate whether we are filled below us
	if (!below) {
	// if nothing is below us, then we're not filled
	ev.seg.myFill.below = false;
	} else {
	// otherwise, we know the answer -- it's the same if whatever is
	// below us is filled above it
	ev.seg.myFill.below = below.seg.myFill.above;
	}
	// since now we know if we're filled below us, we can calculate
	// whether we're filled above us by applying toggle to whatever is
	// below us
	ev.seg.myFill.above = toggle
	? !ev.seg.myFill.below
	: ev.seg.myFill.below;

You can see that I have specific logic around myFill.above and myFill.below.

There is also a special case where a segment is on top of another one (line 549 in same file), which will need updating too, but I would focus on the other section first and see if you can get it to work with ideal conditions.

[velipso]

It would probably be useful to read this section of the tutorial, where I go over this logic in detail: https://sean.fun/a/polygon-clipping-pt2/#annotating-a-single-polygon

[Fribur]

Many Thanks for your reply! As I find the algorithm very elegant, I am going to give it a try to add all the Fillrule logic. Might take me a while as I still struggle to understand everything and all the different combinations of Fillrule and Cliptype make my brain smoke. Here all the combinations of just the subject polygon with itself using Clipper2:

Am I basically aiming for this outcome here after the polygon annotation phase? I have a hunch the Fillrule enhancements to the annotation phase will in the end all be very straight forward and logic, probably similar to your 16 bool array in the selection phase.

[velipso]

Yeah so at a high level, it performs a self-intersection phase for each individual polygon, then the boolean op for the two annotated polygons. So it runs the Intersecter.ts event loop three times in total:

1. Self-intersection polygon A -> generates annotated segments for polygon A
2. Self-intersection polygon B -> generates annotated segments for polygon B
3. Intersect A segments and B segments
4. ... go on to do segment selection and chaining (shouldn't be affected by this change, I think)

I believe you should only care about #1 and #2 -- and inside Intersecter.ts, this phase is identified via if (this.selfIntersection) { ... }.

So yes, your ultimate output should be annotated segments, where each segment has a fill above/below as true or false.

I think if you can do that, then the rest of the algorithms will continue to work (#3 onwards). I could be wrong, but that makes sense to me.

[Fribur]

Alright, attempt to implement FillRule.NonZero using this self intersecting closed polygon 1:
"poly1": { "regions": [ [ [10, 60], [75, 60], [80, 30], [55, 30], [50, 90], [40, 90], [30, 10], [100, 10], [90, 120], [20, 120], [10, 60], ] ], "inverted": false } (Polygon 2 is empty). Key observation is that I need to make the inner edges somehow "non-toggling" during the self intersection phase. How exactly to do that robustly is not quite clear. I have a hunch (confirmed by ChatGPT) that I somehow need to derive this from the winding number, and not just toggling true/false. Still, at least for the test polygon, I was successful making the desired edges non-toggling by doing the following:

• by moving the entire annotation phase BEFORE the intersection test. This ensures that ALL 4 left and right segments created during intersection receive a prior annotation (when a new event is intersected with above/below segment from the current status), and not just the left/right segment of the segment that is already in the status. Thus, when we see the 'right' event eventually, we know it was an self-intersection, and toggle is turned false. (Note the code is C sharp, as my library is for Unity. Once I get this FillRule thing sorted out, I will make it publicly available, thanks to BURST compilation I expects it to be ~100 times faster than normal C-sharp, and hope it might be faster than Clipper2.)

// segment resulted from division
if (fillRule==FillRule.NonZero)
    toggle = ev.seg.above == ev.seg.below; // segment is toggling when above and below fill are the same
else
    toggle = ev.seg.above != ev.seg.below; // segment is toggling when above and below fill are not the same

• once we encounter a new segment, it does not automatically become toggling, rather when the below segment is filled on above and below, then toggle is turned false.

 // new segment
 if(fillRule == FillRule.NonZero && below !=null && below.seg.above == below.seg.below)
     toggle = false;                                 //segment is inside if below segment is filled on both side
 else
     toggle = ev.seg.closed;                         //toggle if we're part of a closed path

All this leads to this output (image is a signed distance field from my font library):

"Union result (Non-Zero)": { "regions": [ [ [75, 60], [52.5, 60], [55, 30], [80, 30], [75, 60], ], [ [100, 10], [30, 10], [36.25, 60], [10, 60], [20, 120], [90, 120], [100, 10], ] ], "inverted": false }

HOWEVER, I tried this with some actual self-overlapping glyphs in my fonts, and it does not quite work: E.g. I either get the inner contour of a 9, or out the outer contour when I modify the division segment check, but not both :-(

I have consulted ChatGPT several times, and it keeps telling me I need use winding count instead of toggle on crossing, but I have not yet figured out how to so so. Here what ChatGPT say's:
✅ Background: Why Polybool only supports Even-Odd

Polybool reduces polygons into sets of segments. Each segment stores:

Which polygon(s) it belongs to

Entry/exit status

Whether it should appear in the result, based on the boolean operation

Polybool currently determines region inside/outside by computing parity (toggle on crossing). That is exactly the even-odd rule.

✅ What must change to support Non-Zero

The non-zero fill rule is winding-count based:

Crossing a segment in its “forward” direction increments winding

Crossing in the opposite direction decrements winding

A point is inside if final winding ≠ 0 (instead of parity = 1)

To add non-zero support, you must modify:

Segment representation → add signed direction

Intersection ordering / sweep logic → maintain winding counters

Classification logic → determine inside/outside using winding instead of parity

Region reconstruction → unchanged, but you pass the new inside/outside flag

[Fribur]

Ok, I think I got a solution. Here the fill logic able to deal with NonZero and EvenOdd:

if (selfIntersection)
{
    //NonZero
    if (fillRule == FillRule.NonZero)
    {
        // (1) winding from a point below the current event towards the bottom of the status
        int windingBelow = 0;
        for (int i = eventIndexInStatus, end = status.Count; i < end; i++)
            windingBelow += status[i].seg.winding;

        // (2) winding from a point above the current event towards the bottom of the status
        var windingAbove = windingBelow + ev.seg.winding;

        // (3) set fill
        ev.seg.below = windingBelow != 0 ? FillStatus.Filled : FillStatus.NotFilled;
        ev.seg.above = windingAbove != 0 ? FillStatus.Filled : FillStatus.NotFilled;
    }
    else //EvenOdd
    {
        bool toggle;
        // (1) determine if the edge is a "toggling edge"
        if (ev.seg.below == FillStatus.Undefined)
            toggle = ev.seg.closed;                             // new segment. toggle if we're part of a closed path
        else
            toggle = ev.seg.above != ev.seg.below;              // segment resulted from division, and is toggling when above and below fill are not the same

        // (2) determine below fill
        if (below == null)
            ev.seg.below = FillStatus.NotFilled;                // no segment is below us, so not filled
        else
            ev.seg.below = below.seg.above;                     // copy the above fill from the segment below 

        // (3) determine above fill
        if (toggle)
            ev.seg.above = ev.seg.below ^ FillStatus.ToggleMask;//above fill is opposite of below fill
        else
            ev.seg.above = ev.seg.below;                        //above fill is same as below fill
    }
}

I am calculating the winding per segment while the segment is created in AddRegion:

/// <summary>
/// For a given polygon edge, calculate a point that is above this edge. 
/// Orient2D is used to determine crossing of a ray from this point downwards with the edge. 
/// If the crossed edge is directed from right to left, we have a positive crossing; otherwise, we have a negative crossing.
/// https://jeffe.cs.illinois.edu/teaching/comptop/2023/notes/02-winding-number.pdf
/// </summary>
public static int GetWinding(double2 a, double2 b)
{
    var wind = 0;
    //calculate a point 2 units "above" edge
    //feels hacky. Is there a better way?
    double2 p;
    p.x = math.min(b.x, a.x) + math.abs(b.x - a.x) / 2;
    p.y = math.max(a.y, b.y) + 2;

    var orient2D = PointUtils.Orient2DFast(a, b, p);
    if (a.x <= p.x && p.x < b.x && orient2D > 0)
        wind = 1;
    else if (b.x <= p.x && p.x < a.x && orient2D < 0)
        wind = -1;
    return wind;
}

This picture visualizes the principle:

Result:

[Fribur]

Update: the code above could not deal properly with vertical edges. This code can: https://github.com/Fribur/TextMeshDOTS/blob/1f224411bce3e4998fa604ec3efcadb248c44e67/Polybool/Intersecter.cs#L329
https://github.com/Fribur/TextMeshDOTS/blob/1f224411bce3e4998fa604ec3efcadb248c44e67/Polybool/Intersecter.cs#L50
https://github.com/Fribur/TextMeshDOTS/blob/1f224411bce3e4998fa604ec3efcadb248c44e67/Polybool/PointUtils.cs#L28