dymokomi/luce-geocore
Source of release 0.7.2
0.7.2 / 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")