dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / modeling / clip.lucb
## Curves against faces: where a curve crosses an edge (both on one
## surface), the point of a curve nearest a point, and whether a point of a
## face's surface lies inside the face, on its boundary or outside. Crossings
## are found on sampled segments, then refined on the exact curves (Newton
## on the distance between them), so a hit is exact to the tolerance.
## A crossing: parameter `t` on the curve, `s` on the edge's carrier.
pub struct Hit:
pub var t: f64
pub var s: f64
## Samples a carrier interval is cut into for a search: lines by length
## against `size`, conics by angle, splines evenly.
func sample_count(w: const Shape*, c: i64, low: f64, high: f64, size: f64) -> usize:
let kind = w.carriers.items[(usize)c].kind
if kind == curve_line: return (usize)math.clamp(math.abs(high - low) / size * 64.0, 4.0, 4096.0)
if kind == curve_circle or kind == curve_ellipse: return (usize)math.clamp(math.abs(high - low) / 0.05, 8.0, 512.0)
# A spline: by its control points (traced curves have many).
let (points, weights, knots, degree) = w.spline_net(w.carriers.items[(usize)c].spline)
_ = weights
_ = knots
_ = degree
return (usize)math.clamp((f64)points.length * 2.0, 96.0, 4096.0)
## The parameter of carrier `c` in [low, high] nearest `p`.
pub func nearest_on(w: const Shape*, c: i64, p: Vector3, low: f64, high: f64) -> f64!:
let carrier = w.carriers.items[(usize)c]
let a = math.min(low, high)
let b = math.max(low, high)
if carrier.kind == curve_line: return math.clamp(p.subtract(carrier.origin).dot(carrier.x), a, b)
var best = a
var best_distance = 1.0e300
let count = 64
for at in 0..<count + 1:
let t = a + (b - a) * (f64)at / (f64)count
let d = (try w.at(c, t)).subtract(p).length()
if d < best_distance:
best_distance = d
best = t
let t = try nearest_from(w, c, p, a, b, best)
if (try w.at(c, t)).subtract(p).length() > best_distance: return best
return t
## The parameter of carrier `c` in [a, b] nearest `p` near `seed`: Newton
## on the derivative of the squared distance, from the seed.
func nearest_from(w: const Shape*, c: i64, p: Vector3, a: f64, b: f64, seed: f64) -> f64!:
var t = seed
for _ in 0..<30:
let (at, d1, d2) = try w.derivatives(c, t)
let r = at.subtract(p)
let g = r.dot(d1)
let curvature = d1.dot(d1) + r.dot(d2)
if math.abs(curvature) < 1e-300: break
let next = math.clamp(t - g / curvature, a, b)
if math.abs(next - t) < (b - a) * 1e-14: break
t = next
return t
## Where carrier `c` on [low, high] crosses edge `e`, both on one surface,
## onto `out`; an edge lying along the curve gives its two ends. `size` is
## the model's extent, `tol` its tolerance.
pub func crossings(w: const Shape*, c: i64, low: f64, high: f64, e: usize, size: f64, tol: f64, out: Growing[Hit]*) -> !:
let edge = w.edges.items[e]
let ec = edge.carrier
# One curve under both (an edge lying along the curve): the ends of the
# stretch they share.
if try same_curve(w, c, e, tol):
try overlap_ends(w, c, low, high, e, tol, out)
return
# Two lines: where they come closest, in closed form.
if w.carriers.items[(usize)c].kind == curve_line and w.carriers.items[(usize)ec].kind == curve_line:
try line_crossing(w, c, low, high, e, tol, out)
return
let n = sample_count(w, c, low, high, size)
let m = sample_count(w, ec, edge.t0, edge.t1, size)
var curve = Growing[Vector3]()
defer curve.close()
var other = Growing[Vector3]()
defer other.close()
for at in 0..<n + 1: try curve.push(try w.at(c, low + (high - low) * (f64)at / (f64)n))
for at in 0..<m + 1: try other.push(try w.at(ec, edge.t0 + (edge.t1 - edge.t0) * (f64)at / (f64)m))
# Boxes apart (by more than a sample's reach): no crossing.
let (cl, ch) = box_of(curve.view())
let (ol, oh) = box_of(other.view())
let pad = (ch.subtract(cl).length() / (f64)n + oh.subtract(ol).length() / (f64)m) + tol * 10.0
if cl.x > oh.x + pad or ol.x > ch.x + pad or cl.y > oh.y + pad or ol.y > ch.y + pad or cl.z > oh.z + pad or ol.z > ch.z + pad: return
# Where the hits found are (on the curve), and the stretches of the
# curve found running along the edge, to skip the segments by them.
var found = Growing[Vector3]()
defer found.close()
var along = Growing[(f64, f64)]()
defer along.close()
let first_hit = out.count
for i in 0..<n:
let a0 = curve.items[i]
let a1 = curve.items[i + 1]
let reach_a = a1.subtract(a0).length()
let ti = low + (high - low) * (f64)i / (f64)n
let tj = low + (high - low) * (f64)(i + 1) / (f64)n
var covered = false
for stretch in along.view():
let (start, finish) = stretch
if math.min(ti, tj) >= math.min(start, finish) and math.max(ti, tj) <= math.max(start, finish): covered = true
if covered: continue
for j in 0..<m:
let b0 = other.items[j]
let b1 = other.items[j + 1]
let reach = (reach_a + b1.subtract(b0).length()) * 0.6 + tol * 10.0
if segment_distance(a0, a1, b0, b1) > reach: continue
var near_hit = false
for q in found.view():
if segment_distance(a0, a1, q, q) <= reach and segment_distance(b0, b1, q, q) <= reach: near_hit = true
if near_hit: continue
let t_guess = low + (high - low) * ((f64)i + 0.5) / (f64)n
let s_guess = edge.t0 + (edge.t1 - edge.t0) * ((f64)j + 0.5) / (f64)m
let (t, s, distance) = try refine(w, c, low, high, ec, edge.t0, edge.t1, t_guess, s_guess)
if distance > tol * 10.0: continue
# A crossing known already (from another segment pair: a coarse
# edge's segment reaches much of a small curve): no more to do,
# and the segments by it are skipped from now on.
var again = false
for hit in out.view():
if (try w.at(c, hit.t)).subtract(try w.at(c, t)).length() <= tol * 10.0 and math.abs(hit.s - s) <= math.abs(edge.t1 - edge.t0) * 1e-6 + 1e-12: again = true
if again:
try found.push(try w.at(c, t))
continue
var at_t = t
var at_s = s
# Touching: a curve meeting the edge tangentially (a G2 blend's
# edge its face's) stays within reach of it over a stretch, and
# the closest point found may be anywhere along it. When that
# stretch runs to the curve's end (or the edge's), that end is
# where they meet.
let ends: f64[2] = [low, high]
for end in ends:
if try runs_along(w, c, t, end, ec, edge.t0, edge.t1, tol, s, other.view()):
try along.push((t, end))
at_t = end
at_s = try nearest_on(w, ec, try w.at(c, end), edge.t0, edge.t1)
# Or to the edge's end, the curve running along it there.
let its_ends: f64[2] = [edge.t0, edge.t1]
for end in its_ends:
if at_t == t and try runs_along(w, ec, s, end, c, low, high, tol, t, curve.view()):
at_s = end
at_t = try nearest_on(w, c, try w.at(ec, end), low, high)
try along.push((t, at_t))
var known = false
for hit in out.view():
if (try w.at(c, hit.t)).subtract(try w.at(c, at_t)).length() <= tol * 10.0 and math.abs(hit.s - at_s) <= math.abs(edge.t1 - edge.t0) * 1e-6 + 1e-12: known = true
if not known: try out.push(Hit(at_t, at_s))
if out.count > first_hit and not known: try found.push(try w.at(c, at_t))
## Whether carrier `c` from `t` to `end` stays within reach (ten
## tolerances) of carrier `ec` on [s0, s1], `seed` its nearest parameter
## to `c` at `t` (where they are within reach): sampled, the far end first
## (a crossing leaves at once), then on from `t`, each nearest point found
## from the last.
## `samples` are `ec` at even steps from s0 to s1 (crossings has them),
## where each nearest search starts.
func runs_along(w: const Shape*, c: i64, t: f64, end: f64, ec: i64, s0: f64, s1: f64, tol: f64, seed: f64, samples: const Vector3[]) -> bool!:
if t == end: return false
let a = math.min(s0, s1)
let b = math.max(s0, s1)
let far = try w.at(c, end)
if (try w.at(ec, try nearest_sampled(w, ec, far, s0, s1, samples))).subtract(far).length() > tol * 10.0: return false
var s = seed
for k in 1..<8:
let p = try w.at(c, t + (end - t) * (f64)k / 8.0)
s = try nearest_from(w, ec, p, a, b, s)
if (try w.at(ec, s)).subtract(p).length() > tol * 10.0:
s = try nearest_sampled(w, ec, p, s0, s1, samples)
if (try w.at(ec, s)).subtract(p).length() > tol * 10.0: return false
return true
## nearest_on, its search started at the nearest of `samples` (carrier
## `c` at even steps from s0 to s1).
func nearest_sampled(w: const Shape*, c: i64, p: Vector3, s0: f64, s1: f64, samples: const Vector3[]) -> f64!:
var best: usize = 0
var best_distance = 1.0e300
for k in 0..<samples.length:
let d = samples[k].subtract(p).length()
if d < best_distance:
best_distance = d
best = k
let seed = s0 + (s1 - s0) * (f64)best / (f64)(samples.length - 1)
let t = try nearest_from(w, c, p, math.min(s0, s1), math.max(s0, s1), seed)
if (try w.at(c, t)).subtract(p).length() > best_distance: return seed
return t
## Where line `c` on [low, high] crosses line edge `e` (not along it):
## their nearest points, when within reach and inside both ranges.
func line_crossing(w: const Shape*, c: i64, low: f64, high: f64, e: usize, tol: f64, out: Growing[Hit]*) -> !:
let a = w.carriers.items[(usize)c]
let edge = w.edges.items[e]
let b = w.carriers.items[(usize)edge.carrier]
let k = a.x.dot(b.x)
let det = 1.0 - k * k
if det < 1e-18: return
let r = a.origin.subtract(b.origin)
let t = (k * r.dot(b.x) - r.dot(a.x)) / det
let u = (r.dot(b.x) - k * r.dot(a.x)) / det
let reach = tol * 10.0
if t < math.min(low, high) - reach or t > math.max(low, high) + reach: return
if u < math.min(edge.t0, edge.t1) - reach or u > math.max(edge.t0, edge.t1) + reach: return
let pa = a.origin.add(a.x.multiply_scalar(t))
let pb = b.origin.add(b.x.multiply_scalar(u))
if pa.subtract(pb).length() > reach: return
let tc = math.clamp(t, math.min(low, high), math.max(low, high))
let uc = math.clamp(u, math.min(edge.t0, edge.t1), math.max(edge.t0, edge.t1))
for hit in out.view():
if math.abs(hit.t - tc) <= reach and math.abs(hit.s - uc) <= reach: return
try out.push(Hit(tc, uc))
func box_of(points: const Vector3[]) -> (Vector3, Vector3):
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for p in points:
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
return (low, high)
## The parameter range of carrier `c` to search all of it (a line: far).
func full_range(w: const Shape*, c: i64) -> (f64, f64):
let carrier = w.carriers.items[(usize)c]
if carrier.kind == curve_line: return (-1.0e12, 1.0e12)
if carrier.kind == curve_circle or carrier.kind == curve_ellipse: return (-math.pi, 3.0 * math.pi)
let (points, weights, knots, degree) = w.spline_net(carrier.spline)
_ = weights
return (knots[(usize)degree], knots[points.length])
## Whether edge `e` lies on carrier `c`'s whole curve: its ends and middle
## on it.
func same_curve(w: const Shape*, c: i64, e: usize, tol: f64) -> bool!:
let edge = w.edges.items[e]
let (low, high) = full_range(w, c)
for k in 0..<3:
let p = try w.at(edge.carrier, edge.t0 + (edge.t1 - edge.t0) * (f64)k * 0.5)
let t = try nearest_on(w, c, p, low, high)
if (try w.at(c, t)).subtract(p).length() > tol * 10.0: return false
return true
## The ends of the stretch where edge `e` and carrier `c` on [low, high]
## (one curve) overlap: each end of either that lies within the other.
func overlap_ends(w: const Shape*, c: i64, low: f64, high: f64, e: usize, tol: f64, out: Growing[Hit]*) -> !:
let edge = w.edges.items[e]
let candidates: f64[2] = [edge.t0, edge.t1]
for s in candidates:
let p = try w.at(edge.carrier, s)
let t = try nearest_on(w, c, p, low, high)
if (try w.at(c, t)).subtract(p).length() <= tol * 10.0: try out.push(Hit(t, s))
let ends: f64[2] = [low, high]
for t in ends:
let p = try w.at(c, t)
let s = try nearest_on(w, edge.carrier, p, edge.t0, edge.t1)
if (try w.at(edge.carrier, s)).subtract(p).length() > tol * 10.0: continue
var known = false
for hit in out.view():
if (try w.at(c, hit.t)).subtract(p).length() <= tol * 10.0: known = true
if not known: try out.push(Hit(t, s))
## Gauss-Newton on |C(t) - E(s)|: the nearest pair of parameters from a
## guess, kept in their intervals, and their distance.
func refine(w: const Shape*, c: i64, low: f64, high: f64, ec: i64, s0: f64, s1: f64, t_guess: f64, s_guess: f64) -> (f64, f64, f64)!:
let tl = math.min(low, high)
let th = math.max(low, high)
let sl = math.min(s0, s1)
let sh = math.max(s0, s1)
var t = t_guess
var s = s_guess
for _ in 0..<40:
let (pc, dc, _) = try w.derivatives(c, t)
let (pe, de_, _) = try w.derivatives(ec, s)
let r = pc.subtract(pe)
let de = de_.multiply_scalar(-1.0)
let a11 = dc.dot(dc)
let a12 = dc.dot(de)
let a22 = de.dot(de)
let b1 = -dc.dot(r)
let b2 = -de.dot(r)
let det = a11 * a22 - a12 * a12
if math.abs(det) < 1e-300: break
let dt = (b1 * a22 - b2 * a12) / det
let ds = (a11 * b2 - a12 * b1) / det
t = math.clamp(t + dt, tl, th)
s = math.clamp(s + ds, sl, sh)
if math.abs(dt) <= (th - tl) * 1e-15 and math.abs(ds) <= (sh - sl) * 1e-15: break
return (t, s, (try w.at(c, t)).subtract(try w.at(ec, s)).length())
## The least distance between segments ab and cd.
func segment_distance(a: Vector3, b: Vector3, c: Vector3, d: Vector3) -> f64:
let u = b.subtract(a)
let v = d.subtract(c)
let w0 = a.subtract(c)
let uu = u.dot(u)
let uv = u.dot(v)
let vv = v.dot(v)
let uw = u.dot(w0)
let vw = v.dot(w0)
let det = uu * vv - uv * uv
var sc = 0.0
var tc = 0.0
if det > 1e-300:
sc = math.clamp((uv * vw - vv * uw) / det, 0.0, 1.0)
tc = math.clamp((uv * sc + vw) / math.max(vv, 1e-300), 0.0, 1.0)
sc = math.clamp((uv * tc - uw) / math.max(uu, 1e-300), 0.0, 1.0)
return a.add(u.multiply_scalar(sc)).subtract(c.add(v.multiply_scalar(tc))).length()
## Where a point of a face's surface lies: outside, inside, on its boundary.
pub let outside: i64 = 0
pub let inside_face: i64 = 1
pub let on_boundary: i64 = 2
## Face `f`'s loops in its surface's chart (loop_chart), and where each
## loop starts.
pub func face_chart(w: const Shape*, f: usize, points: Growing[Vector3]*, starts: Growing[usize]*) -> !:
points.clear()
starts.clear()
let face = w.faces.items[f]
let uses = w.face_uses(f)
var at: usize = 0
for size in w.face_sizes(f):
try starts.push(points.count)
try loop_chart(w, face.surface, try face_pole(w, f), uses[at..<at + (usize)size], points)
at += (usize)size
try starts.push(points.count)
## The pole a face on a sphere closes its loops over (its latitude), so a
## loop going once around bounds a region: the one its outer loop turns
## about (north when it turns positively on an outward face); 0 elsewhere.
## Every piece of the face closes over the same pole, so holes still turn
## the other way.
pub func face_pole(w: const Shape*, f: usize) -> f64!:
let face = w.faces.items[f]
if w.surfaces.items[(usize)face.surface].kind != surface_sphere: return 0.0
var points = Growing[Vector3]()
defer points.close()
let sizes = w.face_sizes(f)
if sizes.length == 0: return 0.0
try loop_chart(w, face.surface, 0.0, w.face_uses(f)[..<(usize)sizes[0]], &points)
# A whole sphere (no loop) closes over no pole.
if points.count == 0: return 0.0
let turned = points.items[points.count - 1].x - points.items[0].x
return 0.5 * math.pi if (turned > 0.0) == face.sense else -0.5 * math.pi
## A loop of edge uses in its surface's chart onto `points`, unwrapped to run
## on continuously (a wrapping angle keeps going past a turn). On a sphere a
## loop going once around is closed over `pole` (face_pole; 0: left open).
## With `coarse` each curved edge takes at most eight steps (enough for a
## loop's turning sense and rough area, not for winding round it); with
## `most` over 0, the chart stops after that many points.
pub func loop_chart(w: const Shape*, surface: i64, pole: f64, uses: const i64[], points: Growing[Vector3]*, coarse: bool = false, most: usize = 0) -> !:
let s = &w.surfaces.items[(usize)surface]
let wraps = periodic(s)
# A torus's tube angle wraps too.
let wraps_v = s.kind == surface_torus
let first_point = points.count
var previous = 0.0
var previous_v = 0.0
var first = true
for use in uses:
let e = edge_index(use)
let edge = w.edges.items[e]
let kind = w.carriers.items[(usize)edge.carrier].kind
var steps: usize = 1
if kind == curve_circle or kind == curve_ellipse: steps = (usize)math.clamp(math.abs(edge.t1 - edge.t0) / 0.05, 2.0, 512.0)
if kind == curve_spline:
let (net, weights, knots, degree) = w.spline_net(w.carriers.items[(usize)edge.carrier].spline)
_ = weights
_ = knots
_ = degree
steps = (usize)math.clamp((f64)net.length, 48.0, 2048.0)
if kind == curve_line and wraps: steps = 8
if coarse and steps > 8: steps = 8
for step in 0..<steps:
let fraction = (f64)step / (f64)steps
let p = try w.edge_at(e, fraction if use > 0 else 1.0 - fraction)
# Along a loop on a B-spline, the last point's parameters seed
# the next's.
# A tolerant edge or vertex lies on the face within its own
# precision; an input's points within its own tolerance, which
# may be looser than the booleans' (the model's size x 1e-7):
# a chart (for turning and rough area) takes them within ten.
let reach = math.max(math.max(w.tolerance * 10.0, w.edge_slack_of(e)), math.max(w.point_slack_of((usize)edge.start), w.point_slack_of((usize)edge.end)))
let (raw, raw_v) = try spline_uv(s, p, reach, Vector3(previous, previous_v, 0.0)) if s.kind == surface_spline and not first else try surface_uv(s, p, reach)
var u = raw
var v = raw_v
if wraps and not first: u = wrap(u, previous)
if wraps_v and not first: v = wrap(v, previous_v)
previous = u
previous_v = v
first = false
try points.push(Vector3(u, v, 0.0))
if most > 0 and points.count - first_point >= most: return
if s.kind == surface_sphere and points.count > first_point and pole != 0.0:
let turned = previous - points.items[first_point].x
if math.abs(turned) > math.pi:
# Back to the start a whole turn on, then over the pole.
let start = points.items[first_point]
let around = start.x + (2.0 * math.pi if turned > 0.0 else -2.0 * math.pi)
try points.push(Vector3(around, start.y, 0.0))
try points.push(Vector3(around, pole, 0.0))
try points.push(Vector3(start.x, pole, 0.0))
## The winding number of the chart's loops about (u, v).
func winding(points: const Vector3[], starts: const usize[], u: f64, v: f64) -> i64:
var total: i64 = 0
for loop in 0..<starts.length - 1:
let first = starts[loop]
let last = starts[loop + 1]
for at in first..<last:
let a = points[at]
let b = points[first if at + 1 == last else at + 1]
let side = (b.x - a.x) * (v - a.y) - (u - a.x) * (b.y - a.y)
if a.y <= v:
if b.y > v and side > 0.0: total += 1
elif b.y <= v and side < 0.0:
total -= 1
return total
## The winding number of the chart's loops about (u, v); with `wraps` (an
## angle chart) each loop sees (u, v) moved by whole turns into its own
## range, since a loop's unwrapped angles start wherever its curve does.
## (A torus wraps its second coordinate too: `wraps_v`.)
pub func chart_winding(points: const Vector3[], starts: const usize[], u: f64, v: f64, wraps: bool, wraps_v: bool = false) -> i64:
var total: i64 = 0
for loop in 0..<starts.length - 1:
let first = starts[loop]
let last = starts[loop + 1]
if last <= first: continue
var shifted = u
var shifted_v = v
if wraps:
var low = points[first].x
for at in first..<last: low = math.min(low, points[at].x)
while shifted < low: shifted += 2.0 * math.pi
while shifted >= low + 2.0 * math.pi: shifted -= 2.0 * math.pi
if wraps_v:
var low_v = points[first].y
for at in first..<last: low_v = math.min(low_v, points[at].y)
while shifted_v < low_v: shifted_v += 2.0 * math.pi
while shifted_v >= low_v + 2.0 * math.pi: shifted_v -= 2.0 * math.pi
let range: usize[2] = [first, last]
total += winding(points, range[..<2], shifted, shifted_v)
return total
## Where `p` lies against face `f`: on its boundary, inside or outside it
## (a point off a B-spline face's surface is outside).
pub func face_contains(w: const Shape*, f: usize, p: Vector3, tol: f64) -> i64!:
let uses = w.face_uses(f)
for use in uses:
let e = edge_index(use)
let edge = w.edges.items[e]
let t = try nearest_on(w, edge.carrier, p, edge.t0, edge.t1)
# A tolerant edge (Stitch's) holds what lies within its precision.
if (try w.at(edge.carrier, t)).subtract(p).length() <= math.max(tol * 10.0, w.edge_slack_of(e)): return on_boundary
var points = Growing[Vector3]()
defer points.close()
var starts = Growing[usize]()
defer starts.close()
try face_chart(w, f, &points, &starts)
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
# Off a B-spline surface (no parameters there) is outside its face.
let (u, v) = surface_uv(s, p, w.tolerance) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
return outside
return inside_face if chart_winding(points.view(), starts.view(), u, v, periodic(s), s.kind == surface_torus) != 0 else outside