dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / polygons / 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.
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 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
# Trim vertices lying on one cell side, per cell. A tangent extremum
# touches a cell that none of its segments enter; that cell must still
# split its side there, or the arrangement gets a T-junction.
let touch_heads = try new i64[nx * ny] --- in memory.heap
defer free(touch_heads) in memory.heap
let touches = try new Segment[points.length * 2] --- in memory.heap
defer free(touches) in memory.heap
var touch_count: usize = 0
for at in 0..<heads.length:
heads[at] = -1
touch_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_line(us, points[ai].x)
let gy = nearest_line(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]
else:
touch_count = touch(us, vs, points[ai], aliases[ai], incidence, touch_heads, touches, touch_count)
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
current = touch_heads[row * nx + col]
while current >= 0:
trim += 1
current = touches[(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 and touch_heads[row * nx + col] < 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 corner_side in 0..<(usize)4:
let a = corners[corner_side]
let b = corners[(corner_side + 1) % 4]
let delta = b.subtract(a)
var count: usize = 2
side_ids[0] = -1 - (i64)corner_grid[corner_side]
side_ids[1] = -1 - (i64)corner_grid[(corner_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]: try place(points, id, a, delta, incidence, side_ids, side_values, &count)
var touching = touch_heads[row * nx + col]
while touching >= 0:
try place(points, touches[(usize)touching].a, a, delta, incidence, side_ids, side_values, &count)
touching = touches[(usize)touching].next
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_loops(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 audit(result.value(), sizes, aliases)
return result
## Insert trim vertex `id` into the sorted pieces of the grid side from `a`
## along `delta` if it lies on that side; one vertex per side position.
func place(points: const Vector3[], id: i64, a: Vector3, delta: Vector3, incidence: f64, side_ids: i64[], side_values: f64[], count: usize*) -> !:
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(): return
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
return
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
## Register a trim vertex lying on exactly one grid line with the two cells
## sharing that side (grid corners are identified through `grid` instead).
func touch(us: const f64[], vs: const f64[], p: Vector3, id: i64, incidence: f64, heads: i64[], touches: Segment[], count: usize) -> usize:
let nx = us.length - 1
let gx = nearest_line(us, p.x)
let gy = nearest_line(vs, p.y)
var result = count
if math.abs(us[gx] - p.x) < incidence:
let row = cell(vs, p.y)
for col in [gx - 1 if gx > 0 else nx, gx]:
if col >= nx: continue
touches[result] = Segment(id, -1, heads[row * nx + col])
heads[row * nx + col] = (i64)result
result += 1
elif math.abs(vs[gy] - p.y) < incidence:
let col = cell(us, p.x)
for row in [gy - 1 if gy > 0 else vs.length - 1, gy]:
if row >= vs.length - 1: continue
touches[result] = Segment(id, -1, heads[row * nx + col])
heads[row * nx + col] = (i64)result
result += 1
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_line(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_line(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_loops(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))])