Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.4

0.7.4 / src / fields / sdf_tree.lucb

## An SDF program as a tree, for editing it primitive by primitive (Edit
## SDF). The postfix program parses once into nodes: primitives, booleans of
## two operands, modifiers of one, and transforms whose one operand lies
## between their start and end ops. An edit is one pass over the ops that
## keeps, drops, rewrites or wraps each (SdfRewrite), so programs of any
## size edit in linear time without recursion.
##
## A primitive's number is its place among the program's primitives. Its
## placement is the transform directly around it (through modifiers), which
## moves compose into; its boolean is the one taking it (with the
## transforms and modifiers around it) as the second operand.

let no_node: i32 = -1

struct SdfNode:
    ## The node's op; a transform's start op, `end` its end op (else the
    ## same op).
    var start: u32
    var end: u32
    var op: u8
    var first: i32
    var second: i32
    var parent: i32

pub struct SdfTree:
    var nodes: Growing[SdfNode]
    ## The node of each op (a transform's start and end ops both name it).
    var owner: Growing[i32]
    ## Primitive nodes in program order.
    var primitives: Growing[i32]
    ## Each node's world placement: the transforms around it composed,
    ## outermost first (a transform's own is not in its entry).
    var worlds: Growing[Matrix4]
    var root: i32

    ## The tree of `sdf`; fails on a transform that does not hold exactly
    ## one distance (programs Luce's nodes and Edit SDF build always do).
    pub static func of(sdf: const Sdf*) -> SdfTree!:
        var tree = SdfTree(Growing[SdfNode](), Growing[i32](), Growing[i32](), Growing[Matrix4](), no_node)
        errdefer tree.close()
        let ops = sdf.op_span()
        let params = sdf.param_span()
        try tree.owner.fill(ops.length, no_node)
        var stack: i32[64] = ---
        var top: usize = 0
        var frame_starts: u32[64] = ---
        var frame_heights: usize[64] = ---
        var frames: usize = 0
        for at in 0..<ops.length:
            let op = ops[at]
            if op <= 4:
                stack[top] = try tree.add(SdfNode((u32)at, (u32)at, op, no_node, no_node, no_node))
                top += 1
            elif op >= 16 and op <= 21:
                stack[top - 2] = try tree.add(SdfNode((u32)at, (u32)at, op, stack[top - 2], stack[top - 1], no_node))
                top -= 1
            elif op == 32:
                frame_starts[frames] = (u32)at
                frame_heights[frames] = top
                frames += 1
            elif op == 33:
                frames -= 1
                if top != frame_heights[frames] + 1: error(errors.invalid, "this SDF program has a transform around more than one shape; it cannot be edited by primitive")
                stack[top - 1] = try tree.add(SdfNode(frame_starts[frames], (u32)at, 32, stack[top - 1], no_node, no_node))
                tree.owner.items[frame_starts[frames]] = stack[top - 1]
            else:
                stack[top - 1] = try tree.add(SdfNode((u32)at, (u32)at, op, stack[top - 1], no_node, no_node))
        tree.root = stack[0]
        # Worlds top down: parents come after their children in postfix, so
        # the reverse node order visits every parent first.
        try tree.worlds.fill(tree.nodes.count, Matrix4())
        var node = tree.nodes.count
        while node > 0:
            node -= 1
            let here = tree.nodes.items[node]
            var inner = tree.worlds.items[node]
            if here.op == 32: inner = inner.multiply(try forward(params, (usize)here.start))
            if here.first >= 0: tree.worlds.items[(usize)here.first] = inner
            if here.second >= 0: tree.worlds.items[(usize)here.second] = inner
        return tree

    func add(node: SdfNode) -> i32!:
        let id = (i32)self.nodes.count
        try self.nodes.push(node)
        if node.first >= 0: self.nodes.items[(usize)node.first].parent = id
        if node.second >= 0: self.nodes.items[(usize)node.second].parent = id
        self.owner.items[node.end] = id
        if node.op <= 4: try self.primitives.push(id)
        return id

    pub func primitive_count() -> usize:
        return self.primitives.count

    ## Primitive `index`'s node.
    func primitive(index: usize) -> SdfNode:
        return self.nodes.items[(usize)self.primitives.items[index]]

    ## Primitive `index`'s world placement (every transform around it).
    pub func primitive_world(index: usize) -> Matrix4:
        return self.worlds.items[(usize)self.primitives.items[index]]

    ## The transform placing primitive `index` directly (through modifiers
    ## only), or no_node.
    func wrap(index: usize) -> i32:
        var node = self.primitive(index).parent
        while node >= 0 and self.nodes.items[(usize)node].op >= 48:
            node = self.nodes.items[(usize)node].parent
        if node >= 0 and self.nodes.items[(usize)node].op == 32: return node
        return no_node

    ## The boolean taking primitive `index` (and what wraps it) as its second
    ## operand, or no_node (the program's first shape has none).
    pub func combiner(index: usize) -> i32:
        var node = self.primitives.items[index]
        var parent = self.nodes.items[(usize)node].parent
        while parent >= 0 and (self.nodes.items[(usize)parent].op == 32 or self.nodes.items[(usize)parent].op >= 48):
            node = parent
            parent = self.nodes.items[(usize)node].parent
        if parent >= 0 and self.nodes.items[(usize)parent].second == node: return parent
        return no_node

    pub func close():
        self.nodes.close()
        self.owner.close()
        self.primitives.close()
        self.worlds.close()

## The forward matrix of the transform op at `at` (it stores the inverse).
func forward(params: const f32[], at: usize) -> Matrix4!:
    let p = params[at * sdf_stride..<(at + 1) * sdf_stride]
    let inverse = Matrix4(Vector3((f64)p[0], (f64)p[1], (f64)p[2]), Vector3((f64)p[3], (f64)p[4], (f64)p[5]),
                          Vector3((f64)p[6], (f64)p[7], (f64)p[8]), Vector3((f64)p[9], (f64)p[10], (f64)p[11]))
    return try affine_inverse(inverse)

## Transform op parameters placing by `matrix`: its inverse and its smallest
## axis scale (see placed_sdf).
func transform_params(matrix: Matrix4, out: f32[]) -> !:
    let inverse = try affine_inverse(matrix)
    let scale = math.min(matrix.x.length(), math.min(matrix.y.length(), matrix.z.length()))
    let values: f64[13] = [inverse.x.x, inverse.x.y, inverse.x.z, inverse.y.x, inverse.y.y, inverse.y.z, inverse.z.x, inverse.z.y, inverse.z.z,
                           inverse.translation.x, inverse.translation.y, inverse.translation.z, scale]
    for at in 0..<(usize)13: out[at] = (f32)values[at]
    for at in 13..<sdf_stride: out[at] = 0.0

## One edit of a program: per op, dropped or kept with a (possibly new) op
## code and parameters, and primitives wrapped in a new transform.
pub struct SdfRewrite:
    var codes: Growing[u8]
    var params: Growing[f32]
    var dropped: Growing[bool]
    ## Per op: -1, or the start (in `wraps`) of a transform's parameters to
    ## wrap the op in.
    var wrapped: Growing[i64]
    var wraps: Growing[f32]

    pub static func of(sdf: const Sdf*) -> SdfRewrite!:
        var result = SdfRewrite(Growing[u8](), Growing[f32](), Growing[bool](), Growing[i64](), Growing[f32]())
        errdefer result.close()
        try result.codes.assign(sdf.op_span())
        try result.params.assign(sdf.param_span())
        try result.dropped.fill(sdf.op_count(), false)
        try result.wrapped.fill(sdf.op_count(), -1)
        return result

    ## Move primitive `index` of `tree` by `delta` in world space: composed
    ## into the transform placing it, or a new one around it.
    pub func move(tree: const SdfTree*, index: usize, delta: Matrix4) -> !:
        let wrap = tree.wrap(index)
        let node = tree.nodes.items[(usize)(wrap if wrap >= 0 else tree.primitives.items[index])]
        # The move in the frame the placement lives in: O⁻¹·D·O.
        let outer = tree.worlds.items[(usize)(wrap if wrap >= 0 else tree.primitives.items[index])]
        let framed = (try affine_inverse(outer)).multiply(delta).multiply(outer)
        if wrap >= 0:
            let placed = framed.multiply(try forward(self.params.view(), (usize)node.start))
            try transform_params(placed, self.params.items[(usize)node.start * sdf_stride..<((usize)node.start + 1) * sdf_stride])
            return
        let start = self.wraps.count
        try self.wraps.extend(start + sdf_stride, 0.0)
        try transform_params(framed, self.wraps.items[start..<start + sdf_stride])
        self.wrapped.items[(usize)node.start] = (i64)start

    ## Primitive `index`'s boolean set to `mode` (0 add, 1 subtract,
    ## 2 intersect; -1 keeps it), smooth over `blend` when positive (< 0
    ## keeps the blend). False when it has none (the first shape).
    pub func combine(tree: const SdfTree*, index: usize, mode: i64, blend: f64) -> bool:
        let node = tree.combiner(index)
        if node < 0: return false
        let at = (usize)tree.nodes.items[(usize)node].start
        let code = self.codes.items[at]
        let kept = (i64)((code - 16) % 3)
        let radius = (f64)self.params.items[at * sdf_stride] if blend < 0.0 else blend
        let smooth = radius > 0.0
        self.codes.items[at] = (u8)(16 + (mode if mode >= 0 else kept) + (3 if smooth else 0))
        self.params.items[at * sdf_stride] = (f32)(radius if smooth else 0.0)
        return true

    ## The primitives marked in `chosen` removed: with every transform and
    ## modifier around them, and each boolean left with one operand, which
    ## takes its place. False when nothing would remain.
    pub func remove(tree: const SdfTree*, chosen: const bool[]) -> bool!:
        var removed = Growing[bool]()
        defer removed.close()
        try removed.fill(tree.nodes.count, false)
        for index in 0..<tree.primitives.count:
            if chosen[index]: removed.items[(usize)tree.primitives.items[index]] = true
        # Children come first in node order, so one pass settles each node.
        for node in 0..<tree.nodes.count:
            let here = tree.nodes.items[node]
            if here.op >= 16 and here.op <= 21:
                removed.items[node] = removed.items[(usize)here.first] and removed.items[(usize)here.second]
            elif here.op > 4:
                removed.items[node] = removed.items[(usize)here.first]
        if removed.items[(usize)tree.root]: return false
        for at in 0..<self.codes.count:
            let node = tree.owner.items[at]
            let here = tree.nodes.items[(usize)node]
            let lone = here.op >= 16 and here.op <= 21 and (removed.items[(usize)here.first] or removed.items[(usize)here.second])
            if removed.items[(usize)node] or lone: self.dropped.items[at] = true
        return true

    ## The edited program.
    pub func finish() -> Sdf*!:
        var count: usize = 0
        for at in 0..<self.codes.count:
            if self.dropped.items[at]: continue
            count += 3 if self.wrapped.items[at] >= 0 else 1
        var ops = try Column[u8].allocate(count)
        errdefer ops.release()
        var params = try Column[f32].filled(count * sdf_stride, 0.0)
        errdefer params.release()
        let out_ops = ops.span()
        let out = params.span()
        var next: usize = 0
        for at in 0..<self.codes.count:
            if self.dropped.items[at]: continue
            let wrap = self.wrapped.items[at]
            if wrap >= 0:
                out_ops[next] = (u8)SdfOp.transform
                memory.copy(out[next * sdf_stride..<(next + 1) * sdf_stride], self.wraps.items[(usize)wrap..<(usize)wrap + sdf_stride], sdf_stride)
                next += 1
            out_ops[next] = self.codes.items[at]
            memory.copy(out[next * sdf_stride..<(next + 1) * sdf_stride], self.params.items[at * sdf_stride..<(at + 1) * sdf_stride], sdf_stride)
            next += 1
            if wrap >= 0:
                out_ops[next] = (u8)SdfOp.end_transform
                next += 1
        return try new_sdf(ops.take(), params.take())

    pub func close():
        self.codes.close()
        self.params.close()
        self.dropped.close()
        self.wrapped.close()
        self.wraps.close()