dymokomi/luce-geocore
Source of release 0.7.8
0.7.8 / src / booleans / crossings.lucb
# mark: Cuts crossing inside a face ============================================================
# In a solid's face the cuts never cross: two of them would mean the other
# solid cuts itself. Rounded points of an earlier cut can make that happen
# by a hair, so crossings are found here, exactly, before triangulating,
# and named by what meets there: three triangles' planes (Cramer's rule on
# their exact normals), or a covering triangle's edge through a triangle.
# Each of the triangles involved finds the same crossing in its own
# triangulation, by the same name, so the cut stays closed.
let three_planes_key: u8 = 3
let three_planes_recipe: u8 = 3
## The point where triangles a, b and c's planes meet, named by their
## points the same whichever of them (or their exact doubles) it is found
## in, and built from the triangles a, b, c.
func three_planes(operands: const Operands*, a: usize, b: usize, c: usize) -> (PointKey, Recipe):
var triples: usize[3][3] = ---
let triangles: usize[3] = [a, b, c]
for k in 0..<(usize)3:
let corners: usize[3] = [operands.vertex(triangles[k], 0), operands.vertex(triangles[k], 1), operands.vertex(triangles[k], 2)]
triples[k] = sorted_three(corners)
# The triples in order.
for i in 0..<(usize)2:
for j in 0..<(usize)(2 - i):
if triple_less(triples[j + 1], triples[j]):
let swap = triples[j]
triples[j] = triples[j + 1]
triples[j + 1] = swap
var v: i32[9] = ---
for k in 0..<(usize)9: v[k] = (i32)triples[k // 3][k % 3]
return (PointKey(three_planes_key, v), Recipe(three_planes_recipe, (i32)a, (i32)b, (i32)c, 0, 0))
func triple_less(x: usize[3], y: usize[3]) -> bool:
for k in 0..<(usize)3:
if x[k] != y[k]: return x[k] < y[k]
return false
struct CrossingWork:
let operands: const Operands*
let cut: const Cut*
let table: const PointTable*
var arenas: Arena[]
var outs: Growing[PointRecord][]
func crossing_slot(context: void*, slot: usize, worker: usize) -> !:
let work = (CrossingWork*)context
let arena = &work.arenas[worker]
let cut = work.cut
let operands = work.operands
let host = (usize)cut.triangles.items[slot]
let projection = operands.projections.items[host]
let first = (usize)cut.segment_starts.items[slot]
let end = (usize)cut.segment_starts.items[slot + 1]
for i in first..<end:
let one = cut.segments.items[i]
let p = work.table.point((usize)one.first)
let q = work.table.point((usize)one.second)
for j in i + 1..<end:
let other = cut.segments.items[j]
if other.first == one.first or other.first == one.second or other.second == one.first or other.second == one.second: continue
let r = work.table.point((usize)other.first)
let s = work.table.point((usize)other.second)
if apart_boxes(&p, &q, &r, &s): continue
let mark = arena.mark()
defer arena.reset(mark)
if (try orient2d_h(arena, &p, &q, &r, projection.u, projection.v)) * (try orient2d_h(arena, &p, &q, &s, projection.u, projection.v)) >= 0: continue
if (try orient2d_h(arena, &r, &s, &p, projection.u, projection.v)) * (try orient2d_h(arena, &r, &s, &q, projection.u, projection.v)) >= 0: continue
try work.outs[slot].push(try crossing_point(operands, host, one, other))
## Whether the boxes of segments pq and rs miss each other.
func apart_boxes(p: const HPoint*, q: const HPoint*, r: const HPoint*, s: const HPoint*) -> bool:
for axis in 0..<(usize)3:
let a = p.near.coordinate(axis)
let b = q.near.coordinate(axis)
let c = r.near.coordinate(axis)
let d = s.near.coordinate(axis)
let slack = p.slack + q.slack + r.slack + s.slack
if math.max(a, b) + slack < math.min(c, d) or math.max(c, d) + slack < math.min(a, b): return true
return false
## The point where segments `one` and `other` cross inside triangle `host`.
func crossing_point(operands: const Operands*, host: usize, one: CutSegment, other: CutSegment) -> PointRecord!:
if one.opposite < 0 and other.opposite < 0:
let (key, recipe) = three_planes(operands, host, (usize)one.source, (usize)other.source)
return PointRecord((i32)host, key, recipe)
if one.opposite >= 0 and other.opposite >= 0:
# Two coplanar triangles' edges crossing in this plane.
let e = edge_off(operands, (usize)one.source, one.opposite)
let f = edge_off(operands, (usize)other.source, other.opposite)
let along = operands.projections.items[host]
return PointRecord((i32)host, edge_edge(e[0], e[1], f[0], f[1]), Recipe(meeting_recipe, (i32)e[0], (i32)e[1], (i32)f[0], (i32)f[1], (i32)along.axis))
let cover = one if one.opposite >= 0 else other
let crossing = other if one.opposite >= 0 else one
# The covering triangle's edge (its points but the far one) through the
# crossing segment's source triangle.
let ends = edge_off(operands, (usize)cover.source, cover.opposite)
let s = (usize)crossing.source
let h = Corners.of(operands, s)
let u = operands.points.items[ends[0]]
let w = operands.points.items[ends[1]]
let su = plane_side(h.at[0], h.at[1], h.at[2], u)
let sw = plane_side(h.at[0], h.at[1], h.at[2], w)
if su * sw >= 0: error(errors.invalid, "Boolean: inconsistent cut (a crossing off its plane)")
var found = Found()
try edge_through(&h, s, ends[0], ends[1], u, w, &found)
if found.count != 1: error(errors.invalid, "Boolean: inconsistent cut (a crossing outside its face)")
return PointRecord((i32)host, found.keys[0], found.recipes[0])
## The points of triangle `t` but `opposite`: the edge facing it.
func edge_off(operands: const Operands*, t: usize, opposite: i32) -> usize[2]:
var ends: usize[2] = [0, 0]
var count: usize = 0
for k in 0..<(usize)3:
let point = operands.vertex(t, k)
if (i32)point != opposite and count < 2:
ends[count] = point
count += 1
return ends
## Find where cut segments cross inside their triangles; their points are
## added to `records` (in triangle order). Whether there were any.
func find_crossings(operands: const Operands*, cut: const Cut*, table: const PointTable*, records: PairOut*) -> bool!:
let slots = cut.triangles.count
if slots == 0: return false
let workers = parallel.workers(slots)
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
let outs = try new Growing[PointRecord][slots] --- in memory.heap
for at in 0..<slots: outs[at] = Growing[PointRecord]()
defer:
for at in 0..<slots: outs[at].close()
free(outs) in memory.heap
var work = CrossingWork(operands, cut, table, arenas, outs)
try parallel.for_each(slots, (void*)&work, crossing_slot)
var any = false
for at in 0..<slots:
for record in outs[at].view():
try records.points.push(record)
any = true
return any
## The point where triangles a, b and c's planes meet, as homogeneous
## coordinates by Cramer's rule: each plane n . x = n . (a corner).
func three_planes_coordinates(arena: Arena*, operands: const Operands*, a: usize, b: usize, c: usize) -> Homogeneous!:
var rows: Plane[3] = ---
let triangles: usize[3] = [a, b, c]
for k in 0..<(usize)3: rows[k] = try plane_of(arena, operands, triangles[k])
let w = try determinant3(arena, rows[0].x, rows[0].y, rows[0].z, rows[1].x, rows[1].y, rows[1].z, rows[2].x, rows[2].y, rows[2].z)
let x = try determinant3(arena, rows[0].d, rows[0].y, rows[0].z, rows[1].d, rows[1].y, rows[1].z, rows[2].d, rows[2].y, rows[2].z)
let y = try determinant3(arena, rows[0].x, rows[0].d, rows[0].z, rows[1].x, rows[1].d, rows[1].z, rows[2].x, rows[2].d, rows[2].z)
let z = try determinant3(arena, rows[0].x, rows[0].y, rows[0].d, rows[1].x, rows[1].y, rows[1].d, rows[2].x, rows[2].y, rows[2].d)
if expansion_sign(w) == 0: error(errors.invalid, "Boolean: inconsistent cut (three crossing planes with no one point)")
return Homogeneous(x, y, z, w)
## A triangle's plane n . x = d, exactly.
struct Plane:
var x: f64[]
var y: f64[]
var z: f64[]
var d: f64[]
func plane_of(arena: Arena*, operands: const Operands*, t: usize) -> Plane!:
var normals: f64[48] = ---
let p = operands.place(t, 0)
let (lx, ly, lz) = normal_exact(p, operands.place(t, 1), operands.place(t, 2), normals[..<48])
let x = try arena.take(lx)
let y = try arena.take(ly)
let z = try arena.take(lz)
for at in 0..<lx: x[at] = normals[at]
for at in 0..<ly: y[at] = normals[16 + at]
for at in 0..<lz: z[at] = normals[32 + at]
let d = try arena_sum(arena, try arena_sum(arena, try arena_scale(arena, x, p.x), try arena_scale(arena, y, p.y)), try arena_scale(arena, z, p.z))
return Plane(x, y, z, d)
## The determinant of a 3 by 3 matrix of expansions, by rows.
func determinant3(arena: Arena*, a: const f64[], b: const f64[], c: const f64[], d: const f64[], e: const f64[], f: const f64[], g: const f64[], h: const f64[], i: const f64[]) -> f64[]!:
let ei_fh = try arena_difference(arena, try arena_product(arena, e, i), try arena_product(arena, f, h))
let di_fg = try arena_difference(arena, try arena_product(arena, d, i), try arena_product(arena, f, g))
let dh_eg = try arena_difference(arena, try arena_product(arena, d, h), try arena_product(arena, e, g))
let total = try arena_sum(arena, try arena_difference(arena, try arena_product(arena, a, ei_fh), try arena_product(arena, b, di_fg)), try arena_product(arena, c, dh_eg))
return total[..<expansion_compress(total)]