dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / modeling / rays.lucb
## Inside or outside a solid by rays through its exact faces: where a ray
## meets each face's surface (closed form for planes, cylinders, cones and
## spheres; sampled and bisected on a torus), and whether the hit lies
## inside the face (its chart's winding). Three clean rays (no hit on a
## face's boundary or grazing it), the majority deciding. No tessellation: classification used to mesh both solids on
## every boolean. B-spline faces are met through their Bezier patches
## (spline_rays.lucb).
## A ray whose |cos| with a plane's normal is below this runs along it.
let ray_along_plane: f64 = 1e-15
## A ray grazes a surface (the inside test is ambiguous) when |cos| with
## its normal is at most this.
let grazing_slack: f64 = 1e-4
## Faces' charts, made the first time a ray meets the face: face f's loops
## are starts[firsts[f]..<firsts[f] + loops[f] + 1] into points.
struct Charts:
var points: Growing[Vector3]
var starts: Growing[usize]
var firsts: Growing[i64]
var loops: Growing[usize]
func close():
self.points.close()
self.starts.close()
self.firsts.close()
self.loops.close()
func new_charts(faces: usize) -> Charts!:
var made = Charts(Growing[Vector3](), Growing[usize](), Growing[i64](), Growing[usize]())
errdefer made.close()
for _ in 0..<faces:
try made.firsts.push(-1)
try made.loops.push(0)
return made
## Face `f`'s chart, made once.
func chart_of(charts: Charts*, w: const Shape*, f: usize) -> (const Vector3[], const usize[])!:
if charts.firsts.items[f] < 0:
var points = Growing[Vector3]()
defer points.close()
var starts = Growing[usize]()
defer starts.close()
try face_chart(w, f, &points, &starts)
let offset = charts.points.count
for p in points.view(): try charts.points.push(p)
charts.firsts.items[f] = (i64)charts.starts.count
charts.loops.items[f] = starts.count - 1
for s in starts.view(): try charts.starts.push(s + offset)
let first = (usize)charts.firsts.items[f]
return (charts.points.view(), charts.starts.view()[first..<first + charts.loops.items[f] + 1])
## Where the ray from `o` along unit `d` meets surface `s` ahead of it
## (parameters onto `out`).
func ray_roots(s: const Surface*, o: Vector3, d: Vector3, out: Growing[f64]*) -> !:
out.clear()
let q = o.subtract(s.origin)
if s.kind == surface_plane:
let along = d.dot(s.z)
if math.abs(along) < ray_along_plane: return
try out.push(-q.dot(s.z) / along)
return
if s.kind == surface_sphere:
try quadratic(d.dot(d), 2.0 * q.dot(d), q.dot(q) - s.radius * s.radius, out)
return
if s.kind == surface_cylinder or s.kind == surface_cone:
# |radial|^2 = (r + h tan a)^2, h along the axis (a cylinder: a = 0).
let k = math.tan(s.angle) if s.kind == surface_cone else 0.0
let dz = d.dot(s.z)
let qz = q.dot(s.z)
let a = d.dot(d) - dz * dz - k * k * dz * dz
let b = 2.0 * (q.dot(d) - qz * dz) - 2.0 * k * dz * (s.radius + k * qz)
let c = q.dot(q) - qz * qz - (s.radius + k * qz) * (s.radius + k * qz)
var roots = Growing[f64]()
defer roots.close()
try quadratic(a, b, c, &roots)
for t in roots.view():
# One nappe: where the radius is not negative.
if s.kind == surface_cylinder or s.radius + k * (qz + t * dz) >= 0.0: try out.push(t)
return
if s.kind == surface_torus:
# A torus: its implicit function along the ray, within its ball.
let reach = s.radius + s.angle
var span = Growing[f64]()
defer span.close()
try quadratic(d.dot(d), 2.0 * q.dot(d), q.dot(q) - reach * reach * 1.0001, &span)
if span.count < 2: return
let low = span.items[0]
let high = span.items[1]
let steps = 256
var previous = torus_value(s, q, d, low)
for k in 1..<steps + 1:
let t = low + (high - low) * (f64)k / (f64)steps
let value = torus_value(s, q, d, t)
if (previous < 0.0) != (value < 0.0):
var a = t - (high - low) / (f64)steps
var b = t
for _ in 0..<60:
let m = (a + b) * 0.5
if (torus_value(s, q, d, m) < 0.0) == (previous < 0.0): a = m
else: b = m
try out.push((a + b) * 0.5)
previous = value
return
error(invalid, "B-spline faces are met by spline_hits")
func torus_value(s: const Surface*, q: Vector3, d: Vector3, t: f64) -> f64:
let p = q.add(d.multiply_scalar(t))
let h = p.dot(s.z)
let ring = math.sqrt(math.max(0.0, p.dot(p) - h * h)) - s.radius
return ring * ring + h * h - s.angle * s.angle
## The real roots of a t^2 + b t + c onto `out`, smaller first.
func quadratic(a: f64, b: f64, c: f64, out: Growing[f64]*) -> !:
if math.abs(a) < nonzero:
if math.abs(b) > nonzero: try out.push(-c / b)
return
let disc = b * b - 4.0 * a * c
if disc < 0.0: return
let spread = math.sqrt(disc)
# The stable form.
let q = -0.5 * (b + (spread if b >= 0.0 else -spread))
var t0 = q / a
var t1 = c / q if math.abs(q) > nonzero else t0
if t1 < t0:
let swap = t0
t0 = t1
t1 = swap
try out.push(t0)
try out.push(t1)
## Whether `point` lies inside the solid made of faces `first..<last` of
## `w`, by the parity of rays through its faces. A ray counts only when it
## is clean: every hit on an analytic face crosses it inside, not on its
## boundary (a ray through an edge two faces share would count twice) and
## not grazing it (a ray tangent to a cylinder meets it twice at one
## point). Rays are tried in a fixed order until three clean ones are
## found; their majority decides (they agree but where the point lies
## within the tolerance of the solid's boundary). Without three, the clean
## ones decide, and without any, the first three. `size` is the model's
## extent (a hit closer than a billionth of it is the start).
## With `lookup` (over `w`), a hit on an analytic face is placed against
## the face by it (face_lookup.lucb: on a plane only the loops round the
## hit are traced), not by winding round the face's whole chart.
func inside_faces(w: const Shape*, charts: Charts*, nets: Nets*, first: usize, last: usize, point: Vector3, size: f64, lookup: Lookup*? = none) -> bool!:
let rays: Vector3[9] = [Vector3(0.5377, 0.8319, 0.1373), Vector3(-0.3271, 0.2491, 0.9116), Vector3(0.7713, -0.5129, -0.3772),
Vector3(-0.6142, -0.4417, 0.6538), Vector3(0.2236, -0.8834, 0.4119), Vector3(-0.8462, 0.3355, -0.4141),
Vector3(0.1093, 0.5904, -0.7997), Vector3(0.9341, 0.2211, 0.2803), Vector3(-0.4789, -0.7462, -0.4625)]
var roots = Growing[f64]()
defer roots.close()
var spline = Growing[SplineHit]()
defer spline.close()
var clean_votes = 0
var clean = 0
var raw_votes = 0
for at in 0..<(usize)9:
if clean == 3: break
let d = try rays[at].normalized()
var hits = 0
var ambiguous = false
for f in first..<last:
let index = (usize)w.faces.items[f].surface
let s = &w.surfaces.items[index]
if s.kind == surface_spline:
try spline_hits(nets, w, index, point, d, &spline)
for hit in spline.view():
if hit.t <= size * relative_zero: continue
let (points, starts) = try chart_of(charts, w, f)
if chart_winding(points, starts, hit.u, hit.v, false, false) != 0: hits += 1
continue
try ray_roots(s, point, d, &roots)
for t in roots.view():
if t <= size * relative_zero: continue
let x = point.add(d.multiply_scalar(t))
# Grazing: the ray along the surface there.
let n = normal_at(s, x, w.tolerance) catch failure: recover Vector3()
if math.abs(n.dot(d)) <= grazing_slack: ambiguous = true
if let faces = lookup:
let where_hit = try lookup_contains(faces, w, f, x, w.tolerance)
if where_hit == on_boundary: ambiguous = true
if where_hit != outside: hits += 1
continue
let (u, v) = try surface_uv(s, x, w.tolerance)
let (points, starts) = try chart_of(charts, w, f)
if chart_winding(points, starts, u, v, periodic(s), s.kind == surface_torus) != 0: hits += 1
let odd = hits % 2 == 1
if at < 3 and odd: raw_votes += 1
if ambiguous: continue
clean += 1
if odd: clean_votes += 1
if clean == 0: return raw_votes >= 2
return clean_votes * 2 > clean
## Rays against every face of one shape, keeping the faces' charts and
## nets between points (a blend's tool ends ask several).
struct ShapeRays:
var charts: Charts
var nets: Nets
func close():
self.charts.close()
self.nets.close()
## Whether `point` lies inside `w` (the shape these were made for), of
## extent `size` (inside_faces).
func inside(w: const Shape*, point: Vector3, size: f64) -> bool!:
return try inside_faces(w, &self.charts, &self.nets, 0, w.faces.count, point, size)
func shape_rays(w: const Shape*) -> ShapeRays!:
var charts = try new_charts(w.faces.count)
errdefer charts.close()
return ShapeRays(charts, try new_nets(w.surfaces.count))