dymokomi/luce-geocore
Source of release 0.7.3
0.7.3 / src / splats / orientation.lucb
## Consistent sides for unsigned axes over a neighbor graph, after Hoppe et
## al. (1992): in each connected part of the graph, a minimum spanning tree
## by edge cost 1 - |aᵤ·aᵥ| carries one side from node to node, each node
## taking its tree neighbor's side (flipped when their axes point apart).
## Nearly parallel neighbors are joined first, so the side crosses creases
## and saddles last and seldom wrong. Each part then keeps or flips its sides
## as a whole, by the sum of the nodes' own votes for their axis (positive:
## as it points). Normals from GSplats uses it so concave regions, whose
## local votes point inward, still follow the rest of the surface.
##
## The tree is Borůvka's, so the costly part runs on the pool: each round,
## every node finds its cheapest edge to another part in parallel, each part
## keeps its nodes' cheapest, and the parts join along those edges. Parts at
## least halve each round. Edges are ordered by cost, then by their two
## nodes, a strict order that both ends see alike, so no round makes a
## cycle. A node's k-NN list is not symmetric: each node scans only its own
## list, and a part reached only through others' lists is joined by them.
from core.growing import Growing
## No edge: a node or part without a candidate this round.
let no_edge: u64 = 0xFFFFFFFFFFFFFFFF
## Into `signs` (±1 per node), the side of each axis in `axes`; `neighbors`
## holds `k` slots per node, the first `found[i]` used; `votes` are the
## nodes' own preferences.
pub func propagated_sides(axes: const Vector3[], neighbors: const u32[], found: const u8[], k: usize, votes: const f64[], signs: f64[]) -> !:
let count = axes.length
if count == 0: return
var work: TreeWork
work.axes = axes
work.neighbors = neighbors
work.found = found
work.k = k
# Union-find parents, and each node's part (its root) as of this round.
work.parents = try new u32[count] --- in memory.heap
defer free(work.parents) in memory.heap
work.parts = try new u32[count] --- in memory.heap
defer free(work.parts) in memory.heap
# Each node's cheapest edge out of its part: the key (cost, then the
# lower node), and the other end.
work.best = try new u64[count] --- in memory.heap
defer free(work.best) in memory.heap
work.other = try new u32[count] --- in memory.heap
defer free(work.other) in memory.heap
# Per root: its part's cheapest edge this round.
let part_best = try new u64[count] --- in memory.heap
defer free(part_best) in memory.heap
let part_from = try new u32[count] --- in memory.heap
defer free(part_from) in memory.heap
let part_to = try new u32[count] --- in memory.heap
defer free(part_to) in memory.heap
for node in 0..<count:
work.parents[node] = (u32)node
work.parts[node] = (u32)node
# The tree's edges, as node pairs.
var tree = Growing[u32]()
defer tree.close()
var joined = true
while joined:
joined = false
ranges.each_range(count, 4096, (void*)&work, cheapest_range)
for node in 0..<count: part_best[node] = no_edge
for node in 0..<count:
let key = work.best[node]
if key == no_edge: continue
let root = (usize)work.parts[node]
if key < part_best[root] or (key == part_best[root] and tie_below(node, (usize)work.other[node], (usize)part_from[root], (usize)part_to[root])):
part_best[root] = key
part_from[root] = (u32)node
part_to[root] = work.other[node]
for root in 0..<count:
if part_best[root] == no_edge: continue
let a = root_of(work.parents, (usize)part_from[root])
let b = root_of(work.parents, (usize)part_to[root])
if a == b: continue
# The higher root joins the lower, so labels stay deterministic.
if a < b: work.parents[b] = (u32)a
else: work.parents[a] = (u32)b
try tree.push(part_from[root])
try tree.push(part_to[root])
joined = true
for node in 0..<count: work.parts[node] = (u32)root_of(work.parents, node)
try tree_sides(axes, tree.items[..<tree.count], votes, signs)
## Whether edge (a, b) orders before (c, d) among equal keys: by the higher node.
func tie_below(a: usize, b: usize, c: usize, d: usize) -> bool:
let first = a if a > b else b
let second = c if c > d else d
return first < second
## The root of `node`, halving the path on the way.
func root_of(parents: u32[], node: usize) -> usize:
var at = node
while (usize)parents[at] != at:
let up = (usize)parents[at]
parents[at] = parents[up]
at = up
return at
struct TreeWork:
var axes: const Vector3[]
var neighbors: const u32[]
var found: const u8[]
var k: usize
var parents: u32[]
var parts: u32[]
var best: u64[]
var other: u32[]
## Each node's cheapest listed edge to another part: the key is the cost in
## the high half and the lower node in the low, so equal costs order alike
## from both ends (tie_below breaks what remains).
func cheapest_range(context: void*, first: usize, end: usize, worker: usize):
_ = worker
let work = (TreeWork*)context
for node in first..<end:
let part = work.parts[node]
let axis = work.axes[node]
var best = no_edge
var best_other: u32 = 0
for slot in 0..<(usize)work.found[node]:
let other = work.neighbors[node * work.k + slot]
if work.parts[(usize)other] == part: continue
let cost = math.clamp(1.0 - math.abs(axis.dot(work.axes[(usize)other])), 0.0, 1.0)
let low = node if node < (usize)other else (usize)other
let key = ((u64)(cost * 2147483647.0) << 32) | (u64)low
if key < best or (key == best and tie_below(node, (usize)other, node, (usize)best_other)):
best = key
best_other = other
work.best[node] = best
work.other[node] = best_other
## Signs from the spanning forest `pairs` (node pairs): each part, walked from
## its first node, carries the side over every tree edge, then faces the way
## its votes say.
func tree_sides(axes: const Vector3[], pairs: const u32[], votes: const f64[], signs: f64[]) -> !:
let count = axes.length
# The forest as compressed rows.
let starts = try new usize[count + 1] in memory.heap
defer free(starts) in memory.heap
for at in 0..<pairs.length: starts[(usize)pairs[at] + 1] += 1
for node in 0..<count: starts[node + 1] += starts[node]
let edges = try new u32[pairs.length + 1] --- in memory.heap
defer free(edges) in memory.heap
let filled = try new usize[count + 1] in memory.heap
defer free(filled) in memory.heap
var at: usize = 0
while at + 1 < pairs.length:
let a = (usize)pairs[at]
let b = (usize)pairs[at + 1]
edges[starts[a] + filled[a]] = (u32)b
filled[a] += 1
edges[starts[b] + filled[b]] = (u32)a
filled[b] += 1
at += 2
for node in 0..<count: signs[node] = 0.0
# A breadth-first walk per part; `order` lists the nodes as they are reached.
let order = try new u32[count + 1] --- in memory.heap
defer free(order) in memory.heap
var reached: usize = 0
for seed in 0..<count:
if signs[seed] != 0.0: continue
let first = reached
signs[seed] = 1.0
order[reached] = (u32)seed
reached += 1
var next = first
while next < reached:
let node = (usize)order[next]
next += 1
let axis = axes[node]
for other in edges[starts[node]..<starts[node + 1]]:
let to = (usize)other
if signs[to] != 0.0: continue
signs[to] = signs[node] if axis.dot(axes[to]) >= 0.0 else -signs[node]
order[reached] = other
reached += 1
# The part's own votes decide which way it faces.
var total: f64 = 0.0
for index in first..<reached: total += votes[(usize)order[index]] * signs[(usize)order[index]]
if total < 0.0:
for index in first..<reached: signs[(usize)order[index]] = -signs[(usize)order[index]]