dymokomi/luce-cad
Source of release 0.9.2
0.9.2 / 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