dymokomi/luce-geocore
Source of release 0.7.4
0.7.4 / src / geometries / triangulation / polygon_triangulation.lucb
## Display triangles of one polygon of any size, in its own plane: a
## scanning ear clipper for small faces with a partition fallback, a linked
## ring for large ones, and a fan for what neither can finish. Face normals
## and the test for faces without an area live here too.
import errors
from luce_std import math
import memory
from math.vector import Vector3
from geometries.triangulation.polygon_partition import partition
from geometries.triangulation.ring_triangulation import triangulate_ring
import geometries.triangulation.face_scratch
## Faces of more corners than this triangulate on a linked ring in about
## linear time (ring_triangulation); smaller ones keep the scanning ear
## clipper below, whose cubic worst case and partition fallback are bounded
## by this. Unlike face_scratch's small-face limit, tests never move it.
pub let ring_corners: usize = 256
## Polygon area has squared-distance units. Normalize relative to its own
## extent, not Vector3's world-space direction cutoff, exactly as ear tests do.
pub func area_normal(area: Vector3, extent2: f64) -> Vector3!:
let length = area_length(area)
if not math.is_finite(length) or not math.is_finite(extent2) or length <= math.max(1e-30,extent2*1e-14):
error(errors.invalid,"polygon has degenerate area")
return area.multiply_scalar(1.0/length)
## A face's unit normal, or the zero vector for a face without an area (its
## points coincide or lie on a line). Meshes keep such faces: they are
## topology, and only their display has no area.
pub func unit_or_zero(area: Vector3, extent2: f64) -> Vector3:
let length = area_length(area)
if not math.is_finite(length) or not math.is_finite(extent2) or length <= math.max(1e-30,extent2*1e-14): return Vector3()
return area.multiply_scalar(1.0/length)
## The length of a face's area vector: `sqrt(dot)` rather than `hypot`, which is
## several times slower. Coordinates are bounded to 1e6, so the squares cannot
## overflow, and an area small enough for them to underflow is degenerate anyway.
pub func area_length(area: Vector3) -> f64:
return math.sqrt(area.x * area.x + area.y * area.y + area.z * area.z)
## Whether a face normal marks a face without an area.
pub func is_degenerate(normal: Vector3) -> bool:
return normal.x == 0.0 and normal.y == 0.0 and normal.z == 0.0
## Display triangles in the face's normal plane: ear clipping supports
## concave polygons created by point editing; what ear clipping and the
## partition cannot finish (a self-intersecting or folded polygon, or one
## without an area, whose normal is zero) is finished as a fan. The face
## itself is never rejected: only its display is approximate. Faces of any
## size; those over `ring_corners` go to triangulate_ring. `output` holds
## 3 * (count - 2) corner indices. Only running out of memory fails.
pub func triangulate(points: const Vector3[], corners: const i64[], start: usize, count: usize, normal: Vector3, output: i64[]) -> !:
if is_degenerate(normal):
fan(start, count, output)
return
if count > ring_corners:
try triangulate_ring(points, corners, start, count, normal, output)
return
let origin = points[(usize)corners[start]]
var extent2: f64 = 0.0
for index in 0..<count:
let delta = points[(usize)corners[start+index]].subtract(origin)
extent2 = math.max(extent2,delta.dot(delta))
# Orientation has area units. A fixed world-space threshold rejects valid
# small trim cells (and the same polygon merely expressed in smaller units).
let epsilon = math.max(1e-30,extent2*1e-14)
# A strictly convex quad clips its first ear at corner 0: the same two
# triangles the loop below would produce, without it.
if count == 4:
var convex = true
for index in 0..<(usize)4:
let a = points[(usize)corners[start + (index + 3) % 4]]
let b = points[(usize)corners[start + index]]
let c = points[(usize)corners[start + (index + 1) % 4]]
convex = convex and b.subtract(a).cross(c.subtract(a)).dot(normal) > epsilon
if convex:
let quad: usize[6] = [3, 0, 1, 1, 2, 3]
for at in 0..<(usize)6: output[at] = (i64)(start + quad[at])
return
var stack: usize[256] = ---
let remaining = try face_scratch.take[usize](stack, count, count)
defer face_scratch.release[usize](stack, remaining)
for index in 0..<count:
remaining[index] = start + index
var length = count
var written: usize = 0
while length > 3:
var clipped = false
for index in 0..<length:
let ai = remaining[(index + length - 1) % length]
let bi = remaining[index]
let ci = remaining[(index + 1) % length]
let a = points[(usize)corners[ai]]
let b = points[(usize)corners[bi]]
let c = points[(usize)corners[ci]]
if b.subtract(a).cross(c.subtract(a)).dot(normal) <= epsilon:
continue
var blocked = false
for other in 0..<length:
let corner = remaining[other]
if corner == ai or corner == bi or corner == ci:
continue
let point = points[(usize)corners[corner]]
if b.subtract(a).cross(point.subtract(a)).dot(normal) >= -epsilon and c.subtract(b).cross(point.subtract(b)).dot(normal) >= -epsilon and a.subtract(c).cross(point.subtract(c)).dot(normal) >= -epsilon:
blocked = true
break
if blocked:
continue
# A legal ear can leave three collinear boundary vertices. Those
# vertices are real seam corners, not a collapsed input polygon;
# choose the other diagonal instead of rejecting the whole face.
if length == 4:
let di = remaining[(index + 2) % length]
let d = points[(usize)corners[di]]
if c.subtract(a).cross(d.subtract(a)).dot(normal) <= epsilon:
continue
output[written] = (i64)ai
output[written + 1] = (i64)bi
output[written + 2] = (i64)ci
written += 3
for at in index..<length - 1:
remaining[at] = remaining[at + 1]
length -= 1
clipped = true
break
if not clipped:
# Greedy ears can strand a rounded, nearly straight trim chain.
# Solve the original polygon transactionally, not the stranded tail.
# Only running out of memory fails; a partition that cannot
# solve the polygon leaves the fan below.
let solved = partition(points,corners,start,count,normal,epsilon,output) catch failure:
if failure.code == memory.exhausted: error(failure.code, failure.message)
recover false
if solved: return
# Self-intersecting or folded: the whole face as a fan (the
# partition may have written over the ears clipped so far).
fan(start, count, output)
return
output[written] = (i64)remaining[0]
output[written + 1] = (i64)remaining[1]
output[written + 2] = (i64)remaining[2]
## Triangles (start, start+k, start+k+1): a fan from the face's first corner.
func fan(start: usize, count: usize, output: i64[]):
var written: usize = 0
for at in 1..<count - 1:
output[written] = (i64)start
output[written + 1] = (i64)(start + at)
output[written + 2] = (i64)(start + at + 1)
written += 3