dymokomi/luce-geocore
Source of release 0.7.5
0.7.5 / src / fields / sample.lucb
## Level sets from other geometry, as narrow-band sparse grids: an SDF
## sampled and a union of spheres around points (a mesh's signed distance
## is mesh_distance.lucb). Voxels `voxel` apart on an axis-aligned grid through the origin;
## `band` voxels of distance kept on each side of the surface (values clamp
## to ±band voxels, and only the band's voxels are active).
##
## Leaves are found first, then filled in parallel. For an SDF, blocks of
## 8×8×8 leaves, then leaves, are skipped when their center is farther from
## the surface than their half diagonal plus the band: the field is
## 1-Lipschitz, so no surface can be inside them.
## The index-to-world transform of voxels `voxel` apart.
pub func voxel_transform(voxel: f64) -> Matrix4:
return Matrix4(Vector3(voxel, 0.0, 0.0), Vector3(0.0, voxel, 0.0), Vector3(0.0, 0.0, voxel), Vector3())
func check_voxel(voxel: f64, band: f64) -> !:
if not (voxel > 0.0 and voxel < 1.0e6) or not (band >= 1.0 and band <= 64.0):
error(errors.invalid, "a level set needs a positive voxel size and a band of 1..64 voxels")
## The leaf range covering `box` grown by `margin`: lowest leaf and counts.
func leaf_range(box: Bounds, margin: f64, voxel: f64) -> (i64, i64, i64, i64, i64, i64)!:
let size = voxel * 8.0
let lx = (i64)math.floor((box.minimum.x - margin) / size)
let ly = (i64)math.floor((box.minimum.y - margin) / size)
let lz = (i64)math.floor((box.minimum.z - margin) / size)
let hx = (i64)math.floor((box.maximum.x + margin) / size)
let hy = (i64)math.floor((box.maximum.y + margin) / size)
let hz = (i64)math.floor((box.maximum.z + margin) / size)
let nx = hx - lx + 1
let ny = hy - ly + 1
let nz = hz - lz + 1
if lx < -key_bias or ly < -key_bias or lz < -key_bias or hx >= key_bias or hy >= key_bias or hz >= key_bias or (f64)nx * (f64)ny * (f64)nz > 1.0e9:
error(errors.limit, "the voxels are too small for this extent")
return (lx, ly, lz, nx, ny, nz)
# mark: SDF
## A narrow-band level set of `sdf`.
pub func sampled_sdf(sdf: const Sdf*, voxel: f64, band: f64, name: str) -> SparseGrid*!:
try check_voxel(voxel, band)
let (lx, ly, lz, nx, ny, nz) = try leaf_range(sdf.bounds(), band * voxel, voxel)
# Blocks of 8 leaves a side, each marking its leaves near the surface.
let bx = (nx + 7) // 8
let by = (ny + 7) // 8
let bz = (nz + 7) // 8
let blocks = (usize)(bx * by * bz)
var marks = try Column[u64].filled(blocks * mask_words, 0)
defer marks.release()
var find = FindWork(sdf, voxel, band, lx, ly, lz, nx, ny, nz, bx, by, marks.span())
try parallel.for_each_range(blocks, 1, (void*)&find, find_leaves)
var keys = Growing[u64]()
defer keys.close()
try gather_marks(marks.view(), lx, ly, lz, bx, by, &keys)
var fill = SdfFill(sdf, voxel, band)
return try grid_of_leaves(name, GridClass.level_set, (f32)(band * voxel), voxel_transform(voxel), keys.view(), fill_sdf_leaf, (void*)&fill)
struct FindWork:
let sdf: const Sdf*
let voxel: f64
let band: f64
let lx: i64
let ly: i64
let lz: i64
let nx: i64
let ny: i64
let nz: i64
let bx: i64
let by: i64
let marks: u64[]
func find_leaves(context: void*, first: usize, end: usize, worker: usize):
let work = (FindWork*)context
let leaf_world = work.voxel * 8.0
let reach = work.band * work.voxel
for block in first..<end:
let b = (i64)block
let x0 = (b % work.bx) * 8
let y0 = ((b // work.bx) % work.by) * 8
let z0 = (b // (work.bx * work.by)) * 8
# The block's center and half diagonal, in world units.
let block_center = Vector3(((f64)(work.lx + x0) + 4.0) * leaf_world, ((f64)(work.ly + y0) + 4.0) * leaf_world, ((f64)(work.lz + z0) + 4.0) * leaf_world)
if math.abs(work.sdf.distance(block_center)) > 4.0 * leaf_world * 1.7320508075688772 + reach: continue
let words = work.marks[block * mask_words..<(block + 1) * mask_words]
for voxel_at in 0..<leaf_voxels:
let x = x0 + (i64)(voxel_at & 7)
let y = y0 + (i64)((voxel_at >> 3) & 7)
let z = z0 + (i64)(voxel_at >> 6)
if x >= work.nx or y >= work.ny or z >= work.nz: continue
let middle = Vector3(((f64)(work.lx + x) + 0.5) * leaf_world, ((f64)(work.ly + y) + 0.5) * leaf_world, ((f64)(work.lz + z) + 0.5) * leaf_world)
if math.abs(work.sdf.distance(middle)) > 0.5 * leaf_world * 1.7320508075688772 + reach: continue
words[voxel_at >> 6] = words[voxel_at >> 6] | ((u64)1 << (u64)(voxel_at & 63))
## Leaf keys of every marked leaf.
func gather_marks(marks: const u64[], lx: i64, ly: i64, lz: i64, bx: i64, by: i64, out: Growing[u64]*) -> !:
for block in 0..<marks.length // mask_words:
let b = (i64)block
let x0 = (b % bx) * 8
let y0 = ((b // bx) % by) * 8
let z0 = (b // (bx * by)) * 8
for word in 0..<mask_words:
var bits = marks[block * mask_words + word]
while bits != 0:
let bit = (usize)trailing_zeros(bits)
bits = bits & (bits - 1)
let voxel_at = word * 64 + bit
try out.push(leaf_key(lx + x0 + (i64)(voxel_at & 7), ly + y0 + (i64)((voxel_at >> 3) & 7), lz + z0 + (i64)(voxel_at >> 6)))
struct SdfFill:
let sdf: const Sdf*
let voxel: f64
let band: f64
func fill_sdf_leaf(context: void*?, leaf: usize, key: u64, values: f32[], mask: u64[]):
let work = (SdfFill*)(context else return)
_ = leaf
let (lx, ly, lz) = key_leaf(key)
let limit = work.band * work.voxel
for at in 0..<mask_words: mask[at] = 0
for voxel_at in 0..<leaf_voxels:
let point = Vector3((f64)(lx * 8 + (i64)(voxel_at & 7)) * work.voxel, (f64)(ly * 8 + (i64)((voxel_at >> 3) & 7)) * work.voxel, (f64)(lz * 8 + (i64)(voxel_at >> 6)) * work.voxel)
let d = work.sdf.distance(point)
values[voxel_at] = (f32)math.clamp(d, -limit, limit)
if math.abs(d) < limit: mask[voxel_at >> 6] = mask[voxel_at >> 6] | ((u64)1 << (u64)(voxel_at & 63))
# mark: Points
## A union of spheres of `radius` around `points` (world), as a level set.
pub func points_level_set(points: const Vector3[], radius: f64, voxel: f64, band: f64, name: str) -> SparseGrid*!:
try check_voxel(voxel, band)
if not (radius > 0.0 and radius < 1.0e6): error(errors.invalid, "spheres need a positive radius")
if points.length == 0: error(errors.invalid, "there are no points")
let reach = radius + band * voxel
let size = voxel * 8.0
# Points bucketed by leaf, so a leaf finds its neighbors.
var buckets = Growing[u64]()
defer buckets.close()
for at in 0..<points.length:
let p = points[at]
try buckets.push(leaf_key((i64)math.floor(p.x / size), (i64)math.floor(p.y / size), (i64)math.floor(p.z / size)))
# Every leaf within reach of an occupied one (occupied leaves once each).
var occupied = Growing[u64]()
defer occupied.close()
try occupied.assign(buckets.view())
try sort_keys(occupied.items[..<occupied.count])
occupied.count = unique_keys(occupied.items[..<occupied.count])
var keys = Growing[u64]()
defer keys.close()
let span = (i64)math.ceil(reach / size)
for bucket in occupied.view():
let (x, y, z) = key_leaf(bucket)
for dz in -span..=span:
for dy in -span..=span:
for dx in -span..=span:
try keys.push(leaf_key(x + dx, y + dy, z + dz))
if keys.count > 200000000: error(errors.limit, "the voxels are too small for these spheres")
# Each point once per leaf key it sits in, sorted, for neighbor search.
var order = Growing[u64]()
defer order.close()
for at in 0..<points.length: try order.push((u64)at)
try sort_by_key(order.items[..<order.count], buckets.view())
var fill = PointFill(points, buckets.view(), order.view(), radius, voxel, band, span)
return try grid_of_leaves(name, GridClass.level_set, (f32)(band * voxel), voxel_transform(voxel), keys.view(), fill_point_leaf, (void*)&fill)
## Point indices sorted by their leaf keys (stable).
func sort_by_key(order: u64[], keys: const u64[]) -> !:
let scratch = try new u64[order.length] --- in memory.heap
defer free(scratch) in memory.heap
var from_order = true
for pass in 0..<(usize)8:
let source = order if from_order else scratch
let target = scratch if from_order else order
var counts: usize[257]
for at in 0..<(usize)257: counts[at] = 0
let shift = (u64)(pass * 8)
for index in source: counts[(usize)((keys[(usize)index] >> shift) & 255) + 1] += 1
for at in 1..<(usize)257: counts[at] += counts[at - 1]
for index in source:
let bucket = (usize)((keys[(usize)index] >> shift) & 255)
target[counts[bucket]] = index
counts[bucket] += 1
from_order = not from_order
struct PointFill:
let points: const Vector3[]
let keys: const u64[]
let order: const u64[]
let radius: f64
let voxel: f64
let band: f64
let span: i64
## The first sorted position whose point's key is at least `key`.
func first_of(work: const PointFill*, key: u64) -> usize:
var low: usize = 0
var high = work.order.length
while low < high:
let middle = (low + high) // 2
if work.keys[(usize)work.order[middle]] < key: low = middle + 1
else: high = middle
return low
func fill_point_leaf(context: void*?, leaf: usize, key: u64, values: f32[], mask: u64[]):
let work = (PointFill*)(context else return)
_ = leaf
let (lx, ly, lz) = key_leaf(key)
let limit = work.band * work.voxel
for at in 0..<leaf_voxels: values[at] = (f32)limit
for at in 0..<mask_words: mask[at] = 0
for dz in -work.span..=work.span:
for dy in -work.span..=work.span:
for dx in -work.span..=work.span:
let neighbor = leaf_key(lx + dx, ly + dy, lz + dz)
var at = first_of(work, neighbor)
while at < work.order.length and work.keys[(usize)work.order[at]] == neighbor:
let sphere = work.points[(usize)work.order[at]]
at += 1
# Only the leaf's voxels within reach of this sphere.
let reach = work.radius + limit
let x0 = math.imax(lx * 8, (i64)math.ceil((sphere.x - reach) / work.voxel))
let x1 = math.imin(lx * 8 + 7, (i64)math.floor((sphere.x + reach) / work.voxel))
let y0 = math.imax(ly * 8, (i64)math.ceil((sphere.y - reach) / work.voxel))
let y1 = math.imin(ly * 8 + 7, (i64)math.floor((sphere.y + reach) / work.voxel))
let z0 = math.imax(lz * 8, (i64)math.ceil((sphere.z - reach) / work.voxel))
let z1 = math.imin(lz * 8 + 7, (i64)math.floor((sphere.z + reach) / work.voxel))
for vz in z0..=z1:
for vy in y0..=y1:
for vx in x0..=x1:
let p = Vector3((f64)vx * work.voxel, (f64)vy * work.voxel, (f64)vz * work.voxel)
let d = p.subtract(sphere).length() - work.radius
let slot = (usize)(vx - lx * 8) + (usize)(vy - ly * 8) * 8 + (usize)(vz - lz * 8) * 64
if d < (f64)values[slot]: values[slot] = (f32)math.max(d, -limit)
for voxel_at in 0..<leaf_voxels:
if math.abs((f64)values[voxel_at]) < limit: mask[voxel_at >> 6] = mask[voxel_at >> 6] | ((u64)1 << (u64)(voxel_at & 63))