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.