dymokomi/luce-geocore
Source of release 0.7.9
0.7.9 / src / booleans / operands.lucb
# mark: Operands ===============================================================================
## Which operand a face belongs to.
let outside_operands: u8 = 0
let operand_a: u8 = 1
let operand_b: u8 = 2
## The two operands as triangles (the mesh's display triangles, so a face
## means what the viewport shows) over exact points: a non-precise mesh's
## f32 positions are exact doubles in its own frame, a precise mesh's f64
## points exact in the world, and `frame` takes them to the world. A's
## triangles come first (below `split`), each operand's in face order.
pub struct Operands:
let mesh: const Mesh*
let topology: Topology
var points: Growing[Vector3]
var frame: Vector3
## Per point: the point it is the same as. Points at exactly one place
## take the lowest number there (B's on A's, and a piece's own points
## rounded together by an earlier cut), so the cut sees one point.
var same: Growing[i32]
## Per face: its operand (outside_operands, operand_a, operand_b) and
## its first triangle in `triangles` (-1 outside).
var face_operand: Growing[u8]
var face_first: Growing[i32]
## Per triangle: its points (after `same`), its corners, its face and
## its projection.
var triangles: Growing[i32]
var corners: Growing[i32]
var faces: Growing[i32]
var projections: Growing[Projection]
var split: usize
func init(mesh: const Mesh*, topology: Topology):
self.mesh = mesh
self.topology = topology
self.points = Growing[Vector3]()
self.frame = Vector3()
self.same = Growing[i32]()
self.face_operand = Growing[u8]()
self.face_first = Growing[i32]()
self.triangles = Growing[i32]()
self.corners = Growing[i32]()
self.faces = Growing[i32]()
self.projections = Growing[Projection]()
self.split = 0
func close():
self.points.close()
self.same.close()
self.face_operand.close()
self.face_first.close()
self.triangles.close()
self.corners.close()
self.faces.close()
self.projections.close()
func triangle_count() -> usize:
return self.faces.count
## Triangle `t`'s operand.
func operand_of(t: usize) -> u8:
return operand_a if t < self.split else operand_b
## Point `k` (0..3) of triangle `t`.
func vertex(t: usize, k: usize) -> usize:
return (usize)self.triangles.items[t * 3 + k]
func place(t: usize, k: usize) -> Vector3:
return self.points.items[self.vertex(t, k)]
## Gather faces `a` and `b` (disjoint) of the mesh.
func gather(a: Bits, b: Bits) -> !:
let mesh = self.mesh
let faces = self.topology.faces()
let positions = mesh.point_span()
# A precise mesh's f64 points, its moved ones read from f32.
var exact = try mesh.exact_points()
defer exact.release()
let precise = exact.view()
try self.points.reserve(positions.length)
for at in 0..<positions.length:
self.points.items[at] = precise[at] if precise.length > 0 else positions[at].vector()
self.points.count = positions.length
self.frame = Vector3() if precise.length > 0 else mesh.position_origin()
try self.face_operand.fill(faces, outside_operands)
try self.face_first.fill(faces, -1)
for face in 0..<faces:
if a.get(face): self.face_operand.items[face] = operand_a
elif b.get(face): self.face_operand.items[face] = operand_b
try self.unify()
try self.add_triangles()
try self.projections.reserve(self.faces.count)
self.projections.count = self.faces.count
var work = ProjectionWork(&self)
try parallel.for_each_range(self.faces.count, 4096, (void*)&work, project_range)
try self.mend_slivers()
## Faces whose display triangles include one without area (collinear
## points of a polygon, rounded so by an earlier cut) triangulated anew,
## exactly, so none is flat; a face that cannot be keeps its own.
func mend_slivers() -> !:
var last: i64 = -1
for t in 0..<self.faces.count:
let face = (i64)self.faces.items[t]
if self.projections.items[t].sense != 0 or face == last or self.collapsed(t): continue
last = face
if try self.retriangulate((usize)face):
let first = (usize)self.face_first.items[(usize)face]
let size = (usize)(self.topology.offsets[(usize)face + 1] - self.topology.offsets[(usize)face])
for at in first..<first + size - 2: self.projections.items[at] = projection_of(self.place(at, 0), self.place(at, 1), self.place(at, 2))
## Ear clip face `face` exactly in the projection its outline faces
## most: each ear strictly convex with no other corner in or on it.
## False (nothing changed) when the outline has no such ears.
func retriangulate(face: usize) -> bool!:
let start = (usize)self.topology.offsets[face]
let size = (usize)self.topology.offsets[face + 1] - start
var normal = Vector3()
for k in 0..<size:
let p = self.points.items[(usize)self.same.items[(usize)self.topology.corners[start + k]]]
let q = self.points.items[(usize)self.same.items[(usize)self.topology.corners[start + (k + 1) % size]]]
normal = normal.add(p.cross(q))
let axis: usize = 0 if math.abs(normal.x) >= math.abs(normal.y) and math.abs(normal.x) >= math.abs(normal.z) else (1 if math.abs(normal.y) >= math.abs(normal.z) else 2)
let along = Projection.along(axis)
let sense: i64 = 1 if normal.coordinate(axis) > 0.0 else (-1 if normal.coordinate(axis) < 0.0 else 0)
if sense == 0: return false
# Corners at the place of the one before them drop out.
var left = Growing[u32]()
defer left.close()
for k in 0..<size:
let point = self.same.items[(usize)self.topology.corners[start + k]]
if self.same.items[(usize)self.topology.corners[start + (k + size - 1) % size]] != point: try left.push((u32)k)
if left.count < 3: return false
var made = Growing[u32]()
defer made.close()
var ears = Growing[u32]()
defer ears.close()
try ears.assign(left.view())
if not try self.ear_clip(start, &ears, along, sense, &made):
# An outline that crosses itself has no ears: a fan from a
# corner with no flat triangle (overlaps are cut as folds).
var fanned = false
for apex in 0..<left.count:
made.clear()
if try self.fan_from(start, left.view(), apex, &made):
fanned = true
break
if not fanned: return false
# The dropped corners' slots: collapsed triangles at one corner.
while made.count < (size - 2) * 3: try made.push(left.items[0])
let first = (usize)self.face_first.items[face]
for at in 0..<made.count:
let corner = start + (usize)made.items[at]
self.corners.items[first * 3 + at] = (i32)corner
self.triangles.items[first * 3 + at] = self.same.items[(usize)self.topology.corners[corner]]
return true
## Ear clip corners `left` (consumed) of the face whose corners start at
## `start` into `made`; false when some ear is missing.
func ear_clip(start: usize, left: Growing[u32]*, along: Projection, sense: i64, made: Growing[u32]*) -> bool!:
while left.count > 3:
var clipped = false
for at in 0..<left.count:
let a = (usize)left.items[(at + left.count - 1) % left.count]
let b = (usize)left.items[at]
let c = (usize)left.items[(at + 1) % left.count]
if not self.is_ear(start, left.view(), a, b, c, along, sense): continue
try made.push((u32)a)
try made.push((u32)b)
try made.push((u32)c)
for move in at..<left.count - 1: left.items[move] = left.items[move + 1]
left.count -= 1
clipped = true
break
if not clipped: return false
let a = self.corner_place(start, (usize)left.items[0])
let b = self.corner_place(start, (usize)left.items[1])
let c = self.corner_place(start, (usize)left.items[2])
if orient2d(a, b, c, along.u, along.v) * sense <= 0: return false
for k in 0..<(usize)3: try made.push(left.items[k])
return true
## The fan of corners `left` from corner `apex` into `made`; false when
## a triangle of it would be flat.
func fan_from(start: usize, left: const u32[], apex: usize, made: Growing[u32]*) -> bool!:
let count = left.length
let a = (usize)left[apex]
for step in 1..<count - 1:
let b = (usize)left[(apex + step) % count]
let c = (usize)left[(apex + step + 1) % count]
if projection_of(self.corner_place(start, a), self.corner_place(start, b), self.corner_place(start, c)).sense == 0: return false
try made.push((u32)a)
try made.push((u32)b)
try made.push((u32)c)
return true
## The place of corner `k` of the face whose corners start at `start`.
func corner_place(start: usize, k: usize) -> Vector3:
return self.points.items[(usize)self.same.items[(usize)self.topology.corners[start + k]]]
## Whether (a, b, c), corners of the face starting at `start`, is an ear
## among the corners `left`: turning the outline's way, no other corner
## inside it or on it (one at a corner's very place aside).
func is_ear(start: usize, left: const u32[], a: usize, b: usize, c: usize, along: Projection, sense: i64) -> bool:
let pa = self.corner_place(start, a)
let pb = self.corner_place(start, b)
let pc = self.corner_place(start, c)
if orient2d(pa, pb, pc, along.u, along.v) * sense <= 0: return false
for other in left:
let k = (usize)other
if k == a or k == b or k == c: continue
let p = self.corner_place(start, k)
if same_place(p, pa) or same_place(p, pb) or same_place(p, pc): continue
if orient2d(pa, pb, p, along.u, along.v) * sense >= 0 and orient2d(pb, pc, p, along.u, along.v) * sense >= 0 and orient2d(pc, pa, p, along.u, along.v) * sense >= 0: return false
return true
## Each operand face's display triangles, A's faces first, each
## operand's in face order: numbered here, filled on the pool.
func add_triangles() -> !:
let offsets = self.topology.offsets
var total: usize = 0
for operand in 1..<(u8)3:
if operand == operand_b: self.split = total
for face in 0..<self.topology.faces():
if self.face_operand.items[face] != operand: continue
self.face_first.items[face] = (i32)total
total += (usize)(offsets[face + 1] - offsets[face]) - 2
try self.triangles.reserve(total * 3)
try self.corners.reserve(total * 3)
try self.faces.reserve(total)
self.triangles.count = total * 3
self.corners.count = total * 3
self.faces.count = total
var work = TriangleFill(&self, self.mesh.triangle_span())
try parallel.for_each_range(self.topology.faces(), 8192, (void*)&work, fill_triangles)
## Number points at one place as the lowest there.
func unify() -> !:
let points = self.points.count
try self.same.reserve(points)
for at in 0..<points: self.same.items[at] = (i32)at
self.same.count = points
let used = try new u8[points] in memory.heap
defer free(used) in memory.heap
let offsets = self.topology.offsets
let corners = self.topology.corners
var count: usize = 0
for face in 0..<self.topology.faces():
if self.face_operand.items[face] == outside_operands: continue
for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
let point = (usize)corners[corner]
if used[point] == 0: count += 1
used[point] = 1
if count == 0: return
var table = try PlaceTable.sized(count)
defer table.close()
for point in 0..<points:
if used[point] != 0: self.same.items[point] = (i32)table.insert(self.points.view(), point)
## Whether triangle `t` has two corners at one point (a sliver an
## earlier cut's rounding closed up): it has no area and no place in
## the cut, its sides' neighbors meeting across it.
func collapsed(t: usize) -> bool:
let a = self.triangles.items[t * 3]
let b = self.triangles.items[t * 3 + 1]
let c = self.triangles.items[t * 3 + 2]
return a == b or b == c or a == c
## Whether triangle `t` has no place in the cut: collapsed, or flat (its
## corners in a line), which its neighbor across the long side makes
## up for by taking the middle corner (see flat_records).
func inert(t: usize) -> bool:
return self.collapsed(t) or self.projections.items[t].sense == 0
## Fail unless each operand is closed: every edge of its faces used as
## often in one direction as in the other (a closed manifold, or solids
## touching along an edge).
func check_closed() -> !:
let topology = &self.topology
let balance = try new i32[topology.edges() * 2] in memory.heap
defer free(balance) in memory.heap
for face in 0..<topology.faces():
let operand = self.face_operand.items[face]
if operand == outside_operands: continue
let shift: usize = 0 if operand == operand_a else 1
for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
let edge = (usize)topology.corner_edges[corner]
let forward = topology.corners[corner] == topology.edge_points[edge * 2]
balance[edge * 2 + shift] += 1 if forward else -1
var open_a: usize = 0
var open_b: usize = 0
for edge in 0..<topology.edges():
if balance[edge * 2] != 0: open_a += 1
if balance[edge * 2 + 1] != 0: open_b += 1
if open_a > 0: error(errors.invalid, "Boolean needs closed pieces: the pieces to combine have open edges (or faces facing opposite ways)")
if open_b > 0: error(errors.invalid, "Boolean needs closed pieces: the pieces to cut with have open edges (or faces facing opposite ways)")
struct TriangleFill:
var operands: Operands*
let display: const i32[]
func fill_triangles(context: void*, first: usize, end: usize, worker: usize):
let work = (TriangleFill*)context
let operands = work.operands
let offsets = operands.topology.offsets
let corners = operands.topology.corners
for face in first..<end:
let at = operands.face_first.items[face]
if at < 0: continue
let start = (usize)offsets[face]
let size = (usize)offsets[face + 1] - start
let from_display = (start - face * 2) * 3
let to = (usize)at
for k in 0..<(size - 2) * 3:
let corner = work.display[from_display + k]
operands.corners.items[to * 3 + k] = corner
operands.triangles.items[to * 3 + k] = operands.same.items[(usize)corners[(usize)corner]]
for k in 0..<size - 2: operands.faces.items[to + k] = (i32)face
struct ProjectionWork:
var operands: Operands*
func project_range(context: void*, first: usize, end: usize, worker: usize):
let work = (ProjectionWork*)context
let operands = work.operands
for t in first..<end:
operands.projections.items[t] = projection_of(operands.place(t, 0), operands.place(t, 1), operands.place(t, 2))
## Points by their exact place: open addressing over the coordinates' bits.
struct PlaceTable:
var slots: i32[]
var mask: usize
static func sized(count: usize) -> PlaceTable!:
var size: usize = 64
while size < count * 2: size *= 2
let slots = try new i32[size] --- in memory.heap
for at in 0..<size: slots[at] = -1
return PlaceTable(slots, size - 1)
func close():
free(self.slots) in memory.heap
## Store `point` unless one is already there; the point there.
func insert(points: const Vector3[], point: usize) -> i64:
let place = points[point]
var at = place_hash(place) & self.mask
while self.slots[at] >= 0:
let other = (usize)self.slots[at]
if same_place(points[other], place): return (i64)other
at = (at + 1) & self.mask
self.slots[at] = (i32)point
return (i64)point
## The point at `place`, or -1.
func find(points: const Vector3[], place: Vector3) -> i64:
var at = place_hash(place) & self.mask
while self.slots[at] >= 0:
let other = (usize)self.slots[at]
if same_place(points[other], place): return (i64)other
at = (at + 1) & self.mask
return -1
## Whether `p` is in the box [lo, hi].
func within(p: Vector3, lo: Vector3, hi: Vector3) -> bool:
return p.x >= lo.x and p.x <= hi.x and p.y >= lo.y and p.y <= hi.y and p.z >= lo.z and p.z <= hi.z
func same_place(a: Vector3, b: Vector3) -> bool:
return a.x == b.x and a.y == b.y and a.z == b.z
## A hash of the exact coordinates (-0 as 0).
func place_hash(p: Vector3) -> usize:
let x = (p.x + 0.0).bits()
let y = (p.y + 0.0).bits()
let z = (p.z + 0.0).bits()
var h = x *% 0x9E3779B97F4A7C15
h = (h ^ (h >> 29)) +% y *% 0xBF58476D1CE4E5B9
h = (h ^ (h >> 31)) +% z *% 0x94D049BB133111EB
h = h ^ (h >> 32)
return (usize)h