Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.3

0.9.3 / src / surfacing / fill_bands.lucb

## The normal equations of a fill (surfacing Stage 7; fill.lucb has the
## plan): a symmetric positive definite matrix over the free control
## points' coordinates, kept as a band below its diagonal, with its
## right-hand side, and the constraint rows that build it.
##
## The unknowns are ordered u-major (control point (i, j) before (i, j + 1),
## its x, y and z together), so every pair of control points whose bases
## overlap (the energy) or meet at one station (a constraint) lies within
## half-bandwidth 3 (du nv + dv) + 2. Cholesky on that band costs n h²
## (n unknowns, h the half-bandwidth) instead of n³: a 32 by 32 span
## quintic net, four thousand unknowns, factors in about a second. The
## matrix is factored once for a net and solved for as many right-hand
## sides as the G2 passes ask, each answer refined by its residual against the
## matrix kept unfactored (weights of a million make the equations stiff).

## A symmetric positive definite band system: (i, i - d) at
## band[i * (half + 1) + d], d to `half`; `kept` the matrix before
## factoring.
struct BandSystem:
    var size: usize
    var half: usize
    var band: Growing[f64]
    var kept: Growing[f64]
    var rhs: Growing[f64]

    func close():
        self.band.close()
        self.kept.close()
        self.rhs.close()

    ## Adds `value` to entries (i, j) and (j, i) (once on the diagonal).
    func add(i: usize, j: usize, value: f64):
        if i >= j: self.band.items[i * (self.half + 1) + i - j] += value
        else: self.band.items[j * (self.half + 1) + j - i] += value

    ## The mean of the diagonal (the scale constraint weights follow).
    func diagonal_mean() -> f64:
        if self.size == 0: return 1.0
        var sum = 0.0
        for i in 0..<self.size: sum += self.band.items[i * (self.half + 1)]
        return sum / (f64)self.size

    ## Factors the band in place (L Lᵀ), the matrix kept for refinement;
    ## a tiny ridge keeps an energy's affine null space from a zero pivot
    ## where constraints leave it loose.
    func factor() -> !:
        let n = self.size
        let w = self.half + 1
        let ridge = 1e-13 * self.diagonal_mean()
        for i in 0..<n: self.band.items[i * w] += ridge
        try self.kept.assign(self.band.view())
        if n == 0: return
        # The hot loops index the band through its pointer (unchecked): every
        # index is within the band by the bounds above.
        let band: f64* = &self.band.items[0]
        for j in 0..<n:
            let low_j = j - fewer(j, self.half)
            # Row j's pointer: (j, k) at row_j - k, the diagonal at row_j - j.
            let row_j: f64* = band + (j * w + j)
            var d = (row_j - j)[0]
            for k in low_j..<j:
                let l = (row_j - k)[0]
                d -= l * l
            if not (d > 0.0): error(invalid, "Fill: the patch's equations have no single answer (the boundaries hold too little of it)")
            let diagonal = math.sqrt(d)
            (row_j - j)[0] = diagonal
            for i in j + 1..<fewer(n, j + w):
                let low_i = i - fewer(i, self.half)
                let row_i: f64* = band + (i * w + i)
                let start = low_i if low_i > low_j else low_j
                # (i, k) and (j, k) for k from start to j: both runs lie
                # backward in memory from their rows' diagonals.
                var a: f64* = row_i - start
                var c: f64* = row_j - start
                var s = (row_i - j)[0]
                for _ in start..<j:
                    s -= a[0] * c[0]
                    a = a - 1
                    c = c - 1
                (row_i - j)[0] = s / diagonal

    ## Solves L Lᵀ x = b in place (`b` becomes x).
    func substitute(b: f64[]):
        let n = self.size
        if n == 0: return
        let w = self.half + 1
        let band: f64* = &self.band.items[0]
        let x: f64* = &b[0]
        for i in 0..<n:
            let row: f64* = band + (i * w + i)
            var s = x[i]
            for k in i - fewer(i, self.half)..<i: s -= (row - k)[0] * x[k]
            x[i] = s / (row - i)[0]
        var i = n
        while i > 0:
            i -= 1
            var s = x[i]
            for k in i + 1..<fewer(n, i + w): s -= band[k * w + k - i] * x[k]
            x[i] = s / band[i * w]

    ## The answer for the right-hand side `self.rhs` onto `out`, refined
    ## three times by its residual against the kept matrix.
    func solve(out: Growing[f64]*) -> !:
        let n = self.size
        let w = self.half + 1
        try out.assign(self.rhs.view())
        self.substitute(out.items[..<n])
        var residual = Growing[f64]()
        defer residual.close()
        for _ in 0..<3:
            try residual.assign(self.rhs.view())
            for i in 0..<n:
                for k in i - fewer(i, self.half)..<i + 1:
                    let a = self.kept.items[i * w + i - k]
                    residual.items[i] -= a * out.items[k]
                    if k != i: residual.items[k] -= a * out.items[i]
            self.substitute(residual.items[..<n])
            for i in 0..<n: out.items[i] += residual.items[i]

## A band system of `size` unknowns and half-bandwidth `half`, zero.
func band_system(size: usize, half: usize) -> BandSystem!:
    var s = BandSystem(size, half, Growing[f64](), Growing[f64](), Growing[f64]())
    errdefer s.close()
    try s.band.fill(size * (half + 1), 0.0)
    try s.rhs.fill(size, 0.0)
    return s

## One constraint row, built a term at a time: a combination of control
## point coordinates (the free ones by unknown, the fixed ones folded into
## `constant`) that should equal a target.
struct FillRow:
    var index: Growing[usize]
    var value: Growing[f64]
    var constant: f64
    ## Each unknown's place in `index` (-1 none), so a term met twice adds.
    var place: Growing[i64]

    func close():
        self.index.close()
        self.value.close()
        self.place.close()

    ## Unknown `at` times `coefficient`.
    func term(at: usize, coefficient: f64) -> !:
        if coefficient == 0.0: return
        let k = self.place.items[at]
        if k >= 0:
            self.value.items[(usize)k] += coefficient
            return
        self.place.items[at] = (i64)self.index.count
        try self.index.push(at)
        try self.value.push(coefficient)

    ## The row's coefficients' length (zero: the row holds nothing free).
    func norm() -> f64:
        var sum = 0.0
        for v in self.value.view(): sum += v * v
        return math.sqrt(sum)

    ## The row into `system` as w (a·x + constant - target)², normalized to
    ## a unit row, then cleared.
    func commit(system: BandSystem*, target: f64, weight: f64):
        let length = self.norm()
        if length > 0.0:
            let w = weight / (length * length)
            let goal = target - self.constant
            for p in 0..<self.index.count:
                let ip = self.index.items[p]
                let ap = self.value.items[p] * w
                system.rhs.items[ip] += ap * goal
                for q in 0..<self.index.count:
                    let iq = self.index.items[q]
                    if iq <= ip: system.add(ip, iq, ap * self.value.items[q])
        self.clear()

    ## The row's value at unknowns `x` (with its constant).
    func evaluate(x: const f64[]) -> f64:
        var sum = self.constant
        for p in 0..<self.index.count: sum += self.value.items[p] * x[self.index.items[p]]
        return sum

    func clear():
        for at in self.index.view(): self.place.items[at] = -1
        self.index.clear()
        self.value.clear()
        self.constant = 0.0

## An empty row over `size` unknowns.
func fill_row(size: usize) -> FillRow!:
    var row = FillRow(Growing[usize](), Growing[f64](), 0.0, Growing[i64]())
    errdefer row.close()
    try row.place.fill(size, -1)
    return row