dymokomi/luce-render
Source of release 0.1.4
0.1.4 / src / render / scene.lucb
#==============================================================================================
#
# render/scene - A scene in the kernels' layout
#
# DESCRIPTION:
# Every polygon of a set and its visible instances as world-space triangles: f32
# positions (x, y, z per point), three point indices per triangle, each
# triangle's polygon (its face in its mesh, offset by the faces of the meshes
# before it), and its shading attributes: the normals of its three corners
# (octahedral, snorm16 × 2) and its material, four u32s. A triangle's material
# is its face's `material` attribute looked up among the set's materials
# (flattened, `materials`): its index + 1, or 0 (the render's default
# material) when the face names none or a material the set lacks. Shading normals follow
# the viewport (luce-3d's mesh batches): an authored N on the first domain that
# has one (corner, point, face, detail), else the mesh's smooth normals. Texture
# coordinates come the same way from `uv` (two f32 a corner, six a triangle;
# zero without one).
# Cameras and lights come flattened to world space. Analytic CAD has no
# triangles until a Tessellate node; such components are counted in
# `skipped`, not drawn.
#
# Splat clouds (Gaussian splats) of the set and its instances are packed by
# splats.lucb into `splats`, with a BVH of their own; plain point clouds are
# counted there, not drawn.
#
# Instances are realized into one triangle list for now; a two-level hierarchy
# (one BVH per prototype, instances above) replaces this with hardware ray tracing.
#
#==============================================================================================
pub struct CompiledScene:
pub var positions: Growing[f32]
## Three point indices per triangle; build_bvh reorders them into leaf order.
pub var indices: Growing[u32]
## Each triangle's polygon, reordered with it.
pub var faces: Growing[u32]
## Four u32s a triangle: its corners' normals (octahedral) and its material.
pub var shading: Growing[u32]
## Six f32s a triangle: its corners' texture coordinates.
pub var uvs: Growing[f32]
pub var nodes: Growing[BvhNode]
## The leaf order build_bvh put the triangles in: the triangle at each
## position was `order[position]` before (Renderer.reload puts a scene
## compiled without its BVH in the same order).
pub var order: Growing[u32]
pub var objects: SceneObjects
## Every material definition of the set and its instances.
pub var materials: Materials
## Components with no triangles to trace (CAD before Tessellate).
pub var skipped: usize
## Gaussian splats, placed in world space (splats.lucb).
pub var splats: CompiledSplats
## Whether the triangles were left out because the renderer's are still
## right (a reload whose materials are the renderer's, by path and
## order: the triangles' material indices stand).
pub var meshes_kept: bool
## Without software trees (a device that traces rays in hardware): half
## the triangles' bounds' diagonal, which the BVH's root gives otherwise.
pub var radius: f64
## Which materials the triangles use, by material index (0 the default,
## then the library's): what is not used loads no textures or programs
## and turns on no kernel feature (a cut-out's eight more rounds).
pub var used: Growing[bool]
pub func init():
self.positions = Growing[f32]()
self.indices = Growing[u32]()
self.faces = Growing[u32]()
self.shading = Growing[u32]()
self.uvs = Growing[f32]()
self.nodes = Growing[BvhNode]()
self.order = Growing[u32]()
self.objects = SceneObjects()
self.materials = Materials()
self.skipped = 0
self.splats = CompiledSplats()
self.meshes_kept = false
self.radius = 0.0
self.used = Growing[bool]()
pub func triangle_count() -> usize:
return self.indices.count // 3
pub func point_count() -> usize:
return self.positions.count // 3
pub func close():
self.positions.close()
self.indices.close()
self.faces.close()
self.shading.close()
self.uvs.close()
self.used.close()
self.nodes.close()
self.order.close()
self.objects.close()
self.materials.close()
self.splats.close()
## `set` compiled: its triangles in world space with their BVH, its splats with
## theirs, and its cameras and lights. Without `geometry`, only what a renderer
## reloads (Renderer.reload, for a set whose geometry it already has): the
## triangles and their materials, no BVH, no splats.
## A compile asked to stop when `stopping` asks: it fails `stopped` at the
## next component or phase. A reload compile given the renderer's
## materials (`known`) leaves the triangles out when the set's are the same
## paths in the same order (`meshes_kept`): a light or a material's values
## changed, and the renderer's triangles stand.
## `trees` false leaves the software BVHs out (hardware tracing builds its
## own acceleration structures from the triangles and splat boxes).
pub func compile_scene(set: const GeometrySet*, geometry: bool = true, stopping: const Stopping*? = none, known: const Materials*? = none, trees: bool = true) -> CompiledScene!:
var scene = CompiledScene()
errdefer scene.close()
var face_base: u32 = 0
try materials_flattened(set, &scene.materials)
try scene.used.fill(scene.materials.count() + 1, false)
if not geometry:
if let held = known: scene.meshes_kept = same_paths(&scene.materials, held)
try add_set(&scene, set, Matrix4(), &face_base, 0, geometry, stopping, not scene.meshes_kept)
if scene.point_count() > 4294967295: error(limit, "a scene holds at most 2^32 points")
try scene_flattened(set, Matrix4(), &scene.objects)
if geometry and trees:
try check_stop(stopping)
try build_bvh(&scene)
try check_stop(stopping)
try build_splat_bvh(&scene.splats)
elif geometry:
scene.radius = half_diagonal(scene.positions.view())
return scene
## Half the diagonal of the bounds of `positions` (xyz triples).
func half_diagonal(positions: const f32[]) -> f64:
if positions.length < 3: return 0.0
var low = Vector3((f64)positions[0], (f64)positions[1], (f64)positions[2])
var high = low
for at in 1..<positions.length // 3:
let p = Vector3((f64)positions[at * 3], (f64)positions[at * 3 + 1], (f64)positions[at * 3 + 2])
low = Vector3(math.min(low.x, p.x), math.min(low.y, p.y), math.min(low.z, p.z))
high = Vector3(math.max(high.x, p.x), math.max(high.y, p.y), math.max(high.z, p.z))
return 0.5 * high.subtract(low).length()
## A request to stop a compile in progress, from another thread.
pub struct Stopping:
var asked: @u32
pub func ask():
self.asked.store(1, .release)
pub func is_asked() -> bool:
return self.asked.load(.acquire) != 0
## Whether `a` and `b` name the same materials in the same order.
func same_paths(a: const Materials*, b: const Materials*) -> bool:
if a.count() != b.count(): return false
for at in 0..<a.count():
if a.path(at) != b.path(at): return false
return true
func check_stop(stopping: const Stopping*?) -> !:
let held = stopping else return
if held.is_asked(): error(stopped, "the compile was stopped")
## Whether `set` and `other` hold the same geometry, so they compile to the
## same triangles and splats: their meshes and point clouds in the same order
## and places, made of the same arrays (blocks are never changed in place, so
## the same block is the same data). Cameras, lights and materials are left
## out: a light or a material node changes none of this.
pub func same_geometry(set: const GeometrySet*, other: const GeometrySet*) -> bool!:
var first: u64 = 14695981039346656037
try hash_set(set, Matrix4(), 0, &first)
var second: u64 = 14695981039346656037
try hash_set(other, Matrix4(), 0, &second)
if first != second: return false
# Charged after the other's arrays, a set costs only its fixed overheads,
# as after its own.
return (try unseen(set, other)) == (try unseen(set, set)) and (try unseen(other, set)) == (try unseen(other, other))
## The shape of a set's geometry: the kind of each mesh and point cloud and
## where it is placed, through the visible instances.
func hash_set(set: const GeometrySet*, matrix: Matrix4, depth: usize, key: u64*) -> !:
if depth > 64: error(invalid, "instances nest more than 64 deep")
for index in 0..<set.component_count():
let entry = set.component(index)
if entry.kind == mesh_component() or entry.kind == points_component():
mix(key, 1 if entry.kind == mesh_component() else 2)
let placement: f64[12] = [matrix.x.x, matrix.x.y, matrix.x.z, matrix.y.x, matrix.y.y, matrix.y.z,
matrix.z.x, matrix.z.y, matrix.z.z, matrix.translation.x, matrix.translation.y, matrix.translation.z]
for at in 0..<(usize)12: mix(key, memory.read[u64]((const void*)&placement[at]))
elif entry.kind == instances_component():
let instances = (const Instances*)entry.data
mix(key, 3)
for at in 0..<instances.count():
let item = instances.item(at)
if not item.visible: continue
try hash_set(item.set, matrix.multiply(item.matrix()), depth + 1, key)
## Bytes of `set`'s geometry that `other`'s does not hold: the arrays it
## lacks, and each component's fixed overhead.
func unseen(set: const GeometrySet*, other: const GeometrySet*) -> usize!:
var ids = IdSet()
defer ids.close()
_ = try geometry_bytes(other, &ids, 0)
return try geometry_bytes(set, &ids, 0)
func geometry_bytes(set: const GeometrySet*, ids: IdSet*, depth: usize) -> usize!:
if depth > 64: error(invalid, "instances nest more than 64 deep")
var bytes: usize = 0
for index in 0..<set.component_count():
let entry = set.component(index)
if entry.kind == mesh_component() or entry.kind == points_component():
let count = entry.kind.bytes
bytes += try count(entry.data, ids)
elif entry.kind == instances_component():
let instances = (const Instances*)entry.data
for at in 0..<instances.count():
let item = instances.item(at)
if item.visible: bytes += try geometry_bytes(item.set, ids, depth + 1)
return bytes
## FNV-1a over a word's bytes.
func mix(key: u64*, word: u64):
var value = word
for at in 0..<(usize)8:
*key = (*key ^ (value & 255)) *% 1099511628211
value = value >> 8
func add_set(scene: CompiledScene*, set: const GeometrySet*, matrix: Matrix4, face_base: u32*, depth: usize, splats: bool, stopping: const Stopping*?, meshes: bool = true) -> !:
if depth > 64: error(invalid, "instances nest more than 64 deep")
for index in 0..<set.component_count():
try check_stop(stopping)
let entry = set.component(index)
if entry.kind == mesh_component():
if meshes: try add_mesh(scene, (const Mesh*)entry.data, matrix, face_base)
elif entry.kind == points_component():
if splats: try add_cloud(&scene.splats, set, matrix)
elif entry.kind == instances_component():
let instances = (const Instances*)entry.data
for at in 0..<instances.count():
let item = instances.item(at)
if not item.visible: continue
try add_set(scene, item.set, matrix.multiply(item.matrix()), face_base, depth + 1, splats, stopping, meshes)
elif entry.kind.unrealizable != "":
scene.skipped += 1
## One mesh's points placed by `matrix`, and its display triangles.
func add_mesh(scene: CompiledScene*, mesh: const Mesh*, matrix: Matrix4, face_base: u32*) -> !:
let points = mesh.point_span()
let origin = mesh.position_origin()
let corners = mesh.corner_span()
let triangles = mesh.triangle_span()
let corner_faces = try mesh.corner_face_span()
let base = (u32)scene.point_count()
try scene.positions.reserve(scene.positions.count + points.length * 3)
for point in points:
let placed = matrix.transform_point(point.vector().add(origin))
scene.positions.items[scene.positions.count] = (f32)placed.x
scene.positions.items[scene.positions.count + 1] = (f32)placed.y
scene.positions.items[scene.positions.count + 2] = (f32)placed.z
scene.positions.count += 3
let count = triangles.length // 3
var normals = try shading_normals(mesh, matrix)
defer normals.close()
let face_materials = try material_indices(&scene.materials, mesh)
defer free(face_materials) in memory.heap
for material in face_materials:
if (usize)material < scene.used.count: scene.used.items[(usize)material] = true
let uv = texture_coordinates(mesh)
# The uv column read directly, not through a checked call per value.
var uv_entry: const Attribute*? = none
if uv.0 >= 0: uv_entry = try mesh.attribute_entry(uv.0)
try scene.uvs.reserve(scene.uvs.count + count * 6)
try scene.indices.reserve(scene.indices.count + count * 3)
try scene.faces.reserve(scene.faces.count + count)
try scene.shading.reserve(scene.shading.count + count * 4)
for at in 0..<count:
for k in 0..<(usize)3:
let corner = (usize)triangles[at * 3 + k]
scene.indices.items[scene.indices.count + k] = base + (u32)corners[corner]
let element = normals.element(corner, (usize)corners[corner], (usize)corner_faces[corner])
scene.shading.items[scene.shading.count + k] = normals.encoded.items[element]
var u: f64 = 0.0
var v: f64 = 0.0
if let entry = uv_entry:
let uv_at = uv_element(uv.1, corner, (usize)corners[corner], (usize)corner_faces[corner], uv.2)
u = entry.number(uv_at, 0)
v = entry.number(uv_at, 1)
scene.uvs.items[scene.uvs.count + k * 2] = (f32)u
scene.uvs.items[scene.uvs.count + k * 2 + 1] = (f32)v
scene.shading.items[scene.shading.count + 3] = face_materials[(usize)corner_faces[(usize)triangles[at * 3]]]
scene.indices.count += 3
scene.shading.count += 4
scene.uvs.count += 6
scene.faces.items[scene.faces.count] = *face_base + (u32)corner_faces[(usize)triangles[at * 3]]
scene.faces.count += 1
*face_base += (u32)mesh.face_count()
## Each face's material: index + 1 in `materials` of the path its `material`
## attribute names, else 0. Each distinct path is looked up once.
func material_indices(materials: const Materials*, mesh: const Mesh*) -> u32[]!:
let faces = (usize)mesh.face_count()
let out = try new u32[faces] in memory.heap
let attribute = mesh.find_attribute("material", 2)
if attribute < 0 or materials.count() == 0: return out
let names = (usize)(try mesh.attribute_string_count(attribute))
let looked = try new u32[names] in memory.heap
defer free(looked) in memory.heap
for at in 0..<names:
let found = materials.index_of(try mesh.attribute_string(attribute, (i64)at))
looked[at] = (u32)(found + 1)
# Each face's string index (text attributes store them), read directly.
let entry = try mesh.attribute_entry(attribute)
let single = (try mesh.attribute_storage(attribute)) == 1
let indices = entry.data.view()
for face in 0..<faces:
let index = memory.read[i32]((const void*)&indices[(0 if single else face) * 4])
if index >= 0 and (usize)index < names: out[face] = looked[(usize)index]
return out
## A mesh's `uv` attribute: its index (-1: none), its domain (0 point, 1
## corner, 2 face) and whether it stores one value for all.
func texture_coordinates(mesh: const Mesh*) -> (i64, i64, bool):
let domains: i64[3] = [1, 0, 2]
for domain in domains:
let index = mesh.find_attribute("uv", domain)
if index < 0: continue
let width = mesh.attribute_width(index) catch failure:
_ = failure
recover 0
let integer = mesh.attribute_integer(index) catch failure:
_ = failure
recover true
if width < 2 or integer: continue
let single = (mesh.attribute_storage(index) catch failure:
_ = failure
recover 0) == 1
return (index, domain, single)
return (-1, 0, false)
func uv_element(domain: i64, corner: usize, point: usize, face: usize, single: bool) -> usize:
if single: return 0
if domain == 1: return corner
if domain == 0: return point
return face
## A mesh's shading normals placed by its matrix and encoded (octahedral),
## one per element of their domain: each element once, however many
## corners share it.
struct ShadingNormals:
var encoded: Growing[u32]
## 0 point, 1 corner, 2 face, 3 detail.
var domain: i64
func element(corner: usize, point: usize, face: usize) -> usize:
if self.domain == 1: return corner
if self.domain == 0: return point
if self.domain == 2: return face
return 0
func close():
self.encoded.close()
## The authored N (corner, point, face, detail) else the smooth normals, read
## where they are (no copy), placed by `matrix` (its inverse transpose, made
## once) and encoded.
func shading_normals(mesh: const Mesh*, matrix: Matrix4) -> ShadingNormals!:
# The cofactors carry the inverse transpose up to the determinant's
# size; its sign keeps a mirroring placement's normals outward. A
# singular placement flattens its triangles to nothing: any normal does.
let determinant = matrix.determinant()
let sign = 1.0 if determinant >= 0.0 else -1.0
let singular = determinant == 0.0 or not math.is_finite(determinant)
let c0 = matrix.y.cross(matrix.z).multiply_scalar(sign)
let c1 = matrix.z.cross(matrix.x).multiply_scalar(sign)
let c2 = matrix.x.cross(matrix.y).multiply_scalar(sign)
var encoded = Growing[u32]()
errdefer encoded.close()
let domains: i64[4] = [1, 0, 2, 3]
for domain in domains:
let index = mesh.find_attribute("N", domain)
if index < 0 or (try mesh.attribute_width(index)) < 3 or (try mesh.attribute_integer(index)): continue
let tuples = try mesh.attribute_tuples(index)
var values = Growing[Float3]()
defer values.close()
try values.fill(tuples, Float3(0.0, 1.0, 0.0))
try mesh.pack_attribute3(index, f32[]((f32*)values.items.data, tuples * 3))
try encode_all(values.view(), c0, c1, c2, singular, &encoded)
return ShadingNormals(encoded, 3 if (try mesh.attribute_storage(index)) == 1 else domain)
try encode_all(try mesh.smooth_normal_span(), c0, c1, c2, singular, &encoded)
return ShadingNormals(encoded, 1 if (try mesh.smooth_normals_corner_domain()) else 0)
func encode_all(normals: const Float3[], c0: Vector3, c1: Vector3, c2: Vector3, singular: bool, out: Growing[u32]*) -> !:
try out.fill(normals.length, 0)
for at in 0..<normals.length:
let n = normals[at].vector()
let placed = Vector3(0.0, 1.0, 0.0) if singular else c0.multiply_scalar(n.x).add(c1.multiply_scalar(n.y)).add(c2.multiply_scalar(n.z))
out.items[at] = octahedral(placed)
## A unit vector as two snorm16 octahedral coordinates (x in the low half), as
## GLSL's unpackSnorm2x16 reads them.
pub func octahedral(n: Vector3) -> u32:
let length = math.abs(n.x) + math.abs(n.y) + math.abs(n.z)
if length <= 0.0: return octahedral(Vector3(0.0, 1.0, 0.0))
var x = n.x / length
var y = n.y / length
if n.z < 0.0:
let fx = (1.0 - math.abs(y)) * (1.0 if x >= 0.0 else -1.0)
let fy = (1.0 - math.abs(x)) * (1.0 if y >= 0.0 else -1.0)
x = fx
y = fy
let qx = (i64)math.round(math.clamp(x, -1.0, 1.0) * 32767.0)
let qy = (i64)math.round(math.clamp(y, -1.0, 1.0) * 32767.0)
return ((u32)(qx & 0xffff)) | ((u32)(qy & 0xffff) << 16)