Luce packages
LuceLuce BaseLuciaOS

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))])