dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / modeling / boolean_result.lucb
## A boolean's result (boolean.lucb steps 6 and 7): the pieces the
## operation keeps, merged where they lie on one surface, written as a new
## B-rep; an edge not used exactly twice, once each way, is an error.
## Classify each connected block by its piece with the fewest boundary
## uses first: a point well inside a piece costs in its boundary, and one
## piece's class serves the block (a plate's face with a hundred holes is
## then never the one asked).
func classify_smallest(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], others: Others*) -> !:
let count = pieces.piece_count()
var smallest = Growing[i64]()
defer smallest.close()
var sizes = Growing[usize]()
defer sizes.close()
try smallest.fill(count, -1)
try sizes.fill(count, 0)
for p in 0..<count:
var size: usize = 0
for c in pieces.piece_cycles(p): size += pieces.cycle(c).length
sizes.items[p] = size
let root = union_root(others.block.items, p)
let best = smallest.items[root]
if best < 0 or size < sizes.items[(usize)best]: smallest.items[root] = (i64)p
for root in 0..<count:
let p = smallest.items[root]
if p >= 0: _ = try classify(work, traced, piece_face[(usize)p], pieces, (usize)p, others)
## The refusal of a result whose edges are not each used twice.
let not_closed = "the result is not a closed solid (some edges are not shared by two faces); this operation is not supported for these shapes yet"
## The refusal of a result that is not a manifold solid.
let non_manifold = "the result would be non-manifold: the bodies touch along an edge or a face, where four faces meet; non-manifold bodies are not supported yet"
## Steps 4 to 7: split, classify, select and write.
func assemble(work: Work*, op: i64, others: Others*) -> interop.Reference[CadModel]!:
let w = &work.w
var traced = try final_shape(work)
defer traced.close()
var pieces = try new_pieces()
defer pieces.close()
var piece_face = Growing[usize]()
defer piece_face.close()
# Each piece's name: its face's, or merged faces' names together.
var piece_name = Growing[i64]()
defer piece_name.close()
try face_pieces(work, &traced, w.faces.count, &pieces, &piece_face, &piece_name)
# Classify and select.
try find_blocks(work, &traced, &pieces, piece_face.view(), others)
try classify_smallest(work, &traced, &pieces, piece_face.view(), others)
var keep = Growing[bool]()
defer keep.close()
var turn = Growing[bool]()
defer turn.close()
for p in 0..<pieces.piece_count():
let f = piece_face.items[p]
let class = try classify(work, &traced, f, &pieces, p, others)
let first = work.is_a(f)
var take = false
var flip = false
if op == op_union:
take = class == class_out or (class == class_same and first)
elif op == op_subtract:
if first: take = class == class_out or class == class_opposite
else:
take = class == class_in
flip = true
else:
take = class == class_in or (class == class_same and first)
try keep.push(take)
try turn.push(flip)
# Faces touching along a line no section follows (contact.lucb), both
# kept: the bodies would be pinched together along it.
for touch in work.contacts.view():
var kept_a = false
var kept_b = false
for p in 0..<pieces.piece_count():
if not keep.items[p]: continue
kept_a = kept_a or piece_face.items[p] == touch.fa
kept_b = kept_b or piece_face.items[p] == touch.fb
if kept_a and kept_b: error(invalid, non_manifold)
try merge_pieces(work, &traced, &pieces, &piece_face, &piece_name, &keep, &turn)
# Every edge used twice, but a face passing through one of them (before
# the zones' seams, which the traced shape does not hold).
if (try pieces_closed(work, &pieces, keep.view(), turn.view())) and (try touches_itself(work, &traced, &pieces, piece_face.view(), keep.view())): error(invalid, non_manifold)
# Faces touching along a section (from outside, joined; one inside the
# other at its face, subtracted) whose kept pieces both reach it: the
# merged faces no longer share the section's edge, and the result
# closes, but it is pinched to nothing along it.
if try pinched(work, &traced, &pieces, piece_face.view(), keep.view(), op): error(invalid, non_manifold)
try seam_zones(work, &traced, &pieces, piece_face.view(), keep.view())
# A result that does not close where the bodies touch along a curve
# (from outside, joined; one inside the other at its face, subtracted)
# leaves edges four faces meet at: named so. (A fillet's tool touches
# the body the same way and closes.)
var touching = false
for touch in work.tangencies.view():
touching = touching or (op == op_union and not touch.same) or (op == op_subtract and touch.same)
return write_result(work, &pieces, piece_face.view(), piece_name.view(), keep.view(), turn.view()) catch failure:
if touching and failure.code == invalid and failure.message.compare(not_closed) == 0: error(invalid, non_manifold)
error(failure.code, failure.message)
## Step 4: the first `faces` faces of the work shape split along the new
## edges into `pieces` on `traced`, each piece's face and name noted.
func face_pieces(work: Work*, traced: const Shape*, faces: usize, pieces: Pieces*, piece_face: Growing[usize]*, piece_name: Growing[i64]*) -> !:
let w = &work.w
var halves = Growing[HalfEdge]()
defer halves.close()
# The faces no new edge crosses and no cut splits keep their loops as
# they are: one piece each, with no tracing (drilling the hundredth
# hole in a plate leaves the other ninety-nine holes' walls whole).
var touched = Growing[bool]()
defer touched.close()
try touched.fill(faces, false)
for section in work.sections.view():
if section.fa >= 0 and (usize)section.fa < faces: touched.items[(usize)section.fa] = true
if section.fb >= 0 and (usize)section.fb < faces: touched.items[(usize)section.fb] = true
for mark in work.imprints.view():
if mark.face < faces: touched.items[mark.face] = true
for f in 0..<faces:
if not touched.items[f] and not (try split_edges(work, f)):
try whole_piece(work, f, pieces)
try piece_face.push(f)
try piece_name.push(w.faces.items[f].name)
continue
halves.clear()
# The boundary, piece by piece, the way the face uses each edge.
for use in w.face_uses(f):
let e = edge_index(use)
let first = work.piece_starts.items[e]
let last = work.piece_starts.items[e + 1]
for k in 0..<last - first:
let id = work.piece_ids.items[first + k if use > 0 else last - 1 - k]
let forward = (id > 0) == (use > 0)
try halves.push(HalfEdge((id if id > 0 else -id) - 1, forward))
let boundary = halves.count
# New edges across it, both ways, unless already on its boundary.
for at in 0..<work.sections.count:
let section = work.sections.items[at]
if section.fa != (i64)f and section.fb != (i64)f: continue
try add_both(&halves, boundary, work.section_ids.items[at])
for mark in work.imprints.view():
if mark.face != f: continue
let first = work.piece_starts.items[mark.edge]
let last = work.piece_starts.items[mark.edge + 1]
for k in first..<last:
let id = work.piece_ids.items[k]
let final = work.finals.items[edge_index(id)]
let middle = try w.at(final.carrier, (final.t0 + final.t1) * 0.5)
if try face_contains(w, f, middle, work.tol) == inside_face: try add_both(&halves, boundary, id)
let before = pieces.piece_count()
try split_face(traced, f, halves.view(), try face_pole(w, f), pieces)
for _ in before..<pieces.piece_count():
try piece_face.push(f)
try piece_name.push(w.faces.items[f].name)
## Whether a cut splits one of face `f`'s edges into pieces.
func split_edges(work: const Work*, f: usize) -> bool!:
for use in work.w.face_uses(f):
let e = edge_index(use)
if work.piece_starts.items[e + 1] - work.piece_starts.items[e] != 1: return true
return false
## Face `f`, whose edges are each one piece, as one piece of its loops in
## their order (its outer loop first).
func whole_piece(work: const Work*, f: usize, pieces: Pieces*) -> !:
let w = &work.w
let uses = w.face_uses(f)
var at: usize = 0
for size in w.face_sizes(f):
for k in 0..<(usize)size:
let use = uses[at + k]
let id = work.piece_ids.items[work.piece_starts.items[edge_index(use)]]
let forward = (id > 0) == (use > 0)
let edge = (id if id > 0 else -id) - 1
try pieces.uses.push((edge + 1) * (1 if forward else -1))
try pieces.pieces.push(pieces.cycle_starts.count - 1)
try pieces.cycle_starts.push(pieces.uses.count)
at += (usize)size
try pieces.piece_starts.push(pieces.pieces.count)
## Add final edge `id` (signed) to `halves` both ways, unless one of the
## first `boundary` halves is it.
func add_both(halves: Growing[HalfEdge]*, boundary: usize, id: i64) -> !:
let edge = (id if id > 0 else -id) - 1
for at in 0..<boundary:
if halves.items[at].edge == edge: return
for at in boundary..<halves.count:
if halves.items[at].edge == edge: return
try halves.push(HalfEdge(edge, true))
try halves.push(HalfEdge(edge, false))
## The shape faces are split in: the final edges over the merged
## vertices, with the work shape's carriers, surfaces and faces (their
## surfaces and senses; their loops are what is being split).
func final_shape(work: Work*) -> Shape!:
var s = empty_shape(work.w.tolerances, work.tol)
errdefer s.close()
for p in work.vertices.view(): try s.points.push(p)
for c in work.w.carriers.view(): try s.carriers.push(c)
for sp in work.w.splines.view(): try s.splines.push(sp)
for p in work.w.spline_points.view(): try s.spline_points.push(p)
for x in work.w.spline_weights.view(): try s.spline_weights.push(x)
for k in work.w.spline_knots.view(): try s.spline_knots.push(k)
for e in work.finals.view(): try s.edges.push(e)
for su in work.w.surfaces.view():
try s.surfaces.push(try Surface(su.kind, su.origin, su.x, su.z, su.radius, su.angle, su.points, su.weights, su.ku, su.kv, su.nu, su.nv, su.du, su.dv))
for face in work.w.faces.view():
try s.faces.push(ShapeFace(face.surface, face.sense, 0, 0, 0, 0))
return s
## Step 7: the kept pieces as a new B-rep, which must be closed.
## A final edge cut from a tolerant edge (Stitch's) keeps its precision.
func write_result(work: Work*, pieces: const Pieces*, piece_face: const usize[], piece_name: const i64[], keep: const bool[], turn: const bool[]) -> interop.Reference[CadModel]!:
var slack = Growing[f64]()
defer slack.close()
try slack.fill(work.finals.count, 0.0)
for e in 0..<work.w.edges.count:
let precision = work.w.edge_slack_of(e)
if precision <= 0.0 or e + 1 >= work.piece_starts.count: continue
for at in work.piece_starts.items[e]..<work.piece_starts.items[e + 1]:
let id = (usize)(edge_index(work.piece_ids.items[at]))
slack.items[id] = math.max(slack.items[id], precision)
# A traced section's edge keeps the distance it was measured to stray
# from its faces (write_pieces records it when over the tolerance).
for at in 0..<work.sections.count:
let section = work.sections.items[at]
if section.precision <= 0.0: continue
let id = (usize)edge_index(work.section_ids.items[at])
slack.items[id] = math.max(slack.items[id], section.precision * 1.01)
return try write_pieces(work, pieces, piece_face, piece_name, keep, turn, true, 0.0, 0.0, slack.view())
## The kept pieces as a new B-rep: with `closed`, every edge must be used
## twice, once each way (a solid); without, an edge used once is an open
## body's boundary (Trim's sheets). An edge or vertex lying off by more
## than the project's fit tolerance F (`exact`, when > 0: Stitch's) is
## tolerant by as much (within F, fitted geometry is where it belongs by
## the fit's contract): a vertex off its edges' ends, an edge by its slack
## in `edge_slack` (a joined or traced edge's), or by `precision` (how far
## Trim's curves may lie off their face) when that is wider.
func write_pieces(work: Work*, pieces: const Pieces*, piece_face: const usize[], piece_name: const i64[], keep: const bool[], turn: const bool[], closed: bool, precision: f64, exact: f64,
edge_slack: const f64[]) -> interop.Reference[CadModel]!:
let w = &work.w
var uses_count = Growing[i64]()
defer uses_count.close()
var direction = Growing[i64]()
defer direction.close()
for _ in 0..<work.finals.count:
try uses_count.push(0)
try direction.push(0)
for p in 0..<pieces.piece_count():
if not keep[p]: continue
for c in pieces.piece_cycles(p):
for use in pieces.cycle(c):
let e = edge_index(use)
uses_count.items[e] += 1
direction.items[e] += (1 if use > 0 else -1) * (-1 if turn[p] else 1)
var open_edges = 0
# Edges four (six, …) faces meet at, as many each way: the bodies touch
# along them, and the answer is a non-manifold body.
var crowded = 0
for e in 0..<work.finals.count:
let used = uses_count.items[e]
if closed and used != 0 and (used != 2 or direction.items[e] != 0):
open_edges += 1
if used >= 4 and used % 2 == 0 and direction.items[e] == 0: crowded += 1
# Open, an edge is a boundary (once) or shared each way (twice).
if not closed and used > 1 and (used != 2 or direction.items[e] != 0): open_edges += 1
if open_edges > 0:
if closed and crowded == open_edges: error(invalid, non_manifold)
if closed: error(invalid, not_closed)
error(invalid, "the result's faces do not meet edge to edge")
# What is where it belongs: within the fit tolerance (or Stitch's own).
let tolerance = exact if exact > 0.0 else work.w.tolerances.fit
let output = try BrepModel.held(work.w.tolerances)
defer output.release()
let b = output.value()
var vertex_ids = Growing[i64]()
defer vertex_ids.close()
for _ in work.vertices.view(): try vertex_ids.push(-1)
var slack = Growing[f64]()
defer slack.close()
try slack.fill(work.vertices.count, 0.0)
# How far each vertex is from its edges' ends: with an exact
# tolerance (Stitch's merged vertices), or without one only where a
# tolerant edge's precision merged it.
for e in 0..<work.finals.count:
if uses_count.items[e] == 0: continue
let edge = work.finals.items[e]
let a = (try w.at(edge.carrier, edge.t0)).subtract(work.placed(edge.start)).length()
let z = (try w.at(edge.carrier, edge.t1)).subtract(work.placed(edge.end)).length()
# A vertex's zone holds its edges' (a tolerant edge's precision).
let own = math.max(edge_slack[e] if e < edge_slack.length else 0.0, precision)
slack.items[(usize)edge.start] = math.max(slack.items[(usize)edge.start], math.max(a * 1.01, own))
slack.items[(usize)edge.end] = math.max(slack.items[(usize)edge.end], math.max(z * 1.01, own))
# The order everything is written in (canonical.lucb): between peers
# one of the result's own geometry.
var layout = try layout_of(work, pieces, piece_face, keep, turn)
defer layout.close()
var edge_ids = Growing[i64]()
defer edge_ids.close()
try edge_ids.fill(work.finals.count, -1)
for e in layout.edges.view():
if uses_count.items[e] == 0: continue
let edge = work.finals.items[e]
let flip = layout.flipped.items[e]
let first = edge.end if flip else edge.start
let last = edge.start if flip else edge.end
for v in [first, last]:
if vertex_ids.items[(usize)v] >= 0: continue
vertex_ids.items[(usize)v] = try b.add_vertex(work.placed(v))
if slack.items[(usize)v] > tolerance: try b.set_vertex_precision(vertex_ids.items[(usize)v], slack.items[(usize)v])
let start = vertex_ids.items[(usize)first]
let end = vertex_ids.items[(usize)last]
let c = w.carriers.items[(usize)edge.carrier]
var forward = (edge.t1 > edge.t0) != flip
var id: i64 = -1
if c.kind == curve_line: id = try b.add_line(start, end)
elif c.kind == curve_circle or c.kind == curve_ellipse:
var axis = c.x.cross(c.y)
# Between peers: the axis up the first axis it leans along, and
# a circle's reference through its first vertex (a closed one's
# seam stays where its vertex is).
var reference = c.x
if work.symmetric:
let (turned, sign_flipped) = canonical_axis(axis)
axis = turned
if sign_flipped: forward = not forward
if c.kind == curve_circle:
let toward = work.placed(first).subtract(c.origin)
reference = toward.subtract(axis.multiply_scalar(toward.dot(axis)))
else:
let (major, _) = canonical_axis(c.x)
reference = major
id = (try b.add_circle(start, end, c.origin, axis, reference, c.a, forward)) if c.kind == curve_circle else (try b.add_ellipse(start, end, c.origin, axis, reference, c.a, c.b, forward))
else:
let (points, weights, knots, degree) = w.spline_net(c.spline)
id = try b.add_spline_edge(start, end, points, weights, degree, knots, forward)
# A joined edge's precision: how far apart the edges it joined lay.
let own = math.max(edge_slack[e] if e < edge_slack.length else 0.0, precision)
if own > tolerance: try b.set_edge_precision(id, own)
edge_ids.items[e] = id
var surface_ids = Growing[i64]()
defer surface_ids.close()
for _ in w.surfaces.view(): try surface_ids.push(-1)
var uses = Growing[i64]()
defer uses.close()
var sizes = Growing[i64]()
defer sizes.close()
for k in 0..<layout.order.count:
let p = layout.order.items[k]
let face = w.faces.items[piece_face[p]]
let si = (usize)face.surface
if surface_ids.items[si] < 0:
let s = w.surfaces.items[si]
surface_ids.items[si] = (try b.add_spline_surface(s.points, s.weights, s.nu, s.nv, s.du, s.dv, s.ku, s.kv)) if s.kind == surface_spline else (try b.add_surface(s.kind, s.origin, s.z, s.x, s.radius, s.angle))
uses.clear()
sizes.clear()
for loop in 0..<layout.loop_count(k):
let cycle = layout.piece_uses(k, loop)
for use in cycle:
let e = edge_index(use)
let runs = (use > 0) != layout.flipped.items[e]
try uses.push((edge_ids.items[e] + 1) * (1 if runs else -1))
try sizes.push((i64)cycle.length)
let made = try b.add_face(surface_ids.items[si], uses.view(), sizes.view(), face.sense != turn[p])
try b.set_face_name(made, w.name(piece_name[p]))
return try CadModel.of_brep(output)
## Whether every edge of the kept pieces is used twice, once each way.
func pieces_closed(work: Work*, pieces: const Pieces*, keep: const bool[], turn: const bool[]) -> bool!:
var uses_count = Growing[i64]()
defer uses_count.close()
var direction = Growing[i64]()
defer direction.close()
try uses_count.fill(work.finals.count, 0)
try direction.fill(work.finals.count, 0)
for p in 0..<pieces.piece_count():
if not keep[p]: continue
for c in pieces.piece_cycles(p):
for use in pieces.cycle(c):
let e = edge_index(use)
uses_count.items[e] += 1
direction.items[e] += (1 if use > 0 else -1) * (-1 if turn[p] else 1)
for e in 0..<work.finals.count:
if uses_count.items[e] != 0 and (uses_count.items[e] != 2 or direction.items[e] != 0): return false
return true
## Whether an edge of the kept pieces lies inside another kept piece's face
## (a hole's wall tangent to a face from inside: the face passes through
## the edge, the solid has no thickness there). Analytic faces whose
## surface the edge lies on, at a quarter, half and three quarters of its
## length, are checked (an edge touching a face at one point, as a ball
## touching a box, is no such edge).
func touches_itself(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[]) -> bool!:
let w = &work.w
var used = Growing[bool]()
defer used.close()
try used.fill(work.finals.count, false)
for p in 0..<pieces.piece_count():
if not keep[p]: continue
for c in pieces.piece_cycles(p):
for use in pieces.cycle(c): used.items[edge_index(use)] = true
for e in 0..<work.finals.count:
if not used.items[e]: continue
let edge = work.finals.items[e]
let middle = try w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
let quarter = try w.at(edge.carrier, edge.t0 * 0.75 + edge.t1 * 0.25)
let three = try w.at(edge.carrier, edge.t0 * 0.25 + edge.t1 * 0.75)
for q in 0..<pieces.piece_count():
if not keep[q]: continue
let f = piece_face[q]
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind == surface_spline: continue
if surface_distance(s, middle) > work.tol * 10.0 or surface_distance(s, quarter) > work.tol * 10.0 or surface_distance(s, three) > work.tol * 10.0: continue
# Not one of its own edges.
var bounds = false
for c in pieces.piece_cycles(q):
for use in pieces.cycle(c):
if edge_index(use) == e: bounds = true
if bounds: continue
if (try piece_holds(work, traced, f, pieces, q, middle)) and (try piece_holds(work, traced, f, pieces, q, quarter)) and (try piece_holds(work, traced, f, pieces, q, three)): return true
return false
## Whether faces the tangencies note touch along a section where the
## operation keeps material on neither side between them, and a kept piece
## of each face reaches that section (bounded by it or holding it).
func pinched(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[], op: i64) -> bool!:
let w = &work.w
for touch in work.tangencies.view():
if not ((op == op_union and not touch.same) or (op == op_subtract and touch.same)): continue
for at in 0..<work.sections.count:
let section = work.sections.items[at]
let pair = (section.fa == (i64)touch.fa and section.fb == (i64)touch.fb) or (section.fa == (i64)touch.fb and section.fb == (i64)touch.fa)
if not pair: continue
let id = work.section_ids.items[at]
let e = edge_index(id)
let edge = work.finals.items[e]
let middle = try w.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
if (try kept_reaches(work, traced, pieces, piece_face, keep, touch.fa, e, middle)) and (try kept_reaches(work, traced, pieces, piece_face, keep, touch.fb, e, middle)): return true
return false
## Whether a kept piece of face `f` has final edge `e` on its boundary or
## holds `p` (on it).
func kept_reaches(work: Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], keep: const bool[], f: usize, e: usize, p: Vector3) -> bool!:
for q in 0..<pieces.piece_count():
if not keep[q] or piece_face[q] != f: continue
for c in pieces.piece_cycles(q):
for use in pieces.cycle(c):
if edge_index(use) == e: return true
if try piece_holds(work, traced, f, pieces, q, p): return true
return false