dymokomi/luce-geocore
Source of release 0.7.5
0.7.5 / src / geometries / dissolve_workspace.lucb
## Bounded local edge dissolves on immutable input. Stable face/edge slots let
## meshing policies inspect neighbors without rebuilding a mesh after each edit.
## `dissolve_edge` is the one-edit form. Both keep the two faces' display
## triangles (the removed edge becomes a display diagonal), which CAD trim
## cells rely on; the Dissolve verb re-triangulates instead.
import memory
import interop
from luce_std import math
import errors
from math.vector import Vector3
from core.polygon_topology import PolygonTopology
from core.growing import grown
from geometries.polygon import Mesh
from geometries.builder import MeshBuilder
from geometries.triangulation.polygon_triangulation import area_normal
import geometries.triangulation.display_triangulation as display_triangles
import geometries.triangulation.face_scratch
struct Face:
let start: usize
let count: usize
let triangle: usize
let parent: i64
var active: bool = true
pub struct DissolveWorkspace: PolygonTopology:
let source: const Mesh*
let points: Vector3[]
let faces: Face[]
## Corner and display storage, grown as joined faces need (see reserve).
var corners: i64[]
var parents: i64[]
var edges: i64[]
var triangles: i64[]
let first: i64[]
let second: i64[]
var nf: usize
var nc: usize
var nt: usize
let manifold: bool
## Borrows source until close; its caller must keep it alive. At most 128
## edits, no input mutation, and no managed owners inside native scratch.
## Room for joined faces of up to 256 corners is made up front; larger
## ones grow the storage.
pub func init(mesh: const Mesh*, edits: usize = 128) -> !:
if edits > 128: error(errors.limit, "dissolve workspace exceeds edit budget")
let nf = (usize)mesh.face_count()
let nc = (usize)mesh.vertex_count()
let nt = (usize)mesh.index_count()
let points = try new Vector3[(usize)mesh.point_count()] --- in memory.heap
errdefer free(points) in memory.heap
let faces = try new Face[nf + edits] --- in memory.heap
errdefer free(faces) in memory.heap
let corners = try new i64[nc + edits * 256] --- in memory.heap
errdefer free(corners) in memory.heap
let parents = try new i64[corners.length] --- in memory.heap
errdefer free(parents) in memory.heap
let edges = try new i64[corners.length] --- in memory.heap
errdefer free(edges) in memory.heap
let triangles = try new i64[nt + edits * 762] --- in memory.heap
errdefer free(triangles) in memory.heap
let first = try new i64[(usize)(try mesh.edge_count())] --- in memory.heap
errdefer free(first) in memory.heap
let second = try new i64[first.length] --- in memory.heap
errdefer free(second) in memory.heap
let forward = try new bool[first.length] --- in memory.heap
defer free(forward) in memory.heap
for at in 0..<first.length:
first[at] = -1
second[at] = -1
for at in 0..<points.length: points[at] = try mesh.point((i64)at)
var manifold = true
for face in 0..<nf:
let start = (usize)(try mesh.face_offset((i64)face))
let count = (usize)(try mesh.face_size((i64)face))
faces[face] = Face(start, count, (start - face * 2) * 3, (i64)face)
for side in 0..<count:
let at = start + side
let point = try mesh.corner_point((i64)at)
let edge = (usize)(try mesh.corner_edge((i64)at))
let direction = point == (try mesh.edge_point((i64)edge, 0))
corners[at] = point
parents[at] = (i64)at
edges[at] = (i64)edge
if first[edge] < 0:
first[edge] = (i64)face
forward[edge] = direction
elif second[edge] == -1:
second[edge] = (i64)face
manifold = manifold and forward[edge] != direction
else:
second[edge] = -2
manifold = false
for at in 0..<nt:
let index = mesh.index((i64)at)
defer index.release()
triangles[at] = try index.get()
self.source = mesh
self.points = points
self.faces = faces
self.corners = corners
self.parents = parents
self.edges = edges
self.triangles = triangles
self.first = first
self.second = second
self.nf = nf
self.nc = nc
self.nt = nt
self.manifold = manifold
## Includes removed slots; scan in order, skipping !active(face).
pub func face_slots() -> i64:
return (i64)self.nf
pub func active(face: i64) -> bool:
return face >= 0 and (usize)face < self.nf and self.faces[(usize)face].active
pub func face_size(face: i64) -> i64!:
if not self.active(face): error(errors.invalid, "inactive dissolve face")
return (i64)self.faces[(usize)face].count
func corner(face: i64, side: i64) -> usize!:
let count = try self.face_size(face)
if side < 0 or side >= count: error(errors.invalid, "dissolve corner out of range")
return self.faces[(usize)face].start + (usize)side
pub func face_point(face: i64, side: i64) -> i64!:
return self.corners[try self.corner(face, side)]
pub func face_edge(face: i64, side: i64) -> i64!:
return self.edges[try self.corner(face, side)]
pub func point_count() -> i64:
return (i64)self.points.length
pub func point(id: i64) -> Vector3!:
if id < 0 or (usize)id >= self.points.length: error(errors.invalid, "dissolve point out of range")
return self.points[(usize)id]
pub func edge_point(edge: i64, side: i64) -> i64!:
return try self.source.edge_point(edge, side)
## The other active face, or -1 for a boundary/nonmanifold edge.
pub func neighbor(face: i64, side: i64) -> i64!:
let edge = (usize)(try self.face_edge(face, side))
if self.first[edge] < 0 or self.second[edge] < 0: return -1
return self.second[edge] if self.first[edge] == face else self.first[edge]
## Join the two faces in their current order, preserving all source display
## triangles and corner provenance. A rejected edit leaves active data intact.
pub func dissolve(edge: i64) -> !:
if edge < 0 or (usize)edge >= self.first.length: error(errors.invalid, "dissolve edge out of range")
if not self.manifold: error(errors.invalid, "Operation needs consistently oriented manifold topology")
let left = self.first[(usize)edge]
let right = self.second[(usize)edge]
if left < 0 or right < 0 or left == right: error(errors.invalid, "Dissolve needs an internal manifold edge")
if self.nf == self.faces.length: error(errors.limit, "dissolve workspace exceeds edit budget")
let a = self.faces[(usize)(left if left < right else right)]
let b = self.faces[(usize)(right if left < right else left)]
let count = a.count + b.count - 2
try self.reserve(count, (count - 2) * 3)
var written: usize = 0
for face in [a, b]:
var side: usize = 0
while side < face.count and self.edges[face.start + side] != edge: side += 1
if side == face.count: error(errors.invalid, "dissolve adjacency lost a corner")
for step in 1..<face.count:
let at = face.start + (side + step) % face.count
self.corners[self.nc + written] = self.corners[at]
self.parents[self.nc + written] = self.parents[at]
self.edges[self.nc + written] = self.edges[at]
written += 1
var triangles: usize = 0
if count <= face_scratch.small_faces():
for at in 0..<count:
for before in 0..<at:
if self.corners[self.nc + at] == self.corners[self.nc + before]: error(errors.invalid, "dissolve requires a simple polygon union")
for face in [a, b]:
for at in 0..<(face.count - 2) * 3:
let point = self.corners[(usize)self.triangles[face.triangle + at]]
var mapped: usize = 0
while mapped < count and self.corners[self.nc + mapped] != point: mapped += 1
if mapped == count: error(errors.invalid, "dissolve lost a source triangle corner")
self.triangles[self.nt + triangles] = (i64)(self.nc + mapped)
triangles += 1
else:
# A large union: the same checks through a hash of its points.
var places = try PointPlaces.of(self.corners[self.nc..<self.nc + count])
defer places.close()
for face in [a, b]:
for at in 0..<(face.count - 2) * 3:
let mapped = places.find(self.corners[(usize)self.triangles[face.triangle + at]])
if mapped < 0: error(errors.invalid, "dissolve lost a source triangle corner")
self.triangles[self.nt + triangles] = (i64)self.nc + mapped
triangles += 1
# Match Mesh's validation for the changed face only. Every other
# face was already validated; the full output is validated again at finish.
let origin = self.points[(usize)self.corners[self.nc]]
var normal = Vector3()
var extent: f64 = 0.0
for at in 0..<count:
let p = self.points[(usize)self.corners[self.nc + at]].subtract(origin)
let q = self.points[(usize)self.corners[self.nc + (at + 1) % count]].subtract(origin)
normal = normal.add(p.cross(q))
extent = math.max(extent, p.dot(p))
_ = try area_normal(normal, extent)
try display_triangles.validate(self.points, self.corners, self.nc, count, self.triangles[self.nt..<self.nt + triangles])
self.faces[self.nf] = Face(self.nc, count, self.nt, a.parent)
self.faces[(usize)left].active = false
self.faces[(usize)right].active = false
for at in 0..<count:
let id = (usize)self.edges[self.nc + at]
if self.first[id] == left or self.first[id] == right: self.first[id] = (i64)self.nf
if self.second[id] == left or self.second[id] == right: self.second[id] = (i64)self.nf
self.first[(usize)edge] = -1
self.second[(usize)edge] = -1
self.nf += 1
self.nc += count
self.nt += triangles
## Materialize once in the same order as sequential immutable dissolves.
pub func finish() -> interop.Reference[Mesh]!:
var out = try MeshBuilder()
defer out.close()
try out.copy_points(self.source)
var stack: i64[762] = ---
for face in self.faces[..<self.nf]:
if not face.active: continue
try out.face((i64)face.count, face.parent)
for at in face.start..<face.start + face.count: try out.corner(self.corners[at], self.parents[at])
let count = (face.count - 2) * 3
let display = try face_scratch.take[i64](stack, face.count, count)
defer face_scratch.release[i64](stack, display)
for at in 0..<count: display[at] = self.triangles[face.triangle + at] - (i64)face.start
try out.set_last_display(display)
return try out.finish(self.source)
## Room for `corners` more corners and `indices` more display indices.
## A failure leaves every stored value as it was.
func reserve(corners: usize, indices: usize) -> !:
self.corners = try grown[i64](self.corners, self.nc, self.nc + corners)
self.parents = try grown[i64](self.parents, self.nc, self.nc + corners)
self.edges = try grown[i64](self.edges, self.nc, self.nc + corners)
self.triangles = try grown[i64](self.triangles, self.nt, self.nt + indices)
pub func close():
free(self.points) in memory.heap
free(self.faces) in memory.heap
free(self.corners) in memory.heap
free(self.parents) in memory.heap
free(self.edges) in memory.heap
free(self.triangles) in memory.heap
free(self.first) in memory.heap
free(self.second) in memory.heap
## The places of a large joined face's points, hashed (open addressing):
## rejects a point twice (the union pinches) and finds a point's corner.
struct PointPlaces:
var keys: i64[]
var places: i64[]
static func of(points: const i64[]) -> PointPlaces!:
var capacity: usize = 16
while capacity < points.length * 2: capacity *= 2
let keys = try new i64[capacity] --- in memory.heap
errdefer free(keys) in memory.heap
let places = try new i64[capacity] --- in memory.heap
errdefer free(places) in memory.heap
for at in 0..<capacity: keys[at] = -1
for at in 0..<points.length:
var slot = PointPlaces.slot_of(points[at], capacity)
while keys[slot] >= 0:
if keys[slot] == points[at]: error(errors.invalid, "dissolve requires a simple polygon union")
slot = (slot + 1) & (capacity - 1)
keys[slot] = points[at]
places[slot] = (i64)at
return PointPlaces(keys, places)
static func slot_of(point: i64, capacity: usize) -> usize:
return (usize)(((u64)point *% 0x9E3779B97F4A7C15) >> 32) & (capacity - 1)
## The corner of `point` in the face, or -1.
func find(point: i64) -> i64:
var slot = PointPlaces.slot_of(point, self.keys.length)
while self.keys[slot] >= 0:
if self.keys[slot] == point: return self.places[slot]
slot = (slot + 1) & (self.keys.length - 1)
return -1
func close():
free(self.keys) in memory.heap
free(self.places) in memory.heap
## `source` with interior edge `edge` dissolved: its two faces joined, their
## display triangles kept. Rejected (invalid) for a boundary, nonmanifold or
## pinching edge.
pub func dissolve_edge(source: const Mesh*, edge: i64) -> interop.Reference[Mesh]!:
var work = try DissolveWorkspace(source, 1)
defer work.close()
try work.dissolve(edge)
return try work.finish()