dymokomi/luce-geocore
Source of release 0.7.9
0.7.9 / src / booleans / cdt_segments.lucb
# mark: Cut segments ===========================================================================
## Pack an edge's two local points for the flip queue.
func edge_word(left: u32, right: u32) -> u64:
return ((u64)left << 32) | (u64)right
extend Triangulation:
## Join local points u and w with cut edges for segment `segment`,
## splitting at any point the segment passes through.
func insert_segment(u: u32, w: u32, segment: u32) -> !:
var at = u
while at != w: at = try self.constrain(at, w, segment)
## Whether local point a, on the line through u and w, lies on u's side
## toward w.
func toward(u: u32, a: u32, w: u32) -> bool!:
let pu = &self.points.items[(usize)u]
let pa = &self.points.items[(usize)a]
let pw = &self.points.items[(usize)w]
var way = try compare_h(self.arena, pw, pu, self.axis_u)
var axis = self.axis_u
if way == 0:
way = try compare_h(self.arena, pw, pu, self.axis_v)
axis = self.axis_v
return try compare_h(self.arena, pa, pu, axis) == way
## Make a cut edge from u toward w: to w, or to the first point on the
## way. Returns where it ended.
func constrain(u: u32, w: u32, segment: u32) -> u32!:
let direct = try self.find_side(u, w)
let back = try self.find_side(w, u)
if direct.0 >= 0 or back.0 >= 0:
try self.fix_edge(u, w, segment)
return w
# The triangle at u the segment leaves through: (u, a, b) with a
# right of it and b left, or a point of the fan on it.
try self.gather_fan(u)
var start: i32 = -1
var side: usize = 3
for at in 0..<self.fan.count:
let t = self.fan.items[at]
let tri = self.tris.items[(usize)t]
let k = tri.corner_of(u)
let a = tri.v[(k + 1) % 3]
let b = tri.v[(k + 2) % 3]
let oa = try self.orient(u, w, a)
let ob = try self.orient(u, w, b)
if oa == 0 and try self.toward(u, a, w):
try self.fix_edge(u, a, segment)
return a
if ob == 0 and try self.toward(u, b, w):
try self.fix_edge(u, b, segment)
return b
if oa < 0 and ob > 0:
start = t
side = k
if start < 0: error(errors.invalid, "Boolean: inconsistent cut (a segment leaves its face)")
# March across the edges it crosses, to w or to a point on it.
self.crossed.clear()
var current = start
var tri = self.tris.items[(usize)current]
var left = tri.v[(side + 2) % 3]
var right = tri.v[(side + 1) % 3]
var end = w
while true:
if (tri.fixed >> (u8)side) & 1 != 0: error(errors.invalid, "Boolean: two cuts cross inside a face (the pieces cross themselves?)")
try self.crossed.push(edge_word(left, right))
let next = tri.n[side]
if next < 0: error(errors.invalid, "Boolean: inconsistent cut (a segment leaves its face)")
let ahead = self.tris.items[(usize)next]
let d = ahead.v[ahead.side_to(current)]
if d == w: break
let od = try self.orient(u, w, d)
if od == 0:
end = d
break
if od > 0:
side = ahead.corner_of(left)
left = d
else:
side = ahead.corner_of(right)
right = d
current = next
tri = ahead
try self.flip_out(u, end)
try self.fix_edge(u, end, segment)
return end
## Flip the crossed edges away until u and `end` are joined (Sloan): an
## edge whose quad is convex turns, and goes back in the queue while it
## still crosses; one whose quad is not waits its turn again.
func flip_out(u: u32, end: u32) -> !:
self.queue.clear()
for word in self.crossed.view(): try self.queue.push(word)
var head: usize = 0
var turns: usize = 0
let most = 64 * self.tris.count * self.tris.count + 1024
while head < self.queue.count:
turns += 1
if turns > most: error(errors.invalid, "Boolean: inconsistent cut (flips do not end)")
let word = self.queue.items[head]
head += 1
let x = (u32)(word >> 32)
let y = (u32)(word & 0xFFFFFFFF)
var found = try self.find_side(x, y)
if found.0 < 0: found = try self.find_side(y, x)
if found.0 < 0: error(errors.invalid, "Boolean: inconsistent cut (a lost edge)")
let t = (usize)found.0
let k = found.1
let tri = self.tris.items[t]
let c = tri.v[k]
let other = self.tris.items[(usize)tri.n[k]]
let d = other.v[other.side_to((i32)t)]
let p = tri.v[(k + 1) % 3]
let q = tri.v[(k + 2) % 3]
if (try self.orient(c, d, p)) * (try self.orient(c, d, q)) < 0:
self.flip(t, k)
if c != u and c != end and d != u and d != end:
if (try self.orient(u, end, c)) * (try self.orient(u, end, d)) < 0: try self.queue.push(edge_word(c, d))
else:
try self.queue.push(word)
# Keep the queue's live part at the front.
if head > 4096 and head * 2 > self.queue.count:
let live = self.queue.count - head
for at in 0..<live: self.queue.items[at] = self.queue.items[head + at]
self.queue.count = live
head = 0
# mark: Triangulating every cut triangle =======================================================
## One cut triangle's pieces: three cut point numbers each, in the host's
## winding, which sides a cut runs along (bits), and the coplanar triangle
## of the other operand covering it (-1 none).
struct Pieces:
var corners: Growing[u32]
var fixed: Growing[u8]
var covers: Growing[i32]
func init():
self.corners = Growing[u32]()
self.fixed = Growing[u8]()
self.covers = Growing[i32]()
func close():
self.corners.close()
self.fixed.close()
self.covers.close()
struct TriangulateWork:
let operands: const Operands*
let cut: const Cut*
let table: const PointTable*
var arenas: Arena[]
var pieces: Pieces[]
func triangulate_range(context: void*, first: usize, end: usize, worker: usize) -> !:
let work = (TriangulateWork*)context
var triangulation = Triangulation(&work.arenas[worker])
defer triangulation.close()
for slot in first..<end:
try triangulate_one(work, &triangulation, slot)
## Triangulate cut triangle `slot`: its corners, its points, its segments,
## then which pieces coplanar triangles cover.
func triangulate_one(work: TriangulateWork*, triangulation: Triangulation*, slot: usize) -> !:
let operands = work.operands
let cut = work.cut
let t = (usize)cut.triangles.items[slot]
let corners: u32[3] = [(u32)operands.vertex(t, 0), (u32)operands.vertex(t, 1), (u32)operands.vertex(t, 2)]
try triangulation.begin(work.table, corners, operands.projections.items[t], (u64)t)
for at in (usize)cut.point_starts.items[slot]..<(usize)cut.point_starts.items[slot + 1]:
let id = cut.points.items[at]
if id == corners[0] or id == corners[1] or id == corners[2]: continue
try triangulation.insert_point(work.table, id)
for at in (usize)cut.segment_starts.items[slot]..<(usize)cut.segment_starts.items[slot + 1]:
let segment = cut.segments.items[at]
try triangulation.insert_segment(local_of(triangulation, segment.first), local_of(triangulation, segment.second), (u32)at)
let pieces = &work.pieces[slot]
for tri in triangulation.tris.view():
for k in 0..<(usize)3: try pieces.corners.push(triangulation.ids.items[(usize)tri.v[k]])
try pieces.fixed.push(tri.fixed)
try pieces.covers.push(-1)
for at in (usize)cut.cover_starts.items[slot]..<(usize)cut.cover_starts.items[slot + 1]:
try mark_cover(operands, cut, triangulation, slot, (usize)cut.covers.items[at], pieces)
## The local number of cut point `id` (inserted): a corner, or one of the
## points after them, which went in in increasing order.
func local_of(triangulation: const Triangulation*, id: u32) -> u32:
for at in 0..<(usize)3:
if triangulation.ids.items[at] == id: return (u32)at
var low: usize = 3
var high = triangulation.ids.count
while low < high:
let middle = (low + high) // 2
if triangulation.ids.items[middle] < id: low = middle + 1
else: high = middle
if low >= triangulation.ids.count or triangulation.ids.items[low] != id: trap("a cut segment's point was not inserted")
return (u32)low
## One edge of a covering triangle, by its packed local points, with the
## covering triangle's point off it.
struct CoverEdge:
let word: u64
let opposite: u32
func cover_edge_less(a: CoverEdge, b: CoverEdge) -> bool:
return a.word < b.word
## Mark the pieces coplanar triangle `other` covers, when it comes before
## the host: of faces lying one on another, the first triangle's pieces
## stand for the stack, the others' go. The covered pieces are the regions
## between its edges, each inside when the triangle lies on its side of
## one of them, and with none of its edges in this triangulation, all of
## it when the host lies inside it.
func mark_cover(operands: const Operands*, cut: const Cut*, triangulation: Triangulation*, slot: usize, other: usize, pieces: Pieces*) -> !:
if other > (usize)cut.triangles.items[slot]: return
let count = triangulation.tris.count
let region = try new i32[count] in memory.heap
defer free(region) in memory.heap
let stack = try new u32[count] --- in memory.heap
defer free(stack) in memory.heap
# Its edges here: the cut edges of segments it covers.
var edges = Growing[CoverEdge]()
defer edges.close()
for edge in triangulation.fixed_edges.view():
let segment = cut.segments.items[(usize)edge.segment]
if segment.cover() != (i32)other: continue
try edges.push(CoverEdge(edge_word(math32_min(edge.first, edge.second), math32_max(edge.first, edge.second)), (u32)segment.opposite))
sort.by(edges.items[..<edges.count], cover_edge_less)
var regions: i32 = 0
for seed in 0..<count:
if region[seed] != 0: continue
regions += 1
region[seed] = regions
var top: usize = 1
stack[0] = (u32)seed
var inside: i64 = 0
while top > 0:
top -= 1
let t = (usize)stack[top]
let tri = triangulation.tris.items[t]
for k in 0..<(usize)3:
let x = tri.v[(k + 1) % 3]
let y = tri.v[(k + 2) % 3]
if (tri.fixed >> (u8)k) & 1 != 0:
let found = find_cover_edge(edges.view(), edge_word(math32_min(x, y), math32_max(x, y)))
if found >= 0:
# The piece is left of x -> y; inside when the
# covering triangle's far point is too.
if inside == 0:
var store: f64[4] = ---
let corner = input_point(operands.points.items[(usize)edges.items[(usize)found].opposite], store[..<4])
let turn = try orient2d_h(triangulation.arena, &triangulation.points.items[(usize)x], &triangulation.points.items[(usize)y], &corner, triangulation.axis_u, triangulation.axis_v) * triangulation.sense
inside = 1 if turn > 0 else -1
continue
let next = tri.n[k]
if next < 0 or region[(usize)next] != 0: continue
region[(usize)next] = regions
stack[top] = (u32)next
top += 1
if inside == 0 and edges.count == 0 and host_inside(operands, cut, slot, other): inside = 1
if inside <= 0: continue
for t in 0..<count:
if region[t] == regions and pieces.covers.items[t] < 0: pieces.covers.items[t] = (i32)other
## The index of the cover edge `word`, or -1.
func find_cover_edge(edges: const CoverEdge[], word: u64) -> i64:
var low: usize = 0
var high = edges.length
while low < high:
let middle = (low + high) // 2
if edges[middle].word < word: low = middle + 1
else: high = middle
return (i64)low if low < edges.length and edges[low].word == word else -1
## Whether every corner of cut triangle `slot` lies in coplanar triangle
## `other` (inside or on its border).
func host_inside(operands: const Operands*, cut: const Cut*, slot: usize, other: usize) -> bool:
let t = (usize)cut.triangles.items[slot]
let h = Corners.of(operands, other)
let projection = operands.projections.items[t]
let sense = orient2d(h.at[0], h.at[1], h.at[2], projection.u, projection.v)
for k in 0..<(usize)3:
if not inside_closed(&h, operands.place(t, k), projection, sense): return false
return true
func math32_min(a: u32, b: u32) -> u32:
return a if a < b else b
func math32_max(a: u32, b: u32) -> u32:
return a if a > b else b
## Triangulate every cut triangle, in parallel; one Pieces per slot.
func triangulate_all(operands: const Operands*, cut: const Cut*, table: const PointTable*, pieces: Pieces[]) -> !:
let count = cut.triangles.count
if count == 0: return
let workers = parallel.workers(count)
let arenas = try new Arena[workers] --- in memory.heap
for at in 0..<workers: arenas[at] = Arena()
defer:
for at in 0..<workers: arenas[at].close()
free(arenas) in memory.heap
var work = TriangulateWork(operands, cut, table, arenas, pieces)
try parallel.for_each_range(count, 16, (void*)&work, triangulate_range)