dymokomi/luce-geocore
Source of release 0.7.8
0.7.8 / src / booleans / boolean.lucb
# mark: Running a boolean ======================================================================
## The operations, as the verb's menu numbers them.
pub let boolean_union: i64 = 0
pub let boolean_subtract: i64 = 1
pub let boolean_intersect: i64 = 2
## Combine faces `a` and `b` of `mesh` (disjoint; each a closed surface)
## by `operation`: what the result makes of the operands' faces, into
## `out`. Other faces are the caller's to keep.
##
## The fast way cuts the operands against each other and their own faces
## only where folds reach the cut. The kept faces are then checked to
## close up; when a fold elsewhere misled a patch they do not, and every
## crossing of each operand with itself is cut too. If even that does not
## close (an operand overlapping itself in its own plane), it is an error.
pub func combine(mesh: const Mesh*, a: Bits, b: Bits, operation: i64, out: Combined*) -> !:
if operation < 0 or operation > 2: error(errors.invalid, "Boolean's operation is 0 (Union), 1 (Subtract) or 2 (Intersect)")
var operands = Operands(mesh, try Topology.of(mesh))
defer operands.close()
try operands.gather(a, b)
try operands.check_closed()
var tree_a = BoxTree()
defer tree_a.close()
var tree_b = BoxTree()
defer tree_b.close()
var trees = TreeWork(&operands, &tree_a, &tree_b)
try parallel.for_each(2, (void*)&trees, build_tree)
let both: BoxTree[2] = [tree_a, tree_b]
var arrangement = Arrangement()
defer arrangement.close()
try arrangement.build(&operands, both[..<2], operation, false)
if not try arrangement.closes(&operands):
arrangement.close()
arrangement = Arrangement()
try arrangement.build(&operands, both[..<2], operation, true)
if not try arrangement.closes(&operands): error(errors.invalid, "Boolean: a piece overlaps itself in its own plane, so the result would not close; separate or clean it first")
try assemble(&operands, &arrangement.cut, &arrangement.table, &arrangement.pieces, &arrangement.classes, out)
## The cut operands and what becomes of every face and piece.
struct Arrangement:
var cut: Cut
var table: PointTable
var made: Growing[Pieces]
var pieces: CutFaces
var classes: Classes
func init():
self.cut = Cut()
self.table = PointTable(no_points[..<0])
self.made = Growing[Pieces]()
self.pieces = CutFaces()
self.classes = Classes()
func close():
self.cut.close()
self.table.close()
for at in 0..<self.made.count: self.made.items[at].close()
self.made.close()
self.pieces.close()
self.classes.close()
## Cut, triangulate and classify; with `full`, every triangle is cut
## against its own operand, not only those the folds lead to.
func build(operands: const Operands*, trees: const BoxTree[], operation: i64, full: bool) -> !:
var records = PairOut()
defer records.close()
try cut_all_pairs(operands, &trees[1], &records)
try flat_records(operands, &records)
try cut_own_pairs(operands, &trees[0], &trees[1], &records, full)
var arena = Arena()
defer arena.close()
self.table = PointTable(operands.points.view())
try self.cut.gather(operands, &records)
try self.cut.store_points(operands, &self.table, &arena)
# Cuts crossing inside faces (an earlier cut's rounding): their
# points join the records and the cut is gathered again.
if try find_crossings(operands, &self.cut, &self.table, &records):
self.cut.close()
self.cut = Cut()
self.table.close()
self.table = PointTable(operands.points.view())
try self.cut.gather(operands, &records)
try self.cut.store_points(operands, &self.table, &arena)
records.close()
try self.cut.merge_coincident(operands, &self.table, &arena)
let slots = self.cut.triangles.count
try self.made.reserve(slots)
for at in 0..<slots: self.made.items[at] = Pieces()
self.made.count = slots
try triangulate_all(operands, &self.cut, &self.table, self.made.items[..<slots])
try self.pieces.gather(operands, &self.cut, self.made.view())
try self.classes.run(operands, &self.table, &self.pieces, trees, operation)
## Whether the kept faces close up: every edge of a kept piece, and
## every edge of a kept whole face that a cut face or more than one
## other face shares, used as often one way as the other.
func closes(operands: const Operands*) -> bool!:
let topology = &operands.topology
let faces = topology.faces()
let pieces = &self.pieces
let fate = self.classes.fate.view()
var halves = Growing[u64]()
defer halves.close()
for piece in 0..<pieces.count():
let kept = fate[faces + piece]
if kept == unit_dropped: continue
for k in 0..<(usize)3:
let x = (u64)pieces.corners.items[piece * 3 + k]
let y = (u64)pieces.corners.items[piece * 3 + (k + 1) % 3]
try halves.push((y << 32) | x if kept == unit_reversed else (x << 32) | y)
for face in 0..<faces:
let kept = fate[face]
if operands.face_operand.items[face] == outside_operands or pieces.cut_face(face) or kept == unit_dropped: continue
let first = (usize)topology.offsets[face]
let size = (usize)topology.offsets[face + 1] - first
for k in 0..<size:
let edge = (usize)topology.corner_edges[first + k]
let from_at = (usize)topology.edge_corner_offsets[edge]
let to_at = (usize)topology.edge_corner_offsets[edge + 1]
var watched = to_at - from_at != 2
for at in from_at..<to_at:
if pieces.cut_face((usize)topology.corner_faces[(usize)topology.edge_corners[at]]): watched = true
if not watched: continue
let x = (u64)operands.same.items[(usize)topology.corners[first + k]]
let y = (u64)operands.same.items[(usize)topology.corners[first + (k + 1) % size]]
if x == y: continue
try halves.push((y << 32) | x if kept == unit_reversed else (x << 32) | y)
sort.sort(halves.items[..<halves.count])
for half in halves.view():
let back = ((half & 0xFFFFFFFF) << 32) | (half >> 32)
if count_of(halves.view(), half) != count_of(halves.view(), back): return false
return true
let no_points: Vector3[1] = [Vector3()]
## How many times sorted `words` holds `word`.
func count_of(words: const u64[], word: u64) -> usize:
var low: usize = 0
var high = words.length
while low < high:
let middle = (low + high) // 2
if words[middle] < word: low = middle + 1
else: high = middle
var end = low
while end < words.length and words[end] == word: end += 1
return end - low
## The two operands' trees, built at once.
struct TreeWork:
let operands: const Operands*
var a: BoxTree*
var b: BoxTree*
func build_tree(context: void*, index: usize, worker: usize) -> !:
let work = (TreeWork*)context
let operands = work.operands
if index == 0: try work.a.build(operands, 0, operands.split)
else: try work.b.build(operands, operands.split, operands.triangle_count())