Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / 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.

## The step (radians) circles and ellipses are sampled at.
let round_sample_step: f64 = 0.05
## Nearest point by Newton: the step it stops at, as a share of the range.
let nearest_from_step_share: f64 = 1e-14
## A crossing repeats a known one when the edge parameters are within this
## share of the edge's span plus this floor.
let repeat_hit_share: f64 = 1e-6
let repeat_hit_floor: f64 = 1e-12
## Lines whose directions' 1 - (a·b)² is below this are parallel.
let line_crossing_parallel: f64 = 1e-18
## Refining a crossing: the steps, as shares of both ranges, it stops at.
let refine_step_share: f64 = 1e-15

## 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) / round_sample_step, 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) < nonzero: break
        let next = math.clamp(t - g / curvature, a, b)
        if math.abs(next - t) < (b - a) * nearest_from_step_share: 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) * repeat_hit_share + repeat_hit_floor: 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) * repeat_hit_share + repeat_hit_floor: 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))
    try merge_touches(w, c, low, high, ec, edge.t0, edge.t1, tol, out, first_hit)

## Hits from `first` on that are one touch: where the curve meets the edge
## tangentially (a sphere's equator edge tangent to a cylinder the section
## runs on), it stays within reach of the edge over a stretch, and a hit
## is found at each sample along it, each a vertex cutting both: the
## section is left in slivers with gaps between. Consecutive hits inside
## both ranges whose stretch of the curve between them stays within reach
## of the edge are one, kept where the two come closest.
func merge_touches(w: const Shape*, c: i64, low: f64, high: f64, ec: i64, s0: f64, s1: f64, tol: f64, out: Growing[Hit]*, first: usize) -> !:
    if out.count < first + 2: return
    let hits = out.items[first..<out.count]
    # In order along the curve (a few hits: insertion).
    for at in 1..<hits.length:
        let hit = hits[at]
        var to = at
        while to > 0 and hits[to - 1].t > hit.t:
            hits[to] = hits[to - 1]
            to -= 1
        hits[to] = hit
    let a = math.min(s0, s1)
    let b = math.max(s0, s1)
    var kept = first
    for at in first + 1..<out.count:
        let previous = out.items[kept]
        let hit = out.items[at]
        let interior = previous.t > low and previous.t < high and hit.t > low and hit.t < high and previous.s > a and previous.s < b and hit.s > a and hit.s < b
        var touching = interior
        var s = previous.s
        for k in 1..<touch_samples:
            if not touching: break
            let p = try w.at(c, previous.t + (hit.t - previous.t) * (f64)k / (f64)touch_samples)
            s = try nearest_from(w, ec, p, a, b, s)
            touching = (try w.at(ec, s)).subtract(p).length() <= tol * 10.0
        if touching:
            # One touch: the closer of the two stands for it.
            let gap_previous = (try w.at(c, previous.t)).subtract(try w.at(ec, previous.s)).length()
            let gap_hit = (try w.at(c, hit.t)).subtract(try w.at(ec, hit.s)).length()
            if gap_hit < gap_previous: out.items[kept] = hit
            continue
        kept += 1
        out.items[kept] = hit
    out.count = kept + 1

## The points a stretch between two hits is checked at for a touch.
let touch_samples: usize = 8

## 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 < line_crossing_parallel: 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])

## The points of an edge `same_curve` checks: its ends and quarters.
let same_curve_samples: usize = 5

## Whether edge `e` lies on carrier `c`'s whole curve: its ends and
## quarters 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)
    # Quarters, not halves: a whole circle's start, middle and end lie on
    # any line through its center.
    for k in 0..<same_curve_samples:
        let p = try w.at(edge.carrier, edge.t0 + (edge.t1 - edge.t0) * (f64)k / (f64)(same_curve_samples - 1))
        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) < nonzero: 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) * refine_step_share and math.abs(ds) <= (sh - sl) * refine_step_share: 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 > nonzero:
        sc = math.clamp((uv * vw - vv * uw) / det, 0.0, 1.0)
    tc = math.clamp((uv * sc + vw) / math.max(vv, nonzero), 0.0, 1.0)
    sc = math.clamp((uv * tc - uw) / math.max(uu, nonzero), 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:
            # Every 0.05 rad, and close enough that a chord strays from its
            # arc by no more than the boolean's decision distance (ten
            # tolerances): r (1 - cos(step / 2)) ≈ r step² / 8, so a ring
            # narrower than a coarse chord's sag still charts as a ring.
            let carrier = w.carriers.items[(usize)edge.carrier]
            let radius = math.max(carrier.a, carrier.b)
            let fine = math.sqrt(8.0 * w.tolerance * 10.0 / math.max(radius, nonzero))
            steps = (usize)math.clamp(math.abs(edge.t1 - edge.t0) / math.min(round_sample_step, fine), 2.0, 4096.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

## How far, as a share of a turn, a point on a full-turn loop's seam
## meridian is moved on to be counted (chart_winding).
let seam_nudge: f64 = 1e-9

## 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
            var high = low
            for at in first..<last:
                low = math.min(low, points[at].x)
                high = math.max(high, points[at].x)
            while shifted < low: shifted += 2.0 * math.pi
            while shifted >= low + 2.0 * math.pi: shifted -= 2.0 * math.pi
            # A loop going once round (closed over a pole) has its chart
            # sides at its first longitude and a turn on: a point on that
            # meridian lies on both, its winding undecided. The region is
            # the same a hair on, where it is decided.
            let turn = 2.0 * math.pi
            if high - low >= turn * (1.0 - seam_nudge) and shifted - low < turn * seam_nudge: shifted = low + turn * seam_nudge
        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