Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.5

0.7.5 / src / splats / reduce.lucb

## Reduce GSplats' kernel: fewer splats that look and weigh about the same.
## A splat's mass is its opacity times σ₁σ₂σ₃, its Gaussian's integral up to
## a constant (plain points weigh 1), and a cloud's centroid is the
## mass-weighted mean of its centers.
##
## - **Merge** (moment matching over a nearest-neighbor graph): each pass
##   finds every splat's 6 nearest within a few splat sizes, orders the pairs
##   by Ward's cost m₁m₂/(m₁+m₂)·d², and merges greedily, each splat at most
##   once, as many pairs as the target still needs. A merged splat keeps the
##   pair's mass and centroid: its center is the mass-weighted mean, its
##   covariance the mass-weighted second moment Σ wₖ(Σₖ + dₖdₖᵀ), its opacity
##   the mass over its new σ₁σ₂σ₃ (clamped to 1, the one way mass is lost),
##   and its Cd and SH the mass-weighted means, the SH taken into the world
##   frame first. Its other attributes come from the heavier splat. Passes
##   repeat, widening the search when pairs run out, until the target is
##   met; whatever remains is pruned by importance.
## - **Importance**: the least visible splats go. A splat's score is what it
##   shows rather than what it weighs: its opacity, times its mean projected
##   area (σ₁σ₂ + σ₂σ₃ + σ₁σ₃)/3 relative to the cloud's median, to the power
##   0.1 (LightGaussian's volume power: size counts only a little), times
##   1 + 4·its color's contrast against the opacity-weighted mean Cd of its 8
##   nearest neighbors. Mass alone (opacity × volume) dropped a capture's
##   small, opaque, colorful detail first (the bonsai's flowers at 25%). With
##   `keep_mass` the kept opacities are scaled by one factor, each clamped to
##   1, chosen so the total mass stays (unless every kept splat reaches
##   opacity 1 first); the centroid moves only by what the removed splats held.

## What Reduce GSplats does.
pub struct ReduceOptions:
    ## The splats left (no more than the cloud has).
    pub let target: usize
    ## Merge pairs, else prune by importance.
    pub let merge: bool
    ## After pruning, scale opacities so the total mass stays.
    pub let keep_mass: bool

## A reduced cloud: its positions (relative to the input's origin) and point
## attributes (detail attributes shared), and what was done.
pub struct Reduced:
    pub var positions: Column[Float3]
    pub var store: AttributeStore
    ## Pairs merged and splats pruned.
    pub var merged: usize
    pub var pruned: usize

    ## Release the positions and attributes.
    pub func close():
        self.positions.release()
        self.store.close()

## The mass of every point of a cloud's `store` into `out` (one per point).
pub func splat_masses(store: const AttributeStore*, out: f64[]):
    let opacity = float_attribute(store, opacity_name, 1)
    let scale = float_attribute(store, scale_name, 3)
    var work = MassWork(Floats.of(store.entry((usize)opacity)) if opacity >= 0 else Floats.empty(), Floats.of(store.entry((usize)scale)) if scale >= 0 else Floats.empty(), opacity >= 0, scale >= 0, out)
    ranges.each_range(out.length, 16384, (void*)&work, mass_range)

struct MassWork:
    let alpha: Floats
    let sigma: Floats
    let has_alpha: bool
    let has_sigma: bool
    let out: f64[]

func mass_range(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (MassWork*)context
    for at in first..<end:
        var m: f64 = 1.0
        if work.has_alpha: m = work.alpha.at(at, 0)
        if work.has_sigma: m = m * math.abs(work.sigma.at(at, 0) * work.sigma.at(at, 1) * work.sigma.at(at, 2))
        work.out[at] = m if math.is_finite(m) else 0.0

## A cloud (`points` relative to `origin`, attributes `store`) reduced to
## `options.target` points (see above). A target at or above the count
## shares everything.
pub func reduced_cloud(points: const Float3[], store: const AttributeStore*, options: const ReduceOptions*) -> Reduced!:
    var positions = try Column[Float3].copy_of(points)
    let attributes = store.shared() catch failure:
        positions.release()
        error(failure.code, failure.message)
    var result = Reduced(positions, attributes, 0, 0)
    errdefer result.close()
    if options.target >= points.length: return result
    if options.merge and is_splat_store(store):
        let sizes = Floats.of(store.entry((usize)float_attribute(store, scale_name, 3)))
        let median = try median_largest(&sizes, points.length)
        var cell = 3.0 * median
        if not (cell > 0.0): cell = 3.0 * mean_spacing(points)
        var widenings: usize = 0
        var samples = ShSamples.make()
        while result.positions.count() > options.target and cell > 0.0 and widenings < 6:
            let pairs = try merge_pass(&result, options.target, cell, &samples)
            result.merged += pairs
            # Few pairs found: the neighbors are farther apart than the search.
            if pairs * 4 < result.positions.count() - options.target + pairs:
                cell *= 2.0
                widenings += 1
    if result.positions.count() > options.target: try prune(&result, options.target, options.keep_mass)
    return result

# mark: Merging

## A candidate pair and its cost.
struct Pair:
    let cost: f64
    let a: u32
    let b: u32

func cheaper(x: Pair, y: Pair) -> bool:
    return x.cost < y.cost or (x.cost == y.cost and (x.a < y.a or (x.a == y.a and x.b < y.b)))

let graph_degree: usize = 6
let unmatched: u32 = 0xFFFFFFFF

## One merge pass over `reduced` with neighbors searched in cubes of `cell`:
## up to count - target pairs merged; returns how many.
func merge_pass(reduced: Reduced*, target: usize, cell: f64, samples: const ShSamples*) -> usize!:
    let count = reduced.positions.count()
    let need = count - target
    let masses = try new f64[count] --- in memory.heap
    defer free(masses) in memory.heap
    splat_masses(&reduced.store, masses)
    var hash = try PointHash.for_radius(reduced.positions.view(), cell)
    defer hash.close()
    let neighbors = try new u32[count * graph_degree] --- in memory.heap
    defer free(neighbors) in memory.heap
    let found = try new u8[count] --- in memory.heap
    defer free(found) in memory.heap
    var search = SearchWork(&hash, cell, neighbors, found)
    # In slot order: a worker's queries share their neighborhoods in cache.
    ranges.each_range(count, 4096, (void*)&search, search_range)
    var listing = try PairList.of(reduced.positions.view(), masses, neighbors, found)
    defer listing.close()
    try sort_pairs(listing.pairs)
    let pairs = listing.pairs
    let partner = try new u32[count] --- in memory.heap
    defer free(partner) in memory.heap
    for at in 0..<count: partner[at] = unmatched
    var merged: usize = 0
    for pair in pairs:
        if merged >= need: break
        if partner[(usize)pair.a] != unmatched or partner[(usize)pair.b] != unmatched: continue
        partner[(usize)pair.a] = pair.b
        partner[(usize)pair.b] = pair.a
        merged += 1
    if merged == 0: return 0
    # The new cloud in the old order: a pair takes its lower index's place,
    # its attributes from the heavier splat.
    let size = count - merged
    let parents = try new i32[size] --- in memory.heap
    defer free(parents) in memory.heap
    let others = try new i32[size] --- in memory.heap
    defer free(others) in memory.heap
    var next: usize = 0
    for at in 0..<count:
        let other = partner[at]
        if other != unmatched and (usize)other < at: continue
        if other == unmatched:
            parents[next] = (i32)at
            others[next] = -1
        else:
            let heavier = at if masses[at] >= masses[(usize)other] else (usize)other
            parents[next] = (i32)heavier
            others[next] = (i32)(at + (usize)other - heavier)
        next += 1
    var made = try gathered(reduced, parents)
    errdefer made.close()
    try merge_into(reduced, &made, parents, others, masses, samples)
    made.merged = reduced.merged
    made.pruned = reduced.pruned
    reduced.close()
    *reduced = made
    return merged

struct SearchWork:
    let hash: const PointHash*
    let radius: f64
    let neighbors: u32[]
    let found: u8[]

func search_range(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (SearchWork*)context
    for slot in first..<end:
        let at = work.hash.point_at(slot)
        work.found[at] = (u8)work.hash.nearest(at, graph_degree, work.radius, work.neighbors[at * graph_degree..<(at + 1) * graph_degree])

## The candidate pairs of a pass, each once: listed by its lower splat, or by
## the higher one when the lower did not list it. Counted, then written, in
## parallel; a pair's cost is the same from either side.
struct PairList:
    var pairs: Pair[]
    ## Where splat a's pairs start (count + 1 entries).
    var starts: usize[]
    let points: const Float3[]
    let masses: const f64[]
    let neighbors: const u32[]
    let found: const u8[]

    static func of(points: const Float3[], masses: const f64[], neighbors: const u32[], found: const u8[]) -> PairList!:
        let count = points.length
        let starts = try new usize[count + 1] --- in memory.heap
        errdefer free(starts) in memory.heap
        var list = PairList(Pair[]((Pair*)0, 0), starts, points, masses, neighbors, found)
        ranges.each_range(count, 8192, (void*)&list, count_pairs)
        var total: usize = 0
        for at in 0..<count:
            let own = starts[at]
            starts[at] = total
            total += own
        starts[count] = total
        list.pairs = try new Pair[total + 1] --- in memory.heap
        list.pairs = list.pairs[..<total]
        ranges.each_range(count, 8192, (void*)&list, write_pairs)
        return list

    func close():
        free(self.starts) in memory.heap
        free(Pair[](self.pairs.data, self.pairs.length + 1)) in memory.heap

    ## Whether splat a writes its pair with its `slot`-th neighbor.
    func owns(a: usize, slot: usize) -> bool:
        let b = (usize)self.neighbors[a * graph_degree + slot]
        if a < b: return true
        for other in 0..<(usize)self.found[b]:
            if (usize)self.neighbors[b * graph_degree + other] == a: return false
        return true

func count_pairs(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let list = (PairList*)context
    for a in first..<end:
        var own: usize = 0
        for slot in 0..<(usize)list.found[a]:
            if list.owns(a, slot): own += 1
        list.starts[a] = own

func write_pairs(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let list = (PairList*)context
    for a in first..<end:
        var at = list.starts[a]
        for slot in 0..<(usize)list.found[a]:
            if not list.owns(a, slot): continue
            let b = (usize)list.neighbors[a * graph_degree + slot]
            let ma = list.masses[a]
            let mb = list.masses[b]
            let weight = ma * mb / (ma + mb) if ma + mb > 0.0 else 0.0
            let d = list.points[a].vector().subtract(list.points[b].vector())
            list.pairs[at] = Pair(weight * d.dot(d), (u32)(a if a < b else b), (u32)(b if a < b else a))
            at += 1

## Sort `pairs` by `cheaper` on the pool: equal runs sorted in parallel, then
## merged pairwise level by level, each level's merges in parallel. `cheaper`
## is a strict total order, so the result is what one sort would give.
func sort_pairs(pairs: Pair[]) -> !:
    let n = pairs.length
    if n < 131072:
        sort.by(pairs, cheaper)
        return
    # 4, 16 or 64 runs: an even number of merge levels ends back in `pairs`.
    var runs: usize = 4
    while runs < 64 and n // (runs * 4) >= 32768: runs *= 4
    let scratch = try new Pair[n] --- in memory.heap
    defer free(scratch) in memory.heap
    var work = SortWork(pairs, scratch, runs, 1)
    ranges.each(runs, (void*)&work, sort_run)
    while work.span < runs:
        ranges.each(runs // (work.span * 2), (void*)&work, merge_runs)
        let read = work.source
        work.source = work.target
        work.target = read
        work.span *= 2

struct SortWork:
    ## Merges read `source` and write `target`, `span` sorted runs at a time.
    var source: Pair[]
    var target: Pair[]
    let runs: usize
    var span: usize

    ## Where run `run` starts.
    func bound(run: usize) -> usize:
        return run * self.source.length // self.runs

func sort_run(context: void*, index: usize, worker: usize):
    _ = worker
    let work = (SortWork*)context
    sort.by(work.source[work.bound(index)..<work.bound(index + 1)], cheaper)

func merge_runs(context: void*, index: usize, worker: usize):
    _ = worker
    let work = (SortWork*)context
    let low = work.bound(index * 2 * work.span)
    let middle = work.bound((index * 2 + 1) * work.span)
    let high = work.bound((index * 2 + 2) * work.span)
    var a = low
    var b = middle
    for at in low..<high:
        if b >= high or (a < middle and not cheaper(work.source[b], work.source[a])):
            work.target[at] = work.source[a]
            a += 1
        else:
            work.target[at] = work.source[b]
            b += 1

## `reduced` through parent map `parents`: positions and point attributes
## gathered, detail attributes shared.
func gathered(reduced: const Reduced*, parents: const i32[]) -> Reduced!:
    let size = parents.length
    var positions = try Column[Float3].allocate(size)
    errdefer positions.release()
    var moving = PointGather(reduced.positions.view(), positions.span(), parents)
    ranges.each_range(size, 65536, (void*)&moving, gather_points)
    var attributes = AttributeStore()
    errdefer attributes.close()
    for index in 0..<reduced.store.count():
        let entry = reduced.store.entry(index)
        if entry.domain != Domain.point:
            try attributes.put(entry.share())
            continue
        try attributes.put(try attribute_ops.remapped(entry, parents, size))
    return Reduced(positions, attributes, 0, 0)

struct PointGather:
    let points: const Float3[]
    let out: Float3[]
    let parents: const i32[]

func gather_points(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (PointGather*)context
    for at in first..<end: work.out[at] = work.points[(usize)work.parents[at]]

## Write the merged splats of `made` (gathered from `reduced` by `parents`;
## `others` names each merged element's second splat, -1 for none).
func merge_into(reduced: const Reduced*, made: Reduced*, parents: const i32[], others: const i32[], masses: const f64[], samples: const ShSamples*) -> !:
    let source = &reduced.store
    let size = parents.length
    var work: MergeWork
    work.parents = parents
    work.others = others
    work.masses = masses
    work.samples = samples
    work.points = reduced.positions.view()
    work.out_points = made.positions.span()
    work.orient = Floats.of(source.entry((usize)float_attribute(source, orient_name, 4)))
    work.scale = Floats.of(source.entry((usize)float_attribute(source, scale_name, 3)))
    work.opacity = Floats.of(source.entry((usize)float_attribute(source, opacity_name, 1)))
    let color_index = float_attribute(source, color_name, 3)
    work.has_color = color_index >= 0
    if work.has_color: work.color = Floats.of(source.entry((usize)color_index))
    let rest_index = float_attribute(source, restorient_name, 4)
    work.has_rest = rest_index >= 0
    if work.has_rest: work.rest = Floats.of(source.entry((usize)rest_index))
    let sh_index = sh_attribute(source)
    if sh_index >= 0: work.sh = source.entry((usize)sh_index)
    # The writable columns of the new cloud (copies of its own).
    let store = &made.store
    work.out_orient = try writable_float32(store, (usize)float_attribute(store, orient_name, 4), size)
    work.out_scale = try writable_float32(store, (usize)float_attribute(store, scale_name, 3), size)
    let opacity_out = (usize)float_attribute(store, opacity_name, 1)
    work.opacity_kind = store.entry(opacity_out).kind
    work.out_opacity = try store.writable(opacity_out)
    if work.has_color:
        let at = (usize)float_attribute(store, color_name, 3)
        work.color_kind = store.entry(at).kind
        work.out_color = try store.writable(at)
    if work.has_rest: work.out_rest = try writable_float32(store, (usize)float_attribute(store, restorient_name, 4), size)
    let out_sh = sh_attribute(store)
    if out_sh >= 0:
        work.out_sh = try writable_sh(store, (usize)out_sh)
        work.out_sh_entry = store.entry((usize)out_sh)
    ranges.each_range(size, 2048, (void*)&work, merge_range)

struct MergeWork:
    var parents: const i32[]
    var others: const i32[]
    var masses: const f64[]
    var samples: const ShSamples*?
    var points: const Float3[]
    var out_points: Float3[]
    var orient: Floats
    var scale: Floats
    var opacity: Floats
    var color: Floats
    var rest: Floats
    var has_color: bool
    var has_rest: bool
    var sh: const Attribute*?
    var out_orient: f32[]
    var out_scale: f32[]
    var out_opacity: u8[]
    var opacity_kind: DataType
    var out_color: u8[]
    var color_kind: DataType
    var out_rest: f32[]
    var out_sh: f32[]
    var out_sh_entry: const Attribute*?

    func quat(values: const Floats*, at: usize) -> Quat:
        return Quat(values.at(at, 0), values.at(at, 1), values.at(at, 2), values.at(at, 3)).normalized()

    ## Element `at` of the new cloud, when it is a merged pair.
    func merge(at: usize):
        if self.others[at] < 0: return
        let pair: usize[2] = [(usize)self.parents[at], (usize)self.others[at]]
        let total = self.masses[pair[0]] + self.masses[pair[1]]
        var weights: f64[2] = [0.5, 0.5]
        if total > 0.0: weights = [self.masses[pair[0]] / total, self.masses[pair[1]] / total]
        var center = Vector3()
        for k in 0..<(usize)2: center = center.add(self.points[pair[k]].vector().multiply_scalar(weights[k]))
        var sigma = Mat3.diagonal(Vector3())
        var color = Vector3()
        for k in 0..<(usize)2:
            let s = pair[k]
            let d = self.points[s].vector().subtract(center)
            let own = compose_covariance(self.quat(&self.orient, s), Vector3(self.scale.at(s, 0), self.scale.at(s, 1), self.scale.at(s, 2)))
            let spread = Mat3([d.x * d.x, d.x * d.y, d.x * d.z, d.y * d.x, d.y * d.y, d.y * d.z, d.z * d.x, d.z * d.y, d.z * d.z])
            for e in 0..<(usize)9: sigma.m[e] = sigma.m[e] + weights[k] * (own.m[e] + spread.m[e])
            if self.has_color: color = color.add(Vector3(self.color.at(s, 0), self.color.at(s, 1), self.color.at(s, 2)).multiply_scalar(weights[k]))
        let shape = decompose_covariance(sigma)
        let volume = shape.scale.x * shape.scale.y * shape.scale.z
        var alpha = math.max(self.opacity.at(pair[0], 0), self.opacity.at(pair[1], 0))
        if volume > 0.0: alpha = math.min(total / volume, 1.0)
        self.out_points[at] = Float3.of(center)
        write_quat(self.out_orient, at, shape.orient)
        self.out_scale[at * 3] = (f32)shape.scale.x
        self.out_scale[at * 3 + 1] = (f32)shape.scale.y
        self.out_scale[at * 3 + 2] = (f32)shape.scale.z
        attribute_ops.write_number(self.out_opacity, self.opacity_kind, at, alpha)
        if self.has_color:
            attribute_ops.write_number(self.out_color, self.color_kind, at * 3, color.x)
            attribute_ops.write_number(self.out_color, self.color_kind, at * 3 + 1, color.y)
            attribute_ops.write_number(self.out_color, self.color_kind, at * 3 + 2, color.z)
        # The merged splat's SH are in the world frame.
        if self.has_rest: write_quat(self.out_rest, at, shape.orient)
        self.merge_sh(at, pair, weights)

    ## The mass-weighted mean of the pair's SH, each turned into the world
    ## frame, into the new element's items (as many as it has).
    func merge_sh(at: usize, pair: usize[2], weights: f64[2]):
        let source = self.sh else return
        let target = self.out_sh_entry else return
        let samples = self.samples else return
        let items = target.item_count(at)
        let first = target.first_item(at)
        var sum: f64[45]
        for k in 0..<(usize)2:
            let s = pair[k]
            var own: f32[45]
            let have = source.item_count(s) if source.item_count(s) < 15 else 15
            for item in 0..<have:
                for channel in 0..<(usize)3: own[item * 3 + channel] = (f32)source.item(s, item, channel)
            if self.has_rest:
                let frame = sh_frame(self.quat(&self.orient, s), self.quat(&self.rest, s))
                let turn = ShRotation.of(samples, frame)
                turn.apply(own[..<have * 3], have)
            for at_value in 0..<have * 3: sum[at_value] = sum[at_value] + weights[k] * (f64)own[at_value]
        for value in 0..<(items if items < 15 else 15) * 3: self.out_sh[first * 3 + value] = (f32)sum[value]

func merge_range(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (MergeWork*)context
    for at in first..<end: work.merge(at)

# mark: Pruning

## A splat's score and its index, highest first.
struct Weighed:
    let mass: f64
    let index: u32

func heavier_first(x: Weighed, y: Weighed) -> bool:
    return x.mass > y.mass or (x.mass == y.mass and x.index < y.index)

## Keep the `target` most important splats of `reduced` (in their order; see
## the module comment), scaling the kept opacities by the lost mass when
## `keep_mass`.
func prune(reduced: Reduced*, target: usize, keep_mass: bool) -> !:
    let count = reduced.positions.count()
    let masses = try new f64[count] --- in memory.heap
    defer free(masses) in memory.heap
    splat_masses(&reduced.store, masses)
    let scores = try new f64[count] --- in memory.heap
    defer free(scores) in memory.heap
    try importance_scores(reduced.positions.view(), &reduced.store, masses, scores)
    let ranked = try new Weighed[count] --- in memory.heap
    defer free(ranked) in memory.heap
    var before: f64 = 0.0
    for at in 0..<count:
        ranked[at] = Weighed(scores[at], (u32)at)
        before += masses[at]
    sort.by(ranked, heavier_first)
    let keep = try new u8[count] in memory.heap
    defer free(keep) in memory.heap
    var after: f64 = 0.0
    for at in 0..<target:
        keep[(usize)ranked[at].index] = 1
        after += masses[(usize)ranked[at].index]
    let parents = try new i32[target + 1] --- in memory.heap
    defer free(parents) in memory.heap
    var next: usize = 0
    for at in 0..<count:
        if keep[at] == 0: continue
        parents[next] = (i32)at
        next += 1
    var made = try gathered(reduced, parents[..<target])
    errdefer made.close()
    let opacity = float_attribute(&made.store, opacity_name, 1)
    if keep_mass and opacity >= 0 and after > 0.0 and before > after:
        let entry = made.store.entry((usize)opacity)
        let kind = entry.kind
        let alpha = Floats.of(entry)
        # Each kept splat's mass per unit opacity (its σ₁σ₂σ₃), and the factor f
        # whose clamped opacities min(f·α, 1) hold the lost mass, by bisection
        # (the clamp makes the mass a monotone, piecewise linear function of f).
        let kept_masses = try new f64[target + 1] --- in memory.heap
        defer free(kept_masses) in memory.heap
        splat_masses(&made.store, kept_masses[..<target])
        var low: f64 = 1.0
        var high: f64 = before / after
        while clamped_mass(&alpha, kept_masses[..<target], high) < before and high < 1.0e12: high *= 2.0
        for _ in 0..<(usize)60:
            let middle = 0.5 * (low + high)
            if clamped_mass(&alpha, kept_masses[..<target], middle) < before: low = middle
            else: high = middle
        let factor = high
        var values = try new f64[target + 1] --- in memory.heap
        defer free(values) in memory.heap
        for at in 0..<target: values[at] = math.min(alpha.at(at, 0) * factor, 1.0)
        let bytes = try made.store.writable((usize)opacity)
        for at in 0..<target: attribute_ops.write_number(bytes, kind, at, values[at])
    made.merged = reduced.merged
    made.pruned = reduced.pruned + count - target
    reduced.close()
    *reduced = made

## Neighbors a splat's color contrast is measured against.
let contrast_neighbors: usize = 8

## Each point's importance into `scores` (see the module comment). Plain
## points (no splat attributes) score their mass, which is 1 each; points
## without Cd have no contrast.
func importance_scores(points: const Float3[], store: const AttributeStore*, masses: const f64[], scores: f64[]) -> !:
    let count = points.length
    if not is_splat_store(store):
        for at in 0..<count: scores[at] = masses[at]
        return
    var work: ScoreWork
    work.points = points
    work.scale = Floats.of(store.entry((usize)float_attribute(store, scale_name, 3)))
    work.alpha = Floats.of(store.entry((usize)float_attribute(store, opacity_name, 1)))
    let color = float_attribute(store, color_name, 3)
    work.color = Floats.of(store.entry((usize)color)) if color >= 0 else Floats.empty()
    work.scores = scores
    # The median projected area, over a sample (a scale for the power).
    let sample = count if count < 65536 else 65536
    let areas = try new f64[sample + 1] --- in memory.heap
    defer free(areas) in memory.heap
    for at in 0..<sample: areas[at] = work.area(at * count // sample)
    work.median_area = selected(areas[..<sample], sample // 2) if sample > 0 else 0.0
    work.hash = none
    let radius = 3.0 * (try median_largest(&work.scale, count))
    work.radius = radius
    var hash = try PointHash.for_radius(points, radius if radius > 0.0 else 1.0)
    defer hash.close()
    if radius > 0.0 and work.color.present(): work.hash = &hash
    ranges.each_range(count, 2048, (void*)&work, score_range)

struct ScoreWork:
    var points: const Float3[]
    var scale: Floats
    var alpha: Floats
    var color: Floats
    var scores: f64[]
    var median_area: f64
    var radius: f64
    var hash: const PointHash*?

    ## Splat `at`'s mean projected area over directions, up to π.
    func area(at: usize) -> f64:
        let a = math.abs(self.scale.at(at, 0))
        let b = math.abs(self.scale.at(at, 1))
        let c = math.abs(self.scale.at(at, 2))
        let value = (a * b + b * c + a * c) / 3.0
        return value if math.is_finite(value) else 0.0

func score_range(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (ScoreWork*)context
    var neighbors: u32[16]
    for at in first..<end:
        let alpha = math.clamp(work.alpha.at(at, 0), 0.0, 1.0)
        var size = 1.0
        if work.median_area > 0.0: size = math.pow(work.area(at) / work.median_area, 0.1)
        var contrast = 0.0
        if let hash = work.hash:
            let found = hash.nearest(at, contrast_neighbors, work.radius, neighbors[..<contrast_neighbors])
            var weight = 0.0
            var mean = Vector3()
            for k in 0..<found:
                let other = (usize)neighbors[k]
                let w = math.max(work.alpha.at(other, 0), 0.0)
                weight += w
                mean = mean.add(Vector3(work.color.at(other, 0), work.color.at(other, 1), work.color.at(other, 2)).multiply_scalar(w))
            if weight > 0.0:
                let own = Vector3(work.color.at(at, 0), work.color.at(at, 1), work.color.at(at, 2))
                contrast = own.subtract(mean.multiply_scalar(1.0 / weight)).length()
        let score = alpha * size * (1.0 + 4.0 * contrast)
        work.scores[at] = score if math.is_finite(score) else 0.0

## The mass of splats of `masses` (at opacities `alpha`) with every opacity
## scaled by `factor` and clamped to 1.
func clamped_mass(alpha: const Floats*, masses: const f64[], factor: f64) -> f64:
    var total: f64 = 0.0
    for at in 0..<masses.length:
        let a = alpha.at(at, 0)
        if not (a > 0.0): continue
        total += masses[at] * math.min(a * factor, 1.0) / a
    return total