dymokomi/luce-render
Source of release 0.1.4
0.1.4 / src / render / bvh.lucb
#==============================================================================================
#
# render/bvh - A binned-SAH bounding volume hierarchy over boxes
#
# DESCRIPTION:
# A binary BVH built top down over primitives' boxes: each node splits its
# primitives at the best of 12 centroid bins on each axis by the surface area
# heuristic (Wald 2007), or stays a leaf when that is cheaper (at most 4 primitives a
# leaf unless they cannot be separated). Children are stored as a pair, so an
# interior node names only its first child. The kernels traverse it with a short
# stack; it is the software path, and the layout hardware ray tracing does not need.
#
# The scene's triangles get one (their indices, polygons and shading attributes
# reordered into leaf order together), and so do its splats (splats.lucb).
#
# Node layout (32 bytes, std430 { vec3 lo; uint first; vec3 hi; uint count; }):
# an interior node has count 0 and children at `first` and `first + 1`; a leaf
# has `count` primitives from primitive `first` in leaf order. An empty tree is
# one root whose low corner is above its high one, which the kernels skip.
#
#==============================================================================================
pub struct BvhNode:
pub var lo: Float3
pub var first: u32
pub var hi: Float3
pub var count: u32
let bins: usize = 12
let leaf_size: usize = 4
## Larger groups that SAH would still keep together are split by count.
let leaf_limit: usize = 16
struct Box:
var lo: Float3
var hi: Float3
static func empty() -> Box:
return Box(Float3(3.0e38, 3.0e38, 3.0e38), Float3(-3.0e38, -3.0e38, -3.0e38))
func grow(other: Box) -> Box:
return Box(Float3(math32.min(self.lo.x, other.lo.x), math32.min(self.lo.y, other.lo.y), math32.min(self.lo.z, other.lo.z)),
Float3(math32.max(self.hi.x, other.hi.x), math32.max(self.hi.y, other.hi.y), math32.max(self.hi.z, other.hi.z)))
func grow_point(p: Float3) -> Box:
return self.grow(Box(p, p))
func area() -> f32:
let x = self.hi.x - self.lo.x
let y = self.hi.y - self.lo.y
let z = self.hi.z - self.lo.z
if x < 0.0 or y < 0.0 or z < 0.0: return 0.0
return 2.0 * (x * y + y * z + z * x)
func axis_of(p: Float3, axis: usize) -> f32:
if axis == 0: return p.x
if axis == 1: return p.y
return p.z
struct Pending:
var node: usize
var first: usize
var count: usize
## Build the scene's BVH and reorder its triangles (and their faces) into leaf order.
pub func build_bvh(scene: CompiledScene*) -> !:
let count = scene.triangle_count()
let boxes = try new Box[count] --- in memory.heap
defer free(boxes) in memory.heap
let p = scene.positions.view()
for at in 0..<count:
var box = Box.empty()
for k in 0..<(usize)3:
let i = (usize)scene.indices.items[at * 3 + k] * 3
box = box.grow_point(Float3(p[i], p[i + 1], p[i + 2]))
boxes[at] = box
let order = try new u32[count] --- in memory.heap
defer free(order) in memory.heap
try build_tree(boxes, order, &scene.nodes)
try scene.order.assign(order)
if count > 0: try reorder(scene, order)
## A BVH over `boxes` into `nodes` (cleared first), and `order`: the primitive
## at each leaf position. No boxes give an empty root (low above high).
func build_tree(boxes: const Box[], order: u32[], nodes: Growing[BvhNode]*) -> !:
let count = boxes.length
nodes.clear()
if count == 0:
try nodes.push(BvhNode(Float3(1.0, 1.0, 1.0), 0, Float3(-1.0, -1.0, -1.0), 0))
return
let centers = try new Float3[count] --- in memory.heap
defer free(centers) in memory.heap
for at in 0..<count:
let box = boxes[at]
centers[at] = Float3(0.5 * (box.lo.x + box.hi.x), 0.5 * (box.lo.y + box.hi.y), 0.5 * (box.lo.z + box.hi.z))
order[at] = (u32)at
try nodes.reserve(2 * count)
try nodes.push(BvhNode(Float3(0.0, 0.0, 0.0), 0, Float3(0.0, 0.0, 0.0), 0))
var stack = Growing[Pending]()
defer stack.close()
try stack.push(Pending(0, 0, count))
while stack.count > 0:
stack.count -= 1
let job = stack.items[stack.count]
var bounds = Box.empty()
var middle = Box.empty()
for at in job.first..<job.first + job.count:
bounds = bounds.grow(boxes[(usize)order[at]])
middle = middle.grow_point(centers[(usize)order[at]])
let leaf_cost = (f32)job.count
var left_count: usize = 0
# A node of `leaf_size` or fewer is a leaf: no split is searched.
var split = Split(-1, 0, 3.0e38)
if job.count > leaf_size: split = best_split(boxes, centers, order[job.first..<job.first + job.count], bounds, middle)
if job.count > leaf_size and (split.cost < leaf_cost or job.count > leaf_limit):
if split.axis >= 0 and split.cost < 3.0e38:
left_count = partition(centers, order[job.first..<job.first + job.count], middle, (usize)split.axis, split.bin)
if left_count == 0 or left_count == job.count:
# Centroids that bins cannot separate: halve by count.
left_count = job.count // 2
if left_count == 0:
nodes.items[job.node] = BvhNode(bounds.lo, (u32)job.first, bounds.hi, (u32)job.count)
continue
let child = nodes.count
try nodes.push(BvhNode(Float3(0.0, 0.0, 0.0), 0, Float3(0.0, 0.0, 0.0), 0))
try nodes.push(BvhNode(Float3(0.0, 0.0, 0.0), 0, Float3(0.0, 0.0, 0.0), 0))
nodes.items[job.node] = BvhNode(bounds.lo, (u32)child, bounds.hi, 0)
try stack.push(Pending(child + 1, job.first + left_count, job.count - left_count))
try stack.push(Pending(child, job.first, left_count))
struct Split:
var axis: i64
var bin: usize
var cost: f32
func bin_of(center: Float3, middle: Box, axis: usize) -> usize:
let lo = axis_of(middle.lo, axis)
let extent = axis_of(middle.hi, axis) - lo
if extent <= 0.0: return 0
let at = (i64)((f32)bins * (axis_of(center, axis) - lo) / extent)
if at < 0: return 0
return (usize)at if at < (i64)bins else bins - 1
## The cheapest bin boundary on any axis: SAH cost relative to the node's area
## (`parent` its bounds), in primitive intersections (one traversal step
## costs one).
func best_split(boxes: const Box[], centers: const Float3[], order: const u32[], parent: Box, middle: Box) -> Split:
var best = Split(-1, 0, 3.0e38)
let area = parent.area()
if area <= 0.0: return best
for axis in 0..<(usize)3:
if axis_of(middle.hi, axis) - axis_of(middle.lo, axis) <= 0.0: continue
var counts: usize[12]
var bounds: Box[12]
for b in 0..<bins:
counts[b] = 0
bounds[b] = Box.empty()
for index in order:
let b = bin_of(centers[(usize)index], middle, axis)
counts[b] += 1
bounds[b] = bounds[b].grow(boxes[(usize)index])
# Sweep from the right for the right side's areas, then from the left.
var right_area: f32[12]
var right_count: usize[12]
var sweep = Box.empty()
var total: usize = 0
var b = bins - 1
while b > 0:
sweep = sweep.grow(bounds[b])
total += counts[b]
right_area[b] = sweep.area()
right_count[b] = total
b -= 1
var left = Box.empty()
var left_count: usize = 0
for split in 1..<bins:
left = left.grow(bounds[split - 1])
left_count += counts[split - 1]
if left_count == 0 or right_count[split] == 0: continue
let cost = 1.0 + (left.area() * (f32)left_count + right_area[split] * (f32)right_count[split]) / area
if cost < best.cost: best = Split((i64)axis, split, cost)
return best
## Primitives of bins below `bin` first; the count of those.
func partition(centers: const Float3[], order: u32[], middle: Box, axis: usize, bin: usize) -> usize:
var low: usize = 0
var high = order.length
while low < high:
if bin_of(centers[(usize)order[low]], middle, axis) < bin:
low += 1
else:
high -= 1
let held = order[low]
order[low] = order[high]
order[high] = held
return low
func reorder(scene: CompiledScene*, order: const u32[]) -> !:
let count = order.length
let indices = try new u32[count * 3] --- in memory.heap
defer free(indices) in memory.heap
let faces = try new u32[count] --- in memory.heap
defer free(faces) in memory.heap
let shading = try new u32[count * 4] --- in memory.heap
defer free(shading) in memory.heap
let uvs = try new f32[count * 6] --- in memory.heap
defer free(uvs) in memory.heap
for at in 0..<count:
let source = (usize)order[at]
for k in 0..<(usize)3: indices[at * 3 + k] = scene.indices.items[source * 3 + k]
for k in 0..<(usize)4: shading[at * 4 + k] = scene.shading.items[source * 4 + k]
for k in 0..<(usize)6: uvs[at * 6 + k] = scene.uvs.items[source * 6 + k]
faces[at] = scene.faces.items[source]
memory.copy(scene.indices.items, indices, count * 3)
memory.copy(scene.faces.items, faces, count)
memory.copy(scene.shading.items, shading, count * 4)
memory.copy(scene.uvs.items, uvs, count * 6)