dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / polygons / predicates.lucb
## Planar topology predicates, separate from CAD fitting/meshing tolerances.
## Fast orientation filter with bounded floating-expansion fallback. The normal
## selects a dominant projection; no constructed plane or coordinate snapping.
## Sign of the projected binary64 determinant. The exact fallback uses TwoDiff,
## TwoSum and FMA product residuals (IEEE round-to-nearest, no reassociation).
## Mesh coordinates and nondegenerate areas keep products in the normal range.
pub func side(a: Vector3, b: Vector3, c: Vector3, normal: Vector3) -> i64:
let axis = dominant(normal)
let direction = normal.x if axis == 0 else (normal.y if axis == 1 else normal.z)
return orient(project(a,axis),project(b,axis),project(c,axis))*(1 if direction > 0.0 else -1)
func orient(p: Vector3, q: Vector3, r: Vector3) -> i64:
let ax = p.x-r.x
let ay = p.y-r.y
let bx = q.x-r.x
let by = q.y-r.y
let left = ax*by
let right = ay*bx
let determinant = left-right
let bound = (math.abs(left)+math.abs(right))*1e-15
if determinant > bound: return 1
if determinant < -bound: return -1
let dx = [residual_tail(p.x,r.x,ax),ax]
let dy = [residual_tail(p.y,r.y,ay),ay]
let ex = [residual_tail(q.x,r.x,bx),bx]
let ey = [residual_tail(q.y,r.y,by),by]
var expansion: f64[32]
var count: usize = 0
for i in 0..<(usize)2:
for j in 0..<(usize)2:
product(expansion,&count,dx[i],ey[j],1.0)
product(expansion,&count,dy[i],ex[j],-1.0)
if count == 0: return 0
return 1 if expansion[count-1] > 0.0 else -1
## Inclusive segment intersection. Nearness is not touching; exact endpoint
## comparisons and determinant signs decide whether two constraints intersect.
pub func intersects(a: Vector3, b: Vector3, c: Vector3, d: Vector3, n: Vector3) -> bool:
let axis = dominant(n)
let p = project(a,axis)
let q = project(b,axis)
let r = project(c,axis)
let s = project(d,axis)
if math.max(p.x,q.x) < math.min(r.x,s.x) or math.max(r.x,s.x) < math.min(p.x,q.x) or math.max(p.y,q.y) < math.min(r.y,s.y) or math.max(r.y,s.y) < math.min(p.y,q.y): return false
let ac = orient(p,q,r)
let ad = orient(p,q,s)
let ca = orient(r,s,p)
let cb = orient(r,s,q)
if ac*ad < 0 and ca*cb < 0: return true
return (ac == 0 and between(p,q,r)) or (ad == 0 and between(p,q,s)) or (ca == 0 and between(r,s,p)) or (cb == 0 and between(r,s,q))
## Inclusive membership in a positive ear, using the same projected signs as
## boundary intersection. A nearby vertex is not automatically inside the ear.
pub func inside_triangle(a: Vector3, b: Vector3, c: Vector3, p: Vector3, n: Vector3) -> bool:
let axis = dominant(n)
let x = project(a,axis)
let y = project(b,axis)
let z = project(c,axis)
let q = project(p,axis)
if q.x < math.min(x.x,math.min(y.x,z.x)) or q.x > math.max(x.x,math.max(y.x,z.x)) or q.y < math.min(x.y,math.min(y.y,z.y)) or q.y > math.max(x.y,math.max(y.y,z.y)): return false
let direction = n.x if axis == 0 else (n.y if axis == 1 else n.z)
let sign = 1 if direction > 0.0 else -1
return orient(x,y,q)*sign >= 0 and orient(y,z,q)*sign >= 0 and orient(z,x,q)*sign >= 0
## Half-open ray crossing for odd/even containment; division-free at near edges.
pub func ray_crosses(a: Vector3, b: Vector3, p: Vector3, n: Vector3) -> bool:
let axis = dominant(n)
let x = project(a,axis)
let y = project(b,axis)
let q = project(p,axis)
if (x.y > q.y) == (y.y > q.y): return false
return (orient(x,y,q) > 0) == (y.y > x.y)
func dominant(n: Vector3) -> i64:
return 2 if math.abs(n.z) >= math.abs(n.x) and math.abs(n.z) >= math.abs(n.y) else (1 if math.abs(n.y) >= math.abs(n.x) else 0)
func project(p: Vector3, axis: i64) -> Vector3:
return Vector3(p.y,p.z,0.0) if axis == 0 else (Vector3(p.z,p.x,0.0) if axis == 1 else Vector3(p.x,p.y,0.0))
func between(a: Vector3, b: Vector3, p: Vector3) -> bool:
return p.x >= math.min(a.x,b.x) and p.x <= math.max(a.x,b.x) and p.y >= math.min(a.y,b.y) and p.y <= math.max(a.y,b.y)
func residual_tail(a: f64, b: f64, difference: f64) -> f64:
let bv = a-difference
return (a-(difference+bv))+(bv-b)
func product(values: f64[], count: usize*, a: f64, b: f64, sign: f64):
let high = a*b
let low = math.fma(a,b,-high)
accumulate(values,count,sign*low)
accumulate(values,count,sign*high)
func accumulate(values: f64[], count: usize*, value: f64):
if value == 0.0: return
var q = value
var written: usize = 0
for at in 0..<*count:
let term = values[at]
let sum = q+term
let virtual = sum-q
let residual = (q-(sum-virtual))+(term-virtual)
if residual != 0.0:
values[written] = residual
written += 1
q = sum
if q != 0.0:
values[written] = q
written += 1
*count = written