Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.6

0.7.6 / src / geometries / triangulation / display_triangulation.lucb

## Validate a supplied triangulation without changing the polygon's wire edges.
## Indices address face corners, not shared points. Geometry producers may use
## a support chart instead of projecting a curved polygon onto an average plane.
import memory
from luce_std import math
from math.vector import Vector3
from errors import invalid
import geometries.triangulation.face_scratch

## Added to an interior edge's key once both of its sides are seen. Keys are
## below count * count, and faces have at most 2^25 corners (the 32M-corner
## budget), so keys stay below it.
let paired: i64 = 1 << 50

pub func validate(points: const Vector3[], corners: const i64[], start: usize, count: usize, indices: const i64[]) -> !:
    if indices.length != (count - 2) * 3: error(invalid, "display triangulation has the wrong triangle count")
    for index in indices:
        if index < (i64)start or index >= (i64)(start + count): error(invalid, "display triangle leaves its polygon")
    for at in 0..<indices.length // 3:
        let a = (usize)indices[at * 3]
        let b = (usize)indices[at * 3 + 1]
        let c = (usize)indices[at * 3 + 2]
        if a == b or b == c or c == a: error(invalid, "display triangle repeats a corner")
        let p = points[(usize)corners[a]]
        let ab = points[(usize)corners[b]].subtract(p)
        let ac = points[(usize)corners[c]].subtract(p)
        let cross = ab.cross(ac)
        # Conditioning belongs to this triangle, just as when it is a separate
        # face. Merging neighboring polygons must not invalidate an unchanged
        # valid display triangle merely by increasing the polygon's extent.
        let extent2 = math.max(ab.dot(ab), ac.dot(ac))
        if cross.length() <= math.max(1e-30, extent2 * 1e-14): error(invalid, "display triangle is degenerate")
    # Triangles and quads need no heap allocation on the construction hot path.
    if count <= 4:
        var table: i64[16]
        var perimeter: bool[4]
        try boundary(indices, start, count, table, perimeter)
    else:
        var capacity: usize = 16
        while capacity < indices.length * 2: capacity *= 2
        let table = try new i64[capacity] --- in memory.heap
        defer free(table) in memory.heap
        for at in 0..<table.length: table[at] = 0
        var stack: bool[256]
        let perimeter = try face_scratch.take[bool](stack, count, count)
        defer face_scratch.release[bool](stack, perimeter)
        for at in 0..<count: perimeter[at] = false
        try boundary(indices, start, count, table, perimeter)

## Each boundary edge once and forward, each interior edge once each way:
## `perimeter` (count entries, all false) marks boundary edges, `table` (a
## zeroed hash of at least twice the edges) keys interior ones.
func boundary(indices: const i64[], start: usize, count: usize, table: i64[], perimeter: bool[]) -> !:
    for triangle in 0..<indices.length // 3:
        for edge in 0..<(usize)3:
            let a = (usize)indices[triangle * 3 + edge] - start
            let b = (usize)indices[triangle * 3 + (edge + 1) % 3] - start
            if b == (a + 1) % count:
                if perimeter[a]: error(invalid, "display triangulation repeats a boundary edge")
                perimeter[a] = true
                continue
            if a == (b + 1) % count: error(invalid, "display triangulation reverses a boundary edge")
            let low = a if a < b else b
            let high = b if a < b else a
            let key = (i64)(low * count + high + 1)
            var slot = (low * 73856093 + high * 19349663) % table.length
            while table[slot] != 0:
                let value = table[slot]
                let magnitude = value if value > 0 else -value
                if (magnitude - paired if magnitude > paired else magnitude) == key: break
                slot = (slot + 1) % table.length
            let signed = key if a < b else -key
            if table[slot] == 0: table[slot] = signed
            elif table[slot] == -signed: table[slot] = key + paired
            else: error(invalid, "display triangulation has inconsistent interior edges")
    for at in 0..<count:
        if not perimeter[at]: error(invalid, "display triangulation omits a boundary edge")
    for value in table:
        if value != 0 and value <= paired: error(invalid, "display triangulation has an open interior edge")