dymokomi/luce-geocore
Source of release 0.7.9
0.7.9 / src / verbs / builder.lucb
## The topology a verb builds: points, faces and corners with their parents
## in the input, from which every attribute and group is carried (see
## propagate.lucb). A parent of -1 is a new element (zero, empty, not a
## member); interpolated points and corners name weighted parents (a Mix).
## Faces copied with their corners in order keep the input's triangles, so
## CAD cut cells survive; other faces are ear clipped in parallel.
pub struct TopologyBuilder:
## Points in f64, measured from the input's origin.
var positions: Growing[Vector3]
var offsets: Growing[i32]
var corners: Growing[i32]
var point_parents: Growing[i32]
var face_parents: Growing[i32]
var corner_parents: Growing[i32]
## Per face: 1 when its corners are its parent's, in order, 2 when in
## reverse order; 0 when it is ear clipped.
var copied: Growing[u8]
var point_mix: Mix
var corner_mix: Mix
var origin: Vector3
## Point pairs whose edges are the output selection (see select_edge).
var selected_edges: Growing[i32]
## Triangulate new faces as fans and trust them (no ear clipping, no
## area check; face normals left zero): subdivision templates, whose
## positions the display replaces.
pub var fans: bool = false
## Keep f64 points (a precise mesh) even when the source has none: a
## boolean's cut points, which the next boolean reads as they were made.
pub var precise: bool = false
pub func init():
self.positions = Growing[Vector3]()
self.offsets = Growing[i32]()
self.corners = Growing[i32]()
self.point_parents = Growing[i32]()
self.face_parents = Growing[i32]()
self.corner_parents = Growing[i32]()
self.copied = Growing[u8]()
self.point_mix = Mix()
self.corner_mix = Mix()
self.origin = Vector3()
self.selected_edges = Growing[i32]()
self.fans = false
self.precise = false
## Start from `source`'s frame (its origin).
pub func begin(source: const Mesh*) -> !:
self.origin = source.position_origin()
try self.offsets.push(0)
try self.point_mix.offsets.push(0)
try self.corner_mix.offsets.push(0)
pub func point_count() -> usize:
return self.positions.count
pub func face_count() -> usize:
return self.face_parents.count
pub func corner_count() -> usize:
return self.corners.count
## A point at `position` (world) with one parent (-1: new).
pub func point(position: Vector3, parent: i32) -> i32!:
try self.positions.push(position.subtract(self.origin))
try self.point_parents.push(parent)
return (i32)(self.positions.count - 1)
## A point interpolated from weighted parents.
pub func mixed_point(position: Vector3, parents: const i32[], weights: const f32[]) -> i32!:
try self.positions.push(position.subtract(self.origin))
try self.point_parents.push(try mix_entry(&self.point_mix, parents, weights))
return (i32)(self.positions.count - 1)
## Every point of `source`, each its own parent, in one pass.
pub func copy_points(source: const Mesh*) -> !:
let positions = source.point_span()
let exact = precise_span(source)
let first = self.positions.count
try self.positions.reserve(first + positions.length)
try self.point_parents.reserve(first + positions.length)
for at in 0..<positions.length:
self.positions.items[first + at] = exact[at].subtract(self.origin) if exact.length > 0 else positions[at].vector()
self.point_parents.items[first + at] = (i32)at
self.positions.count += positions.length
self.point_parents.count += positions.length
## `count` more points whose positions and parents are set afterwards
## (`place_point`, by threads each on its own points); the first one's
## number.
pub func extend_points(count: usize) -> usize!:
let first = self.positions.count
try self.positions.reserve(first + count)
try self.point_parents.reserve(first + count)
self.positions.count = first + count
self.point_parents.count = first + count
return first
## Point `index` (from `extend_points`) at `position` (world), with one
## parent (-1: new).
pub func place_point(index: usize, position: Vector3, parent: i32):
self.positions.items[index] = position.subtract(self.origin)
self.point_parents.items[index] = parent
## Set point `index`'s position (world).
pub func move_point(index: i32, position: Vector3):
self.positions.items[(usize)index] = position.subtract(self.origin)
pub func position(index: i32) -> Vector3:
return self.positions.items[(usize)index].add(self.origin)
## Start a face whose parent is `parent`; `copied` when its corners will
## be its parent's, in order (its triangles are then kept), `reversed`
## when they will be its parent's in reverse order.
pub func face(parent: i32, copied: bool = false, reversed: bool = false) -> !:
try self.face_parents.push(parent)
try self.copied.push(2 if reversed else (1 if copied else 0))
pub func corner(point: i32, parent: i32) -> !:
try self.corners.push(point)
try self.corner_parents.push(parent)
pub func mixed_corner(point: i32, parents: const i32[], weights: const f32[]) -> !:
try self.corners.push(point)
try self.corner_parents.push(try mix_entry(&self.corner_mix, parents, weights))
## A corner mix that several corners share (see `shared_corner`): a
## face's center in every one of its subdivided quads stores its parents
## once, not once a quad, which for an n-gon is n rather than n * n.
pub func shared_mix(parents: const i32[], weights: const f32[]) -> i32!:
return try mix_entry(&self.corner_mix, parents, weights)
## A corner at `point` whose parent is `mix` from `shared_mix`.
pub func shared_corner(point: i32, mix: i32) -> !:
try self.corners.push(point)
try self.corner_parents.push(mix)
## Close the face begun last; faces need at least 3 corners (the corner
## budget is checked in finish).
pub func end_face() -> !:
let size = (i64)self.corners.count - (i64)self.offsets.items[self.offsets.count - 1]
if size < 3: error(errors.invalid, "an operation made a face with fewer than 3 corners")
try self.offsets.push((i32)self.corners.count)
## Faces first..<end of `source` unchanged (points numbered as in the
## input: after `copy_points`), in one tight pass.
pub func copy_faces(source: const Mesh*, first: usize, end: usize) -> !:
if end <= first: return
let offsets = source.offset_span()
let corners = source.corner_span()
let from_corner = (usize)offsets[first]
let to_corner = (usize)offsets[end]
let count = to_corner - from_corner
let faces = end - first
try self.corners.reserve(self.corners.count + count)
try self.corner_parents.reserve(self.corner_parents.count + count)
try self.offsets.reserve(self.offsets.count + faces)
try self.face_parents.reserve(self.face_parents.count + faces)
try self.copied.reserve(self.copied.count + faces)
let shift = (i32)self.corners.count - (i32)from_corner
memory.copy(self.corners.items[self.corners.count..], corners[from_corner..<to_corner], count)
for at in 0..<count: self.corner_parents.items[self.corner_parents.count + at] = (i32)(from_corner + at)
for at in 0..<faces:
self.offsets.items[self.offsets.count + at] = offsets[first + at + 1] + shift
self.face_parents.items[self.face_parents.count + at] = (i32)(first + at)
self.copied.items[self.copied.count + at] = 1
self.corners.count += count
self.corner_parents.count += count
self.offsets.count += faces
self.face_parents.count += faces
self.copied.count += faces
## Face `face` of `source` unchanged: its corners (with this builder's
## point numbers `points`, or its own when empty) and its triangles.
pub func copy_face(source: const Mesh*, face: usize, points: const i32[]) -> !:
let offsets = source.offset_span()
let corners = source.corner_span()
try self.face((i32)face, true)
for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
let point = corners[corner]
try self.corner(points[(usize)point] if points.length > 0 else point, (i32)corner)
try self.end_face()
## Select the edge between points `a` and `b` of the result (the output
## selection is then these edges).
pub func select_edge(a: i32, b: i32) -> !:
try self.selected_edges.push(a)
try self.selected_edges.push(b)
## Remove the points no corner uses, renumbering the rest in order (a
## verb that replaces some input points copies them all first).
## A point selection `selected`, when given, is renumbered with them, and
## so are the point numbers in `renumber` (a removed point's become -1).
pub func drop_unused_points(selected: BitsBuilder*? = none, renumber: Growing[i32]*? = none) -> !:
let points = self.positions.count
let map = try new i32[points] --- in memory.heap
defer free(map) in memory.heap
for at in 0..<points: map[at] = -1
for point in self.corners.view(): map[(usize)point] = 0
var kept: usize = 0
for at in 0..<points:
if map[at] < 0: continue
map[at] = (i32)kept
self.positions.items[kept] = self.positions.items[at]
self.point_parents.items[kept] = self.point_parents.items[at]
kept += 1
if let bits = selected:
var renumbered = try BitsBuilder.zeros(kept)
for at in 0..<points:
if map[at] >= 0 and bits.view().get(at): renumbered.set((usize)map[at])
bits.close()
*bits = renumbered
self.positions.count = kept
self.point_parents.count = kept
var renumbering = Renumbering(map[..<points], self.corners.items[..<self.corners.count])
try parallel.for_each_range(self.corners.count, 65536, (void*)&renumbering, renumber_range)
renumbering.values = self.selected_edges.items[..<self.selected_edges.count]
try parallel.for_each_range(self.selected_edges.count, 65536, (void*)&renumbering, renumber_range)
if let others = renumber:
renumbering.values = others.items[..<others.count]
try parallel.for_each_range(others.count, 65536, (void*)&renumbering, renumber_range)
## The mesh: positions, faces, triangles (kept or clipped), normals, and
## every attribute of `source` through the parents.
pub func finish(source: const Mesh*) -> Mesh*!:
let points = self.positions.count
let faces = self.face_parents.count
let corner_total = self.corners.count
try check_mesh_size(points, faces, corner_total)
var positions = try Column[Float3].allocate(points)
defer positions.release()
let placed = positions.span()
for at in 0..<points: placed[at] = Float3.of(self.positions.items[at])
var exact: Column[Vector3]
defer exact.release()
if self.precise or precise_span(source).length > 0:
exact = try Column[Vector3].allocate(points)
let out = exact.span()
for at in 0..<points: out[at] = self.positions.items[at].add(self.origin)
var offsets = try Column[i32].copy_of(self.offsets.view())
defer offsets.release()
var corners = try Column[i32].copy_of(self.corners.view())
defer corners.release()
var triangles = try Column[i32].allocate((corner_total - faces * 2) * 3)
defer triangles.release()
var work = TriangleWork(source.offset_span(), source.triangle_span(), self.offsets.view(), self.face_parents.view(), self.copied.view(), triangles.span(), self.fans)
try parallel.for_each_range(faces, 4096, (void*)&work, copy_triangles)
var normals: Column[Float3]
defer normals.release()
if self.fans: normals = try Column[Float3].filled(faces, Float3.of(Vector3()))
let storage = try assembled(positions.take(), self.origin, offsets.take(), corners.take(), triangles.take(), normals.take(), exact.take())
errdefer mesh_dispose(storage)
try propagate(source, storage, self.point_parents.view(), self.face_parents.view(), self.corner_parents.view(), &self.point_mix, &self.corner_mix)
return storage
pub func close():
self.positions.close()
self.offsets.close()
self.corners.close()
self.point_parents.close()
self.face_parents.close()
self.corner_parents.close()
self.copied.close()
self.selected_edges.close()
self.point_mix.close()
self.corner_mix.close()
## A mix entry for `parents`/`weights`: its parent code (-2 - entry). One
## parent of full weight is that parent itself.
func mix_entry(mix: Mix*, parents: const i32[], weights: const f32[]) -> i32!:
if parents.length == 1: return parents[0]
let entry = mix.offsets.count - 1
for at in 0..<parents.length:
try mix.parents.push(parents[at])
try mix.weights.push(weights[at])
try mix.offsets.push((i32)mix.parents.count)
return -2 - (i32)entry
## Point numbers renumbered through `map` (out of range or removed: -1).
struct Renumbering:
var map: const i32[]
var values: i32[]
func renumber_range(context: void*, first: usize, end: usize, worker: usize) -> !:
let renumbering = (Renumbering*)context
let map = renumbering.map
for at in first..<end:
let point = renumbering.values[at]
renumbering.values[at] = map[(usize)point] if point >= 0 and (usize)point < map.length else -1
struct TriangleWork:
let source_offsets: const i32[]
let source_triangles: const i32[]
let offsets: const i32[]
let parents: const i32[]
let copied: const u8[]
let triangles: i32[]
let fans: bool
## Copied faces take their parent's triangles, shifted to their corners;
## the rest are marked for ear clipping.
func copy_triangles(context: void*, first: usize, end: usize, worker: usize):
let work = (TriangleWork*)context
for face in first..<end:
let start = (usize)work.offsets[face]
let size = (usize)work.offsets[face + 1] - start
let target = (start - face * 2) * 3
if work.copied[face] == 0:
if not work.fans:
work.triangles[target] = -1
continue
for triangle in 0..<size - 2:
work.triangles[target + triangle * 3] = (i32)start
work.triangles[target + triangle * 3 + 1] = (i32)(start + triangle + 1)
work.triangles[target + triangle * 3 + 2] = (i32)(start + triangle + 2)
continue
let parent = (usize)work.parents[face]
let old_start = (usize)work.source_offsets[parent]
let from_triangle = (old_start - parent * 2) * 3
let shift = (i32)start - (i32)old_start
if work.copied[face] == 1:
for at in 0..<(size - 2) * 3:
work.triangles[target + at] = work.source_triangles[from_triangle + at] + shift
continue
# Reversed: corner k is the old corner size - 1 - k, winding flipped.
for triangle in 0..<size - 2:
for side in 0..<(usize)3:
let old = work.source_triangles[from_triangle + triangle * 3 + 2 - side] - (i32)old_start
work.triangles[target + triangle * 3 + side] = (i32)start + (i32)size - 1 - old