Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.5

0.7.5 / src / geometries / triangulation / ring_triangulation.lucb

## Ear clipping for large faces, in about linear time (after Mapbox's
## earcut). The face is projected into the plane of its normal and its
## corners kept as a doubly linked ring. An ear is a strictly convex corner
## whose triangle holds no reflex corner: only reflex corners can lie in an
## ear of a simple polygon, so only they are tested, found through a
## uniform grid over the face, and the reflex set shrinks as ears go (the
## two corners beside a clipped ear are classified again).
##
## Clipping goes on from the ear just cut, not from the start: candidates
## wait in a queue, first every convex corner (every other one first, so
## the first triangles do not all fan from one corner), then the two corners
## beside each ear clipped, whose triangles changed. A corner found blocked
## leaves the queue until a neighbor changes, so long runs of reflex corners
## (a comb's teeth, a spiral's inner wall) are not walked over lap after
## lap. When the queue runs dry, every convex corner is looked at once more.
##
## When such a look finds no ear, the corners without an area (collinear
## runs, doubled points) are clipped as ears; when there are none of those
## either (a self-intersecting or folded face), the rest of the ring is
## finished as a fan. So the face always gets its count - 2 triangles, and
## only running out of memory fails.
from luce_std import math
import memory
from math.vector import Vector3

## Corner kinds in Ring.kinds.
let convex: u8 = 0
## Reflex, or without an area.
let reflex: u8 = 1
## Out of the ring.
let clipped: u8 = 2

## The ring and what the ear test reads, all indexed by local corner.
struct Ring:
    ## Corners projected into the face's plane, measured from its first.
    let x: f64[]
    let y: f64[]
    let next: u32[]
    let previous: u32[]
    let kinds: u8[]
    var reflex_count: usize
    ## Areas at most this are no area (the extent-relative cutoff of the
    ## small-face ear clipper).
    let epsilon: f64
    ## Every corner bucketed into `columns` x `rows` cells over the face's
    ## bounds, shaped like them: cell k's corners are
    ## members[cells[k]..<cells[k + 1]].
    let cells: u32[]
    let members: u32[]
    let columns: usize
    let rows: usize
    let low_x: f64
    let low_y: f64
    let scale_x: f64
    let scale_y: f64

    ## Twice the signed area of corners a, b, c (positive counterclockwise
    ## about the normal).
    func area(a: usize, b: usize, c: usize) -> f64:
        return (self.x[b] - self.x[a]) * (self.y[c] - self.y[a]) - (self.y[b] - self.y[a]) * (self.x[c] - self.x[a])

    ## The area of corner `at` with its current neighbors.
    func turn(at: usize) -> f64:
        return self.area((usize)self.previous[at], at, (usize)self.next[at])

    ## Grid column (or row, of `size`) of coordinate `value`.
    static func cell(value: f64, low: f64, scale: f64, size: usize) -> usize:
        let place = (value - low) * scale
        if not (place > 0.0): return 0
        let index = (usize)place
        return index if index < size else size - 1

    ## The grid cell of corner `at`.
    func cell_of(at: usize) -> usize:
        return Ring.cell(self.y[at], self.low_y, self.scale_y, self.rows) * self.columns + Ring.cell(self.x[at], self.low_x, self.scale_x, self.columns)

    ## Whether corner `point` lies in triangle a, b, c or on its edges, with
    ## the same tolerance as the small-face ear test.
    func inside(point: usize, a: usize, b: usize, c: usize) -> bool:
        return self.area(a, b, point) >= -self.epsilon and self.area(b, c, point) >= -self.epsilon and self.area(c, a, point) >= -self.epsilon

    ## The x range of triangle a, b, c within grid row `row`, widened a
    ## little against rounding; empty (low > high) when it misses the row.
    func row_span(a: usize, b: usize, c: usize, row: usize) -> (f64, f64):
        let height = 1.0 / self.scale_y
        let bottom = self.low_y + (f64)row * height - height * 0.000001
        let top = bottom + height * 1.000002
        var low = 1.0e308
        var high = -1.0e308
        let ends: usize[3] = [a, b, c]
        for side in 0..<(usize)3:
            let p = ends[side]
            let q = ends[(side + 1) % 3]
            # Edge p-q's part in the band, by where it starts or crosses.
            if self.y[p] >= bottom and self.y[p] <= top:
                low = math.min(low, self.x[p])
                high = math.max(high, self.x[p])
            for bound in [bottom, top]:
                if (self.y[p] - bound) * (self.y[q] - bound) < 0.0:
                    let along = self.x[p] + (bound - self.y[p]) / (self.y[q] - self.y[p]) * (self.x[q] - self.x[p])
                    low = math.min(low, along)
                    high = math.max(high, along)
        let slack = 0.000001 / self.scale_x if self.scale_x > 0.0 else 0.0
        return (low - slack, high + slack)

    ## Whether convex corner `ear` may be clipped: no reflex corner of the
    ## ring in its triangle. The grid cells looked at are those the triangle
    ## covers row by row, so a long thin triangle at a slant stays cheap. A
    ## reflex corner at the very place of the ear's first corner does not
    ## block it (a face touching itself there, as earcut allows).
    func clear(ear: usize) -> bool:
        if self.reflex_count == 0: return true
        let a = (usize)self.previous[ear]
        let c = (usize)self.next[ear]
        let low_x = math.min(self.x[a], math.min(self.x[ear], self.x[c]))
        let high_x = math.max(self.x[a], math.max(self.x[ear], self.x[c]))
        let low_y = math.min(self.y[a], math.min(self.y[ear], self.y[c]))
        let high_y = math.max(self.y[a], math.max(self.y[ear], self.y[c]))
        let first_column = Ring.cell(low_x, self.low_x, self.scale_x, self.columns)
        let last_column = Ring.cell(high_x, self.low_x, self.scale_x, self.columns)
        let first_row = Ring.cell(low_y, self.low_y, self.scale_y, self.rows)
        let last_row = Ring.cell(high_y, self.low_y, self.scale_y, self.rows)
        for row in first_row..=last_row:
            var from_column = first_column
            var to_column = last_column
            if first_row != last_row:
                let (low, high) = self.row_span(a, ear, c, row)
                if low > high: continue
                let left = Ring.cell(low, self.low_x, self.scale_x, self.columns)
                let right = Ring.cell(high, self.low_x, self.scale_x, self.columns)
                if left > from_column: from_column = left
                if right < to_column: to_column = right
            for column in from_column..=to_column:
                let k = row * self.columns + column
                for slot in (usize)self.cells[k]..<(usize)self.cells[k + 1]:
                    let point = (usize)self.members[slot]
                    if self.kinds[point] != reflex or point == a or point == ear or point == c: continue
                    if self.x[point] == self.x[a] and self.y[point] == self.y[a]: continue
                    if self.inside(point, a, ear, c): return false
        return true

    ## Classify corner `at` again after a neighbor of it was clipped.
    func classify(at: usize):
        let kind = convex if self.turn(at) > self.epsilon else reflex
        if kind == self.kinds[at]: return
        if kind == reflex: self.reflex_count += 1
        else: self.reflex_count -= 1
        self.kinds[at] = kind

    ## Take corner `ear` out of the ring (its triangle already written).
    func unlink(ear: usize):
        let a = self.previous[ear]
        let c = self.next[ear]
        self.next[(usize)a] = c
        self.previous[(usize)c] = a
        if self.kinds[ear] == reflex: self.reflex_count -= 1
        self.kinds[ear] = clipped
        self.classify((usize)a)
        self.classify((usize)c)

## Corners waiting for an ear test: a circular queue holding each corner at
## most once.
struct Candidates:
    let queue: u32[]
    let queued: u8[]
    var head: usize
    var size: usize

    func push(at: usize):
        if self.queued[at] != 0: return
        self.queue[(self.head + self.size) % self.queue.length] = (u32)at
        self.queued[at] = 1
        self.size += 1

    func pop() -> usize:
        let at = (usize)self.queue[self.head]
        self.head = (self.head + 1) % self.queue.length
        self.size -= 1
        self.queued[at] = 0
        return at

    ## Every convex corner of the ring from `first` on (`remaining` corners),
    ## every other one first.
    func seed(ring: const Ring*, first: usize, remaining: usize):
        for parity in 0..<(usize)2:
            var at = first
            for step in 0..<remaining:
                if step % 2 == parity and ring.kinds[at] == convex: self.push(at)
                at = (usize)ring.next[at]

## Write the count - 2 triangles of face corners start..<start + count
## (corner indices into `corners`, which index `points`) to `output`, wound
## counterclockwise about the unit `normal`.
pub func triangulate_ring(points: const Vector3[], corners: const i64[], start: usize, count: usize, normal: Vector3, output: i64[]) -> !:
    assert(count >= 3 and count < 4294967296 and output.length == (count - 2) * 3)
    # In-plane axes: x across the normal, y = normal x x (so 2D areas are
    # 3D areas measured along the normal).
    let axis = Vector3(1.0, 0.0, 0.0) if math.abs(normal.x) < 0.9 else Vector3(0.0, 1.0, 0.0)
    let across = axis.subtract(normal.multiply_scalar(axis.dot(normal)))
    let u = across.multiply_scalar(1.0 / across.length())
    let v = normal.cross(u)
    let origin = points[(usize)corners[start]]
    # Turned to the face's principal axes, so the grid's bounds fit a long
    # face at a slant closely (its corners spread over the cells).
    var extent2: f64 = 0.0
    var sum_u = 0.0
    var sum_v = 0.0
    var sum_uu = 0.0
    var sum_vv = 0.0
    var sum_uv = 0.0
    for at in 0..<count:
        let delta = points[(usize)corners[start + at]].subtract(origin)
        extent2 = math.max(extent2, delta.dot(delta))
        let du = delta.dot(u)
        let dv = delta.dot(v)
        sum_u += du
        sum_v += dv
        sum_uu += du * du
        sum_vv += dv * dv
        sum_uv += du * dv
    let n = (f64)count
    let turn = 0.5 * math.atan2(2.0 * (sum_uv / n - sum_u * sum_v / (n * n)), (sum_uu - sum_u * sum_u / n) / n - (sum_vv - sum_v * sum_v / n) / n)
    let along = u.multiply_scalar(math.cos(turn)).add(v.multiply_scalar(math.sin(turn)))
    let up = v.multiply_scalar(math.cos(turn)).subtract(u.multiply_scalar(math.sin(turn)))
    let x = try new f64[count] --- in memory.heap
    defer free(x) in memory.heap
    let y = try new f64[count] --- in memory.heap
    defer free(y) in memory.heap
    var low_x = 0.0
    var high_x = 0.0
    var low_y = 0.0
    var high_y = 0.0
    for at in 0..<count:
        let delta = points[(usize)corners[start + at]].subtract(origin)
        x[at] = delta.dot(along)
        y[at] = delta.dot(up)
        low_x = math.min(low_x, x[at])
        high_x = math.max(high_x, x[at])
        low_y = math.min(low_y, y[at])
        high_y = math.max(high_y, y[at])
    let next = try new u32[count] --- in memory.heap
    defer free(next) in memory.heap
    let previous = try new u32[count] --- in memory.heap
    defer free(previous) in memory.heap
    let kinds = try new u8[count] --- in memory.heap
    defer free(kinds) in memory.heap
    for at in 0..<count:
        next[at] = (u32)((at + 1) % count)
        previous[at] = (u32)((at + count - 1) % count)
    # About one corner a cell, the cells about square: a long thin face
    # gets many columns and few rows.
    let width = high_x - low_x
    let height = high_y - low_y
    let aspect = width / height if width > 0.0 and height > 0.0 else 1.0
    let columns = grid_size(math.sqrt((f64)count * aspect), count)
    let rows = grid_size(math.sqrt((f64)count / aspect), count)
    let cells = try new u32[columns * rows + 1] --- in memory.heap
    defer free(cells) in memory.heap
    let members = try new u32[count] --- in memory.heap
    defer free(members) in memory.heap
    let queue = try new u32[count] --- in memory.heap
    defer free(queue) in memory.heap
    let queued = try new u8[count] --- in memory.heap
    defer free(queued) in memory.heap
    var ring = Ring(x, y, next, previous, kinds, 0, math.max(1e-30, extent2 * 1e-14), cells, members, columns, rows, low_x, low_y,
                    (f64)columns / width if width > 0.0 else 0.0, (f64)rows / height if height > 0.0 else 0.0)
    for at in 0..<count:
        kinds[at] = convex if ring.turn(at) > ring.epsilon else reflex
        if kinds[at] == reflex: ring.reflex_count += 1
    fill_grid(&ring, count)
    memory.set(queued, 0)
    var candidates = Candidates(queue, queued, 0, 0)
    var written: usize = 0
    var remaining = count
    # A corner still in the ring.
    var cursor: usize = 0
    candidates.seed(&ring, cursor, remaining)
    # Whether the queue has held every convex corner since the last clip.
    var fresh = true
    while remaining > 3:
        if candidates.size == 0:
            if fresh:
                # No strict ear anywhere: clip the corners without an area.
                var removed: usize = 0
                for _ in 0..<remaining:
                    if remaining <= 3: break
                    let after = (usize)ring.next[cursor]
                    if math.abs(ring.turn(cursor)) <= ring.epsilon:
                        written = emit(output, written, start, (usize)ring.previous[cursor], cursor, after)
                        ring.unlink(cursor)
                        remaining -= 1
                        removed += 1
                    cursor = after
                if removed == 0:
                    # Self-intersecting or folded: the rest as a fan.
                    for _ in 0..<remaining - 2:
                        let second = (usize)ring.next[cursor]
                        written = emit(output, written, start, cursor, second, (usize)ring.next[second])
                        ring.unlink(second)
                    return
            candidates.seed(&ring, cursor, remaining)
            fresh = true
            continue
        let ear = candidates.pop()
        if ring.kinds[ear] != convex or not ring.clear(ear): continue
        let a = (usize)ring.previous[ear]
        let c = (usize)ring.next[ear]
        written = emit(output, written, start, a, ear, c)
        ring.unlink(ear)
        remaining -= 1
        candidates.push(a)
        candidates.push(c)
        cursor = a
        fresh = false
    _ = emit(output, written, start, (usize)ring.previous[cursor], cursor, (usize)ring.next[cursor])

## Cells along one side of the grid: `wanted` rounded down, 1..count.
func grid_size(wanted: f64, count: usize) -> usize:
    if not (wanted >= 1.0): return 1
    if wanted >= (f64)count: return count
    return (usize)wanted

## Bucket every corner into the ring's grid (a counting sort by cell).
func fill_grid(ring: Ring*, count: usize):
    let total = ring.columns * ring.rows
    for at in 0..<ring.cells.length: ring.cells[at] = 0
    for at in 0..<count: ring.cells[ring.cell_of(at) + 1] += 1
    for k in 0..<total: ring.cells[k + 1] += ring.cells[k]
    for at in 0..<count:
        let k = ring.cell_of(at)
        # cells[k] runs ahead while filling; shifted back below.
        ring.members[(usize)ring.cells[k]] = (u32)at
        ring.cells[k] += 1
    var k = total
    while k > 0:
        ring.cells[k] = ring.cells[k - 1]
        k -= 1
    ring.cells[0] = 0

## Triangle a, b, c (local corners) as corner indices; the next free slot.
func emit(output: i64[], written: usize, start: usize, a: usize, b: usize, c: usize) -> usize:
    output[written] = (i64)(start + a)
    output[written + 1] = (i64)(start + b)
    output[written + 2] = (i64)(start + c)
    return written + 3