Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.2

0.7.2 / 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