Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.4

0.7.4 / src / code / winding.lucb

# Generalized winding numbers (VEX `windingnumber`): 1 inside a closed, outward-facing
# mesh, 0 outside, fractional near holes. Exact solid angles near the point and, for
# clusters far from it, the second-order expansion of Barill et al. ("Fast Winding
# Numbers", 2018), over a binary tree of the triangles built once per cook. Values are
# within about 0.2% of the exact sum near the surface, closer farther away.

## Triangles per leaf.
let winding_leaf: usize = 8
## A cluster this many radii away is far enough for its dipole.
let winding_beta: f64 = 2.0

## A cluster: its triangles (a leaf) or children, the area-weighted center, the radius
## around it holding every corner, the summed area vector, and the moments of the
## surface about the center: `moment[3i + j]` sums the integral of y_i times area_j,
## `third[9i + 3j + k]` the integral of y_i y_j times area_k (y the offset from the center).
struct WindingNode:
    var center: Vector3
    var radius: f64
    var area: Vector3
    var moment: f64[9]
    var third: f64[27]
    ## The Hessian's delta terms folded: `delta[j]` is the sum over i of
    ## third[i][j][i] + third[j][i][i] + third[i][i][j], so they cost one dot product.
    var delta: f64[3]
    var first: u32
    var count: u32
    var left: u32
    var right: u32

## The tree over one input's display triangles (positions relative to its origin).
struct WindingTree:
    var built: bool
    var nodes: collections.List[WindingNode]
    var order: u32[]
    var corners: Vector3[]

    func close():
        if not self.built: return
        self.nodes.destroy()
        free(self.order) in memory.heap
        free(self.corners) in memory.heap
        self.built = false

    ## Build the tree over `mesh`'s triangles.
    func build(mesh: const Mesh*) -> !:
        let triangles = mesh.triangle_span()
        let corners = mesh.corner_span()
        let positions = mesh.point_span()
        let count = triangles.length // 3
        self.corners = try new Vector3[count * 3] --- in memory.heap
        self.order = try new u32[count] --- in memory.heap
        for t in 0..<count:
            for k: usize in 0..<3: self.corners[t * 3 + k] = positions[(usize)corners[(usize)triangles[t * 3 + k]]].vector()
            self.order[t] = (u32)t
        self.nodes = collections.List[WindingNode]()
        self.built = true
        if count > 0: _ = try self.split(0, count)

    ## The node over `order[first..<end]`, its children built first.
    func split(first: usize, end: usize) -> u32!:
        var center = Vector3()
        var area = Vector3()
        var weight: f64 = 0.0
        var low = Vector3(1.0e300, 1.0e300, 1.0e300)
        var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
        for at in first..<end:
            let t = (usize)self.order[at]
            let a = self.corners[t * 3]
            let b = self.corners[t * 3 + 1]
            let c = self.corners[t * 3 + 2]
            let n = b.subtract(a).cross(c.subtract(a)).multiply_scalar(0.5)
            let size = n.length()
            let middle = a.add(b).add(c).multiply_scalar(1.0 / 3.0)
            center = center.add(middle.multiply_scalar(size))
            weight += size
            area = area.add(n)
            low = Vector3(math.min(low.x, middle.x), math.min(low.y, middle.y), math.min(low.z, middle.z))
            high = Vector3(math.max(high.x, middle.x), math.max(high.y, middle.y), math.max(high.z, middle.z))
        center = center.multiply_scalar(1.0 / weight) if weight > 0.0 else low.add(high).multiply_scalar(0.5)
        var radius: f64 = 0.0
        var moment: f64[9]
        var third: f64[27]
        for at in first..<end:
            let t = (usize)self.order[at]
            for k: usize in 0..<3: radius = math.max(radius, self.corners[t * 3 + k].subtract(center).length())
            let a = self.corners[t * 3]
            let b = self.corners[t * 3 + 1]
            let c = self.corners[t * 3 + 2]
            let n = b.subtract(a).cross(c.subtract(a)).multiply_scalar(0.5)
            let y = a.add(b).add(c).multiply_scalar(1.0 / 3.0).subtract(center)
            let ys: f64[3] = [y.x, y.y, y.z]
            let ns: f64[3] = [n.x, n.y, n.z]
            # A triangle's mean of y y^T: (sum of v v^T + s s^T) / 12, v its corners and s
            # their sum, all from the center.
            let va = a.subtract(center)
            let vb = b.subtract(center)
            let vc = c.subtract(center)
            let v: f64[9] = [va.x, va.y, va.z, vb.x, vb.y, vb.z, vc.x, vc.y, vc.z]
            let sum: f64[3] = [va.x + vb.x + vc.x, va.y + vb.y + vc.y, va.z + vb.z + vc.z]
            for i: usize in 0..<3:
                for j: usize in 0..<3:
                    moment[i * 3 + j] += ys[i] * ns[j]
                    let mean = (v[i] * v[j] + v[3 + i] * v[3 + j] + v[6 + i] * v[6 + j] + sum[i] * sum[j]) * (1.0 / 12.0)
                    for k: usize in 0..<3: third[(i * 3 + j) * 3 + k] += mean * ns[k]
        var delta: f64[3]
        for j: usize in 0..<3:
            for i: usize in 0..<3: delta[j] += third[(i * 3 + j) * 3 + i] + third[(j * 3 + i) * 3 + i] + third[(i * 3 + i) * 3 + j]
        let id = (u32)self.nodes.length()
        try self.nodes.append(WindingNode(center = center, radius = radius, area = area, moment = moment, third = third, delta = delta, first = (u32)first, count = (u32)(end - first), left = 0, right = 0))
        if end - first <= winding_leaf:
            return id
        # Split at the middle of the widest axis of the triangles' centers.
        let size = high.subtract(low)
        let axis = 0 if size.x >= size.y and size.x >= size.z else (1 if size.y >= size.z else 2)
        let cut = axis_value(low.add(high).multiply_scalar(0.5), axis)
        var lo = first
        var hi = end
        while lo < hi:
            let t = (usize)self.order[lo]
            let middle = self.corners[t * 3].add(self.corners[t * 3 + 1]).add(self.corners[t * 3 + 2]).multiply_scalar(1.0 / 3.0)
            if axis_value(middle, axis) < cut:
                lo += 1
            else:
                hi -= 1
                let held = self.order[lo]
                self.order[lo] = self.order[hi]
                self.order[hi] = held
        if lo == first or lo == end: lo = (first + end) // 2
        let left = try self.split(first, lo)
        let right = try self.split(lo, end)
        let node = &self.nodes.items()[(usize)id]
        node.left = left
        node.right = right
        node.count = 0
        return id

    ## The winding number at `p` (relative to the mesh's origin).
    func winding(p: Vector3) -> f64:
        if not self.built or self.nodes.length() == 0: return 0.0
        var total: f64 = 0.0
        var stack: u32[64]
        var depth: usize = 1
        stack[0] = 0
        let nodes = self.nodes.view()
        while depth > 0:
            depth -= 1
            let node = &nodes[(usize)stack[depth]]
            let to = node.center.subtract(p)
            let distance = to.length()
            if distance > winding_beta * node.radius and distance > 0.0:
                total += far_field(node, to, distance)
                continue
            if node.count > 0:
                for at in (usize)node.first..<(usize)(node.first + node.count):
                    let t = (usize)self.order[at]
                    total += solid_angle(self.corners[t * 3].subtract(p), self.corners[t * 3 + 1].subtract(p), self.corners[t * 3 + 2].subtract(p))
                continue
            stack[depth] = node.left
            stack[depth + 1] = node.right
            depth += 2
        return total / (4.0 * math.pi)

## A far cluster's solid angle from `p`, `to` its center less `p`: the Taylor expansion of
## F(x) = (x - p) / |x - p|^3 to second order integrated against the area, F(center) .
## area, then its Jacobian with the first moment, then half its Hessian with the second.
func far_field(node: const WindingNode*, to: Vector3, distance: f64) -> f64:
    let d2 = distance * distance
    let d3 = d2 * distance
    let d5 = d3 * d2
    let d7 = d5 * d2
    let rx = to.x
    let ry = to.y
    let rz = to.z
    # r^T M r, and the cubic form sum T_ijk r_i r_j r_k with the outer pair summed first.
    let rmr = rx * (node.moment[0] * rx + node.moment[1] * ry + node.moment[2] * rz) + ry * (node.moment[3] * rx + node.moment[4] * ry + node.moment[5] * rz) + rz * (node.moment[6] * rx + node.moment[7] * ry + node.moment[8] * rz)
    var cubic: f64 = 0.0
    for k: usize in 0..<3:
        let r = rx if k == 0 else (ry if k == 1 else rz)
        let q = rx * (node.third[k] * rx + node.third[3 + k] * ry + node.third[6 + k] * rz) + ry * (node.third[9 + k] * rx + node.third[12 + k] * ry + node.third[15 + k] * rz) + rz * (node.third[18 + k] * rx + node.third[21 + k] * ry + node.third[24 + k] * rz)
        cubic += q * r
    let linear = node.delta[0] * rx + node.delta[1] * ry + node.delta[2] * rz
    let first = to.dot(node.area) / d3
    let second = (node.moment[0] + node.moment[4] + node.moment[8]) / d3 - 3.0 * rmr / d5
    let third_order = 0.5 * (-3.0 * linear / d5 + 15.0 * cubic / d7)
    return first + second + third_order

func axis_value(v: Vector3, axis: i64) -> f64:
    return v.x if axis == 0 else (v.y if axis == 1 else v.z)

## The signed solid angle of triangle (a, b, c) seen from the origin (Van Oosterom and
## Strackee): positive when the triangle faces away from the origin.
func solid_angle(a: Vector3, b: Vector3, c: Vector3) -> f64:
    let la = a.length()
    let lb = b.length()
    let lc = c.length()
    let det = a.dot(b.cross(c))
    let below = la * lb * lc + a.dot(b) * lc + b.dot(c) * la + c.dot(a) * lb
    return 2.0 * math.atan2(det, below)

## Register `windingnumber`.
func bind_winding(host: Host*) -> !:
    try host.builtin("Geometry", "windingnumber", engine.Builtin.of("windingnumber", [Kind.i64, Kind.f32, Kind.f32, Kind.f32, Kind.f32], [Kind.f32], winding_lanes))

func winding_lanes(call: engine.Call*):
    let state = state_of(call) else return
    let out = call.f32_result(0)
    for lane in 0..<call.lanes:
        out[lane] = 0.0
        let source = source_or_fail(state, call, lane) else continue
        let mesh = source.mesh else continue
        if not source.winding.built:
            call.fail(lane)
            continue
        out[lane] = (f32)source.winding.winding(position_argument(call, 1, lane).subtract(mesh.position_origin()))