Boolean operations failing in case of overlapping faces

[jonmendenhall]

I was playing around with this for some CAD modelling in python and seem to have hit a problem with boolean operations on certain shapes.

Following a process similar to what I would do in Inventor, I generated a mesh to be the main part, and a smaller mesh that will be cut from it. The smaller mesh shares many faces with the larger one though so I think that might be causing some issues.

The shape is meant to be a rail with a slot cut out in the bottom right of the profile:

Any boolean operations with both of these shapes fails with the following error message: madcad.triangulation.TriangulationError: ('no more feasible triangles (algorithm failure or bad input outline)', [16, 17, 15])

I've tried the same idea with two bricks in the same configuration (larger one, and smaller one in bottom right touching same faces cutout) and it works fine so I'm not sure what's wrong with these meshes for them to be the problem (if they are).

I've included the meshes as .stl files in this zip so the meshes can be checked for errors (body is the larger one, and cut is the one intended to be subtracted)

meshes.zip

Any help would be appreciated!

If it is of any value, I construct the meshes by the following steps:

1. generate lists of left and right points
2. create outline with counter clockwise winding
3. extrude outline up on Z axis and add bottom and top faces (bottom_normal=-Z, top_normal=Z)
4. mergeclose (unnecessary?)

[jimy-byerley]

Hello and welcome here @jonmendenhall

You meshes are perfectly generated and there is nothing wrong from it. You issue seems to come from a common issue with most mesh boolean operations: The algorithm doesn't know which face to keep/remove when there is overlaping faces between the solids (this is because mathematically, both are interior and exterior at the same time, so there is an ambiguity) The current madcad algorithm doesn't fix that ambiguity yet (I have to work it one day :sweat_smile: ) You attempt to do the same kind of operation on bricks might have worked by chance.

So, the only short term solution is to intrudice a little gap between the overlapping faces to make the faces not overlapping anymore. An very smal translation is sufficient in your case:

import madcad as mc

body = mc.read('meshes/body.stl')
body = mc.segmentation(body.finish())  # this is reworking the stl imported content because stl files only provide disconnected triangles, and boolean operations work on connected ones
cut = mc.read('meshes/cut.stl')
cut = mc.segmentation(cut.finish())

r = mc.difference(
      body, 
      cut.transform(0.001*vec3(1,-1,-1)),  # ugly translation trick
      )

And I get what I think is your expected result:

Let me know it it works for you !

Just as a little piece of advice:

• your extrude_volume can rely on the ability of madcad.extrusion to work with surfaces directly. If I correctly understood its purpose

  extrusion(vec, flatsurface(outline, bottom_normal))

• In order to create you left and right segments, you can directly create a Wire

  outline = wire(lefts) + wire(rights).flip())
  # eventually convert it to Web
  outline = web(wire(lefts) + wire(rights).flip()))

[jonmendenhall]

Ahh gotcha thanks! I figured that small translation / scaling was the only solution as of now.

It seems like mesh boolean operations should be able to handle removing the overlapping area of faces without any ambiguity. Considering the cut faces are being subtracted, the faces of body should have the overlapping portion removed but I assume that increases the complexity of the algorithm significantly when it tries to match that newly boolean'ed set of triangles back to the rest of the mesh.

[jimy-byerley]

Yes, making the boolean operation resilient to overlapping faces, or even deterministic over which of them is to be kept, would be a huge improvement :) But when I finished to implement the working version of the current version, I needed some fresh air ... and time meet the subtle bugs my unit tests were not showing. To I delayed improvements, and had many fancy ideas to work on since ;)

I will try to look into it in the coming months I cannot say yet there is absolutely no way to fix those ambiguities without increasing complexity.

[jimy-byerley]

This issue will stay opened until I find a solution or decide the solution cost is unacceptable

[jonmendenhall]

You've done a great job with this so far! It's really nice that this exists in Python, but isn't quite what I need for my application... now I'm controlling Autodesk Inventor via python to generate the models I need.

I'm not sure when (if ever) there will be a full B-Rep system in python, but if that ever comes and has acceptable performance that would be awesome!

[jimy-byerley]

Well at least there is some OpenCascade wrappers:

• pyocct
• freecad

But I find them ways too verbose to build geometries only from scripts

[GlennWSo]

Yes, making the boolean operation resilient to overlapping faces, or even deterministic over which of them is to be kept, would be a huge improvement :) But when I finished to implement the working version of the current version, I needed some fresh air ... and time meet the subtle bugs my unit tests were not showing. To I delayed improvements, and had many fancy ideas to work on since ;)

I will try to look into it in the coming months I cannot say yet there is absolutely no way to fix those ambiguities without increasing complexity.

Robust boolean operations on geometries with coplanar faces is non trivial. And making the boolean operations robust in this case may come at performance cost.

Take Blender for example:

It implements 2 solver algorithms one faster and the other is exact. And leaves it up to the user to decide what they want.

[jimy-byerley]

Blender improved their boolean operations since the time I designed the boolean operations in madcad :thinking: I should take a fresh look at their code. I feel so stupid still working with blender 2.82 when 3 is out On madcad, we should generally focus on exact solutions whenever possible