dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / polygons / grid_lattice.lucb
## Point location for lattice insertion (grid.lucb's insert_grid): which
## lattice points lie inside the trim (even-odd along each lattice row,
## against the triangulation's boundary, which insertion never splits),
## which lie next to a boundary point (one bucket per lattice cell), and the
## triangle holding a point (a walk across neighbors from the last one).
## Each answer is what scanning every point or triangle would give, at the
## cost of a few neighbors: a 64-division face's lattice has 65536 cells.
## A triangle mesh's neighbors as it is split: `across[f * 3 + k]` is the
## triangle across corner k's edge (k to k + 1) of triangle f, or -1 on the
## boundary (and where more than two triangles meet).
struct Neighbors:
var across: Growing[i64]
## Neighbors of `mesh`'s triangles, from its corners.
static func of(mesh: const MeshBuilder*) -> Neighbors!:
var made = Neighbors(across = Growing[i64]())
errdefer made.close()
try made.across.fill(mesh.nf * 3, -1)
let keys = try new u64[mesh.nf * 3] --- in memory.heap
defer free(keys) in memory.heap
let order = try new i64[keys.length] --- in memory.heap
defer free(order) in memory.heap
for slot in 0..<keys.length: keys[slot] = edge_key(mesh, slot)
try sort.order(keys, order)
var at: usize = 0
while at < order.length:
var end = at + 1
while end < order.length and keys[(usize)order[end]] == keys[(usize)order[at]]: end += 1
let first = (usize)order[at]
if end == at + 2 and opposed(mesh, first, (usize)order[at + 1]):
made.across.items[first] = (i64)(order[at + 1] // 3)
made.across.items[(usize)order[at + 1]] = (i64)(first // 3)
at = end
return made
func close():
self.across.close()
## Room for a triangle appended to the mesh (its neighbors set later).
func grow() -> !:
try self.across.push(-1)
try self.across.push(-1)
try self.across.push(-1)
func set(face: usize, values: const i64[]):
for k in 0..<(usize)3: self.across.items[face * 3 + k] = values[k]
## Triangle `face`'s slot whose edge runs from `a` to `b` (3: none).
func slot(mesh: const MeshBuilder*, face: usize, a: i64, b: i64) -> usize:
for k in 0..<(usize)3:
if mesh.corners[face * 3 + k] == a and mesh.corners[face * 3 + (k + 1) % 3] == b: return k
return 3
## Triangle `face` (if any) now has `value` across its edge from `a` to `b`.
func relink(mesh: const MeshBuilder*, face: i64, a: i64, b: i64, value: i64):
if face < 0: return
let k = self.slot(mesh, (usize)face, a, b)
if k < 3: self.across.items[(usize)face * 3 + k] = value
## Corner slot `slot`'s edge, either way round.
func edge_key(mesh: const MeshBuilder*, slot: usize) -> u64:
let a = (u64)mesh.corners[slot]
let b = (u64)mesh.corners[slot - slot % 3 + (slot % 3 + 1) % 3]
return (a << 32) | b if a < b else (b << 32) | a
## Whether two slots of one edge run opposite ways (consistently wound).
func opposed(mesh: const MeshBuilder*, first: usize, second: usize) -> bool:
return mesh.corners[first] != mesh.corners[second]
## The lattice's cells, their boundary points, and the boundary's
## crossings of the current lattice row.
struct Lattice:
var origin: Vector3
var u: Vector3
var v: Vector3
var umin: f64
var vmin: f64
var spacing: f64
var vertical: f64
var columns: usize
var rows: usize
## Each cell's first boundary point and each point's next in its cell.
var heads: i64[]
var next: i64[]
## Boundary segments in lattice coordinates (u0, v0, u1, v1 each).
var segments: Growing[f64]
## The sides a lattice point must keep clear of (the boundary's and the
## seams the constraints keep), as `segments`; each cell's first entry
## of those passing within a quarter cell of it, each entry's side and
## next entry in its cell.
var sides: Growing[f64]
var side_heads: i64[]
var side_of: Growing[i64]
var side_next: Growing[i64]
## The current row's crossings, ascending, and how many lie before the
## last column asked about.
var crossings: Growing[f64]
var passed: usize = 0
func close():
if self.heads.length > 0: free(self.heads) in memory.heap
if self.next.length > 0: free(self.next) in memory.heap
if self.side_heads.length > 0: free(self.side_heads) in memory.heap
self.sides.close()
self.side_of.close()
self.side_next.close()
self.segments.close()
self.crossings.close()
## Point `p`'s lattice coordinates.
func at(p: Vector3) -> Vector3:
let relative = p.subtract(self.origin)
return Vector3(relative.dot(self.u), relative.dot(self.v), 0.0)
## Ready for row `row`: its boundary crossings sorted.
func start_row(row: usize) -> !:
let y = self.vmin + ((f64)row + 0.5) * self.vertical
self.crossings.clear()
self.passed = 0
var at: usize = 0
while at < self.segments.count:
let s = self.segments.items[at..<at + 4]
if (s[1] > y) != (s[3] > y): try self.crossings.push(s[0] + (y - s[1]) * (s[2] - s[0]) / (s[3] - s[1]))
at += 4
sort.sort(self.crossings.items[..<self.crossings.count])
## Whether column `column` of the current row is inside the trim
## (columns asked in ascending order).
func inside(column: usize) -> bool:
let x = self.umin + ((f64)column + 0.5) * self.spacing
while self.passed < self.crossings.count and self.crossings.items[self.passed] < x: self.passed += 1
return self.passed % 2 == 1
## Whether a boundary point lies within a fifth of a cell of cell
## (`column`, `row`)'s center (such a point lies in that cell).
func near(mesh: const MeshBuilder*, column: usize, row: usize, p: Vector3) -> bool:
var point = self.heads[row * self.columns + column]
while point >= 0:
let relative = mesh.points[(usize)point].subtract(p)
if math.abs(relative.dot(self.u)) < self.spacing * 0.2 and math.abs(relative.dot(self.v)) < self.vertical * 0.2: return true
point = self.next[(usize)point]
return false
## Whether `p` (the center of cell `column`, `row`) lies within a
## quarter of a cell of a kept side and inside its 120-degree lens
## (seeing it at more than 120 degrees): a point there makes a needle
## against the side, whichever triangle it lands in (a long trim side
## passing a hair from the lattice, as a sphere's equator does by a
## hole's rim).
func beside_side(column: usize, row: usize, p: Vector3) -> bool:
let q = self.at(p)
let reach = math.min(self.spacing, self.vertical) * 0.25
var entry = self.side_heads[row * self.columns + column]
while entry >= 0:
let at = (usize)self.side_of.items[(usize)entry] * 4
let ax = self.sides.items[at] - q.x
let ay = self.sides.items[at + 1] - q.y
let bx = self.sides.items[at + 2] - q.x
let by = self.sides.items[at + 3] - q.y
let length = math.hypot(bx - ax, by - ay)
if math.abs(ax * by - ay * bx) <= reach * length and ax * bx + ay * by < -0.5 * math.hypot(ax, ay) * math.hypot(bx, by): return true
entry = self.side_next.items[(usize)entry]
return false
## The lattice over `mesh`'s points (all on its boundary: none inserted
## yet), its boundary segments those of an odd number of triangles.
func lattice(mesh: const MeshBuilder*, neighbors: const Neighbors*, origin: Vector3, u: Vector3, v: Vector3, umin: f64, vmin: f64, spacing: f64, vertical: f64, columns: usize, rows: usize, constraints: TrimConstraints) -> Lattice!:
var made = Lattice(origin = origin, u = u, v = v, umin = umin, vmin = vmin, spacing = spacing, vertical = vertical, columns = columns, rows = rows, heads = try new i64[columns * rows] --- in memory.heap, next = try new i64[mesh.np] --- in memory.heap, segments = Growing[f64](), sides = Growing[f64](), side_heads = try new i64[columns * rows] --- in memory.heap, side_of = Growing[i64](), side_next = Growing[i64](), crossings = Growing[f64]())
errdefer made.close()
for at in 0..<made.heads.length: made.heads[at] = -1
for point in 0..<mesh.np:
made.next[point] = -1
let p = made.at(mesh.points[point])
let column = math.floor((p.x - umin) / spacing)
let row = math.floor((p.y - vmin) / vertical)
if column < 0.0 or row < 0.0 or column >= (f64)columns or row >= (f64)rows: continue
let bucket = (usize)row * columns + (usize)column
made.next[point] = made.heads[bucket]
made.heads[bucket] = (i64)point
# A seam traced both ways meets itself: its slots link (neighbors), so
# only unlinked slots bound the trim. More than two triangles on an edge
# count by parity: each unlinked slot is a boundary segment, and a pair
# of them over one edge cancels in the even-odd count.
for slot in 0..<mesh.nf * 3:
let ia = mesh.corners[slot]
let ib = mesh.corners[slot - slot % 3 + (slot % 3 + 1) % 3]
let open = neighbors.across.items[slot] < 0
if not open and not constraints.contains(ia, ib): continue
let a = made.at(mesh.points[(usize)ia])
let b = made.at(mesh.points[(usize)ib])
for value in [a.x, a.y, b.x, b.y]:
if open: try made.segments.push(value)
try made.sides.push(value)
# Each segment in the cells its box reaches, a quarter cell wider.
for at in 0..<made.side_heads.length: made.side_heads[at] = -1
let reach = math.min(spacing, vertical) * 0.25
for segment in 0..<made.sides.count // 4:
let s = made.sides.items[segment * 4..<segment * 4 + 4]
let first_column = math.max(0.0, math.floor((math.min(s[0], s[2]) - reach - umin) / spacing))
let last_column = math.min((f64)columns - 1.0, math.floor((math.max(s[0], s[2]) + reach - umin) / spacing))
let first_row = math.max(0.0, math.floor((math.min(s[1], s[3]) - reach - vmin) / vertical))
let last_row = math.min((f64)rows - 1.0, math.floor((math.max(s[1], s[3]) + reach - vmin) / vertical))
if first_column > last_column or first_row > last_row: continue
for row in (usize)first_row..<(usize)last_row + 1:
for column in (usize)first_column..<(usize)last_column + 1:
let bucket = row * columns + column
try made.side_next.push(made.side_heads[bucket])
made.side_heads[bucket] = (i64)made.side_of.count
try made.side_of.push((i64)segment)
return made
## A triangle holding `p` (no side more than `epsilon` outside; a point on
## a side may get either triangle beside it, and the caller splits both),
## walked to across neighbors from `start`; -1 when the walk meets the
## boundary or runs too long (the caller then scans every triangle).
func walk(mesh: const MeshBuilder*, neighbors: const Neighbors*, start: i64, p: Vector3, n: Vector3, epsilon: f64) -> i64:
var face = start
for step in 0..<most_steps:
let at = (usize)face * 3
let pa = mesh.points[(usize)mesh.corners[at]]
let pb = mesh.points[(usize)mesh.corners[at + 1]]
let pc = mesh.points[(usize)mesh.corners[at + 2]]
let sides = [pb.subtract(pa).cross(p.subtract(pa)).dot(n), pc.subtract(pb).cross(p.subtract(pb)).dot(n), pa.subtract(pc).cross(p.subtract(pc)).dot(n)]
var leave: usize = 3
var worst = -epsilon
for k in 0..<(usize)3:
if sides[k] < worst:
worst = sides[k]
leave = k
if leave == 3: return face
face = neighbors.across.items[at + leave]
if face < 0: return -1
return -1
## The first triangle (in order) holding `p` within `epsilon`, or -1.
func scan_triangles(mesh: const MeshBuilder*, p: Vector3, n: Vector3, epsilon: f64) -> i64:
for face in 0..<mesh.nf:
let pa = mesh.points[(usize)mesh.corners[face * 3]]
let pb = mesh.points[(usize)mesh.corners[face * 3 + 1]]
let pc = mesh.points[(usize)mesh.corners[face * 3 + 2]]
if pb.subtract(pa).cross(p.subtract(pa)).dot(n) < -epsilon or pc.subtract(pb).cross(p.subtract(pb)).dot(n) < -epsilon or pa.subtract(pc).cross(p.subtract(pc)).dot(n) < -epsilon: continue
return (i64)face
return -1
## A walk longer than this (round a concave trim's notch) gives way to a scan.
let most_steps: usize = 4096