dymokomi/luce-prism
Source of release 0.6.0
0.6.0 / src / indexes / spatial.lucb
## Uniform-grid point index. Large search bounds fall back to the occupied points.
import interop
from luce_std import math
import indexes.ranked
from query.results import Selection
from collections.index import Index
from document import Document, assemble_element, walk_document
from model import Element
from animation import resolve_property
from storage import List
from types import DType, invalid
import strings
struct Point32:
pub var x: f32
pub var y: f32
pub var z: f32
pub struct Vec3:
pub var x: f64
pub var y: f64
pub var z: f64
func narrow(point: Vec3) -> Point32:
return Point32((f32)point.x, (f32)point.y, (f32)point.z)
func distance(a: Point32, b: Point32) -> f64:
# The original subtracts float components before widening to double.
let x = (f64)(a.x - b.x)
let y = (f64)(a.y - b.y)
let z = (f64)(a.z - b.z)
return x * x + y * y + z * z
func finite(point: Point32) -> bool:
return math.is_finite((f64)point.x) and math.is_finite((f64)point.y) and math.is_finite((f64)point.z)
pub struct SpatialIndex:
var rows: Selection = Selection()
var points: List[Point32]
var grid: Index
var cell: f64
pub func init(doc: interop.Reference[Document], field: str, cell: f64 = 1.0) -> !:
self.rows = Selection()
self.points = List[Point32]()
self.grid = Index()
self.cell = cell if cell > 0.0 and math.is_finite(cell) else 1.0
errdefer self.close()
try self.build(doc, field)
func coordinate(value: f64) -> i64!:
let coordinate = math.floor(value / self.cell)
if not math.is_finite(coordinate) or coordinate < -4611686018427387904.0 or coordinate >= 4611686018427387904.0:
error(invalid, "spatial coordinate exceeds the supported grid")
return (i64)coordinate
func consider(element: const Element*, field: str) -> !:
let position = element.property(field) else return
var value = try resolve_property(&element.properties.items[position], 0.0)
defer value.close()
if value.kind != DType.float32 or value.shape.count != 1 or value.shape.items[0] != 3:
return
let point = Point32((f32)try value.number(0), (f32)try value.number(1), (f32)try value.number(2))
let x = try self.coordinate((f64)point.x)
let y = try self.coordinate((f64)point.y)
let z = try self.coordinate((f64)point.z)
var scratch: u8[100]
_ = try self.grid.add(try strings.format(scratch, f"{x}:{y}:{z}"), self.points.count)
try self.points.push(point)
try self.rows.append(element)
func build(doc: interop.Reference[Document], field: str) -> !:
let view = try doc.get()
if view.is_layered():
var paths = try walk_document(view)
defer paths.close()
for path in paths.span():
var element = try assemble_element(view, path)
defer element.close()
try self.consider(&element, field)
return
for element in view.view_data().elements.span():
try self.consider(&element, field)
pub func size() -> usize:
return self.points.count
func candidates(lo: const f64[], hi: const f64[]) -> List[usize]!:
var result: List[usize]
errdefer result.close()
var minimum: i64[3]
var maximum: i64[3]
var volume: f64 = 1.0
for i in 0..<(usize)3:
if lo[i] > hi[i]:
return result
minimum[i] = try self.coordinate(lo[i])
maximum[i] = try self.coordinate(hi[i])
volume *= (f64)maximum[i] - (f64)minimum[i] + 1.0
if volume > (f64)(self.points.count * 8 + 64):
try result.reserve(self.points.count)
for i in 0..<self.points.count:
try result.push(i)
return result
for x in minimum[0]..=maximum[0]:
for y in minimum[1]..=maximum[1]:
for z in minimum[2]..=maximum[2]:
var scratch: u8[100]
if let position = self.grid.find(try strings.format(scratch, f"{x}:{y}:{z}")):
for row in self.grid.buckets.items[position].rows.span():
try result.push(row)
return result
func sphere(center: Point32, radius: f64) -> List[ranked.Hit]!:
var result: List[ranked.Hit]
errdefer result.close()
if not finite(center) or not math.is_finite(radius):
error(invalid, "spatial query must be finite")
if radius < 0.0 or self.points.count == 0:
return result
let lo = [(f64)center.x - radius, (f64)center.y - radius, (f64)center.z - radius]
let hi = [(f64)center.x + radius, (f64)center.y + radius, (f64)center.z + radius]
var candidates = try self.candidates(lo, hi)
defer candidates.close()
let square = radius * radius
for row in candidates.span():
let squared = distance(self.points.items[row], center)
if squared <= square:
try result.push(ranked.Hit(row = row, score = -squared))
return result
pub func within(center: Vec3, radius: f64) -> interop.Reference[Selection]!:
var hits = try self.sphere(narrow(center), radius)
defer hits.close()
return try ranked.select(self.rows.view_data(), hits.span(), hits.count)
pub func count_within(center: Vec3, radius: f64) -> usize!:
var hits = try self.sphere(narrow(center), radius)
defer hits.close()
return hits.count
pub func nearest(center: Vec3, count: usize = 1) -> interop.Reference[Selection]!:
let point = narrow(center)
if not finite(point):
error(invalid, "spatial query must be finite")
var hits: List[ranked.Hit]
defer hits.close()
if count > 0:
try hits.reserve(self.points.count)
for row in 0..<self.points.count:
try hits.push(ranked.Hit(row = row, score = -distance(self.points.items[row], point)))
return try ranked.select(self.rows.view_data(), hits.span(), count)
pub func in_box(lo: Vec3, hi: Vec3) -> interop.Reference[Selection]!:
let lower = narrow(lo)
let upper = narrow(hi)
let minimum = [(f64)lower.x, (f64)lower.y, (f64)lower.z]
let maximum = [(f64)upper.x, (f64)upper.y, (f64)upper.z]
var candidates = try self.candidates(minimum, maximum)
defer candidates.close()
var hits: List[ranked.Hit]
defer hits.close()
for row in candidates.span():
let point = self.points.items[row]
if point.x >= lower.x and point.x <= upper.x and point.y >= lower.y and point.y <= upper.y and point.z >= lower.z and point.z <= upper.z:
try hits.push(ranked.Hit(row = row))
return try ranked.select(self.rows.view_data(), hits.span(), hits.count)
pub func close():
self.rows.close()
self.points.close()
self.grid.close()
pub let spatial_index_type = interop.Type[SpatialIndex]("Prism spatial index", SpatialIndex.close, closeable = true)