Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-3d

Source of release 0.9.2

0.9.2 / src / renderers / fog_texels.lucb

## A fog grid made dense for the GPU (renderers/fog_volume.lucb draws it). The
## grid's leaves span a box of voxels; the box, padded by one texel of the
## background on every side, becomes texels whose z slices lie side by side in
## one rgba16_float atlas: red the density, green the optical depth toward the
## key light, blue toward the sky (+Y), alpha the emission field (a second
## grid of the set, sampled at each texel's center; zero without one). The optical depths (density integrated
## along world length) are swept plane by plane on the CPU when the volume is
## made, so the shader's lighting is two texture reads, and a changed density
## scale needs no new sweep (the shader scales them). A box larger than
## `most_texels` is averaged down by a whole factor until it fits.
import memory
from luce_std import math, parallel
import errors
from luce_geocore.geocore import Vector3, Matrix4
from luce_geocore.kernel import SparseGrid, GridSampler, key_leaf

## The most texels a volume uploads: 256³, 128 MiB of half floats.
let most_texels: usize = 16777216
## The widest and tallest atlas luce-gpu textures allow.
let atlas_side: usize = 16384
## Optical depths are clamped below the largest half float.
let deepest: f64 = 60000.0

## A fog grid's texels: the atlas and where its box lies in the world.
pub struct FogTexels:
    ## Texels across the box: x, y and z.
    pub var counts: usize[3]
    ## Slices per atlas row, and the atlas's size in texels.
    pub var columns: usize
    pub var width: usize
    pub var height: usize
    ## Box coordinates (0..1 across the box) to world.
    pub var box: Matrix4
    ## The world length of a texel's shortest edge.
    pub var voxel: f64
    ## The highest density.
    pub var peak: f64
    ## The atlas: four half floats a texel, rows top down.
    pub var texels: f16[]

    ## Free the atlas.
    pub func close():
        if self.texels.length > 0: free(self.texels) in memory.heap
        var empty: f16[]
        self.texels = empty

## The texels of fog `grid` placed by `matrix`, its optical depths swept toward
## `light` (a world direction toward the key light) and toward +Y, and the
## values of `emission` (a grid of the same set) in alpha.
pub func fog_texels(grid: const SparseGrid*, emission: const SparseGrid*?, matrix: Matrix4, light: Vector3) -> FogTexels!:
    let keys = grid.keys.view()
    if keys.length == 0: error(errors.invalid, "an empty fog grid has nothing to draw")
    let (fx, fy, fz) = key_leaf(keys[0])
    var low: i64[3] = [fx, fy, fz]
    var high = low
    for key in keys:
        let (x, y, z) = key_leaf(key)
        let leaf: i64[3] = [x, y, z]
        for axis in 0..<(usize)3:
            if leaf[axis] < low[axis]: low[axis] = leaf[axis]
            if leaf[axis] > high[axis]: high[axis] = leaf[axis]
    # Voxels across the leaves' box, then the smallest averaging factor that fits.
    var extent: i64[3] = [0, 0, 0]
    for axis in 0..<(usize)3: extent[axis] = (high[axis] - low[axis] + 1) * 8
    var factor: i64 = 1
    var counts: usize[3] = [0, 0, 0]
    var columns: usize = 0
    while true:
        for axis in 0..<(usize)3: counts[axis] = (usize)((extent[axis] + factor - 1) // factor + 2)
        columns = atlas_columns(counts)
        if columns > 0 and counts[0] * counts[1] * counts[2] <= most_texels: break
        factor += 1
    let rows = (counts[2] + columns - 1) // columns
    # Texel t covers voxels origin + t * factor ..< origin + (t + 1) * factor: one
    # texel of padding before the leaves' first voxel. Voxel i sits at index i, so
    # the box starts half a voxel before the origin.
    var origin: i64[3] = [0, 0, 0]
    for axis in 0..<(usize)3: origin[axis] = low[axis] * 8 - factor
    let span = (f64)factor
    let index_box = Matrix4(Vector3((f64)counts[0] * span, 0.0, 0.0), Vector3(0.0, (f64)counts[1] * span, 0.0), Vector3(0.0, 0.0, (f64)counts[2] * span),
                            Vector3((f64)origin[0] - 0.5, (f64)origin[1] - 0.5, (f64)origin[2] - 0.5))
    let box = matrix.multiply(grid.transform).multiply(index_box)
    var voxel = 1.0e300
    for axis in 0..<(usize)3:
        let edge = box_axis(box, axis).length() / (f64)counts[axis]
        voxel = math.min(voxel, edge)
    if not (voxel > 0.0 and math.is_finite(voxel)): error(errors.invalid, "a fog grid's transform must be invertible and finite")
    let density = try densities(grid, origin, factor, counts)
    defer free(density) in memory.heap
    let width = columns * counts[0]
    let height = rows * counts[1]
    var result = FogTexels(counts = counts, columns = columns, width = width, height = height, box = box, voxel = voxel, peak = 0.0)
    result.texels = try new f16[width * height * 4] --- in memory.heap
    errdefer result.close()
    memory.set(u8[]((u8*)result.texels.data, result.texels.length * 2), 0)
    let layout = Layout(counts, columns, width)
    var peak = 0.0
    for z in 0..<counts[2]:
        for y in 0..<counts[1]:
            for x in 0..<counts[0]:
                let value = density[x + counts[0] * (y + counts[1] * z)]
                peak = math.max(peak, (f64)value)
                result.texels[layout.at(x, y, z) * 4] = (f16)math.min((f64)value, deepest)
    result.peak = peak
    try sweep(density, &layout, box, try light.normalized(), result.texels, 1)
    try sweep(density, &layout, box, Vector3(0.0, 1.0, 0.0), result.texels, 2)
    if let field = emission:
        var work = EmissionWork(grid, field, origin, factor, &layout, result.texels)
        try parallel.for_each_range(counts[2], 1, (void*)&work, sample_emission)
    return result

## Slices per atlas row so that the atlas is about square and at most
## `atlas_side` texels each way; 0 when no layout fits.
func atlas_columns(counts: usize[3]) -> usize:
    if counts[0] > atlas_side or counts[1] > atlas_side: return 0
    let widest = atlas_side // counts[0]
    var columns = (usize)math.ceil(math.sqrt((f64)counts[2] * (f64)counts[1] / (f64)counts[0]))
    if columns > widest: columns = widest
    if columns > counts[2]: columns = counts[2]
    if columns == 0: columns = 1
    let rows = (counts[2] + columns - 1) // columns
    if rows * counts[1] > atlas_side:
        columns = widest
        if (counts[2] + columns - 1) // columns * counts[1] > atlas_side: return 0
    return columns

## Column `axis` (0 x, 1 y, 2 z) of `box`'s linear part.
func box_axis(box: Matrix4, axis: usize) -> Vector3:
    if axis == 0: return box.x
    return box.y if axis == 1 else box.z

## Where texel (x, y, z) lies in the atlas: its z slice's tile, row by row.
struct Layout:
    let counts: usize[3]
    let columns: usize
    let width: usize

    func at(x: usize, y: usize, z: usize) -> usize:
        let column = z % self.columns
        let row = z // self.columns
        return (row * self.counts[1] + y) * self.width + column * self.counts[0] + x

# mark: Densities

## Each texel's density: the average of the voxels it covers (`factor` across),
## voxels outside the leaves at the background. Texels run x fastest, then y.
func densities(grid: const SparseGrid*, origin: i64[3], factor: i64, counts: usize[3]) -> f32[]!:
    let total = counts[0] * counts[1] * counts[2]
    let out = try new f32[total] --- in memory.heap
    for at in 0..<total: out[at] = grid.background
    var work = DenseWork(grid, origin, factor, counts, out)
    if factor == 1:
        # Leaves write disjoint texels.
        try parallel.for_each_range(grid.leaf_count(), 16, (void*)&work, fill_leaves)
    else:
        fill_leaves((void*)&work, 0, grid.leaf_count(), 0)
    return out

struct DenseWork:
    let grid: const SparseGrid*
    let origin: i64[3]
    let factor: i64
    let counts: usize[3]
    let out: f32[]

func fill_leaves(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (DenseWork*)context
    let keys = work.grid.keys.view()
    let values = work.grid.values.view()
    let background = work.grid.background
    let weight = (f32)(1.0 / (f64)(work.factor * work.factor * work.factor))
    let counts = work.counts
    for leaf in first..<end:
        let (lx, ly, lz) = key_leaf(keys[leaf])
        let base = leaf * 512
        for k in 0..<(i64)8:
            let tz = (usize)((lz * 8 + k - work.origin[2]) // work.factor)
            for j in 0..<(i64)8:
                let ty = (usize)((ly * 8 + j - work.origin[1]) // work.factor)
                let row = counts[0] * (ty + counts[1] * tz)
                for i in 0..<(i64)8:
                    let tx = (usize)((lx * 8 + i - work.origin[0]) // work.factor)
                    let value = values[base + (usize)(i + j * 8 + k * 64)]
                    if work.factor == 1: work.out[row + tx] = value
                    else: work.out[row + tx] += (value - background) * weight

# mark: Emission

struct EmissionWork:
    let grid: const SparseGrid*
    let field: const SparseGrid*
    let origin: i64[3]
    let factor: i64
    let layout: const Layout*
    let texels: f16[]

## The emission field at each texel's center (in the density grid's index
## space, then the set's world, where both grids lie), slices `first..<end`.
func sample_emission(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (EmissionWork*)context
    let counts = work.layout.counts
    var sampler = GridSampler.of(work.field)
    let span = (f64)work.factor
    for z in first..<end:
        for y in 0..<counts[1]:
            for x in 0..<counts[0]:
                let index = Vector3((f64)work.origin[0] - 0.5 + ((f64)x + 0.5) * span, (f64)work.origin[1] - 0.5 + ((f64)y + 0.5) * span,
                                    (f64)work.origin[2] - 0.5 + ((f64)z + 0.5) * span)
                let value = sampler.sample(work.grid.transform.transform_point(index))
                work.texels[work.layout.at(x, y, z) * 4 + 3] = (f16)math.clamp(value, 0.0, deepest)

# mark: Optical depths

## Sweep the optical depth toward `direction` (world, unit) into `channel` of
## every atlas texel: plane by plane along the texel axis nearest the
## direction, starting at the plane nearest the light, each texel's depth is
## its neighbor's toward the light (bilinear in the plane before) plus the
## trapezoid of the two densities over the world step between them.
func sweep(density: const f32[], layout: const Layout*, box: Matrix4, direction: Vector3, texels: f16[], channel: usize) -> !:
    let counts = layout.counts
    # The direction in texel units.
    let inverse = try box.inverse()
    let local = inverse.transform_direction(direction)
    let d: f64[3] = [local.x * (f64)counts[0], local.y * (f64)counts[1], local.z * (f64)counts[2]]
    var march: usize = 0
    for axis in 1..<(usize)3:
        if math.abs(d[axis]) > math.abs(d[march]): march = axis
    if d[march] == 0.0: error(errors.invalid, "a light direction must be nonzero")
    let across = (march + 1) % 3
    let along = (march + 2) % 3
    let lead = math.abs(d[march])
    let toward = Vector3(d[0] / lead / (f64)counts[0], d[1] / lead / (f64)counts[1], d[2] / lead / (f64)counts[2])
    let step = box.transform_direction(toward).length()
    let plane = counts[across] * counts[along]
    var work = SweepWork(density = density, layout = layout, texels = texels, channel = channel, march = march, across = across, along = along,
                         offset = [d[across] / lead, d[along] / lead], step = step, plane = 0, neighbor = -1)
    work.previous = try new f32[plane] --- in memory.heap
    defer free(work.previous) in memory.heap
    work.current = try new f32[plane] --- in memory.heap
    defer free(work.current) in memory.heap
    let planes = counts[march]
    let rising = d[march] > 0.0
    for index in 0..<planes:
        # Toward +march, the light's side is the last plane.
        work.plane = planes - 1 - index if rising else index
        work.neighbor = -1 if index == 0 else (i64)(work.plane + 1 if rising else work.plane - 1)
        try parallel.for_each_range(counts[along], 8, (void*)&work, sweep_rows)
        let swapped = work.previous
        work.previous = work.current
        work.current = swapped

struct SweepWork:
    let density: const f32[]
    let layout: const Layout*
    let texels: f16[]
    let channel: usize
    ## The texel axis marched along, and the plane's two axes.
    let march: usize
    let across: usize
    let along: usize
    ## Where the neighbor toward the light lies in the plane before, in texels.
    let offset: f64[2]
    ## The world length between a texel and that neighbor.
    let step: f64
    var plane: usize
    ## The plane before (toward the light), or -1 at the first.
    var neighbor: i64
    var previous: f32[]
    var current: f32[]

func sweep_rows(context: void*, first: usize, end: usize, worker: usize):
    _ = worker
    let work = (SweepWork*)context
    let counts = work.layout.counts
    let width = counts[work.across]
    for v in first..<end:
        for u in 0..<width:
            var at: usize[3] = [0, 0, 0]
            at[work.march] = work.plane
            at[work.across] = u
            at[work.along] = v
            let density = (f64)work.density[at[0] + counts[0] * (at[1] + counts[1] * at[2])]
            var depth = 0.0
            if work.neighbor >= 0:
                let (before, depth_before) = neighbor_values(work, (f64)u + work.offset[0], (f64)v + work.offset[1])
                depth = depth_before + 0.5 * (density + before) * work.step
            else:
                depth = 0.5 * density * work.step
            work.current[u + width * v] = (f32)depth
            work.texels[work.layout.at(at[0], at[1], at[2]) * 4 + work.channel] = (f16)math.min(depth, deepest)

## The density and optical depth at (u, v) of the plane before, bilinear; zero
## outside the box.
func neighbor_values(work: const SweepWork*, u: f64, v: f64) -> (f64, f64):
    let counts = work.layout.counts
    let u0 = math.floor(u)
    let v0 = math.floor(v)
    let fu = u - u0
    let fv = v - v0
    var density = 0.0
    var depth = 0.0
    for corner in 0..<(usize)4:
        let cu = (i64)u0 + (i64)(corner & 1)
        let cv = (i64)v0 + (i64)(corner >> 1)
        if cu < 0 or cv < 0 or cu >= (i64)counts[work.across] or cv >= (i64)counts[work.along]: continue
        let weight = (fu if corner & 1 != 0 else 1.0 - fu) * (fv if corner >> 1 != 0 else 1.0 - fv)
        var at: usize[3] = [0, 0, 0]
        at[work.march] = (usize)work.neighbor
        at[work.across] = (usize)cu
        at[work.along] = (usize)cv
        density += weight * (f64)work.density[at[0] + counts[0] * (at[1] + counts[1] * at[2])]
        depth += weight * (f64)work.previous[(usize)cu + counts[work.across] * (usize)cv]
    return (density, depth)