Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / booleans / predicates.lucb

# mark: Predicates on input points =============================================================

# Orientation signs of input points (f64 coordinates taken as exact). A
# floating evaluation decides when its value clears Shewchuk's error bound
# for that evaluation order; otherwise the determinant is expanded exactly
# on the stack. Constructions need the exact value itself (`*_exact`).

## Shewchuk's static error bounds: (3 + 16e)e and (7 + 56e)e, e = 2^-53.
let orient2d_bound: f64 = 3.3306690738754716e-16
let orient3d_bound: f64 = 7.771561172376103e-16

## An exact difference of two coordinates: one or two components.
struct Tail:
    var parts: f64[2]
    var count: usize

    static func of(a: f64, b: f64) -> Tail:
        var made = Tail([0.0, 0.0], 0)
        made.count = difference_into(a, b, made.parts[..<2])
        return made

## a * b - c * d exactly, each factor an exact difference, into h (room 16).
func minor_exact(a: const Tail*, b: const Tail*, c: const Tail*, d: const Tail*, h: f64[]) -> usize:
    var scratch: f64[8] = ---
    var left: f64[8] = ---
    var right: f64[8] = ---
    let l = expansion_times_short(a.parts[..<a.count], b.parts[..<b.count], left[..<8], scratch[..<8])
    let r = expansion_times_short(c.parts[..<c.count], d.parts[..<d.count], right[..<8], scratch[..<8])
    expansion_negate(right[..<r])
    return expansion_sum(left[..<l], right[..<r], h)

## The orientation of (a, b, c) in the plane of coordinates `u` and `v`:
## positive counterclockwise, 0 collinear.
func orient2d(a: Vector3, b: Vector3, c: Vector3, u: usize, v: usize) -> i64:
    let left = (b.coordinate(u) - a.coordinate(u)) * (c.coordinate(v) - a.coordinate(v))
    let right = (b.coordinate(v) - a.coordinate(v)) * (c.coordinate(u) - a.coordinate(u))
    let determinant = left - right
    let bound = orient2d_bound * (math.abs(left) + math.abs(right))
    if determinant > bound: return 1
    if determinant < -bound: return -1
    var exact: f64[16] = ---
    return expansion_sign(exact[..<orient2d_exact(a, b, c, u, v, exact[..<16])])

## orient2d's determinant exactly, into h (room 16).
func orient2d_exact(a: Vector3, b: Vector3, c: Vector3, u: usize, v: usize, h: f64[]) -> usize:
    var bu = Tail.of(b.coordinate(u), a.coordinate(u))
    var bv = Tail.of(b.coordinate(v), a.coordinate(v))
    var cu = Tail.of(c.coordinate(u), a.coordinate(u))
    var cv = Tail.of(c.coordinate(v), a.coordinate(v))
    return minor_exact(&bu, &cv, &bv, &cu, h)

## Which side of the plane through a, b, c point d is on: positive on the
## side the normal (b - a) x (c - a) points to, 0 on the plane.
func plane_side(a: Vector3, b: Vector3, c: Vector3, d: Vector3) -> i64:
    let bx = b.x - a.x
    let by = b.y - a.y
    let bz = b.z - a.z
    let cx = c.x - a.x
    let cy = c.y - a.y
    let cz = c.z - a.z
    let dx = d.x - a.x
    let dy = d.y - a.y
    let dz = d.z - a.z
    let cydz = cy * dz
    let czdy = cz * dy
    let czdx = cz * dx
    let cxdz = cx * dz
    let cxdy = cx * dy
    let cydx = cy * dx
    let determinant = bx * (cydz - czdy) + by * (czdx - cxdz) + bz * (cxdy - cydx)
    let permanent = math.abs(bx) * (math.abs(cydz) + math.abs(czdy)) + math.abs(by) * (math.abs(czdx) + math.abs(cxdz)) + math.abs(bz) * (math.abs(cxdy) + math.abs(cydx))
    let bound = orient3d_bound * permanent
    if determinant > bound: return 1
    if determinant < -bound: return -1
    var exact: f64[192] = ---
    return expansion_sign(exact[..<side_exact(a, b, c, d, exact[..<192])])

## side's determinant exactly, into h (room 192).
func side_exact(a: Vector3, b: Vector3, c: Vector3, d: Vector3, h: f64[]) -> usize:
    var bx = Tail.of(b.x, a.x)
    var by = Tail.of(b.y, a.y)
    var bz = Tail.of(b.z, a.z)
    var cx = Tail.of(c.x, a.x)
    var cy = Tail.of(c.y, a.y)
    var cz = Tail.of(c.z, a.z)
    var dx = Tail.of(d.x, a.x)
    var dy = Tail.of(d.y, a.y)
    var dz = Tail.of(d.z, a.z)
    var minor: f64[16] = ---
    var scratch: f64[64] = ---
    var first: f64[64] = ---
    var second: f64[64] = ---
    var both: f64[128] = ---
    var count = minor_exact(&cy, &dz, &cz, &dy, minor[..<16])
    let one = expansion_times_short(minor[..<count], bx.parts[..<bx.count], first[..<64], scratch[..<64])
    count = minor_exact(&cz, &dx, &cx, &dz, minor[..<16])
    let two = expansion_times_short(minor[..<count], by.parts[..<by.count], second[..<64], scratch[..<64])
    let pair = expansion_sum(first[..<one], second[..<two], both[..<128])
    count = minor_exact(&cx, &dy, &cy, &dx, minor[..<16])
    let three = expansion_times_short(minor[..<count], bz.parts[..<bz.count], first[..<64], scratch[..<64])
    return expansion_sum(both[..<pair], first[..<three], h)

## The normal (b - a) x (c - a) of a triangle exactly: three expansions of
## room 16 each in h (room 48), and their lengths.
func normal_exact(a: Vector3, b: Vector3, c: Vector3, h: f64[]) -> (usize, usize, usize):
    var bx = Tail.of(b.x, a.x)
    var by = Tail.of(b.y, a.y)
    var bz = Tail.of(b.z, a.z)
    var cx = Tail.of(c.x, a.x)
    var cy = Tail.of(c.y, a.y)
    var cz = Tail.of(c.z, a.z)
    let x = minor_exact(&by, &cz, &bz, &cy, h[..<16])
    let y = minor_exact(&bz, &cx, &bx, &cz, h[16..<32])
    let z = minor_exact(&bx, &cy, &by, &cx, h[32..<48])
    return (x, y, z)

## Whether `p`, on the line through a and b, lies strictly between them.
func strictly_between(a: Vector3, b: Vector3, p: Vector3) -> bool:
    for axis in 0..<(usize)3:
        let x = a.coordinate(axis)
        let y = b.coordinate(axis)
        if x == y: continue
        let z = p.coordinate(axis)
        return (x < z and z < y) or (y < z and z < x)
    return false

## The plane a triangle is projected to: the coordinates `u` and `v`
## (dropping `axis`, in cyclic order so the projection keeps the normal's
## sense along +axis) and the projected orientation `sense` (+1 or -1;
## 0: the triangle has no area).
pub struct Projection:
    pub let axis: usize
    pub let u: usize
    pub let v: usize
    pub let sense: i64

    ## The projection along `axis`, sense unset.
    static func along(axis: usize) -> Projection:
        return Projection(axis, (axis + 1) % 3, (axis + 2) % 3, 0)

## The projection of triangle (a, b, c) that keeps the most area: along its
## normal's largest component, whose exact sign is the sense. A triangle
## with no area in any projection has sense 0.
func projection_of(a: Vector3, b: Vector3, c: Vector3) -> Projection:
    let normal = b.subtract(a).cross(c.subtract(a))
    let nx = math.abs(normal.x)
    let ny = math.abs(normal.y)
    let nz = math.abs(normal.z)
    let first: usize = 0 if nx >= ny and nx >= nz else (1 if ny >= nz else 2)
    # The largest approximate component is almost always exactly nonzero;
    # the others are tried for a sliver whose estimate misleads.
    for step in 0..<(usize)3:
        let axis = (first + step) % 3
        let along = Projection.along(axis)
        let sense = orient2d(a, b, c, along.u, along.v)
        if sense != 0: return Projection(axis, along.u, along.v, sense)
    return Projection.along(first)