Incorrect triangulation of polygons with many holes

[TonyCrane]

I tried to use Text to write Chinese, but there were many problems.
For example, the simplest one is to write the word "回". But the result is this (contains unnecessary connections):

class TextBug(Scene):
    def construct(self):
        txt = Text("回", font="庞门正道标题体", height=FRAME_HEIGHT-1)
        self.add(txt)

I lowered its opacity and showed the point set and its indices. The result is this:

class TextBug(Scene):
    def construct(self):
        txt = Text("回", font="庞门正道标题体", height=FRAME_HEIGHT-1)
        txt.set_fill(opacity=0.3)
        self.add(txt)
        points = txt[0].get_points()
        ind = index_labels(points).set_color(PURPLE).set_stroke(width=1)
        self.add(ind)

The position and order of the point set are correct. So I suspect that there may be an error in the triangulation, so I displayed the inner triangles in the triangulation, and the result is this:

class TextBug(Scene):
    def construct(self):
        txt = Text("回", font="庞门正道标题体", height=FRAME_HEIGHT-1)
        txt.set_fill(opacity=0.3)
        self.add(txt)
        points = txt[0].get_points()
        ind = index_labels(points).set_color(PURPLE).set_stroke(width=1)
        self.add(ind)
        tri = txt[0].get_triangulation()
        tri_indices = tri[len(points):]
        a = tri_indices[0::3]
        b = tri_indices[1::3]
        c = tri_indices[2::3]
        for i, _ in enumerate(a):
            self.add(Polygon(points[a[i]], points[b[i]], points[c[i]],\
            stroke_color=WHITE, stroke_width=4, fill_color=ORANGE, fill_opacity=0.5))

Basically it is certain that there is a problem, but I don't know how to solve it.

---

In addition, this is the svg file of this Chinese character, you can use SVGMobject to test it.
d17bf5c77d8120cd.txt (change its extension to .svg, because GitHub does not support uploading svg files here)
And it this way, not only Text will have problems, but SVGMobject and even other mobjects may also have such problems.
So, @3b1b please take a look at this.

[3b1b]

The best solution to this would be to find a replacement for the current "earclip_triangulation" function. Unfortunately, this does not seem to work well for polygons with too many holes. I have previously looked for a more robust library in python, and if you can find one do let me know.

I can take a look at this example and try to fix it more directly, but I'm hesitant to make any promises.

[3b1b]

One solution here would be to find a more robust polygon triangulation library written in C, not python, and use that.

[TonyCrane]

I just tried another simpler Scene:

def get_tri(mob):
    tri = mob.get_triangulation()
    points = mob.get_points()
    tri_indices = tri[len(points):]
    a = tri_indices[0::3]
    b = tri_indices[1::3]
    c = tri_indices[2::3]
    tris = VGroup()
    for i, _ in enumerate(a):
        tris.add(Polygon(points[a[i]], points[b[i]], points[c[i]],\
        stroke_color=WHITE, stroke_width=4, fill_color=ORANGE, fill_opacity=0.5))
    return tris

def get_dots(mob):
    points = mob.get_points()
    dots = VGroup()
    for point in points:
        dots.add(SmallDot(point, color=PURPLE))
    return dots

class SquaresTri(Scene):
    def construct(self):
        squares = VGroup(*[
            Square(i) for i in np.arange(7, 0, -2)
        ])
        self.add(squares)
        square = VMobject()
        square.set_fill(opacity=0.3)
        for index, mob in enumerate(squares):
            if index % 2:
                square.append_points(mob.get_points()[::-1])
            else:
                square.append_points(mob.get_points())
        self.add(square)
        self.add(get_tri(square), get_dots(square))

The expected result is like (made in cairo-backend version):

But the code now give me this:

And if I try more squares, that is to change np.arange(7, 0, -2) to np.arange(7, 0, -1), it will give me this error:

Traceback (most recent call last):
  File "manim.py", line 5, in <module>
    manimlib.main()
  File "...\manimlib\__init__.py", line 12, in main
    scene.run()
  File "...\manimlib\scene\scene.py", line 76, in run
    self.tear_down()
  File "...\manimlib\scene\scene.py", line 95, in tear_down
    self.interact()
.........
  File "...\manimlib\mobject\types\vectorized_mobject.py", line 800, in get_triangulation      
    inner_tri_indices = inner_vert_indices[earclip_triangulation(inner_verts, rings)]
  File "...\manimlib\utils\space_ops.py", line 364, in earclip_triangulation
    j = int(norms[norms[:, 1].argmin()][0])
IndexError: too many indices for array: array is 1-dimensional, but 2 were indexed

So there may exactly be something wrong in earclip_triangulation.

[BenEcon]

This may be helpful: https://github.com/SebLague/Ear-Clipping-Triangulation/tree/master

Furthermore, I think earclip_triangulation itself can not resolve this issue. It is needed to tell how many holes in the object and the topology among the holes so that the vertices data can be correctly established. To include general Chinese characters, it is required to find a way to find the pattern about the topology of holes among different parts of each Chinese character.

For TonyCrane’s SquareTris example, the issue I think is function get_triangulation in vectorized_mobject.py. It treats the inner square with one hole as a convex polygon. Correctly, it should have 8 triangles, however the code gives 2 triangles.

[naveen521kk]

Am I wrong in saying https://trimsh.org/ would handle this?

[3b1b]

Okay, I think I may have fixed it with this commit. Let me know if that works for you.

[3b1b]

Am I wrong in saying https://trimsh.org/ would handle this?

Maybe I'm missing something, but it looks like trimesh is useful for working with and manipulating meshes of 3d objects once you already have them, but I'm not seeing where it would be useful for finding the triangulation of a 2d polygon with many holes.

[BenEcon]

Okay, I think I may have fixed it with this commit. Let me know if that works for you.

Great, it works now.

[TonyCrane]

The aforementioned SquaresTri scene has been able to run normally. And some Chinese can also be displayed normally:


But the "回" mentioned at the beginning and the svg file still cannot be displayed correctly:


I guess it’s because the points of the svg with the word "回" are concentrated first on the inner circle and then on the outer circle, causing the outer circle to cover the inner circle:

[3b1b]

Can you attach the relevant svg? When I render that character in other fonts it looks fine, but I don't currently have the font from the example above installed.

[TonyCrane]

Here: d17bf5c77d8120cd.txt (change its extension to .svg, because GitHub does not support uploading svg files here)
(I sent this svg at the front of this issue, but it may not be obvious)
I also tested other fonts and they all display normally.

[3b1b]

Okay, I'll look into it.

[3b1b]

Alright, I believe this change should actually fix it in a more robust way. It works on the svg you passed, and it seems to work on all the Chinese text I try, let me know how it looks @TonyCrane.

[TonyCrane]

That's great! And I also tried some other characters and even a whole passage, they all look good.

[TonyCrane]

But there may be still a bug. When I tried to run the SquaresTri Scene, it can't display properly, which can display correctly before this changes.

class SquaresTri(Scene):
    def construct(self):
        squares = VGroup(*[
            Square(i) for i in np.arange(7, 0, -1)
        ])
        self.add(squares)
        square = VMobject()
        square.set_fill(opacity=0.3)
        for index, mob in enumerate(squares):
            if index % 2:
                square.append_points(mob.get_points()[::-1])
            else:
                square.append_points(mob.get_points())
        self.add(square)

[3b1b]

Fascinating. Unless I am mistaken, I believe this is an error with the mapbox_earcut library, and not with the wrapper I wrote around it.

In some sense, this is an "unstable" exception. What I mean that is that if you perturb the squares slightly, e.g.

squares = VGroup(*[ Square(i).shift(0.1 * i * RIGHT) for i in np.arange(7, 0, -1) ])
then it works properly. Also, if you call square.insert_n_curves(10), it will render correctly.

The wrapper is just there to turn a polygon with holes into a continuous polygon by connecting the holes, analogous to how the limit of a keyhole contour is a discontinuous contour with a hole in it. The way it connects up indices in the perturbed example is the same as how it does in the faulty centered example, which leads me to believe it's not an issue with that connecting process. From there, it's up to the mapbox_earcut library to fill in the single continuous polygon correctly.

Perhaps this means the ultimate solution really does lie with finding a better triangulation library.

If it's alright, I'll go ahead and close this issue since it seems like the exception involving holes within holes within holes may be pathological enough not to come up in practice. But of course, feel free to reopen it if it does.

[BenEcon]

Fascinating. Unless I am mistaken, I believe this is an error with the mapbox_earcut library, and not with the wrapper I wrote around it.

In some sense, this is an "unstable" exception. What I mean that is that if you perturb the squares slightly, e.g.

squares = VGroup(*[ Square(i).shift(0.1 * i * RIGHT) for i in np.arange(7, 0, -1) ])
then it works properly. Also, if you call square.insert_n_curves(10), it will render correctly.

The wrapper is just there to turn a polygon with holes into a continuous polygon by connecting the holes, analogous to how the limit of a keyhole contour is a discontinuous contour with a hole in it. The way it connects up indices in the perturbed example is the same as how it does in the faulty centered example, which leads me to believe it's not an issue with that connecting process. From there, it's up to the mapbox_earcut library to fill in the single continuous polygon correctly.

Perhaps this means the ultimate solution really does lie with finding a better triangulation library.

If it's alright, I'll go ahead and close this issue since it seems like the exception involving holes within holes within holes may be pathological enough not to come up in practice. But of course, feel free to reopen it if it does.

The Chinese character shown in svg is not correctly displayed.
54bc7458065788e9.txt
Change txt to svg.

From previous codes, it is perfectly displayed.

ChineseCh.mp4

[3b1b]

Okay, maybe not as pathological as I suspect. I'll look into if this can be fixed without changing the triangulation library, otherwise, that's probably what we'll need to do.

[BenEcon]

Okay, maybe not as pathological as I suspect. I'll look into if this can be fixed without changing the triangulation library, otherwise, that's probably what we'll need to do.

You offered another two versions about this issue, they all work. But this one, it fails.

[3b1b]

Man, this is getting hackier by the minute. I've added one more tweak, which seems to fix this character and the others I try, but clearly, the game of small tweaks to fix edge cases suggests a deeper fix may still be needed.

[BenEcon]

Man, this is getting hackier by the minute. I've added one more tweak, which seems to fix this character and the others I try, but clearly, the game of small tweaks to fix edge cases suggests a deeper fix may still be needed.

Great, at least for 99.9% scenarios, it is enough. If possible, I think it is a great idea to have a video lecture about earcut algorithm and how to cut and paste different parts by some examples like the aforementioned to work with earcut algorithm, I think it will be interesting and very useful.