Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.3

0.7.3 / src / geometries / point_hash.lucb

## A spatial hash of points: each point sits in the cell of its position
## quantized to `size`, and cells hash into a power-of-two bucket table at
## least twice the points, so lookups stay constant time at any mesh size.
## Neighbor queries walk the 27 cells around a position. Fuse, mirror maps
## and soft selection share it.
from luce_std import math
from core.growing import Growing
from math.vector import Vector3

## A cell of the hash's grid, in whole cell units.
pub struct Cell:
    pub let x: i64
    pub let y: i64
    pub let z: i64

    ## The cell `dx`, `dy`, `dz` cells away.
    pub func moved(dx: i64, dy: i64, dz: i64) -> Cell:
        return Cell(self.x + dx, self.y + dy, self.z + dz)

pub struct PointHash:
    pub let size: f64
    var heads: Growing[i32]
    var next: Growing[i32]

    ## An empty hash for points 0..<`capacity`, in cells `size` wide.
    pub static func empty(capacity: usize, size: f64) -> PointHash!:
        var grid = PointHash(size, Growing[i32](), Growing[i32]())
        errdefer grid.close()
        var buckets: usize = 1024
        while buckets < capacity * 2: buckets *= 2
        try grid.heads.fill(buckets, -1)
        try grid.next.fill(capacity, -1)
        return grid

    ## A hash holding every one of `positions`.
    pub static func build(positions: const Vector3[], size: f64) -> PointHash!:
        var grid = try PointHash.empty(positions.length, size)
        for at in 0..<positions.length: grid.insert(at, positions[at])
        return grid

    ## Add point `index` (below the capacity) at `point`.
    pub func insert(index: usize, point: Vector3):
        let bucket = self.bucket(self.cell_of(point))
        self.next.items[index] = self.heads.items[bucket]
        self.heads.items[bucket] = (i32)index

    pub func cell_of(point: Vector3) -> Cell:
        return Cell((i64)math.floor(point.x / self.size), (i64)math.floor(point.y / self.size), (i64)math.floor(point.z / self.size))

    ## The last point added to `cell`'s bucket, or -1; `after` walks the rest.
    ## A bucket also holds points of other cells that hash alike.
    pub func first(cell: Cell) -> i32:
        return self.heads.items[self.bucket(cell)]

    pub func after(point: i32) -> i32:
        return self.next.items[(usize)point]

    ## The point of `positions` nearest `point` within `reach` (at most the
    ## cell size), or -1.
    pub func nearest(positions: const Vector3[], point: Vector3, reach: f64) -> i32:
        let home = self.cell_of(point)
        var found: i32 = -1
        var best = reach
        for dx in (i64)-1..<(i64)2:
            for dy in (i64)-1..<(i64)2:
                for dz in (i64)-1..<(i64)2:
                    var candidate = self.first(home.moved(dx, dy, dz))
                    while candidate >= 0:
                        let distance = positions[(usize)candidate].subtract(point).length()
                        if distance <= best:
                            best = distance
                            found = candidate
                        candidate = self.after(candidate)
        return found

    pub func close():
        self.heads.close()
        self.next.close()

    func bucket(cell: Cell) -> usize:
        let value = (cell.x *% 73856093) ^ (cell.y *% 19349663) ^ (cell.z *% 83492791)
        return (usize)(value & 0x7FFFFFFFFFFF) & (self.heads.count - 1)