Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.7

0.7.7 / 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))