boolean -- Boolean cut/intersect/stitch meshes

This modules provide boolean operations for all kind of meshes.

Strictly speaking, boolean operations are operations on mathematically defined sets. In a n-dimensinal space it applies to subsets of point of the same dimension (volumes in 3D, surfaces in 2D). Here, volumes are defined by their exterior envelope (a Mesh) and surfaces by their contour (Web). So the boolean operation consist of intersecting the envelopes and contours and decide which cutted parts to keep.

This relies on a new intersection algorithm named syandana. It finds candidates for intersections using a spacial hashing of triangles over a voxel (see madcad.hashing). This is solving the problem of putting triangles in an octree. Also to avoid the increasing complexity of the operation with flat planes divided in multiple parallel triangles, the algorithm is implemented with a detection of ngons.

The syandana algorithm achieves intersections of meshes in nearly O(n) where usual methods are O(n**2)

After intersection, the selection of surface sides to keep or not is done through a propagation.

Note

Web boolean operations theoretically means something only in a 2d space, and it takes place in a 3d space here, causing many situations where a web portion can be both inside and outside the contour. The algorithm here works even with meshes that are not planar at all. but it always assumes that the web you give it can be processed consistently as if it was.

Note

Mesh boolean operation is relying on the surface outer normal to decide what is exterior and interior. It's always a local decision (ie. a decision made at the intersection), So the meshes must be well oriented.

Web boolean operations on the other hand CANNOT be local due to the 3d space it's laying in. (a higher dimension than the surface it's theoreticall meant to outline). So it may sometimes not behave the way you expect it. To solve ambiguities of interior and exterior, the most outer part of first mesh argument is always considered to belong to the exterior. And the information is propagated through the web.

Most common

pierce(m, ref, side=False, prec=None)

Cut a web/mesh and remove its parts considered inside the ref shape

Overloads:

    pierce(Mesh, Mesh) -> Mesh
    pierce(Web, Web) -> Web
    pierce(Web, Mesh) -> Web

side decides which part of each mesh to keep

• False keeps the exterior part (part exclusive to the other mesh)
• True keeps the interior part (the common part)

Source code in madcad/boolean.py

def pierce(m, ref, side=False, prec=None):
	''' Cut a web/mesh and remove its parts considered inside the `ref` shape

		Overloads:

			pierce(Mesh, Mesh) -> Mesh
			pierce(Web, Web) -> Web
			pierce(Web, Mesh) -> Web

		`side` decides which part of each mesh to keep

		 - False keeps the exterior part (part exclusive to the other mesh)
		 - True keeps the interior part (the common part)
	'''
	op = pierce_ops.get((type(m), type(ref)))
	if not op:
		raise TypeError('pierce is not possible between {} and {}'.format(type(m).__name__, type(ref).__name__))
	return op(m, ref, side, prec)

Between Web (The result is the white part, the green part is the ref parameter)

rect = web(
    wire([vec3(-w, -h, 0), vec3(w, -h, 0), vec3(w, h, 0), vec3(-w, h, 0)])
    .close()
    .segmented()
)
hole = web(Circle((O, Z), 1.5))

result = pierce(rect, hole)

Between Web and Mesh:

rect = web(
    wire([vec3(-w, -h, 0), vec3(w, -h, 0), vec3(w, h, 0), vec3(-w, h, 0)])
    .close()
    .segmented()
)
hole = extrusion(Circle((O, Z), 1.5), 4 * Z, alignment=0.5)

result = pierce(rect, hole)

Between Mesh:

rect = flatsurface(
    wire([vec3(-w, -h, 0), vec3(w, -h, 0), vec3(w, h, 0), vec3(-w, h, 0)])
)
rect = rect.transform(Z) + rect.transform(-Z).flip()
hole = extrusion(flatsurface(Circle((O, Z), 1.5)).flip(), 4 * Z, alignment=0.5)

result = pierce(rect, hole)

boolean(a, b, sides=(False, True), prec=None)

Cut two web/mesh and keep its interior or exterior parts

Overloads:

    boolean(Mesh, Mesh) -> Mesh
    boolean(Web, Web) -> Web

sides decides which part of each mesh to keep

• False keeps the exterior part (part exclusive to the other mesh)
• True keeps the common part

Source code in madcad/boolean.py

def boolean(a, b, sides=(False,True), prec=None):
	''' Cut two web/mesh and keep its interior or exterior parts

		Overloads:

			boolean(Mesh, Mesh) -> Mesh
			boolean(Web, Web) -> Web

		`sides` decides which part of each mesh to keep

		 - False keeps the exterior part (part exclusive to the other mesh)
		 - True keeps the common part
	'''
	op = boolean_ops.get((type(a), type(b)))
	if not op:
		raise TypeError('boolean is not possible between {} and {}'.format(type(a), type(b)))
	return op(a, b, sides, prec)

Between Web:

w, h = 2, 1
a = web(
    wire([vec3(-w, -h, 0), vec3(w, -h, 0), vec3(w, h, 0), vec3(-w, h, 0)])
    .close()
    .segmented()
)
b = web(Circle((O, Z), 1.5))

result = boolean(a, b, (False, False))

Between Mesh:

w, h = 3, 2
rect = flatsurface(
    wire([vec3(-w, -h, 0), vec3(w, -h, 0), vec3(w, h, 0), vec3(-w, h, 0)])
)
a = rect.transform(Z) + rect.transform(-Z).flip()
b = extrusion(flatsurface(Circle((O, Z), 1.5)).flip(), 4 * Z, alignment=0.5)

result = boolean(a, b, (False, False))

Those are shortcuts for boolean:

union(a, b)

Return a mesh for the union of the volumes. It is a boolean with selector (False,False)

Source code in madcad/boolean.py

def union(a, b) -> Mesh:
	''' Return a mesh for the union of the volumes.
		It is a boolean with selector `(False,False)`
	'''
	return boolean(a,b, (False,False))

difference(a, b)

Return a mesh for the volume of a less the common volume with b It is a boolean with selector (False, True)

Source code in madcad/boolean.py

def difference(a, b) -> Mesh:
	''' Return a mesh for the volume of `a` less the common volume with `b`
		It is a boolean with selector `(False, True)`
	'''
	return boolean(a,b, (False,True))

intersection(a, b)

Return a mesh for the common volume. It is a boolean with selector (True, True)

Source code in madcad/boolean.py

def intersection(a, b) -> Mesh:
	''' Return a mesh for the common volume.
		It is a boolean with selector `(True, True)`
	'''
	return boolean(a,b, (True,True))

More advanced

cut_web(w1, ref, prec=None)

Cut the web edges at their intersectsions with the ref web

Return

(cutted, frontier)

    :cutted(Web):   is `w1` with the edges cutted, but representing the same lines as before
    :frontier(Wire): is a Web where edges are the intersection edges, and whose groups are the causing faces in `ref`

Source code in madcad/boolean.py

def cut_web(w1: Web, ref: Web, prec=None) -> '(Web, Wire)':
	''' Cut the web edges at their intersectsions with the `ref` web

		Return:
			`(cutted, frontier)`

				:cutted(Web):	is `w1` with the edges cutted, but representing the same lines as before
				:frontier(Wire): is a Web where edges are the intersection edges, and whose groups are the causing faces in `ref`
		'''
	if not prec:  prec = w1.precision()
	frontier = Wire(w1.points, [], [], groups=ref.edges)

	# topology informations for optimization
	points = PointSet(prec, manage=w1.points)
	prox = PositionMap(meshcellsize(ref))
	for e in range(len(ref.edges)):
		prox.add(ref.edgepoints(e), e)
	conn = connpe(w1.edges)

	mn = Web(w1.points, groups=w1.groups)  # resulting web
	for e1 in range(len(w1.edges)):
		processed = False  # flag enabled when the edge is reconstructed

		# collect edges in ref that can have intersection with e1
		close = set( prox.get(w1.edgepoints(e1)) )
		if close:
			# no need to get the straight zone around because on the case of an edge, it will not grow in complexity more than the number of cut segments
			# and an edge is easy to reweb after multiple intersections
			# compute intersections
			segts = {}
			for e2 in close:
				intersect = intersect_edges(w1.edgepoints(e1), ref.edgepoints(e2), prec)
				if intersect:
					seg = points.add(intersect)
					segts.setdefault(seg, e2)

			# reconstruct the geometries
			if segts:
				e = w1.edges[e1]
				# reweb the cutted edge
				direction = w1.points[e[1]] - w1.points[e[0]]
				sorted_segts = sorted(segts.items(), key=lambda s: dot(w1.points[s[0]], direction))
				# append the rewebed edge in association with the original track
				frontier += Wire(
						w1.points,
						map(itemgetter(0), sorted_segts),
						map(itemgetter(1), sorted_segts),
						ref.edges,
						)

				suite = list(map(itemgetter(0), sorted_segts))
				if suite[0] != e[0]:	suite.insert(0, e[0])
				if suite[-1] != e[-1]:	suite.append(e[-1])
				mn += web(Wire(
						w1.points,
						suite,
						[w1.tracks[e1]] * len(suite),
						w1.groups,
						))
				processed = True

		# keep the non intersected faces as is
		if not processed:
			mn.edges.append(w1.edges[e1])
			mn.tracks.append(w1.tracks[e1])

	mn.check()
	return mn, frontier

cut_web_mesh(w1, ref, prec=None)

Cut the web inplace at its intersections with the ref web.

Return

(cutted, frontier)

Source code in madcad/boolean.py

def cut_web_mesh(w1: Web, ref: Mesh, prec=None) -> '(Web, Wire)':
	''' Cut the web inplace at its intersections with the `ref` web.

	Return:
		`(cutted, frontier)`
	'''
	if not prec:  prec = w1.precision()
	frontier = Wire(w1.points, [], [], groups=ref.faces)

	# topology informations for optimization
	points = PointSet(prec, manage=w1.points)
	prox = PositionMap(meshcellsize(ref))
	for f in range(len(ref.faces)):
		prox.add(ref.facepoints(f), f)
	conn = connpe(w1.edges)

	mn = Web(w1.points, groups=w1.groups)  # resulting web
	for e1 in range(len(w1.edges)):
		processed = False	# flag enabled when the edge is reconstructed

		# collect edges in ref that can have intersection with e1
		close = set(prox.get(w1.edgepoints(e1)))
		if close:

			# no need to get the straight zone around because on the case of an edge, it will not grow in complexity more than the number of cut segments
			# and an edge is easy to remesh after multiple intersections
			# compute intersections
			segts = {}
			for f2 in close:
				intersect = intersect_edge_face(w1.edgepoints(e1), ref.facepoints(f2), prec)
				if intersect:
					seg = points.add(intersect)
					segts.setdefault(seg, f2)

			# reconstruct the geometries
			if segts:
				e = w1.edges[e1]
				# reweb the cutted edge
				direction = w1.points[e[1]] - w1.points[e[0]]
				sorted_segts = sorted(segts.items(), key=lambda s: dot(w1.points[s[0]], direction))
				# append the rewebed edge in association with the original track
				frontier += Wire(
						w1.points,
						list(map(itemgetter(0), sorted_segts)),
						list(map(itemgetter(1), sorted_segts)),
						ref.faces,
						)
				mn += web(Wire(
						w1.points,
						[e[0]] + list(map(itemgetter(0), sorted_segts)) + [e[1]],
						[w1.tracks[e1]] * (len(sorted_segts)+2),
						w1.groups,
						))
				processed = True

		# keep the non intersected faces as is
		if not processed:
			mn.edges.append(w1.edges[e1])
			mn.tracks.append(w1.tracks[e1])

	return mn, frontier

cut_mesh(m1, m2, prec=None)

Cut m1 faces at their intersections with m2.

Return:

    `(cutted, frontier)`

            :cutted(Mesh):  is `m1` with the faces cutted, but representing the same surface as before
            :frontier(Web): is a Web where edges are the intersection edges, and whose groups are the causing faces in `m2`

Returning the intersection edges in m1 and associated m2 faces. The algorithm is using ngon intersections and retriangulation, in order to avoid infinite loops and intermediate triangles.

Source code in madcad/boolean.py

def cut_mesh(m1, m2, prec=None) -> '(Mesh, Web)':
	''' Cut m1 faces at their intersections with m2.

	Return:

		`(cutted, frontier)`

			:cutted(Mesh):	is `m1` with the faces cutted, but representing the same surface as before
			:frontier(Web): is a Web where edges are the intersection edges, and whose groups are the causing faces in `m2`

	Returning the intersection edges in m1 and associated m2 faces.
	The algorithm is using ngon intersections and retriangulation, in order to avoid infinite loops and intermediate triangles.
	'''
	if not prec:	prec = m1.precision()
	mn, frontier = core.cut_surface(m1, m2, prec)
	frontier.groups = m2.faces

	return mn, frontier