Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / booleans / bvh.lucb

# mark: Box tree ===============================================================================

## Leaves hold at most this many triangles.
let box_leaf: usize = 8

struct BoxNode:
    var lo: Vector3
    var hi: Vector3
    ## Leaf: its first entry in `order`. Inner: the right child (the left
    ## follows its parent).
    var first: u32
    ## Leaf: how many triangles. Inner: 0.
    var count: u32

## A bounding-volume tree over one operand's triangles, in f64 so every box
## holds its triangle's exact points: two boxes that miss each other prove
## the triangles do. Built as a linear BVH (Lauterbach et al. 2009): the
## triangles sorted along a Morton curve through their box centers, then
## halved by count, so building costs a sort and one pass.
pub struct BoxTree:
    var nodes: Growing[BoxNode]
    var order: Growing[u32]
    var lo: Growing[Vector3]
    var hi: Growing[Vector3]

    func init():
        self.nodes = Growing[BoxNode]()
        self.order = Growing[u32]()
        self.lo = Growing[Vector3]()
        self.hi = Growing[Vector3]()

    func close():
        self.nodes.close()
        self.order.close()
        self.lo.close()
        self.hi.close()

    ## Build over triangles first..<end of `operands`.
    func build(operands: const Operands*, first: usize, end: usize) -> !:
        let count = end - first
        try self.order.reserve(count)
        try self.lo.reserve(count)
        try self.hi.reserve(count)
        self.order.count = count
        self.lo.count = count
        self.hi.count = count
        if count == 0: return
        var boxes = BoxWork(operands, first, self.lo.items, self.hi.items)
        try parallel.for_each_range(count, 16384, (void*)&boxes, box_range)
        # Morton codes of the box centers in the whole box, with the
        # triangle in the low half of each key so the order is total.
        var lo = self.lo.items[0]
        var hi = self.hi.items[0]
        for at in 1..<count:
            lo = lower(lo, self.lo.items[at])
            hi = upper(hi, self.hi.items[at])
        let keys = try new u64[count * 2] --- in memory.heap
        defer free(keys) in memory.heap
        var coding = CodeWork(self.lo.items, self.hi.items, lo, hi, keys[..<count])
        try parallel.for_each_range(count, 16384, (void*)&coding, code_range)
        radix_sort(keys[..<count], keys[count..<count * 2])
        for at in 0..<count: self.order.items[at] = (u32)(keys[at] & 0xFFFFFFFF)
        try self.nodes.reserve(2 * (count // box_leaf + 1))
        _ = try self.make(0, count)

    ## The subtree over order[first..<end], halved by count; its index.
    func make(first: usize, end: usize) -> usize!:
        let id = self.nodes.count
        if end - first <= box_leaf:
            var lo = self.lo.items[(usize)self.order.items[first]]
            var hi = self.hi.items[(usize)self.order.items[first]]
            for at in first + 1..<end:
                let t = (usize)self.order.items[at]
                lo = lower(lo, self.lo.items[t])
                hi = upper(hi, self.hi.items[t])
            try self.nodes.push(BoxNode(lo, hi, (u32)first, (u32)(end - first)))
            return id
        try self.nodes.push(BoxNode(Vector3(), Vector3(), 0, 0))
        let middle = first + (end - first) // 2
        let left = try self.make(first, middle)
        let right = try self.make(middle, end)
        let a = self.nodes.items[left]
        let b = self.nodes.items[right]
        self.nodes.items[id] = BoxNode(lower(a.lo, b.lo), upper(a.hi, b.hi), (u32)right, 0)
        return id

    ## The triangles (operand numbering) whose boxes meet [lo, hi], appended
    ## to `found` in tree order.
    func overlapping(lo: Vector3, hi: Vector3, base: usize, found: Growing[u32]*) -> !:
        if self.nodes.count == 0: return
        var stack: u32[64] = ---
        var count: usize = 1
        stack[0] = 0
        while count > 0:
            count -= 1
            let id = (usize)stack[count]
            let node = self.nodes.items[id]
            if node.lo.x > hi.x or node.hi.x < lo.x or node.lo.y > hi.y or node.hi.y < lo.y or node.lo.z > hi.z or node.hi.z < lo.z: continue
            if node.count == 0:
                stack[count] = node.first
                stack[count + 1] = (u32)(id + 1)
                count += 2
                continue
            for at in (usize)node.first..<(usize)(node.first + node.count):
                let t = (usize)self.order.items[at]
                let a = self.lo.items[t]
                let b = self.hi.items[t]
                if a.x > hi.x or b.x < lo.x or a.y > hi.y or b.y < lo.y or a.z > hi.z or b.z < lo.z: continue
                try found.push((u32)(base + t))

## Sort 64-bit keys by their high 32 bits (the low half is unique, so the
## order is total), least significant byte first, through `scratch`.
func radix_sort(keys: u64[], scratch: u64[]):
    var source = keys
    var target = scratch
    for pass in 0..<(u64)4:
        let shift = 32 + pass * 8
        var counts: usize[257] = ---
        for at in 0..<(usize)257: counts[at] = 0
        for key in source: counts[(usize)((key >> shift) & 0xFF) + 1] += 1
        for at in 1..<(usize)257: counts[at] += counts[at - 1]
        for key in source:
            let digit = (usize)((key >> shift) & 0xFF)
            target[counts[digit]] = key
            counts[digit] += 1
        let swap = source
        source = target
        target = swap
    # Four passes: the sorted keys are back in `keys`.

## Spread the low 10 bits of `x` to every third bit.
func morton_spread(x: u64) -> u64:
    var v = x & 0x3FF
    v = (v | (v << 16)) & 0x30000FF
    v = (v | (v << 8)) & 0x300F00F
    v = (v | (v << 4)) & 0x30C30C3
    v = (v | (v << 2)) & 0x9249249
    return v

struct CodeWork:
    let lo: const Vector3[]
    let hi: const Vector3[]
    let low: Vector3
    let high: Vector3
    var keys: u64[]

## Each triangle's key: the Morton code of its box center on a 1024-cell
## grid over all boxes, then its number.
func code_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (CodeWork*)context
    let size = work.high.subtract(work.low)
    let sx = 1023.0 / size.x if size.x > 0.0 else 0.0
    let sy = 1023.0 / size.y if size.y > 0.0 else 0.0
    let sz = 1023.0 / size.z if size.z > 0.0 else 0.0
    for at in first..<end:
        let center = work.lo[at].add(work.hi[at]).multiply_scalar(0.5).subtract(work.low)
        let x = (u64)math.min(1023.0, math.max(0.0, center.x * sx))
        let y = (u64)math.min(1023.0, math.max(0.0, center.y * sy))
        let z = (u64)math.min(1023.0, math.max(0.0, center.z * sz))
        let code = (morton_spread(x) << 2) | (morton_spread(y) << 1) | morton_spread(z)
        work.keys[at] = (code << 32) | (u64)at

struct BoxWork:
    let operands: const Operands*
    let first: usize
    let lo: Vector3[]
    let hi: Vector3[]

func box_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (BoxWork*)context
    for at in first..<end:
        let t = work.first + at
        let a = work.operands.place(t, 0)
        let b = work.operands.place(t, 1)
        let c = work.operands.place(t, 2)
        work.lo[at] = lower(a, lower(b, c))
        work.hi[at] = upper(a, upper(b, c))

func lower(a: Vector3, b: Vector3) -> Vector3:
    return Vector3(math.min(a.x, b.x), math.min(a.y, b.y), math.min(a.z, b.z))

func upper(a: Vector3, b: Vector3) -> Vector3:
    return Vector3(math.max(a.x, b.x), math.max(a.y, b.y), math.max(a.z, b.z))