Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / layout / trim_memo.lucb

## Exact memo of one face's pure trim computations: NURBS point inversions and
## edge/grid crossings. Layout reconciliation is Gauss-Seidel over faces (each
## face sees its neighbors' newest cuts), so it stays serial; a parallel pass
## fills this memo speculatively first, and the serial pass reuses any entry
## whose inputs match bit for bit. Results are identical to the serial code
## whatever the speculation guessed; a wrong guess only costs a miss.

let words: usize = 11
let most_entries: usize = 1 << 17

pub struct TrimMemo:
    var keys: u64[]
    var values: Vector3[]
    var states: u8[]
    var count: usize = 0

    pub func close():
        if self.states.length > 0:
            free(self.keys) in memory.heap
            free(self.values) in memory.heap
            free(self.states) in memory.heap
        self.count = 0

    ## Slot of `key`: its entry (state 1 ok, 2 failed), or an empty slot (0).
    func slot(key: const u64[]) -> usize:
        var mixed: u64 = 1469598103934665603
        for word in key:
            mixed = (mixed ^ word) *% 1099511628211
            mixed = mixed ^ (mixed >> 29)
        var at = (usize)(mixed % (u64)self.states.length)
        while self.states[at] != 0:
            var same = true
            for index in 0..<words:
                if self.keys[at * words + index] != key[index]:
                    same = false
                    break
            if same: return at
            at = (at + 1) % self.states.length
        return at

    ## The stored result for `key`: none when absent; `failed` when the
    ## computation raised an `invalid` error.
    pub func find(key: const u64[], failed: bool*) -> Vector3?:
        if self.states.length == 0: return none
        let at = self.slot(key)
        if self.states[at] == 0: return none
        *failed = self.states[at] == 2
        return self.values[at]

    pub func put(key: const u64[], value: Vector3, failed: bool) -> !:
        if self.count >= most_entries: return
        if (self.count + 1) * 2 > self.states.length: try self.grow()
        let at = self.slot(key)
        if self.states[at] == 0: self.count += 1
        memory.copy(self.keys[at * words..<(at + 1) * words], key, words)
        self.values[at] = value
        self.states[at] = 2 if failed else 1

    func grow() -> !:
        let capacity = 1024 if self.states.length == 0 else self.states.length * 2
        let keys = try new u64[capacity * words] --- in memory.heap
        errdefer free(keys) in memory.heap
        let values = try new Vector3[capacity] --- in memory.heap
        errdefer free(values) in memory.heap
        let states = try new u8[capacity] --- in memory.heap
        for at in 0..<capacity: states[at] = 0
        let old_keys = self.keys
        let old_values = self.values
        let old_states = self.states
        self.keys = keys
        self.values = values
        self.states = states
        self.count = 0
        for at in 0..<old_states.length:
            if old_states[at] == 0: continue
            let key = old_keys[at * words..<(at + 1) * words]
            let slot = self.slot(key)
            memory.copy(self.keys[slot * words..<(slot + 1) * words], key, words)
            self.values[slot] = old_values[at]
            self.states[slot] = old_states[at]
            self.count += 1
        if old_states.length > 0:
            free(old_keys) in memory.heap
            free(old_values) in memory.heap
            free(old_states) in memory.heap

## The exact bits of `value`, so equal keys mean bit-identical inputs.
pub func bits(value: f64) -> u64:
    return value.bits()

## `chart_parameter(s, p, seed, tolerance)` through `memo`. Only NURBS inversions are
## worth remembering; analytic charts are closed-form.
pub func memo_parameter(memo: TrimMemo*?, s: Surface, p: Vector3, seed: Vector3, tolerance: f64) -> Vector3!:
    let table = memo else return try chart_parameter(s, p, seed, tolerance)
    if s.kind != surface_spline: return try chart_parameter(s, p, seed, tolerance)
    var key: u64[11]
    key[0] = 1
    key[1] = bits(p.x)
    key[2] = bits(p.y)
    key[3] = bits(p.z)
    key[4] = bits(seed.x)
    key[5] = bits(seed.y)
    key[6] = bits(seed.z)
    key[7] = 0
    key[8] = 0
    key[9] = 0
    key[10] = 0
    var failed = false
    if let found = table.find(key[..<11], &failed):
        if failed: error(invalid, "NURBS boundary projection exceeds CAD tolerance")
        return found
    let result = chart_parameter(s, p, seed, tolerance) catch failure:
        if failure.code == invalid: try table.put(key[..<11], Vector3(), true)
        error(failure.code, failure.message)
    try table.put(key[..<11], result, false)
    return result