Better documentation for FillRule about manifold

[briansturgill]

@elalish OK, I'm a bit slow. But I get it now. Because of the need to keep things extrudable, Clipper2 maintains
a set of paths that only have winding 0 and 1. NonZero, EvenOdd and Positive all handle winding 0 and 1 in the exact
same way... thus in my SVG output I could even use NonZero and get the same result.
Thanks for your patience!

[geoffder]

The fill rule parameter is only exposed in the constructors intentionally, as once the initial "cleanup" union is performed on user provided paths, all winding thereafter is positive.

[elalish]

Lots of confidence in this title... would you mind providing an example of what is broken, i.e. a returned vs expected result?

EvenOdd loses winding direction information and results lots of "kissing" polygons, which is not terribly helpful for solid geometry.

[pca006132]

In my understanding, everything in manifold is done in Positive fill rule. The constructor is just for users to convert their polygons using alternate fill rules into Positive. I think as long as the representation is consistent, the fill rule used for boolean operation should not matter?

Maybe we should document this better though, e.g. the result of ToPolygons is Positive.

[briansturgill]

@elalish Clipper2 does not loose winding information when EvenOdd is used. Its internal representation does have
the needed winding consistency needed for things like Extrude.

As to "what is broken". You provide all the FillRules. You provide a way to use a FillRule in a constructor.
I had no idea that the FillRule would be ignored later in other operations. I spent two whole days figuring out
what the problem was. If you give a user an enum of FillRules, is it odd that they want to use them?
Were it not for Clipper2's documentation, it would have taken even longer to understand.

You're worried about "kissing polygons"... not really a problem for my end users.
(They just don't have that sort of complexity in paths.)
What IS concerning for my end users is Clipper2's auto "repair" of self-intersecting paths.
This results in 2 paths that share a point. VERY BAD for 3d printing purposes.
It should simply be reported as the error that it is.
Indeed, its presence is almost certainly an indication of a mistake in listing the path points.

@pca006132 is correct, it really should be better documented. Clipper2 handles all these fill types.
I'm not sure why only one was chosen. The point in using EvenOdd is that users don't have to understand winding,
Clipper2 takes care of that for them. EvenOdd is much more commonly understood. I had never even
heard of Positive until I started dealing with Manifold. According to Clipper2 documentation only Android
and OpenGL support it.

Below is a python script I used to test EvenOdd. You can comment out any subset of .reverse() and Clipper2 will
provide the same, correctly wound (for extrude purposes) set of paths.

Anyway, I will simply use FillRule.Positive. I need to do my own checking for self-intersecting paths.
I can straighten out winding issues for end users while I'm doing that. Maybe I'll have them list
holes separately from contours...

I cannot find a real definition of the positive fill rule anywhere (Clipper2 sort of has one).
In particular it never says what holes are.
I am pretty sure that ccw means contour, and cw means hole. Multiple exterior contours are allowed.
No hole or contour should intersect any other path or itself.
But that definition is lacking... can holes contain holes (without an intervening interior contour)?
Can interior contours contain interior contours (without an intervening hole)?
I tried looking through OpenGL docs, but they don't seem to mention Positive very often.
The thing about EvenOdd is that these questions are easily answered.

winding.py

import manifold3d as m

def winding(lv: list[tuple[float, float]]) -> str:
    def wstr(winding):
        if winding > 0: return "cw"
        if winding < 0: return "ccw"
        return "zero"

    length = len(lv)
    if length < 3: return "too small"
    winding = 0.0
    for i in range(0, length):
        winding += (lv[(i + 1) % length][0] - lv[i][0]) * (lv[(i + 1) % length][1] + lv[i][1])
    return wstr(winding)


circ_outer = m.CrossSection.circle(8, 20)
circ_inner = m.CrossSection.circle(1, 20).translate((5, 0))
circ_inner2 = m.CrossSection.circle(1, 20).translate((-5, 0))
circ_inner3 = m.CrossSection.circle(3, 20)
circ_inner4 = m.CrossSection.circle(2, 20)

po = circ_outer.to_polygons()[0]
pi = circ_inner.to_polygons()[0]
pi2 = circ_inner2.to_polygons()[0]
pi3 = circ_inner3.to_polygons()[0]
pi4 = circ_inner4.to_polygons()[0]

assert winding(po) == "ccw"
assert winding(pi) == "ccw"

po = po.tolist()
pi = pi.tolist()
pi2 = pi2.tolist()
pi3 = pi3.tolist()
pi4 = pi4.tolist()
#po.reverse()
pi.reverse()
pi2.reverse()
pi3.reverse()
pi4.reverse()
print(winding(po))
circ_w_hole = m.CrossSection([po, pi, pi2, pi3, pi4, circ_outer.translate((20,0)).to_polygons()[0]], m.FillRule.EvenOdd)

pcwh = circ_w_hole.to_polygons()
print(len(pcwh), len(po), len(pi))
print(pcwh)
for p in pcwh:
    print(winding(p))
#import piecad
#piecad.view(piecad.Obj2d(circ_w_hole))

o = circ_w_hole.extrude(10)
o.num_vert()
print('empty:', o.is_empty(), o.status())
#piecad.save("/tmp/test.obj", piecad.Obj3d(o))

[pca006132]

You can have a look at the winding number definition, winding number <= 0 is a hole when you use positive fill rule.

Can interior contours contain interior contours (without an intervening hole)?

Yes, though I think in the output we just collapse winding numbers to either 1 and 0? Not sure about that.

[pca006132]

btw changing the title as this seems to be only affecting documentation

[geoffder]

Can interior contours contain interior contours (without an intervening hole)?

Yes, though I think in the output we just collapse winding numbers to either 1 and 0? Not sure about that.

Contours (positive winding) in contours and holes (negative winding) in holes (without the other between) are just unioned away. Like adding a smaller circle to a bigger one.

[elalish]

@briansturgill it sounds like some more documentation of what a winding number is might help here. Check out https://en.wikipedia.org/wiki/Point_in_polygon for examples. This is why pasting images into issues like this is so critical. The purpose of winding number is exactly to convert overlapping polygons into non-overlapping polygons. Information is always lost in this process, but EvenOdd loses different information than Positive.

[briansturgill]

From Clipper2 docs:
Even-Odd: Only odd numbered sub-regions are filled
Non-Zero: Only non-zero sub-regions are filled
Positive: Only sub-regions with winding counts > 0 are filled
Negative: Only sub-regions with winding counts < 0 are filled
and then there is (https://en.wikipedia.org/wiki/Nonzero-rule):
"If the total winding number is zero, P is outside C; otherwise, it is inside."

UPDATE:... gave wrong quote:
"Some implementations instead score up the number of clockwise revolutions, so that clockwise crossings are awarded +1, counter-clockwise crossings -1. The result is the same."

What, specifically is the difference between non-zero and positive?
They look to be exactly the same to me.

[briansturgill]

Yet there is definitely some difference, from Clipper2 source:

//nb: SVG only supports fill rules NonZero and EvenOdd
  //    so while we can clip using Positive and Negative
  //    we can't displaying these paths accurately in SVG
  //    without (safely) changing the fill rule

  inline void SvgAddSubject(SvgWriter& svg, const PathsD& path, FillRule fillrule)
  {
    if (svg.Fill_Rule() == FillRule::Positive ||
      svg.Fill_Rule() == FillRule::Negative)
    {
      svg.AddPaths(path, false, fillrule, 0x0, subj_stroke_clr, 0.8, false);
      PathsD tmp = Union(path, svg.Fill_Rule());
      svg.AddPaths(tmp, false, fillrule, subj_brush_clr, subj_stroke_clr, 0.8, false);
    } 
    else
      svg.AddPaths(path, false, fillrule, subj_brush_clr, subj_stroke_clr, 0.8, false);
  }

[briansturgill]

OK, I apparently have no understanding of non-zero whatsoever.
But I think I really do understand Positive now.
I think it has a flaw, on the second example for Negative, the square is too small.
CORRECTION, I tried a small sample program and it does indeed leave only the small inner square.
Here's a picture I found:

import manifold3d as m
s1 = [(0.0,0.0), (20.0,0.0), (20.0,20.0), (0.0,20.0)]
s2 = [(5.0,5.0), (5.0,15.0), (15.0,15.0), (15.0,5.0)]
s3 = [(8.0,8.0), (8.0,12.0), (12.0,12.0), (12.0,8.0)]
print(winding(s1))
print(winding(s2))
print(winding(s3))
nested_s = m.CrossSection([s1, s2, s3], m.FillRule.Negative)
print(nested_s.to_polygons())

#import piecad
#piecad.save("/tmp/test.svg", piecad.Obj2d(nested_s))

[elalish]

That's an excellent picture of how winding numbers work; do you understand now? I'd be happy to put a link to it in our docs if you have one.

[briansturgill]

@elalish https://image.slidesharecdn.com/cg-surfacedetectionilluminationmodelssurface-renderingmodels-course9-111015013406-phpapp01/75/cg-opengl-surface-detectionilluminationrendering-modelscourse-9-9-2048.jpg?cb=1668135447
Don't know how permanent that like will be though (it was part of a slide deck).
Here's another source: https://www.flipcode.com/archives/article_tesselating_windingrules.gif

Here's a whole tutorial: https://what-when-how.com/opengl-programming-guide/polygon-tessellation-tessellators-and-quadrics-opengl-programming-part-2/

Oh, I am getting it now, I even understand why Negative did what it did (smallest square only).
I must say I find it very weird though.

Is it really true I could use EvenOdd anyway... I think I know why it was "broken"... I looked 2d at in SVG which
look at it as EvenOdd. I can't imagine trying to explain to the average maker how to make a polygon with a hole
using Positive.

[elalish]

First off, if you draw a valid polygon, it doesn't matter because all fill rules have the same result. The only time fill rule matters is when your polygon has winding numbers that are not just zero and one. Since CCW is positive, a CW poly inside of a CCW poly is always a hole. And yes, they can be nested in an alternating way, again with no difference from fill rule. That's why we apply fill rule on construction: it turns invalid polygons into valid ones that have only winding numbers zero and one.

[elalish]

Oh, except negative. That's a weird one, since that makes CW positive.

[briansturgill]

@elalish OK, I'm having good success with very nested polygons and some 2d booleans thrown in using EvenOdd.
It works fine with my SVG export. But I'm still a bit apprehensive that it's because I tend to think in terms of EvenOdd.
Clipper2 needs to know the FillRule for booleans and other clipping. Why?
Surely that means that the ops must sometimes produce different results for different FillRules?

[briansturgill]

@elalish The only time I know that paths (ignore winding) are different between EvenOdd and Positive is that you can have holes in holes and shapes in shapes in Positive. However, Clipper (wisely) collapses them. In other words, winding aside, paths in Clipper are Positive and EvenOdd. Thus, in some sense we get lucky here?