dymokomi/luce-cad
Source of release 0.9.1
0.9.1 / src / tessellation / cut_grid.lucb
## Polygon/cell intersection in a shared UV arrangement. Input trim chains must
## already be split at grid crossings: this keeps ownership of CAD seams in CAD.
## Whole cells remain quads; clipped cells retain their polygon boundary.
import memory
from luce_std import math
import interop
from luce_geocore.geocore import Vector3, Mesh, MeshBuilder, invalid
from tessellation.trim import TrimPolygon
import tessellation.cut_topology as topology
struct Segment:
var a: i64 = -1
var b: i64 = -1
var next: i64 = -1
var used: bool = false
## One cell's scratch, grown to the busiest cell: a cell may hold any number
## of trim segments and loops.
struct Cell:
var edges: Segment[]
var side_ids: i64[]
var side_values: f64[]
var paths: i64[]
var offsets: usize[]
var sizes: usize[]
var areas: f64[]
var mapped: i64[]
var loops: i64[]
var positions: Vector3[]
## Room for a cell of `trim` trim segments: they, and the grid side
## pieces between their endpoints (at most 1 + 2 * trim per side).
func reserve(trim: usize) -> !:
let edges = trim * 9 + 4
if edges <= self.edges.length: return
self.close()
let capacity = math.max((f64)edges, (f64)self.edges.length * 2.0)
let size = (usize)math.max(64.0, capacity)
self.edges = try new Segment[size] --- in memory.heap
self.side_ids = try new i64[size] --- in memory.heap
self.side_values = try new f64[size] --- in memory.heap
self.paths = try new i64[size] --- in memory.heap
self.offsets = try new usize[size] --- in memory.heap
self.sizes = try new usize[size] --- in memory.heap
self.areas = try new f64[size] --- in memory.heap
self.mapped = try new i64[size] --- in memory.heap
self.loops = try new i64[size + 1] --- in memory.heap
self.positions = try new Vector3[size] --- in memory.heap
func close():
if self.edges.length == 0: return
free(self.edges) in memory.heap
free(self.side_ids) in memory.heap
free(self.side_values) in memory.heap
free(self.paths) in memory.heap
free(self.offsets) in memory.heap
free(self.sizes) in memory.heap
free(self.areas) in memory.heap
free(self.mapped) in memory.heap
free(self.loops) in memory.heap
free(self.positions) in memory.heap
## Intersect an axis-aligned grid with an outer loop and holes. The first output
## vertices are exactly the input vertices, in order; no trim vertex is welded.
pub func cut_grid(points: const Vector3[], sizes: const i64[], us: const f64[], vs: const f64[], identities: const i64[]) -> interop.Reference[Mesh]!:
if us.length < 2 or vs.length < 2 or us.length * vs.length > 131072:
error(invalid, "trim grid exceeds layout budget")
if sizes.length == 0: error(invalid, "trim grid requires a loop")
for value in us:
if not math.is_finite(value): error(invalid, "nonfinite U grid station")
for value in vs:
if not math.is_finite(value): error(invalid, "nonfinite V grid station")
for p in points:
if not p.is_finite() or math.abs(p.z) > 1e-12: error(invalid, "trim grid requires finite UV points")
for at in 1..<us.length:
if us[at] <= us[at - 1]: error(invalid, "trim grid U stations must increase")
for at in 1..<vs.length:
if vs[at] <= vs[at - 1]: error(invalid, "trim grid V stations must increase")
let extent = math.max(us[us.length - 1] - us[0], vs[vs.length - 1] - vs[0])
let epsilon = math.max(1e-12, extent * 1e-7)
# CAD fitting tolerance is not topological equality. Near-tangent trim
# points must not be treated as lying on a grid side or on each other.
let incidence = math.max(1e-13, extent * 1e-12)
let aliases = try topology.identify(points, identities)
defer free(aliases) in memory.heap
let nx = us.length - 1
let ny = vs.length - 1
let heads = try new i64[nx * ny] --- in memory.heap
defer free(heads) in memory.heap
let grid = try new i64[us.length * vs.length] --- in memory.heap
defer free(grid) in memory.heap
let boundary = try new Segment[points.length] --- in memory.heap
defer free(boundary) in memory.heap
for at in 0..<heads.length: heads[at] = -1
for at in 0..<grid.length: grid[at] = -1
var mesh = try MeshBuilder(precise = true)
defer mesh.close()
for p in points: _ = try mesh.point(p)
var offset: usize = 0
for loop in 0..<sizes.length:
if sizes[loop] < 3 or (usize)sizes[loop] > points.length - offset: error(invalid, "invalid trim grid loop")
let count = (usize)sizes[loop]
var area: f64 = 0.0
for at in 0..<count: area += points[offset + at].cross(points[offset + (at + 1) % count]).z
let forward = (area > 0.0) == (loop == 0)
for at in 0..<count:
let ai = offset + at
let bi = offset + (at + 1) % count
let a = points[ai if forward else bi]
let b = points[bi if forward else ai]
let mid = a.add(b).multiply_scalar(0.5)
let x = owner(us, mid.x, a.y > b.y, incidence) if math.abs(a.x - b.x) < incidence else cell(us, mid.x)
let y = owner(vs, mid.y, b.x > a.x, incidence) if math.abs(a.y - b.y) < incidence else cell(vs, mid.y)
if x >= nx or y >= ny: error(invalid, "trim lies outside grid")
if math.min(a.x, b.x) < us[x] - epsilon or math.max(a.x, b.x) > us[x + 1] + epsilon or math.min(a.y, b.y) < vs[y] - epsilon or math.max(a.y, b.y) > vs[y + 1] + epsilon:
error(invalid, "trim edge crosses an unsplit grid line")
boundary[ai] = Segment(aliases[ai if forward else bi], aliases[bi if forward else ai], heads[y * nx + x])
heads[y * nx + x] = (i64)ai
let gx = nearest(us, points[ai].x)
let gy = nearest(vs, points[ai].y)
if math.abs(us[gx] - points[ai].x) < incidence and math.abs(vs[gy] - points[ai].y) < incidence:
let previous = grid[gy * us.length + gx]
if previous >= 0 and previous != aliases[ai]:
error(invalid, "distinct trim vertices coincide on grid")
grid[gy * us.length + gx] = aliases[ai]
offset += count
if offset != points.length: error(invalid, "trim grid loops do not cover vertices")
var scratch = Cell()
defer scratch.close()
let crossings = try new f64[points.length] --- in memory.heap
defer free(crossings) in memory.heap
for row in 0..<ny:
# One scanline classification per row replaces O(cells * trim vertices)
# point-in-polygon tests for the overwhelmingly common untouched cells.
let crossing_count = scanline(points, sizes, (vs[row] + vs[row + 1]) * 0.5, crossings)
for col in 0..<nx:
let corners = [Vector3(us[col], vs[row], 0.0), Vector3(us[col + 1], vs[row], 0.0), Vector3(us[col + 1], vs[row + 1], 0.0), Vector3(us[col], vs[row + 1], 0.0)]
let corner_grid = [row * us.length + col, row * us.length + col + 1, (row + 1) * us.length + col + 1, (row + 1) * us.length + col]
let center = corners[0].add(corners[2]).multiply_scalar(0.5)
var length: usize = 0
var current = heads[row * nx + col]
var trim: usize = 0
while current >= 0:
trim += 1
current = boundary[(usize)current].next
try scratch.reserve(trim)
let edges = scratch.edges
let side_ids = scratch.side_ids
let side_values = scratch.side_values
current = heads[row * nx + col]
while current >= 0:
let segment = boundary[(usize)current]
try add(edges, &length, segment.a, segment.b)
current = segment.next
if length == 0:
if not row_inside(crossings[..<crossing_count], center.x): continue
try mesh.face(4)
for at in 0..<(usize)4: try mesh.corner(try grid_point(&mesh, grid, corner_grid[at], corners[at]))
continue
let trim_count = length
for side in 0..<(usize)4:
let a = corners[side]
let b = corners[(side + 1) % 4]
let delta = b.subtract(a)
var count: usize = 2
side_ids[0] = -1 - (i64)corner_grid[side]
side_ids[1] = -1 - (i64)corner_grid[(side + 1) % 4]
side_values[0] = 0.0
side_values[1] = 1.0
for index in 0..<trim_count:
for id in [edges[index].a, edges[index].b]:
let p = points[(usize)id]
let t = p.subtract(a).dot(delta) / delta.dot(delta)
if t < -incidence or t > 1.0 + incidence or math.abs(delta.cross(p.subtract(a)).z) > incidence * delta.length(): continue
var duplicate = false
for at in 0..<count:
if math.abs(side_values[at] - t) * delta.length() < incidence:
if side_ids[at] >= 0 and side_ids[at] != id: error(invalid, "distinct trim vertices coincide on a grid side")
side_ids[at] = id
duplicate = true
break
if duplicate: continue
if count == side_ids.length: error(invalid, "trim cell side exceeds budget")
var at = count
while at > 0 and side_values[at - 1] > t:
side_values[at] = side_values[at - 1]
side_ids[at] = side_ids[at - 1]
at -= 1
side_values[at] = t
side_ids[at] = id
count += 1
for at in 0..<count - 1:
let p = a.add(delta.multiply_scalar((side_values[at] + side_values[at + 1]) * 0.5))
if not inside(points, sizes, Vector3(inward(p.x, center.x), inward(p.y, center.y), 0.0)): continue
let start = try resolve(&mesh, grid, us, vs, side_ids[at])
let end = try resolve(&mesh, grid, us, vs, side_ids[at + 1])
try add(edges, &length, start, end)
try emit(&mesh, &scratch, length, epsilon)
let result = try mesh.finish()
errdefer result.release()
try topology.audit(result.value(), sizes, aliases)
return result
func add(edges: Segment[], length: usize*, a: i64, b: i64) -> !:
if a == b: return
for at in 0..<*length:
if edges[at].a == a and edges[at].b == b: return
if *length == edges.length: error(invalid, "trim cell exceeds segment budget")
edges[*length] = Segment(a, b)
*length += 1
func resolve(mesh: MeshBuilder*, grid: i64[], us: const f64[], vs: const f64[], id: i64) -> i64!:
if id >= 0: return id
let at = (usize)(-id - 1)
return try grid_point(mesh, grid, at, Vector3(us[at % us.length], vs[at // us.length], 0.0))
func grid_point(mesh: MeshBuilder*, grid: i64[], at: usize, p: Vector3) -> i64!:
if grid[at] < 0: grid[at] = try mesh.point(p)
return grid[at]
## Locate stations without a linear scan in the inner clipping loop.
pub func cell(values: const f64[], p: f64) -> usize:
var low: usize = 0
var high = values.length - 1
while high - low > 1:
let mid = (low + high) // 2
if values[mid] <= p: low = mid
else: high = mid
return low
func nearest(values: const f64[], p: f64) -> usize:
let at = cell(values, p)
return at if math.abs(values[at] - p) < math.abs(values[at + 1] - p) else at + 1
func owner(values: const f64[], p: f64, positive: bool, epsilon: f64) -> usize:
let line = nearest(values, p)
if math.abs(values[line] - p) >= epsilon: return cell(values, p)
if positive: return line
return line - 1 if line > 0 else values.length - 1
func inward(value: f64, center: f64) -> f64:
let delta = center - value
let distance = math.min(math.abs(delta) * 0.5, math.max(math.abs(delta) * 1e-12, (math.abs(value) + 1.0) * 2e-15))
return value + distance if delta > 0.0 else value - distance
func inside(points: const Vector3[], sizes: const i64[], p: Vector3) -> bool:
var result = false
var offset: usize = 0
for size in sizes:
for at in 0..<(usize)size:
let a = points[offset + at]
let b = points[offset + (at + 1) % (usize)size]
if (a.y > p.y) != (b.y > p.y) and p.x < a.x + (b.x - a.x) * (p.y - a.y) / (b.y - a.y): result = not result
offset += (usize)size
return result
func scanline(points: const Vector3[], sizes: const i64[], y: f64, values: f64[]) -> usize:
var count: usize = 0
var offset: usize = 0
for size in sizes:
for at in 0..<(usize)size:
let a = points[offset + at]
let b = points[offset + (at + 1) % (usize)size]
if (a.y > y) == (b.y > y): continue
let x = a.x + (b.x - a.x) * (y - a.y) / (b.y - a.y)
var index = count
while index > 0 and values[index - 1] > x:
values[index] = values[index - 1]
index -= 1
values[index] = x
count += 1
offset += (usize)size
return count
func row_inside(crossings: const f64[], x: f64) -> bool:
var low: usize = 0
var high = crossings.length
while low < high:
let mid = (low + high) // 2
if crossings[mid] <= x: low = mid + 1
else: high = mid
return (crossings.length - low) % 2 == 1
## Walk the cell's first `length` segments into loops and emit each outer
## loop, with the holes it encloses, as faces. A loop without holes stays one
## face of any size (geocore triangulates it for display).
func emit(mesh: MeshBuilder*, scratch: Cell*, length: usize, epsilon: f64) -> !:
let edges = scratch.edges[..<length]
let paths = scratch.paths
let offsets = scratch.offsets
let sizes = scratch.sizes
let areas = scratch.areas
var count: usize = 0
var written: usize = 0
for edge in 0..<edges.length:
if edges[edge].used: continue
if count == sizes.length: error(invalid, "trim cell exceeds loop budget")
offsets[count] = written
var current = edge
var area: f64 = 0.0
while true:
if edges[current].used or written == paths.length: error(invalid, "invalid trim cell cycle")
let a = edges[current].a
let b = edges[current].b
paths[written] = a
written += 1
edges[current].used = true
area += mesh.points[(usize)a].cross(mesh.points[(usize)b]).z
if b == edges[edge].a: break
var next = edges.length
var best: f64 = -4.0
let direction = mesh.points[(usize)b].subtract(mesh.points[(usize)a])
for candidate in 0..<edges.length:
if edges[candidate].used or edges[candidate].a != b: continue
let d = mesh.points[(usize)edges[candidate].b].subtract(mesh.points[(usize)b])
let angle = math.atan2(direction.cross(d).z, direction.dot(d))
if angle > best:
next = candidate
best = angle
if next == edges.length:
error(invalid, "open trim cell boundary")
current = next
sizes[count] = written - offsets[count]
areas[count] = area
count += 1
for loop in 0..<count:
if areas[loop] <= epsilon * epsilon: continue
let positions = scratch.positions
let mapped = scratch.mapped
let loops = scratch.loops
var nc: usize = 0
var nl: usize = 0
for candidate in 0..<count:
if candidate != loop:
if areas[candidate] >= 0.0: continue
let p = mesh.points[(usize)paths[offsets[candidate]]]
var enclosed = false
for at in 0..<sizes[loop]:
let a = mesh.points[(usize)paths[offsets[loop] + at]]
let b = mesh.points[(usize)paths[offsets[loop] + (at + 1) % sizes[loop]]]
if (a.y > p.y) != (b.y > p.y) and p.x < a.x + (b.x - a.x) * (p.y - a.y) / (b.y - a.y): enclosed = not enclosed
if not enclosed: continue
# Outer loop must precede holes, regardless of graph traversal order.
if candidate == loop: continue
loops[nl + 1] = (i64)sizes[candidate]
for at in 0..<sizes[candidate]:
let id = paths[offsets[candidate] + at]
mapped[sizes[loop] + nc] = id
positions[sizes[loop] + nc] = mesh.points[(usize)id]
nc += 1
nl += 1
if sizes[loop] < 3: error(invalid, "trim cell cycle has fewer than three vertices")
if nl == 0:
try mesh.face((i64)sizes[loop])
for at in 0..<sizes[loop]: try mesh.corner(paths[offsets[loop] + at])
else:
loops[0] = (i64)sizes[loop]
for at in 0..<sizes[loop]:
mapped[at] = paths[offsets[loop] + at]
positions[at] = mesh.points[(usize)mapped[at]]
let part = try TrimPolygon.triangulate(positions[..<sizes[loop] + nc], loops[..<nl + 1], Vector3(0.0, 0.0, 1.0))
defer part.release()
for face in 0..<part.value().face_count():
try mesh.face(3)
for at in 0..<3: try mesh.corner(mapped[(usize)(try part.value().face_point(face, at))])