dymokomi/luce-geocore
Source of release 0.7.8
0.7.8 / src / booleans / pairs.lucb
# mark: Pairs ==================================================================================
# Each A triangle against each B triangle whose box meets its own is cut
# exactly, with signs of input points only: where its plane crosses the
# other's edges and the other's plane crosses its edges, whether those
# crossings fall inside, on an edge or at a corner, and for coplanar pairs
# where their edges cross. The result is points, named by what they are so
# that every pair that finds one names it alike, and the segments between
# them, recorded for both triangles.
## How a cut point is named, by input points (after Operands.same) only,
## so a triangle and its exact double name it alike: an input point
## (`v[0]`), an edge crossing a triangle's inside (the edge's points
## sorted, then the triangle's), two edges crossing (each edge's points
## sorted, the lower edge first), or three triangles' planes meeting (each
## triangle's points sorted, the triangles in order).
struct PointKey:
let kind: u8
let v: i32[9]
func less(other: PointKey) -> bool:
if self.kind != other.kind: return self.kind < other.kind
for at in 0..<(usize)9:
if self.v[at] != other.v[at]: return self.v[at] < other.v[at]
return false
func same(other: PointKey) -> bool:
if self.kind != other.kind: return false
for at in 0..<(usize)9:
if self.v[at] != other.v[at]: return false
return true
let input_key: u8 = 0
let edge_triangle_key: u8 = 1
let edge_edge_key: u8 = 2
## How a cut point is built: an input point (`p`), segment `p`-`q`
## crossing the plane of points `a`, `b`, `c`, or segment `p`-`q` meeting
## line `a`-`b` in the plane of projection axis `c`.
struct Recipe:
let kind: u8
let p: i32
let q: i32
let a: i32
let b: i32
let c: i32
func less(other: Recipe) -> bool:
if self.kind != other.kind: return self.kind < other.kind
if self.p != other.p: return self.p < other.p
if self.q != other.q: return self.q < other.q
if self.a != other.a: return self.a < other.a
if self.b != other.b: return self.b < other.b
return self.c < other.c
let input_recipe: u8 = 0
let crossing_recipe: u8 = 1
let meeting_recipe: u8 = 2
## A point that lies on triangle `triangle`.
struct PointRecord:
let triangle: i32
let key: PointKey
let recipe: Recipe
## A segment of the cut on triangle `triangle`: where triangle `source`
## crosses it (`opposite` -1), or an edge of coplanar triangle `source`
## that overlaps it, whose point `opposite` is off that edge.
struct SegmentRecord:
let triangle: i32
let first: PointKey
let second: PointKey
let source: i32
let opposite: i32
## Coplanar triangles `triangle` and `other` meet.
struct CoverRecord:
let triangle: i32
let other: i32
## What the pairs of one range of A triangles found.
struct PairOut:
var points: Growing[PointRecord]
var segments: Growing[SegmentRecord]
var covers: Growing[CoverRecord]
func init():
self.points = Growing[PointRecord]()
self.segments = Growing[SegmentRecord]()
self.covers = Growing[CoverRecord]()
func close():
self.points.close()
self.segments.close()
self.covers.close()
## The points one pair found, at most a few.
struct Found:
var keys: PointKey[8]
var recipes: Recipe[8]
var count: usize
func add(key: PointKey, recipe: Recipe) -> !:
for at in 0..<self.count:
if self.keys[at].same(key): return
if self.count == 8: error(errors.invalid, "Boolean: inconsistent cut (the pieces cross themselves?)")
self.keys[self.count] = key
self.recipes[self.count] = recipe
self.count += 1
func point_key(p: usize) -> PointKey:
return PointKey(input_key, [(i32)p, 0, 0, 0, 0, 0, 0, 0, 0])
func point_recipe(p: usize) -> Recipe:
return Recipe(input_recipe, (i32)p, 0, 0, 0, 0)
func edge_triangle(u: usize, w: usize, triangle: const usize[3]) -> PointKey:
let t = sorted_three(triangle)
return PointKey(edge_triangle_key, [(i32)(u if u < w else w), (i32)(w if u < w else u), (i32)t[0], (i32)t[1], (i32)t[2], 0, 0, 0, 0])
func edge_edge(u: usize, w: usize, x: usize, y: usize) -> PointKey:
let a: usize[2] = [u if u < w else w, w if u < w else u]
let b: usize[2] = [x if x < y else y, y if x < y else x]
let a_first = a[0] < b[0] or (a[0] == b[0] and a[1] < b[1])
let low = a if a_first else b
let high = b if a_first else a
return PointKey(edge_edge_key, [(i32)low[0], (i32)low[1], (i32)high[0], (i32)high[1], 0, 0, 0, 0, 0])
## Three point numbers in increasing order.
func sorted_three(points: const usize[3]) -> usize[3]:
var t: usize[3] = [points[0], points[1], points[2]]
if t[0] > t[1]:
let swap = t[0]
t[0] = t[1]
t[1] = swap
if t[1] > t[2]:
let swap = t[1]
t[1] = t[2]
t[2] = swap
if t[0] > t[1]:
let swap = t[0]
t[0] = t[1]
t[1] = swap
return t
## The three points of triangle `t` and their places.
struct Corners:
var ids: usize[3]
var at: Vector3[3]
static func of(operands: const Operands*, t: usize) -> Corners:
return Corners([operands.vertex(t, 0), operands.vertex(t, 1), operands.vertex(t, 2)], [operands.place(t, 0), operands.place(t, 1), operands.place(t, 2)])
## Whether `p`, in the plane of `h`, is inside `h` or on its border, in
## projection `projection` (h's sense there).
func inside_closed(h: const Corners*, p: Vector3, projection: Projection, sense: i64) -> bool:
for k in 0..<(usize)3:
if orient2d(h.at[k], h.at[(k + 1) % 3], p, projection.u, projection.v) * sense < 0: return false
return true
## Cut A triangle `t` with B triangle `s`; with `own`, two triangles of
## one operand (see cut_own_pairs), whose coplanar overlaps are left be.
func cut_pair(operands: const Operands*, t: usize, s: usize, out: PairOut*, own: bool = false) -> !:
if operands.inert(t) or operands.inert(s): return
let a = Corners.of(operands, t)
let b = Corners.of(operands, s)
let pa = operands.projections.items[t]
let pb = operands.projections.items[s]
var sb: i64[3] = [0, 0, 0]
var sa: i64[3] = [0, 0, 0]
for k in 0..<(usize)3: sb[k] = plane_side(a.at[0], a.at[1], a.at[2], b.at[k])
if apart(sb): return
for k in 0..<(usize)3: sa[k] = plane_side(b.at[0], b.at[1], b.at[2], a.at[k])
if apart(sa): return
if sb[0] == 0 and sb[1] == 0 and sb[2] == 0:
# A face of one operand lying beside another of its own (a flat
# region's triangles) only touches it: nothing to record.
if own and not overlapping(&a, &b, pa): return
try cut_coplanar(&a, &b, t, s, pa, out)
return
var found = Found()
try crossings(&a, &b, t, sb, pa, &found)
try crossings(&b, &a, s, sa, pb, &found)
if found.count == 0: return
if found.count > 2: error(errors.invalid, "Boolean: inconsistent cut (the pieces cross themselves?)")
# Two faces of one operand meeting only at a point they share do not
# cross: nothing to record (else every fan would spread the search).
if own and found.count == 1 and found.keys[0].kind == input_key and shares_point(&a, &b, (usize)found.keys[0].v[0]): return
for at in 0..<found.count:
try out.points.push(PointRecord((i32)t, found.keys[at], found.recipes[at]))
try out.points.push(PointRecord((i32)s, found.keys[at], found.recipes[at]))
if found.count == 2:
try out.segments.push(SegmentRecord((i32)t, found.keys[0], found.keys[1], (i32)s, -1))
try out.segments.push(SegmentRecord((i32)s, found.keys[0], found.keys[1], (i32)t, -1))
## Whether both triangles have point `p`.
func shares_point(a: const Corners*, b: const Corners*, p: usize) -> bool:
return (a.ids[0] == p or a.ids[1] == p or a.ids[2] == p) and (b.ids[0] == p or b.ids[1] == p or b.ids[2] == p)
## Whether coplanar triangles a and b overlap in more than a border: no
## edge line of either has the other wholly on its far side or on it.
func overlapping(a: const Corners*, b: const Corners*, projection: Projection) -> bool:
let sense_b = orient2d(b.at[0], b.at[1], b.at[2], projection.u, projection.v)
for k in 0..<(usize)3:
var apart_a = true
var apart_b = true
for j in 0..<(usize)3:
if orient2d(a.at[k], a.at[(k + 1) % 3], b.at[j], projection.u, projection.v) * projection.sense > 0: apart_a = false
if orient2d(b.at[k], b.at[(k + 1) % 3], a.at[j], projection.u, projection.v) * sense_b > 0: apart_b = false
if apart_a or apart_b: return false
return true
## Whether all three signs are the same and not zero.
func apart(signs: const i64[3]) -> bool:
return (signs[0] > 0 and signs[1] > 0 and signs[2] > 0) or (signs[0] < 0 and signs[1] < 0 and signs[2] < 0)
## Where `guest` (its points' sides of host's plane in `signs`) meets host
## triangle `h` (number `host`): its points on that plane inside h, and its
## edges crossing that plane inside h.
func crossings(h: const Corners*, guest: const Corners*, host: usize, signs: const i64[3], projection: Projection, found: Found*) -> !:
for k in 0..<(usize)3:
if signs[k] == 0 and inside_closed(h, guest.at[k], projection, projection.sense):
try found.add(point_key(guest.ids[k]), point_recipe(guest.ids[k]))
for k in 0..<(usize)3:
let j = (k + 1) % 3
if signs[k] * signs[j] >= 0: continue
try edge_through(h, host, guest.ids[k], guest.ids[j], guest.at[k], guest.at[j], found)
## Where edge u-w (points `u_id`, `w_id`), its ends strictly on opposite
## sides of h's plane, passes host triangle h (number `host`): inside it,
## on one of its edges, at one of its corners, or outside it (nothing).
func edge_through(h: const Corners*, host: usize, u_id: usize, w_id: usize, u: Vector3, w: Vector3, found: Found*) -> !:
var o: i64[3] = [0, 0, 0]
var zeros: usize = 0
var positive = false
var negative = false
for e in 0..<(usize)3:
o[e] = plane_side(u, w, h.at[e], h.at[(e + 1) % 3])
if o[e] == 0: zeros += 1
if o[e] > 0: positive = true
if o[e] < 0: negative = true
if positive and negative: return
let recipe = Recipe(crossing_recipe, (i32)u_id, (i32)w_id, (i32)h.ids[0], (i32)h.ids[1], (i32)h.ids[2])
if zeros == 0:
try found.add(edge_triangle(u_id, w_id, h.ids), recipe)
elif zeros == 1:
for e in 0..<(usize)3:
if o[e] == 0: try found.add(edge_edge(u_id, w_id, h.ids[e], h.ids[(e + 1) % 3]), recipe)
elif zeros == 2:
# On two edges' lines: the corner they share.
for e in 0..<(usize)3:
if o[e] != 0 and o[(e + 1) % 3] == 0 and o[(e + 2) % 3] == 0:
let corner = h.ids[(e + 2) % 3]
try found.add(point_key(corner), point_recipe(corner))
## Coplanar t and s: each one's points inside the other, and each one's
## edges clipped to the other as segments; where they overlap, they cover
## each other (see mark_cover).
func cut_coplanar(a: const Corners*, b: const Corners*, t: usize, s: usize, projection: Projection, out: PairOut*) -> !:
let sense_b = orient2d(b.at[0], b.at[1], b.at[2], projection.u, projection.v)
var touched = false
touched = try clip_edges(a, b, t, s, projection, projection.sense, sense_b, out) or touched
touched = try clip_edges(b, a, s, t, projection, sense_b, projection.sense, out) or touched
if touched:
try out.covers.push(CoverRecord((i32)t, (i32)s))
try out.covers.push(CoverRecord((i32)s, (i32)t))
## Edges of `g` (number `guest`) clipped to `h` (number `host`), as
## segments on host covered by guest, and g's points inside h. Whether
## anything was found.
func clip_edges(h: const Corners*, g: const Corners*, host: usize, guest: usize, projection: Projection, sense_h: i64, sense_g: i64, out: PairOut*) -> bool!:
var touched = false
for k in 0..<(usize)3:
if inside_closed(h, g.at[k], projection, sense_h):
try out.points.push(PointRecord((i32)host, point_key(g.ids[k]), point_recipe(g.ids[k])))
touched = true
for k in 0..<(usize)3:
let j = (k + 1) % 3
var found = Found()
let p = g.at[k]
let q = g.at[j]
if inside_closed(h, p, projection, sense_h): try found.add(point_key(g.ids[k]), point_recipe(g.ids[k]))
if inside_closed(h, q, projection, sense_h): try found.add(point_key(g.ids[j]), point_recipe(g.ids[j]))
for e in 0..<(usize)3:
let f = (e + 1) % 3
let r = h.at[e]
let s = h.at[f]
let or_ = orient2d(p, q, r, projection.u, projection.v)
let os = orient2d(p, q, s, projection.u, projection.v)
if or_ * os >= 0: continue
let op = orient2d(r, s, p, projection.u, projection.v)
let oq = orient2d(r, s, q, projection.u, projection.v)
if op * oq >= 0: continue
try found.add(edge_edge(g.ids[k], g.ids[j], h.ids[e], h.ids[f]), Recipe(meeting_recipe, (i32)g.ids[k], (i32)g.ids[j], (i32)h.ids[e], (i32)h.ids[f], (i32)projection.axis))
for e in 0..<(usize)3:
let r = h.at[e]
if orient2d(p, q, r, projection.u, projection.v) == 0 and strictly_between(p, q, r):
try found.add(point_key(h.ids[e]), point_recipe(h.ids[e]))
if found.count > 2: error(errors.invalid, "Boolean: inconsistent cut (the pieces cross themselves?)")
for at in 0..<found.count:
try out.points.push(PointRecord((i32)host, found.keys[at], found.recipes[at]))
if found.count > 0: touched = true
if found.count == 2:
try out.segments.push(SegmentRecord((i32)host, found.keys[0], found.keys[1], (i32)guest, (i32)g.ids[(k + 2) % 3]))
return touched
# mark: All pairs ==============================================================================
## A triangles in each range of the pair search.
let pair_chunk: usize = 256
struct PairWork:
let operands: const Operands*
let tree: const BoxTree*
var outs: PairOut[]
var found: Growing[u32][]
func pair_range(context: void*, index: usize, worker: usize) -> !:
let work = (PairWork*)context
let operands = work.operands
let first = index * pair_chunk
let end = first + pair_chunk if first + pair_chunk < operands.split else operands.split
let found = &work.found[worker]
for t in first..<end:
let a = operands.place(t, 0)
let b = operands.place(t, 1)
let c = operands.place(t, 2)
found.clear()
try work.tree.overlapping(lower(a, lower(b, c)), upper(a, upper(b, c)), operands.split, found)
for at in 0..<found.count:
try cut_pair(operands, t, (usize)found.items[at], &work.outs[index])
## Every pair of A and B triangles cut, the records gathered in A-triangle
## order (the same whatever the thread count).
func cut_all_pairs(operands: const Operands*, tree: const BoxTree*, out: PairOut*) -> !:
let chunks = (operands.split + pair_chunk - 1) // pair_chunk
if chunks == 0: return
let outs = try new PairOut[chunks] --- in memory.heap
for at in 0..<chunks: outs[at] = PairOut()
defer:
for at in 0..<chunks: outs[at].close()
free(outs) in memory.heap
let workers = parallel.workers(chunks)
let found = try new Growing[u32][workers] --- in memory.heap
for at in 0..<workers: found[at] = Growing[u32]()
defer:
for at in 0..<workers: found[at].close()
free(found) in memory.heap
var work = PairWork(operands, tree, outs, found)
try parallel.for_each(chunks, (void*)&work, pair_range)
for at in 0..<chunks:
for record in outs[at].points.view(): try out.points.push(record)
for record in outs[at].segments.view(): try out.segments.push(record)
for record in outs[at].covers.view(): try out.covers.push(record)