Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / circularize.lucb

## Circularize: the group's loops made circles, after Maya's Circularize and
## Blender's LoopTools Circle. Edges give their chains (edge_chains.lucb):
## a loop becomes a circle round its center (the points' mean weighted by
## their edges' lengths) in its plane (Newell's normal), a run an arc of the
## circle that fits it best (Kåsa's least squares in its plane). Faces give
## their regions' outlines, each a circle, and the points inside a region
## follow: an outline that is star-shaped about its center maps every
## inner point along its ray from the center, so a region keeps its rings
## and spokes; a ring of faces between two outlines (a hole's rim) becomes
## the ring between two concentric circles. Radius 0 fits each circle to
## its points; Even spaces a loop's points at equal angles (else each keeps
## its own); Flatten puts them in the plane (else each keeps its height
## off it); Twist turns them about the center; Influence blends from where
## they were. The output selection is the group.

let circularize_parms: ParmSpec[5] = [
    ParmSpec("Radius", ParmKind.number, 0.0, 0.0, 100000.0, 1, "", "The circle's radius; 0 fits it to each loop's points. A ring's inner circle keeps its share of the outer.", 2.0),
    ParmSpec("Even", ParmKind.toggle, 1.0, 0.0, 1.0, 1, "", "Space each loop's points at equal angles; off, each point keeps its angle about the center."),
    ParmSpec("Flatten", ParmKind.toggle, 1.0, 0.0, 1.0, 1, "", "Put the loop in its plane; off, each point keeps its height off the plane."),
    ParmSpec("Twist", ParmKind.number, 0.0, -360.0, 360.0, 1, "", "Turn the points about the center by this many degrees.", more = true),
    ParmSpec("Influence", ParmKind.number, 1.0, 0.0, 1.0, 1, "", "How far the points move toward the circle: 0 leaves them, 1 is the circle.")]

let circularize_also: Domain[1] = [Domain.face]
let circularize_picks: PickSpec[1] = [PickSpec("Loops", "edges faces points")]

func circularize_verb() -> Verb:
    return Verb("Circularize", "Deform", "Make the group's edge loops, or its regions' outlines, circles", Domain.edge, true, circularize_parms, false, cook_circularize, false, circularize_also,
                section = "Modify", family = "Shape", icon = "circularize", picks = circularize_picks, drag = 4, drag_mode = "amount")

## How a run of Circularize places points.
struct CircleSettings:
    let radius: f64
    let even: bool
    let flatten: bool
    let twist: f64
    let influence: f64

## A plane frame: a center, its normal and two axes in it.
struct Frame:
    let center: Vector3
    let normal: Vector3
    let u: Vector3
    let v: Vector3

## The two axes square to `normal`, the first along `toward` where it can be.
func frame_at(center: Vector3, normal: Vector3, toward: Vector3) -> Frame:
    var u = toward.subtract(normal.multiply_scalar(toward.dot(normal)))
    if u.length() < 1.0e-12 * math.max(1.0, toward.length()):
        u = Vector3(1.0, 0.0, 0.0) if math.abs(normal.x) < 0.9 else Vector3(0.0, 1.0, 0.0)
        u = u.subtract(normal.multiply_scalar(u.dot(normal)))
    u = u.multiply_scalar(1.0 / u.length())
    return Frame(center, normal, u, normal.cross(u))

## Wrap an angle into (-π, π].
func wrapped(angle: f64) -> f64:
    var a = angle
    while a > math.pi: a -= 2.0 * math.pi
    while a <= -math.pi: a += 2.0 * math.pi
    return a

## The frame of the loop through `chain`'s points: its center (weighted by
## the edges at each point), Newell's normal, the first axis toward its
## first point; none for a loop with no area. Also its area.
func loop_frame(positions: const Float3[], chain: const i32[]) -> (Frame, f64)?:
    let count = chain.length
    var center = Vector3()
    var total = 0.0
    for at in 0..<count:
        let p = positions[(usize)chain[at]].vector()
        let before = positions[(usize)chain[(at + count - 1) % count]].vector()
        let after = positions[(usize)chain[(at + 1) % count]].vector()
        let weight = p.subtract(before).length() + after.subtract(p).length()
        center = center.add(p.multiply_scalar(weight))
        total += weight
    if not (total > 0.0): return none
    center = center.multiply_scalar(1.0 / total)
    var newell = Vector3()
    for at in 0..<count:
        let a = positions[(usize)chain[at]].vector().subtract(center)
        let b = positions[(usize)chain[(at + 1) % count]].vector().subtract(center)
        newell = newell.add(a.cross(b))
    let length = newell.length()
    if length < 1.0e-24 or length < 1.0e-12 * total * total: return none
    let normal = newell.multiply_scalar(1.0 / length)
    return (frame_at(center, normal, positions[(usize)chain[0]].vector().subtract(center)), length * 0.5)

## One loop seen from its circle's frame, in the order of increasing angle:
## where its points were (angle, distance off the center, height off the
## plane) and where they go (each angle's shift, each new height), and the
## circle's radius. Inner points of a region look their place up in it.
struct Polar:
    var angles: Growing[f64]
    var radii: Growing[f64]
    var heights: Growing[f64]
    ## New angle less old, unwrapped along the order; one more entry for
    ## the step from the last point round to the first.
    var shifts: Growing[f64]
    var raised: Growing[f64]
    var radius: f64
    ## Whether every ray from the center crosses the loop once.
    var star: bool

    func init():
        self.angles = Growing[f64]()
        self.radii = Growing[f64]()
        self.heights = Growing[f64]()
        self.shifts = Growing[f64]()
        self.raised = Growing[f64]()
        self.radius = 0.0
        self.star = false

    func close():
        self.angles.close()
        self.radii.close()
        self.heights.close()
        self.shifts.close()
        self.raised.close()

    ## Along the ray at `angle`: where the loop was (distance, height),
    ## the angle that ray's crossing goes to, and its new height.
    func at(angle: f64) -> (f64, f64, f64, f64):
        let count = self.angles.count
        let first = self.angles.items[0]
        var x = first + wrapped(angle - first)
        if x < first: x += 2.0 * math.pi
        # The last entry not past x.
        var low: usize = 0
        var high = count
        while high - low > 1:
            let middle = (low + high) // 2
            if self.angles.items[middle] <= x: low = middle
            else: high = middle
        let next = low + 1
        let next_angle = self.angles.items[next] if next < count else first + 2.0 * math.pi
        let next_radius = self.radii.items[next % count]
        # Where the ray crosses the side from entry `low` to the next.
        let a = (self.radii.items[low] * math.cos(self.angles.items[low]), self.radii.items[low] * math.sin(self.angles.items[low]))
        let b = (next_radius * math.cos(next_angle), next_radius * math.sin(next_angle))
        let d = (math.cos(x), math.sin(x))
        let side = (b.0 - a.0, b.1 - a.1)
        let det = d.1 * side.0 - d.0 * side.1
        var s = 0.0
        var distance = 0.0
        if math.abs(det) > 1.0e-30:
            s = math.clamp((d.0 * a.1 - d.1 * a.0) / det, 0.0, 1.0)
            distance = math.sqrt((a.0 + s * side.0) * (a.0 + s * side.0) + (a.1 + s * side.1) * (a.1 + s * side.1))
        else:
            let span = next_angle - self.angles.items[low]
            s = (x - self.angles.items[low]) / span if span > 0.0 else 0.0
            distance = self.radii.items[low] + s * (next_radius - self.radii.items[low])
        let shift = self.shifts.items[low] + s * (self.shifts.items[next] - self.shifts.items[low])
        let height = self.heights.items[low] + s * (self.heights.items[next % count] - self.heights.items[low])
        let raised = self.raised.items[low] + s * (self.raised.items[next % count] - self.raised.items[low])
        return (distance, x + shift, height, raised)

## Place `chain`'s loop on its circle in `frame`: each point's new place in
## `targets` (beside the chain), and the loop's `polar` view. `scale` sets
## the radius as a share of the fit (a ring's inner loop) when above 0.
func circle_loop(positions: const Float3[], chain: const i32[], frame: Frame, settings: const CircleSettings*, scale: f64, targets: Vector3[], polar: Polar*) -> !:
    let count = chain.length
    let angles = try new f64[count] --- in memory.heap
    defer free(angles) in memory.heap
    let radii = try new f64[count] --- in memory.heap
    defer free(radii) in memory.heap
    let heights = try new f64[count] --- in memory.heap
    defer free(heights) in memory.heap
    var fit = 0.0
    var total = 0.0
    for at in 0..<count:
        let d = positions[(usize)chain[at]].vector().subtract(frame.center)
        heights[at] = d.dot(frame.normal)
        let x = d.dot(frame.u)
        let y = d.dot(frame.v)
        angles[at] = math.atan2(y, x)
        radii[at] = math.sqrt(x * x + y * y)
        let before = positions[(usize)chain[(at + count - 1) % count]].vector()
        let after = positions[(usize)chain[(at + 1) % count]].vector()
        let p = positions[(usize)chain[at]].vector()
        let weight = p.subtract(before).length() + after.subtract(p).length()
        fit += radii[at] * weight
        total += weight
    fit = fit / total if total > 0.0 else 0.0
    # Which way round the loop runs about the normal, and whether its
    # angles only ever grow that way (star-shaped about the center).
    var winding = 0.0
    for at in 0..<count: winding += wrapped(angles[(at + 1) % count] - angles[at])
    let way = 1.0 if winding > 0.0 else -1.0
    var star = math.abs(winding) > math.pi
    for at in 0..<count:
        if wrapped(angles[(at + 1) % count] - angles[at]) * way <= 0.0: star = false
    var radius = settings.radius if settings.radius > 0.0 else fit
    if scale > 0.0: radius = fit * scale
    # Even: the rotation that best fits equal steps to the points' own angles.
    let twist = settings.twist * math.pi / 180.0
    var start = 0.0
    if settings.even:
        var sine = 0.0
        var cosine = 0.0
        for at in 0..<count:
            let offset = angles[at] - way * 2.0 * math.pi * (f64)at / (f64)count
            sine += math.sin(offset)
            cosine += math.cos(offset)
        start = math.atan2(sine, cosine)
    let goes = try new f64[count] --- in memory.heap
    defer free(goes) in memory.heap
    for at in 0..<count:
        goes[at] = (start + way * 2.0 * math.pi * (f64)at / (f64)count if settings.even else angles[at]) + twist
        let height = 0.0 if settings.flatten else heights[at]
        targets[at] = frame.center.add(frame.u.multiply_scalar(radius * math.cos(goes[at]))).add(frame.v.multiply_scalar(radius * math.sin(goes[at]))).add(frame.normal.multiply_scalar(height))
    # The polar view, from the point of least angle in increasing order.
    polar.radius = radius
    polar.star = star
    var lowest: usize = 0
    for at in 1..<count:
        if angles[at] < angles[lowest]: lowest = at
    var angle = angles[lowest]
    var shift = wrapped(goes[lowest] - angles[lowest])
    for step in 0..<count:
        let at = (lowest + step) % count if way > 0.0 else (lowest + count - step) % count
        if step > 0:
            let before = (lowest + step - 1) % count if way > 0.0 else (lowest + count - step + 1) % count
            angle += wrapped(angles[at] - angles[before])
            shift += wrapped(wrapped(goes[at] - angles[at]) - shift)
        try polar.angles.push(angle)
        try polar.radii.push(radii[at])
        try polar.heights.push(heights[at])
        try polar.shifts.push(shift)
        try polar.raised.push(0.0 if settings.flatten else heights[at])
    try polar.shifts.push(shift + wrapped(polar.shifts.items[0] - shift))

## The arc that fits an open run best, its points placed on it (in
## `targets`); false for a run too straight or short to bend.
func arc_run(positions: const Float3[], chain: const i32[], settings: const CircleSettings*, targets: Vector3[]) -> bool:
    let count = chain.length
    if count < 3: return false
    var center = Vector3()
    for point in chain: center = center.add(positions[(usize)point].vector())
    center = center.multiply_scalar(1.0 / (f64)count)
    var newell = Vector3()
    var size = 0.0
    for at in 0..<count:
        let a = positions[(usize)chain[at]].vector().subtract(center)
        let b = positions[(usize)chain[(at + 1) % count]].vector().subtract(center)
        newell = newell.add(a.cross(b))
        size = math.max(size, a.length())
    if newell.length() < 1.0e-9 * size * size: return false
    let frame = frame_at(center, newell.multiply_scalar(1.0 / newell.length()), positions[(usize)chain[0]].vector().subtract(center))
    # Kåsa: x² + y² + D x + E y + F = 0 by least squares.
    var m = (0.0, 0.0, 0.0, 0.0, 0.0, 0.0)
    var r = (0.0, 0.0, 0.0)
    for point in chain:
        let d = positions[(usize)point].vector().subtract(center)
        let x = d.dot(frame.u)
        let y = d.dot(frame.v)
        let z = -(x * x + y * y)
        m = (m.0 + x * x, m.1 + x * y, m.2 + x, m.3 + y * y, m.4 + y, m.5 + 1.0)
        r = (r.0 + x * z, r.1 + y * z, r.2 + z)
    # Solve [[xx xy x] [xy yy y] [x y n]] (D E F) = r by Cramer's rule.
    let det = m.0 * (m.3 * m.5 - m.4 * m.4) - m.1 * (m.1 * m.5 - m.4 * m.2) + m.2 * (m.1 * m.4 - m.3 * m.2)
    if math.abs(det) < 1.0e-30: return false
    let dd = (r.0 * (m.3 * m.5 - m.4 * m.4) - m.1 * (r.1 * m.5 - m.4 * r.2) + m.2 * (r.1 * m.4 - m.3 * r.2)) / det
    let ee = (m.0 * (r.1 * m.5 - r.2 * m.4) - r.0 * (m.1 * m.5 - m.4 * m.2) + m.2 * (m.1 * r.2 - r.1 * m.2)) / det
    let ff = (m.0 * (m.3 * r.2 - m.4 * r.1) - m.1 * (m.1 * r.2 - m.2 * r.1) + r.0 * (m.1 * m.4 - m.3 * m.2)) / det
    let cx = -dd * 0.5
    let cy = -ee * 0.5
    let squared = cx * cx + cy * cy - ff
    if not (squared > 0.0) or not math.is_finite(squared): return false
    let radius = settings.radius if settings.radius > 0.0 else math.sqrt(squared)
    let middle = center.add(frame.u.multiply_scalar(cx)).add(frame.v.multiply_scalar(cy))
    # Angles about the fitted center, unwrapped along the run.
    var first = 0.0
    var last = 0.0
    var angle = 0.0
    for at in 0..<count:
        let d = positions[(usize)chain[at]].vector().subtract(middle)
        let a = math.atan2(d.dot(frame.v), d.dot(frame.u))
        angle = a if at == 0 else angle + wrapped(a - angle)
        if at == 0: first = angle
        last = angle
        targets[at] = Vector3(angle, d.dot(frame.normal), 0.0)
    let twist = settings.twist * math.pi / 180.0
    for at in 0..<count:
        let own = targets[at]
        let goes = (first + (last - first) * (f64)at / (f64)(count - 1) if settings.even else own.x) + twist
        let height = 0.0 if settings.flatten else own.y
        targets[at] = middle.add(frame.u.multiply_scalar(radius * math.cos(goes))).add(frame.v.multiply_scalar(radius * math.sin(goes))).add(frame.normal.multiply_scalar(height))
    return true

## A region of faces: its outline loops (their chain indices) and how its
## inner points map: the frame shared by its loops and the polar views of
## its outer and inner loop (-1: none).
struct Region:
    var loops: Growing[u32]
    var frame: Frame
    var outer: i64
    var inner: i64

    func init():
        self.loops = Growing[u32]()
        self.frame = Frame(Vector3(), Vector3(), Vector3(), Vector3())
        self.outer = -1
        self.inner = -1

    func close():
        self.loops.close()

## What mapping a region's inner points reads, per point in parallel.
struct InnerWork:
    let points: const u32[]
    let regions: const i32[]
    let rings: const Region[]
    let polars: const Polar[]
    let positions: Float3[]
    let influence: f64

func map_inner(context: void*, first: usize, end: usize, worker: usize):
    let work = (InnerWork*)context
    for at in first..<end:
        let point = (usize)work.points[at]
        let region = &work.rings[(usize)work.regions[at]]
        let frame = region.frame
        let p = work.positions[point].vector()
        let d = p.subtract(frame.center)
        let h = d.dot(frame.normal)
        let x = d.dot(frame.u)
        let y = d.dot(frame.v)
        let angle = math.atan2(y, x)
        let distance = math.sqrt(x * x + y * y)
        let outer = &work.polars[(usize)region.outer]
        let out = outer.at(angle)
        var reach = 0.0
        var goes = out.1
        var height = h
        if region.inner < 0:
            let share = distance / out.0 if out.0 > 1.0e-30 else 0.0
            reach = share * outer.radius
            height = h + share * (out.3 - out.2)
        else:
            let inner = &work.polars[(usize)region.inner]
            let within = inner.at(angle)
            let span = out.0 - within.0
            let t = math.clamp((distance - within.0) / span, 0.0, 1.0) if span > 1.0e-30 else 0.0
            reach = inner.radius + t * (outer.radius - inner.radius)
            goes = within.1 + t * wrapped(out.1 - within.1)
            height = h + (within.3 - within.2) + t * ((out.3 - out.2) - (within.3 - within.2))
        let target = frame.center.add(frame.u.multiply_scalar(reach * math.cos(goes))).add(frame.v.multiply_scalar(reach * math.sin(goes))).add(frame.normal.multiply_scalar(height))
        work.positions[point] = Float3.of(p.add(target.subtract(p).multiply_scalar(work.influence)))

func cook_circularize(input: const VerbInput*, output: VerbOutput*) -> !:
    let p = input.parms
    let settings = CircleSettings(p.at(0), p.at(1) != 0.0, p.at(2) != 0.0, p.at(3), p.at(4))
    if not (settings.radius >= 0.0) or not math.is_finite(settings.radius): error(errors.invalid, "Circularize's radius must be finite and not negative")
    if not math.is_finite(settings.twist) or not (settings.influence >= 0.0 and settings.influence <= 1.0): error(errors.invalid, "Circularize's twist must be finite and its influence in 0..1")
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    output.positions = mesh_positions(mesh)
    _ = try output.positions.writable()
    let positions = output.positions.span()
    output.selection = try BitsBuilder.copy_of(input.group)
    output.selection_domain = input.domain
    var moved = try BitsBuilder.zeros(topology.points)
    defer moved.close()
    if input.domain == Domain.face:
        try circularize_regions(input, &topology, &settings, positions, &moved, output)
    else:
        try circularize_chains(&topology, input.group, &settings, positions, &moved, output)
    try output.moved.reserve(moved.view().population())
    for point in 0..<topology.points:
        if moved.view().get(point): try output.moved.push((u32)point)

## Edges: each loop its circle, each run its arc. The chains are fitted
## in parallel, each into its own slots of `targets` (beside the chain
## points); then their points move in order, so a point two runs share (a
## branch) takes the later run's place, as one thread would leave it.
func circularize_chains(topology: const Topology*, group: Bits, settings: const CircleSettings*, positions: Float3[], moved: BitsBuilder*, output: VerbOutput*) -> !:
    var chains = EdgeChains()
    defer chains.close()
    try edge_chains(topology, group, &chains)
    let count = chains.count()
    let targets = try new Vector3[chains.points.count] --- in memory.heap
    defer free(targets) in memory.heap
    let placed = try new bool[count] --- in memory.heap
    defer free(placed) in memory.heap
    var work = ChainFit(&chains, positions, settings, targets[..<chains.points.count], placed[..<count])
    work.failed.store(0, .relaxed)
    try parallel.for_each_range(count, 16, (void*)&work, fit_chains)
    if work.failed.load(.acquire) != 0: error(memory.exhausted, "out of memory fitting circles")
    var skipped: usize = 0
    for index in 0..<count:
        if not placed[index]:
            skipped += 1
            continue
        let first = (usize)chains.starts.items[index]
        let chain = chains.chain(index)
        try place_chain(positions, chain, targets[first..<first + chain.length], settings.influence, moved)
    if skipped > 0:
        output.warning = "Some chains are too straight or too short to make a circle; they stay"
        output.skipped = skipped

## What fitting the chains reads and writes, per chain in parallel.
struct ChainFit:
    let chains: const EdgeChains*
    let positions: const Float3[]
    let settings: const CircleSettings*
    let targets: Vector3[]
    let placed: bool[]
    var failed: @u32

func fit_chains(context: void*, first: usize, end: usize, worker: usize):
    let work = (ChainFit*)context
    for index in first..<end:
        let chain = work.chains.chain(index)
        let start = (usize)work.chains.starts.items[index]
        let slots = work.targets[start..<start + chain.length]
        work.placed[index] = false
        if work.chains.closed.items[index] != 0 and chain.length >= 3:
            let found = loop_frame(work.positions, chain) else continue
            var polar = Polar()
            circle_loop(work.positions, chain, found.0, work.settings, 0.0, slots, &polar) catch failure:
                polar.close()
                work.failed.store(1, .relaxed)
                continue
            polar.close()
            work.placed[index] = true
        elif work.chains.closed.items[index] == 0:
            work.placed[index] = arc_run(work.positions, chain, work.settings, slots)

## Move `chain`'s points `influence` of the way to `targets`.
func place_chain(positions: Float3[], chain: const i32[], targets: const Vector3[], influence: f64, moved: BitsBuilder*) -> !:
    for at in 0..<chain.length:
        let point = (usize)chain[at]
        let p = positions[point].vector()
        positions[point] = Float3.of(p.add(targets[at].subtract(p).multiply_scalar(influence)))
        moved.set(point)

## Faces: each region's outlines circles, its inner points mapped.
func circularize_regions(input: const VerbInput*, topology: const Topology*, settings: const CircleSettings*, positions: Float3[], moved: BitsBuilder*, output: VerbOutput*) -> !:
    let faces = topology.faces()
    let group = input.group
    # Regions: the group's faces joined across edges both of whose faces are
    # in the group.
    let regions = try new i32[faces] --- in memory.heap
    defer free(regions) in memory.heap
    let queue = try new u32[faces] --- in memory.heap
    defer free(queue) in memory.heap
    for face in 0..<faces: regions[face] = -1
    var region_count: usize = 0
    for seed in 0..<faces:
        if not group.get(seed) or regions[seed] >= 0: continue
        regions[seed] = (i32)region_count
        queue[0] = (u32)seed
        var head: usize = 0
        var tail: usize = 1
        while head < tail:
            let face = (usize)queue[head]
            head += 1
            for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
                let edge = (usize)topology.corner_edges[corner]
                for slot in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
                    let other = (usize)topology.corner_faces[(usize)topology.edge_corners[slot]]
                    if group.get(other) and regions[other] < 0:
                        regions[other] = (i32)region_count
                        queue[tail] = (u32)other
                        tail += 1
        region_count += 1
    # The outlines: edges of exactly one of the group's faces.
    var outline = try BitsBuilder.zeros(topology.edges())
    defer outline.close()
    for edge in 0..<topology.edges():
        var inside: usize = 0
        for slot in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
            if group.get((usize)topology.corner_faces[(usize)topology.edge_corners[slot]]): inside += 1
        if inside == 1: outline.set(edge)
    var chains = EdgeChains()
    defer chains.close()
    try edge_chains(topology, outline.view(), &chains)
    let rings = try new Region[region_count] --- in memory.heap
    for at in 0..<region_count: rings[at] = Region()
    defer:
        for at in 0..<region_count: rings[at].close()
        free(rings) in memory.heap
    for index in 0..<chains.count():
        if chains.closed.items[index] == 0 or chains.chain(index).length < 3: continue
        let face = region_face(topology, group, chains.chain(index))
        try rings[(usize)regions[face]].loops.push((u32)index)
    var polars = Growing[Polar]()
    defer:
        for at in 0..<polars.count: polars.items[at].close()
        polars.close()
    var targets = Growing[Vector3]()
    defer targets.close()
    for region in 0..<region_count: try circle_region(positions, &chains, &rings[region], settings, &polars, &targets, moved)
    # Inner points: on the group's faces, off every outline, in a region
    # whose outlines map them.
    var inner = Growing[u32]()
    defer inner.close()
    var owners = Growing[i32]()
    defer owners.close()
    var on_outline = try BitsBuilder.zeros(topology.points)
    defer on_outline.close()
    for edge in 0..<topology.edges():
        if not outline.view().get(edge): continue
        on_outline.set((usize)topology.edge_points[edge * 2])
        on_outline.set((usize)topology.edge_points[edge * 2 + 1])
    var seen = try BitsBuilder.zeros(topology.points)
    defer seen.close()
    var unmapped = try BitsBuilder.zeros(region_count)
    defer unmapped.close()
    for face in 0..<faces:
        if not group.get(face): continue
        let ring = &rings[(usize)regions[face]]
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            let point = (usize)topology.corners[corner]
            if on_outline.view().get(point) or seen.view().get(point): continue
            seen.set(point)
            if ring.outer < 0:
                unmapped.set((usize)regions[face])
                continue
            try inner.push((u32)point)
            try owners.push(regions[face])
            moved.set(point)
    var work = InnerWork(inner.view(), owners.view(), rings[..<region_count], polars.view(), positions, settings.influence)
    try parallel.for_each_range(inner.count, 4096, (void*)&work, map_inner)
    let kept = unmapped.view().population()
    if kept > 0:
        output.warning = "Some regions' outlines are not star-shaped about their centers, or a region has more than two outlines: their outlines are circles but their inner points stay"
        output.skipped = kept

## The group face along the first edge of an outline chain.
func region_face(topology: const Topology*, group: Bits, chain: const i32[]) -> usize:
    let a = (usize)chain[0]
    let b = (usize)chain[1]
    for slot in (usize)topology.point_edge_offsets[a]..<(usize)topology.point_edge_offsets[a + 1]:
        let edge = (usize)topology.point_edges[slot]
        let other = (usize)topology.edge_points[edge * 2] + (usize)topology.edge_points[edge * 2 + 1] - a
        if other != b: continue
        for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
            let face = (usize)topology.corner_faces[(usize)topology.edge_corners[at]]
            if group.get(face): return face
    trap("an outline edge has no face of the group")

## A region's outlines made circles (one: about its own center; two: the
## ring between two concentric circles, about the outer's center), and,
## when they map its inner points, its frame and polar views set. Each loop
## is placed as soon as it is measured: loops share no points, and the
## inner points read only the polar views.
func circle_region(positions: Float3[], chains: const EdgeChains*, ring: Region*, settings: const CircleSettings*, polars: Growing[Polar]*, targets: Growing[Vector3]*, moved: BitsBuilder*) -> !:
    let count = ring.loops.count
    if count == 0: return
    # The outer loop: the one of most area.
    var outer: usize = 0
    var best = -1.0
    var outer_frame = Frame(Vector3(), Vector3(), Vector3(), Vector3())
    for at in 0..<count:
        if let found = loop_frame(positions, chains.chain((usize)ring.loops.items[at])):
            if found.1 > best:
                best = found.1
                outer = at
                outer_frame = found.0
    if best < 0.0: return
    let shared = count == 2
    ring.frame = outer_frame
    # The outer loop first: a ring's inner circle keeps its share of it.
    var scale = 0.0
    for step in 0..<count:
        let at = outer if step == 0 else (step - 1 if step - 1 < outer else step)
        let chain = chains.chain((usize)ring.loops.items[at])
        var frame = outer_frame
        if not shared and at != outer:
            let found = loop_frame(positions, chain) else continue
            frame = found.0
        try targets.fill(chain.length, Vector3())
        var polar = Polar()
        circle_loop(positions, chain, frame, settings, scale if step > 0 and shared else 0.0, targets.items[..<chain.length], &polar) catch failure:
            polar.close()
            error(failure.code, failure.message)
        if step == 0 and shared:
            let fit = polar_fit(positions, chain, frame)
            scale = polar.radius / fit if fit > 0.0 else 0.0
        let star = polar.star
        polars.push(polar) catch failure:
            polar.close()
            error(failure.code, failure.message)
        let index = (i64)polars.count - 1
        if step == 0: ring.outer = index if star else -2
        elif shared: ring.inner = index if star else -2
        try place_chain(positions, chain, targets.view()[..<chain.length], settings.influence, moved)
    # Inner points map only through star-shaped outlines, one or two.
    if count > 2 or ring.outer < 0 or (shared and ring.inner < 0):
        ring.outer = -1
        ring.inner = -1

## A loop's mean distance from `frame`'s center in its plane, weighted by
## the edges at each point (circle_loop's fit).
func polar_fit(positions: const Float3[], chain: const i32[], frame: Frame) -> f64:
    let count = chain.length
    var fit = 0.0
    var total = 0.0
    for at in 0..<count:
        let p = positions[(usize)chain[at]].vector()
        let d = p.subtract(frame.center)
        let x = d.dot(frame.u)
        let y = d.dot(frame.v)
        let before = positions[(usize)chain[(at + count - 1) % count]].vector()
        let after = positions[(usize)chain[(at + 1) % count]].vector()
        let weight = p.subtract(before).length() + after.subtract(p).length()
        fit += math.sqrt(x * x + y * y) * weight
        total += weight
    return fit / total if total > 0.0 else 0.0