dymokomi/luce-geocore
Source of release 0.7.9
0.7.9 / src / geometries / polygon / edits.lucb
## Operators that publish new meshes: remapping through parent maps, position
## edits, placement and merging. Position edits copy the positions once, share
## the topology, its caches, the triangles and every attribute, recompute only
## the faces around moved points, and refit the spatial index.
extend Mesh:
## All operators publish new meshes. Parent maps are output-to-input indices;
## -1 means a genuinely new element (zero-valued attributes). Empty maps mean
## unchanged indexing, valid only when domain cardinality is unchanged. Edge
## attributes follow their corners. The result is precise when this mesh
## is, or when `precise` asks.
pub func remapped(points: const Vector3[], sizes: const i64[], corners: const i64[],
point_parents: const i64[], face_parents: const i64[], corner_parents: const i64[], preserve_normals: bool = false, display: const i64[]? = none, precise: bool = false) -> interop.Reference[Mesh]!:
try validate_map(point_parents, points.length, self.positions.count())
try validate_map(face_parents, sizes.length, self.offsets.count() - 1)
try validate_map(corner_parents, corners.length, self.corners.count())
let result = try make_mesh(points, sizes, corners, display, precise or self.is_precise())
errdefer result.release()
let output = result.value()
var unchanged_geometry = points.length == self.positions.count() and sizes.length == self.offsets.count() - 1 and corners.length == self.corners.count()
if unchanged_geometry and not preserve_normals:
let old_offsets = self.offsets.view()
let old_corners = self.corners.view()
for at in 0..<points.length:
let old = self.point_at(at)
unchanged_geometry = unchanged_geometry and points[at].x == old.x and points[at].y == old.y and points[at].z == old.z
for at in 0..<sizes.length:
unchanged_geometry = unchanged_geometry and sizes[at] == (i64)(old_offsets[at + 1] - old_offsets[at])
for at in 0..<corners.length:
unchanged_geometry = unchanged_geometry and corners[at] == (i64)old_corners[at]
let pp = try narrowed(point_parents)
defer free(pp) in memory.heap
let fp = try narrowed(face_parents)
defer free(fp) in memory.heap
let cp = try narrowed(corner_parents)
defer free(cp) in memory.heap
try self.transfer_attributes(output, pp, fp, cp, unchanged_geometry or preserve_normals)
return result
## Put every attribute of this mesh on `output` through the parent maps
## (empty: unchanged indexing); edge attributes follow `edge_parents_of`.
## An authored N is dropped unless `keep_normals`: after an arbitrary edit
## the derived normals are right and the old ones stale.
func transfer_attributes(output: Mesh*, point_parents: const i32[], face_parents: const i32[], corner_parents: const i32[], keep_normals: bool) -> !:
var edge_map: i32[]
defer:
if edge_map.length > 0: free(edge_map) in memory.heap
for index in 0..<self.attributes.count():
let entry = self.attributes.entry(index)
if entry.name() == "N" and not keep_normals:
continue
if entry.domain == Domain.edge and edge_map.length == 0 and corner_parents.length > 0:
edge_map = try self.edge_parents_of(output, corner_parents)
let parents = point_parents if entry.domain == Domain.point else (corner_parents if entry.domain == Domain.corner else (edge_map if entry.domain == Domain.edge else face_parents))
try output.attributes.put(try attribute_ops.remapped(entry, parents, (try output.domain_size(entry.domain))))
## The old edge each of `output`'s edges continues, or -1 for a new edge.
## An output corner and the next one in its face continue an old edge when
## their parents are neighbors in an old face (in either direction): the
## bottom of an extrusion wall continues its old edge, while the wall's
## sides, whose ends share one parent, are new.
func edge_parents_of(output: const Mesh*, corner_parents: const i32[]) -> i32[]!:
let new_edges = (try output.edge_arrays()).1
let old_edges = (try self.edge_arrays()).1
let old_faces = try self.corner_faces()
let old_offsets = self.offsets.view()
let offsets = output.offsets.view()
let parents = try new i32[(usize)(try output.edge_count())] --- in memory.heap
for at in 0..<parents.length: parents[at] = -1
for face in 0..<offsets.length - 1:
let start = (usize)offsets[face]
let end = (usize)offsets[face + 1]
for corner in start..<end:
let edge = (usize)new_edges[corner]
if parents[edge] >= 0: continue
let a = corner_parents[corner]
let b = corner_parents[corner + 1 if corner + 1 < end else start]
if a < 0 or b < 0 or a == b: continue
let old_face = (usize)old_faces[(usize)a]
if old_face != (usize)old_faces[(usize)b]: continue
let old_start = old_offsets[old_face]
let size = old_offsets[old_face + 1] - old_start
if old_start + (a - old_start + 1) % size == b:
parents[edge] = old_edges[(usize)a]
elif old_start + (b - old_start + 1) % size == a:
parents[edge] = old_edges[(usize)b]
return parents
## Position-only edits keep this mesh's topology, its caches and its
## triangle indices, recomputing moved faces' normals and the bounds. The
## spatial index refits lazily on the first query. Authored normals ("N")
## around the moved points take the new shape's smooth normals; the rest
## keep theirs (normal_refresh.lucb).
pub func with_positions(points: const Vector3[]) -> interop.Reference[Mesh]!:
if points.length != self.positions.count(): error(errors.invalid, "a position edit keeps the point count")
if self.is_precise(): return try self.precise_moved(points, self.origin, false)
let previous = self.positions.view()
var fresh = try Column[Float3].allocate(points.length)
defer fresh.release()
let output = fresh.span()
for at in 0..<points.length:
if not points[at].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
output[at] = Float3.of(points[at].subtract(self.origin))
let moved = try changed_points(previous, output)
defer free(moved) in memory.heap
return try self.repositioned(fresh, self.origin, moved, false)
pub func moved_points(selection: const i64[], delta: Vector3) -> interop.Reference[Mesh]!:
if not delta.is_finite():
error(errors.invalid, "point displacement must be finite")
let count = self.positions.count()
let marked = try new bool[count] --- in memory.heap
defer free(marked) in memory.heap
memory.set(u8[]((u8*)marked.data, count), 0)
var unique: usize = 0
for index in selection:
try checked(index, count)
if not marked[(usize)index]:
marked[(usize)index] = true
unique += 1
if self.is_precise():
# Moved in f64 (a displacement below f32 spacing stays): the f64
# and f32 columns copied, only the marked points written.
var standing = try self.exact_points()
defer standing.release()
var exact = try Column[Vector3].copy_of(standing.view())
defer exact.release()
var positions = self.positions.share()
defer positions.release()
let rounded = try positions.writable()
let world = exact.span()
let changed = try new u32[unique] --- in memory.heap
defer free(changed) in memory.heap
var listed: usize = 0
for point in 0..<count:
if not marked[point]: continue
world[point] = world[point].add(delta)
if not world[point].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
let next = Float3.of(world[point].subtract(self.origin))
if next.x != rounded[point].x or next.y != rounded[point].y or next.z != rounded[point].z:
rounded[point] = next
changed[listed] = (u32)point
listed += 1
return try self.with_precise(&exact, &positions, self.origin, changed[..<listed], false)
var fresh = self.positions.share()
defer fresh.release()
let output = try fresh.writable()
let moved = try new u32[unique] --- in memory.heap
defer free(moved) in memory.heap
var written: usize = 0
for point in 0..<count:
if not marked[point]: continue
let next = Float3.of(output[point].vector().add(delta))
if next.x != output[point].x or next.y != output[point].y or next.z != output[point].z:
output[point] = next
moved[written] = (u32)point
written += 1
return try self.repositioned(fresh, self.origin, moved[..<written], false)
## Whether this mesh differs from `previous` only in its positions and
## its output selection: a verb's moved positions can then be made over
## `previous` (verbs' finish, a drag's last frame).
pub func repositions(previous: const Mesh*) -> bool:
if previous.corners.id() != self.corners.id() or previous.offsets.id() != self.offsets.id() or previous.origin != self.origin: return false
if previous.precise.id() != self.precise.id() or previous.positions.count() != self.positions.count(): return false
var kept: usize = 0
for index in 0..<self.attributes.count():
let entry = self.attributes.entry(index)
if entry.name() == ".selection": continue
let found = previous.attributes.find(entry.name(), entry.domain)
if found < 0: return false
let other = previous.attributes.entry((usize)found)
if other.data.id() != entry.data.id() or other.table.id() != entry.table.id(): return false
kept += 1
var before: usize = 0
for index in 0..<previous.attributes.count():
if previous.attributes.entry(index).name() != ".selection": before += 1
return kept == before
## Share `fresh` (positions relative to `origin`) whose points `moved`
## changed; the caller keeps its own reference. `rigid` promises an orientation-preserving affine map: no
## triangle folds and shading normals stay valid.
func repositioned(fresh: Column[Float3], origin: Vector3, moved: const u32[], rigid: bool) -> interop.Reference[Mesh]!:
# Once filled, the storage belongs to adopt, which disposes it on failure.
return try adopt_storage(try self.repositioned_storage(fresh, origin, moved, rigid))
func repositioned_storage(fresh: Column[Float3], origin: Vector3, moved: const u32[], rigid: bool, keep_normals: bool = false) -> Mesh*!:
var owned = fresh.share()
if moved.length == 0 and origin == self.origin:
owned.release()
return try self.snapshot_storage()
errdefer owned.release()
let incidence = try self.incidence()
let shape = position_edit.Shape(self.positions.view(), owned.view(), origin, self.offsets.view(), self.corners.view(), self.triangles.view(), incidence.0, incidence.1)
# The bounds grow from this mesh's when the origin stays.
let before: Bounds? = self.extent if origin == self.origin else none
var edit = try position_edit.reposition(&shape, self.normals, moved, rigid, before)
errdefer edit.close()
var attributes = try self.attributes.shared()
errdefer attributes.close()
if not rigid and not keep_normals:
let surface = Surface(owned.view(), self.offsets.view(), self.corners.view(), edit.normals.view(), incidence.0, incidence.1)
try refresh_normals(&attributes, &surface, moved)
let reuse_triangles = edit.triangles.is_empty()
let queries = try QueryCache.after(self.queries)
errdefer release_query(queries)
let shading = try ShadingCache.after(self.shading, moved)
errdefer release_shading(shading)
# A precise mesh's f64 points are shared: a moved point's f32
# position is no longer its f64 point's rounding, so it reads as
# that position plus the origin (Mesh.point_at); the rest stay exact.
let storage = try new Mesh[1] --- in memory.heap
storage[0] = self.shared_columns()
# Record provenance: caches keyed on the old positions update in place.
owned.set_parent(self.positions.id())
if moved.length > 0 and moved.length < owned.count():
owned.set_changed((usize)min_of(moved), (usize)max_of(moved) + 1)
storage[0].positions.release()
storage[0].positions = owned
# New positions: the trail (if any) described the old ones.
storage[0].trail.release()
var no_trail: Column[u32]
storage[0].trail = no_trail
storage[0].trail_base = 0
storage[0].trail_of = 0
storage[0].origin = origin
storage[0].normals.release()
storage[0].normals = edit.normals
if not reuse_triangles:
storage[0].triangles.release()
storage[0].triangles = edit.triangles
storage[0].extent = edit.extent
storage[0].attributes = attributes
storage[0].queries = queries
storage[0].shading = shading
_ = self.topology.users.add(1, .relaxed)
return storage.data
## A display mesh: `fresh` positions (relative to this mesh's origin, the
## caller keeping its reference) whose points `moved` changed, with this
## mesh's triangles and every other column shared. Face normals of the
## faces around `moved` are recomputed; a face that collapses keeps a zero
## normal instead of failing (a subdivided limit surface may pinch).
func displayed_storage(fresh: Column[Float3], moved: const u32[]) -> Mesh*!:
var owned = fresh.share()
errdefer owned.release()
let incidence = try self.incidence()
var normals = self.normals.share()
errdefer normals.release()
let output = try normals.writable()
# The faces around the moved points, listed as they are met.
let faces = self.offsets.count() - 1
var touched = try BitsBuilder.zeros(faces)
defer touched.close()
var list = Growing[u32]()
defer list.close()
for point in moved:
for at in (usize)incidence.0[(usize)point]..<(usize)incidence.0[(usize)point + 1]:
let face = (usize)incidence.1[at]
if touched.view().get(face): continue
touched.set(face)
try list.push((u32)face)
var work = DisplayNormals(owned.view(), self.offsets.view(), self.corners.view(), list.view(), output)
try parallel.for_each_range(list.count, 4096, (void*)&work, display_normals)
var attributes = try self.attributes.shared()
errdefer attributes.close()
let queries = try QueryCache.after(self.queries)
errdefer release_query(queries)
let shading = try ShadingCache.after(self.shading, moved)
errdefer release_shading(shading)
# The bounds grow from this mesh's unless a point that held one moved in.
let shape = position_edit.Shape(self.positions.view(), owned.view(), self.origin, self.offsets.view(), self.corners.view(), self.triangles.view(), incidence.0, incidence.1)
let extent = try position_edit.moved_bounds(&shape, moved, self.extent)
let storage = try new Mesh[1] --- in memory.heap
storage[0] = self.shared_columns()
owned.set_parent(self.positions.id())
if moved.length > 0 and moved.length < owned.count():
owned.set_changed((usize)min_of(moved), (usize)max_of(moved) + 1)
storage[0].positions.release()
storage[0].positions = owned
# New positions: the trail (if any) described the old ones.
storage[0].trail.release()
var no_trail: Column[u32]
storage[0].trail = no_trail
storage[0].trail_base = 0
storage[0].trail_of = 0
storage[0].normals.release()
storage[0].normals = normals
storage[0].extent = extent
storage[0].attributes = attributes
storage[0].queries = queries
storage[0].shading = shading
_ = self.topology.users.add(1, .relaxed)
return storage.data
pub func transformed(translation: Vector3, rotation: Vector3, scale: Vector3) -> interop.Reference[Mesh]!:
if not translation.is_finite() or not rotation.is_finite() or not scale.is_finite() or math.abs(scale.x) < 0.000001 or math.abs(scale.y) < 0.000001 or math.abs(scale.z) < 0.000001:
error(errors.invalid, "mesh transform must be finite and nonsingular")
let matrix = Matrix4.compose(translation, rotation, scale)
return try self.placed(matrix)
## Affine placement preserves attributes and inverse-transposes normals.
pub func placed(matrix: Matrix4) -> interop.Reference[Mesh]!:
if not matrix.is_finite() or math.abs(matrix.determinant()) < 0.000000000001:
error(errors.invalid, "mesh placement must be finite and nonsingular")
# Without a reflection, placement is a position-only edit: topology and
# triangles are shared, and no triangle can fold. The origin moves with
# the mesh, so positions only take the linear part.
if matrix.determinant() > 0.0 and self.is_precise():
let points = try self.world_points(matrix)
defer free(points) in memory.heap
let result = try self.precise_moved(points, matrix.transform_point(self.origin), true)
errdefer result.release()
try position_edit.transform_normals(&result.value().attributes, matrix)
return result
if matrix.determinant() > 0.0:
let origin = matrix.transform_point(self.origin)
let previous = self.positions.view()
var fresh = try Column[Float3].allocate(previous.length)
defer fresh.release()
let output = fresh.span()
for at in 0..<previous.length:
output[at] = Float3.of(matrix.transform_direction(previous[at].vector()))
let moved = try new u32[previous.length] --- in memory.heap
defer free(moved) in memory.heap
for at in 0..<moved.length: moved[at] = (u32)at
let placed_mesh = try self.repositioned(fresh, origin, moved, true)
errdefer placed_mesh.release()
try position_edit.transform_normals(&placed_mesh.value().attributes, matrix)
return placed_mesh
# Reversing corners preserves outward normals under a reflection.
let points = try self.world_points(matrix)
defer free(points) in memory.heap
let old_corners = self.corners.view()
let offsets = self.offsets.view()
let faces = offsets.length - 1
let sizes = try new i64[faces] --- in memory.heap
defer free(sizes) in memory.heap
let corners = try new i64[old_corners.length] --- in memory.heap
defer free(corners) in memory.heap
let parents = try new i64[old_corners.length] --- in memory.heap
defer free(parents) in memory.heap
for face in 0..<faces:
let start = (usize)offsets[face]
let count = (usize)offsets[face + 1] - start
sizes[face] = (i64)count
for at in 0..<count:
corners[start + at] = (i64)old_corners[start + count - 1 - at]
parents[start + at] = (i64)(start + count - 1 - at)
var unchanged: i64[]
let old_triangles = self.triangles.view()
let display = try new i64[old_triangles.length] --- in memory.heap
defer free(display) in memory.heap
for triangle in 0..<display.length // 3:
for at in 0..<(usize)3:
let old = (usize)old_triangles[triangle * 3 + (2 - at)]
display[triangle * 3 + at] = parents[old]
let result = try self.remapped(points, sizes, corners, unchanged, unchanged, parents, true, display)
errdefer result.release()
try position_edit.transform_normals(&result.value().attributes, matrix)
return result
## Every point placed by `matrix`, in f64; the caller frees them.
func world_points(matrix: Matrix4) -> Vector3[]!:
let points = try new Vector3[self.positions.count()] --- in memory.heap
for at in 0..<points.length:
points[at] = matrix.transform_point(self.point_at(at))
return points
## A precise mesh over new f64 `points` (world), its f32 positions their
## rounding relative to `origin`: a position edit like any other (the
## topology, its caches and the triangles shared, normals redone around
## the points that moved), with a new f64 column. `rigid` as for
## `repositioned`.
func precise_moved(points: const Vector3[], origin: Vector3, rigid: bool) -> interop.Reference[Mesh]!:
var exact = try Column[Vector3].copy_of(points)
defer exact.release()
var fresh = try Column[Float3].allocate(points.length)
defer fresh.release()
let output = fresh.span()
for at in 0..<points.length:
if not points[at].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
output[at] = Float3.of(points[at].subtract(origin))
var moved: u32[]
if origin == self.origin:
moved = try changed_points(self.positions.view(), output)
else:
moved = try new u32[points.length] --- in memory.heap
for at in 0..<moved.length: moved[at] = (u32)at
defer free(moved) in memory.heap
return try self.with_precise(&exact, &fresh, origin, moved, rigid)
## `fresh` positions (relative to `origin`) whose points `moved` changed,
## over this mesh's topology, with `exact` as the f64 points.
func with_precise(exact: const Column[Vector3]*, fresh: const Column[Float3]*, origin: Vector3, moved: const u32[], rigid: bool) -> interop.Reference[Mesh]!:
let storage = try self.repositioned_storage(*fresh, origin, moved, rigid)
storage.precise.release()
storage.precise = exact.share()
return try adopt_storage(storage)
## This mesh's points and faces, then `other`'s (see concatenated).
pub func merged(other: interop.Reference[Mesh]) -> interop.Reference[Mesh]!:
let parts: MeshPart[2] = [MeshPart(&self, Matrix4()), MeshPart(try other.get(), Matrix4())]
return try concatenated(parts)
## A parent map in i32 (the caller frees it); empty stays empty.
func narrowed(parents: const i64[]) -> i32[]!:
let result = try new i32[parents.length] --- in memory.heap
for at in 0..<parents.length: result[at] = (i32)parents[at]
return result
## The points whose stored positions differ between `previous` and `next`.
## The caller frees the list.
pub func changed_points(previous: const Float3[], next: const Float3[]) -> u32[]!:
# Counted per chunk in parallel, then written per chunk at its offset.
let chunks = (next.length + 65535) // 65536
let counts = try new usize[chunks + 1] --- in memory.heap
defer free(counts) in memory.heap
var none_yet: u32[]
var work = ChangedWork(previous, next, counts, none_yet)
try parallel.for_each_range(chunks, 1, (void*)&work, count_changed)
var total: usize = 0
for chunk in 0..<chunks:
let count = counts[chunk]
counts[chunk] = total
total += count
let moved = try new u32[total] --- in memory.heap
errdefer free(moved) in memory.heap
work.moved = moved
try parallel.for_each_range(chunks, 1, (void*)&work, write_changed)
return moved
struct ChangedWork:
let previous: const Float3[]
let next: const Float3[]
let counts: usize[]
var moved: u32[]
func count_changed(context: void*, first: usize, end: usize, worker: usize):
let work = (ChangedWork*)context
for chunk in first..<end:
let start = chunk * 65536
let stop = start + 65536 if work.next.length - start > 65536 else work.next.length
var count: usize = 0
for at in start..<stop:
let a = work.previous[at]
let b = work.next[at]
if a.x != b.x or a.y != b.y or a.z != b.z: count += 1
work.counts[chunk] = count
func write_changed(context: void*, first: usize, end: usize, worker: usize):
let work = (ChangedWork*)context
for chunk in first..<end:
let start = chunk * 65536
let stop = start + 65536 if work.next.length - start > 65536 else work.next.length
var written = work.counts[chunk]
for at in start..<stop:
let a = work.previous[at]
let b = work.next[at]
if a.x != b.x or a.y != b.y or a.z != b.z:
work.moved[written] = (u32)at
written += 1
func min_of(values: const u32[]) -> u32:
var least = values[0]
for value in values: least = value if value < least else least
return least
func max_of(values: const u32[]) -> u32:
var most = values[0]
for value in values: most = value if value > most else most
return most
struct DisplayNormals:
let positions: const Float3[]
let offsets: const i32[]
let corners: const i32[]
let faces: const u32[]
let normals: Float3[]
func display_normals(context: void*, first: usize, end: usize, worker: usize):
let work = (DisplayNormals*)context
for listed in first..<end:
let face = (usize)work.faces[listed]
let start = (usize)work.offsets[face]
let size = (usize)work.offsets[face + 1] - start
var normal = Vector3()
for at in 0..<size:
let p = work.positions[(usize)work.corners[start + at]].vector()
let q = work.positions[(usize)work.corners[start + (at + 1) % size]].vector()
normal = normal.add(p.cross(q))
let length = normal.length()
work.normals[face] = Float3.of(normal.multiply_scalar(1.0 / length) if length > 0.0 else Vector3())