boolean.cut_mesh fails with TriangulationError

[WizardUli]

import numpy as np
from madcad import *

base = brick(width=vec3(236, 170, 2))
hole_positions = [vec3(x, y, 0) for x in np.linspace(-225 / 2, 225 / 2, 5) for y in [-155 / 2, 155 / 2]]

hole_cutouts = mesh.mesh([cylinder(bottom=pos - 50 * Z, top=pos + 50 * Z, radius=3 / 2) for pos in hole_positions])
cable_cutout = brick(width=vec3(5, 20, 50), center=vec3(53.5, 0, 0))

part0 = difference(base, hole_cutouts)
part1 = difference(part0, cable_cutout)
show([part0, cable_cutout], display_wire=True)
# show([part1], display_wire=True)

fails with

Traceback (most recent call last):
  File "/home/michal/Projects/Cyberdeck/xxx.py", line 11, in <module>
    part1 = difference(part0, cable_cutout)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/boolean.py", line 638, in difference
    return boolean(a,b, (False,True))
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/boolean.py", line 620, in boolean
    return op(a, b, sides, prec)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/boolean.py", line 254, in boolean_mesh
    mc1 = pierce_mesh(m1, m2, sides[0], prec)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/boolean.py", line 166, in pierce_mesh
    m1, frontier = cut_mesh(m1, m2, prec)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/boolean.py", line 147, in cut_mesh
    flat = triangulation.triangulation_closest(segts, normal, prec)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/triangulation.py", line 694, in triangulation_closest
    result += triangulation_outline(loop, z, prec)
  File "/nix/store/x6y0mcbxr1jrx6kh3spks0yxf44rfmp1-python3-3.10.11-env/lib/python3.10/site-packages/madcad/triangulation.py", line 232, in triangulation_outline
    raise TriangulationError("no more feasible triangles (algorithm failure or bad input outline)", [outline.indices[i] for i in hole])
madcad.triangulation.TriangulationError: ('no more feasible triangles (algorithm failure or bad input outline)', [571, 628, 289, 274, 275, 5, 1931, 1929, 1950, 1952, 1931, 5, 159])

I'm on revision 22437d1 but I also reproduced it on v0.15.1.

[WizardUli]

I don't understand yet how all the pymadcad internals works but I think I've found something which may be of interest.

When I display the argument which crashes the triangulation_outline function I see a self-intersecting wire (near the top left hole as seen on picture):

However if I move the cutting brick a little to the left (e.g. when instead of center=vec3(53.5, 0, 0) I use center=vec3(43.5, 0, 0)) then I see no self-intersection and the whole boolean operation completes OK:

[jimy-byerley]

Yes, I observed the same
I think the issue comes from madcad.triangulation.line_bridges which is responsible for linking holes to outlines in faces

[jimy-byerley]

I can reproduce it even without the boolean operation, just from user-made webs:

base = parallelogram(236*X, 170*Y, align=vec2(0.5), fill=False)
hole_positions = [vec3(x, y, 0) 
	for x in linrange(-225 / 2, 225 / 2, div=3) 
	for y in [-155 / 2, 155 / 2]]
hole_cutouts = web([
		Circle(Axis(pos,Z), radius=3 / 2) 
		for pos in hole_positions]).flip()
cable_cutouts = parallelogram(5*X, 20*Y, origin=53.5*X, align=vec2(0.5), fill=False).flip()
#f = flatsurface(web([base, hole_cutouts]))
f = flatsurface(web([base, hole_cutouts, cable_cutouts]))

So now we are sure it is not coming from the boolean operation itself but only the triangulation step

[jimy-byerley]

Ok I got the problem:
The algorithm I made for line_bridges has a failure in case it is matching a point to a long edge

On the above picture we can see the current algorithm is creating to link unconnected components of a wire before triangulation. The edge crossing a circle is due to failure.

So ... I will work on a new algorithm for this. This may take some time before I have it ready so this issue will have to wait for it ...

[WizardUli]

Hello again. Any news on this? Since I'm hitting this issue with anything I try to do and any workaround I devise just delays the problem a few steps, I was thinking I could look into it myself. I guess what am I asking is: Have you been planning to look at it sometime soon?

[jimy-byerley]

Hello, to be honest I had no time in past month. I have slightly more time now.
So I only took some time few weeks ago and started something on branch triangulation, but it is not ready yet.

Of course you can look into it if you want, but be warned that the constraints for the new triangulation algorithm are demanding:

• must be faster than O(n*k) (with n the number of vertices, k the number of non-convex vertices
• must deal with holes, and non-connex outlines
• must deal with straight but subdivided edges (aka. degenerated edges)
• must deal with coincident points
• must be robust to floating points precision issues
• must be inexpensive for a small number of vertices
• must accept an unstructured list of connected edges as input

So to summarize it must work in every situation the current one is working, and this time with no side case (side case like we have in this topic)