dymokomi/luce-cad
Source of release 0.9.2
0.9.2 / src / tessellation / face_cache.lucb
## The per-face tessellation cache. A face's mesh is a function of its
## support surface, the curves of its edge uses, the shared boundary points
## it sits on (its edges' samples and its frozen interior-row points), its
## layout plan and the tessellation parameters. Each face job's result is
## kept as a piece whose corners name those boundary points by their place
## in the face's boundary table, not by global point id, so the piece stays
## valid when unrelated edges gain or lose samples and every id after them
## shifts. The key hashes all the inputs (boundary points by position, and
## by which table entries share a point and how their ids rank), so a hit
## rebuilds exactly what a fresh face job would.
## A 64-bit running hash of numbers.
pub struct Hasher:
var value: u64 = 0x9E3779B97F4A7C15
pub func mix(input: u64):
var h = (self.value ^ input) *% 0x100000001B3
h = h ^ (h >> 29)
self.value = h *% 0xBF58476D1CE4E5B9
## The value's bits (-0 and +0 alike).
pub func number(input: f64):
var value = input + 0.0
self.mix(u64[]((u64*)&value, 1)[0])
pub func integer(input: i64):
self.mix((u64)input)
pub func point(input: Vector3):
self.number(input.x)
self.number(input.y)
self.number(input.z)
## One face's cached tessellation. Corners >= 0 are the piece's own points;
## corners < 0 are boundary-table entries, -(entry + 1). Shared by count.
pub struct Piece:
var users: @usize
pub var key: u64
pub var points: Vector3[]
pub var sizes: i64[]
pub var corners: i64[]
pub var display: i64[]
pub var normals: f64[]
## What the face job recorded in its plan: strategy and grid use.
pub var method: i64
pub var applied: bool
pub func release_piece(piece: Piece*):
if piece.users.sub(1, .acq_rel) != 1: return
if piece.points.length > 0: free(piece.points) in memory.heap
if piece.sizes.length > 0: free(piece.sizes) in memory.heap
if piece.corners.length > 0: free(piece.corners) in memory.heap
if piece.display.length > 0: free(piece.display) in memory.heap
if piece.normals.length > 0: free(piece.normals) in memory.heap
free(piece) in memory.heap
## A new piece holding these arrays (moved in), with one user.
pub func new_piece(key: u64, points: Vector3[], sizes: i64[], corners: i64[], display: i64[], normals: f64[], method: i64, applied: bool) -> Piece*!:
let storage = try new Piece[1] --- in memory.heap
let piece = &storage[0]
piece.users.store(1, .relaxed)
piece.key = key
piece.points = points
piece.sizes = sizes
piece.corners = corners
piece.display = display
piece.normals = normals
piece.method = method
piece.applied = applied
return piece
## Pieces by face, one model's. Faces keep their slot while their key holds.
pub struct FaceCache:
var lock: sync.Mutex
var pieces: Growing[Piece*?]
var hits: usize = 0
pub func init():
self.lock = sync.Mutex()
self.pieces = Growing[Piece*?]()
self.hits = 0
## The piece of `face` when its key is `key`, shared; else none.
pub func find(face: usize, key: u64) -> Piece*?:
self.lock.lock()
defer self.lock.unlock()
if face >= self.pieces.count: return none
let piece = self.pieces.items[face] else return none
if piece.key != key: return none
_ = piece.users.add(1, .relaxed)
self.hits += 1
return piece
## Keep `piece` for `face` (its share moves in), replacing another.
pub func put(face: usize, piece: Piece*) -> !:
self.lock.lock()
defer self.lock.unlock()
if face >= self.pieces.count:
let old = self.pieces.count
try self.pieces.reserve(face + 1)
for at in old..<face + 1: self.pieces.items[at] = none
self.pieces.count = face + 1
if let previous = self.pieces.items[face]: release_piece(previous)
self.pieces.items[face] = piece
## Faces answered from the cache since the last call.
pub func take_hits() -> usize:
self.lock.lock()
defer self.lock.unlock()
let hits = self.hits
self.hits = 0
return hits
pub func close():
for piece in self.pieces.view():
if let held = piece: release_piece(held)
self.pieces.close()
## A copy of `source`'s pieces for a model derived from it (its faces in the
## same order): every piece shared.
pub func inherited(source: FaceCache*) -> FaceCache*!:
let copy = try new FaceCache() in memory.heap
errdefer:
copy.close()
free(copy) in memory.heap
source.lock.lock()
defer source.lock.unlock()
try copy.pieces.reserve(source.pieces.count)
for piece in source.pieces.view():
if let held = piece: _ = held.users.add(1, .relaxed)
copy.pieces.items[copy.pieces.count] = piece
copy.pieces.count += 1
return copy
pub func dispose_cache(cache: FaceCache*):
cache.close()
free(cache) in memory.heap
## Every face's boundary table: its edge uses' samples in order, then its
## interior-row points, as global point ids (`ids`, face f's entries from
## `starts[f]`); `sorted` holds each table's (id, entry) pairs by id.
pub struct Tables:
pub var ids: Growing[i64]
pub var starts: Growing[u32]
pub var sorted: Growing[i64]
pub func init():
self.ids = Growing[i64]()
self.starts = Growing[u32]()
self.sorted = Growing[i64]()
pub func of(face: usize) -> const i64[]:
return self.ids.items[(usize)self.starts.items[face]..<(usize)self.starts.items[face + 1]]
## The entry of global point `id` in `face`'s table, or -1.
pub func entry(face: usize, id: i64) -> i64:
let first = (usize)self.starts.items[face]
var low = first
var high = (usize)self.starts.items[face + 1]
while low < high:
let middle = (low + high) // 2
if self.sorted.items[middle] >> 20 < id: low = middle + 1
else: high = middle
if low < (usize)self.starts.items[face + 1] and self.sorted.items[low] >> 20 == id: return self.sorted.items[low] & 0xFFFFF
return -1
pub func close():
self.ids.close()
self.starts.close()
self.sorted.close()
## The tables of every face.
pub func face_tables(faces: const BrepFace[], samples: const Samples[], plans: const GridLayout[], tables: Tables*) -> !:
try tables.starts.push(0)
for index in 0..<faces.length:
let first = tables.ids.count
for use in faces[index].uses:
let edge = edge_index(use)
for id in samples[edge].ids: try tables.ids.push(id)
for row in plans[index].row_ids:
for id in row.values: try tables.ids.push(id)
let count = tables.ids.count - first
if count >= 0xFFFFF: error(memory.exhausted, "a CAD face's boundary table is too large to cache")
for entry in 0..<count: try tables.sorted.push((tables.ids.items[first + entry] << 20) | (i64)entry)
sort.sort(tables.sorted.items[first..<first + count])
try tables.starts.push((u32)tables.ids.count)
## The key of face `index`: every input its face job reads.
pub func face_key(index: usize, faces: const BrepFace[], surfaces: const Surface[], edges: const Curve[], samples: const Samples[], plans: const GridLayout[], points: const Vector3[], tables: const Tables*, divisions: i64, tolerance: f64, edge_size: f64) -> u64:
var h = Hasher()
h.integer(divisions)
h.number(tolerance)
h.number(edge_size)
let face = faces[index]
h.integer(1 if face.sense else 0)
for size in face.sizes: h.integer(size)
hash_surface(&h, surfaces[(usize)face.surface])
for use in face.uses:
h.integer(1 if use > 0 else -1)
let edge = edge_index(use)
hash_curve(&h, edges[edge])
# Baseline samples by their table entries.
for id in samples[edge].baseline: h.integer(tables.entry(index, id))
# Boundary points: position, first entry naming the same point, and the
# rank of their ids (a renumbering that keeps the order keeps the key).
let table = tables.of(index)
for entry in 0..<table.length:
let id = table[entry]
h.point(points[(usize)id])
h.integer(tables.entry(index, id))
let first = (usize)tables.starts.items[index]
for at in first..<(usize)tables.starts.items[index + 1]: h.integer(tables.sorted.items[at] & 0xFFFFF)
hash_plan(&h, plans[index], tables, index)
return h.value
func hash_surface(h: Hasher*, surface: Surface):
h.integer(surface.kind)
h.integer(1 if surface.edited else 0)
h.point(surface.origin)
h.point(surface.x)
h.point(surface.z)
h.number(surface.radius)
h.number(surface.angle)
h.integer(surface.nu)
h.integer(surface.nv)
h.integer(surface.du)
h.integer(surface.dv)
for point in surface.points: h.point(point)
for weight in surface.weights: h.number(weight)
for knot in surface.ku: h.number(knot)
for knot in surface.kv: h.number(knot)
func hash_curve(h: Hasher*, curve: Curve):
h.integer(curve.kind)
h.point(curve.origin)
h.point(curve.x)
h.point(curve.y)
h.number(curve.radius)
h.integer(curve.degree)
h.integer(1 if curve.sense else 0)
h.number(curve.angle)
h.number(curve.sweep)
for point in curve.points: h.point(point)
for weight in curve.weights: h.number(weight)
for knot in curve.knots: h.number(knot)
func hash_stations(h: Hasher*, stations: Stations):
h.integer((i64)stations.count)
h.number(stations.epsilon)
h.number(stations.separation)
h.integer((i64)stations.baseline)
h.integer((i64)stations.limit)
for value in stations.values[..<stations.count]: h.number(value)
## The plan as the face job reads it (its own rows' points by table entry).
func hash_plan(h: Hasher*, plan: GridLayout, tables: const Tables*, face: usize):
h.integer(1 if plan.valid else 0)
h.integer(1 if plan.cut_first else 0)
h.number(plan.epsilon)
h.point(plan.trim_low)
h.point(plan.trim_high)
h.integer(1 if plan.independent_phase else 0)
h.integer(1 if plan.pitch_axes[0] else 0)
h.integer(1 if plan.pitch_axes[1] else 0)
hash_stations(h, plan.u)
hash_stations(h, plan.v)
h.integer((i64)plan.rows.length)
for row in plan.rows: hash_stations(h, row)
for row in plan.row_ids:
h.integer((i64)row.values.length)
for id in row.values: h.integer(tables.entry(face, id))
for flow in plan.flow: h.integer(1 if flow else 0)
for applied in plan.applied: h.integer(1 if applied else 0)
for method in plan.method: h.integer(method)
h.integer((i64)plan.seen)
for chain in plan.chains:
h.integer((i64)chain.points.length)
for point in chain.points: h.point(point)
for time in chain.times: h.number(time)