dymokomi/luce-geocore
Source of release 0.7.3
0.7.3 / src / geometries / position_edit.lucb
## Position-only edits: new positions over unchanged polygon topology. Only
## the faces around moved points get new normals and a fold check; the
## topology, its caches, the attributes and (unless a face folded) the
## triangles are shared with the previous mesh. CAD cut-cell n-gons carry
## support-chart triangles that ear clipping in an average plane cannot
## reproduce, which is why triangles are kept rather than recomputed.
from luce_std import math
import memory
import errors
from luce_std import parallel
from core.geometry import Bounds
from core.float3 import Float3
from core.shared import Column
from core.attributes import AttributeStore, DataType, Role, Storage
from core.attribute_ops import typed_mut
from math.vector import Vector3
from math.matrix import Matrix4
from geometries.triangulation.polygon_triangulation import triangulate, is_degenerate
import geometries.triangulation.face_scratch
from splats import LinearPart, turn_rotations
## Owned columns for the new mesh. `triangles` is empty when the previous
## triangles remain valid and are shared.
pub struct Repositioned:
pub var normals: Column[Float3]
pub var triangles: Column[i32]
pub var extent: Bounds
pub func close():
self.normals.release()
self.triangles.release()
## The arrays a position edit reads.
pub struct Shape:
pub let previous: const Float3[]
pub let positions: const Float3[]
pub let origin: Vector3
pub let offsets: const i32[]
pub let corners: const i32[]
pub let triangles: const i32[]
## Point to face incidence (offsets into faces).
pub let incident_offsets: const i32[]
pub let incident_faces: const i32[]
## Finite and bounded to 1e6 like construction, in parallel: the bounds of
## `positions` placed at `origin`.
pub func bounds_of(positions: const Float3[], origin: Vector3) -> Bounds!:
if positions.length == 0: return Bounds(origin, origin)
let chunks = (positions.length + 65535) // 65536
let results = try new Extent[chunks] --- in memory.heap
defer free(results) in memory.heap
var work = ExtentWork(positions, results)
try parallel.for_each_range(chunks, 1, (void*)&work, chunk_extent)
var lo = results[0].lo
var hi = results[0].hi
var finite = true
for result in results:
finite = finite and result.finite
lo = Vector3(math.min(lo.x, result.lo.x), math.min(lo.y, result.lo.y), math.min(lo.z, result.lo.z))
hi = Vector3(math.max(hi.x, result.hi.x), math.max(hi.y, result.hi.y), math.max(hi.z, result.hi.z))
let minimum = lo.add(origin)
let maximum = hi.add(origin)
if not finite or math.max(math.abs(minimum.x), math.abs(maximum.x)) > 1000000.0 or math.max(math.abs(minimum.y), math.abs(maximum.y)) > 1000000.0 or math.max(math.abs(minimum.z), math.abs(maximum.z)) > 1000000.0:
error(errors.invalid, "mesh points must be finite and bounded to 1e6")
return Bounds(minimum, maximum)
struct Extent:
var lo: Vector3
var hi: Vector3
var finite: bool
struct ExtentWork:
let positions: const Float3[]
let results: Extent[]
func chunk_extent(context: void*, first: usize, end: usize, worker: usize):
let work = (ExtentWork*)context
for chunk in first..<end:
let start = chunk * 65536
let stop = start + 65536 if work.positions.length - start > 65536 else work.positions.length
var lo = work.positions[start]
var hi = lo
var finite = true
for at in start..<stop:
let p = work.positions[at]
finite = finite and p.x - p.x == 0.0 and p.y - p.y == 0.0 and p.z - p.z == 0.0
lo = Float3(p.x if p.x < lo.x else lo.x, p.y if p.y < lo.y else lo.y, p.z if p.z < lo.z else lo.z)
hi = Float3(p.x if p.x > hi.x else hi.x, p.y if p.y > hi.y else hi.y, p.z if p.z > hi.z else hi.z)
work.results[chunk] = Extent(lo.vector(), hi.vector(), finite)
## New normals, bounds and (when a face folded) triangles for `shape`, whose
## points `moved` changed. `rigid` promises an orientation-preserving affine
## map, under which no triangle can fold.
pub func reposition(shape: const Shape*, normals: Column[Float3], moved: const u32[], rigid: bool) -> Repositioned!:
let extent = try bounds_of(shape.positions, shape.origin)
let faces = shape.offsets.length - 1
# Every point moved: every face gets a new normal, into a fresh column (nothing of
# the old one survives, so nothing is copied) with no face list to build.
let every = moved.length == shape.positions.length
var list: u32[]
if not every:
list = try touched_faces(shape, moved, faces)
defer:
if not every: free(list) in memory.heap
var fresh: Column[Float3]
if every:
fresh = try Column[Float3].allocate(faces)
else:
fresh = normals.share()
errdefer fresh.release()
let output = fresh.span() if every else try fresh.writable()
var work = NormalWork(shape, list, every, normals.view(), output, rigid)
try parallel.for_each_range(faces if every else list.length, 2048, (void*)&work, face_normals)
var triangles: Column[i32]
errdefer triangles.release()
if work.folded.load(.acquire) != 0:
triangles = try Column[i32].copy_of(shape.triangles)
let copy = triangles.span()
for at in 0..<(faces if every else list.length):
let face = at if every else (usize)list[at]
try retriangulate(shape, face, output[face].vector(), copy)
return Repositioned(fresh, triangles, extent)
## The faces around the `moved` points, ascending.
func touched_faces(shape: const Shape*, moved: const u32[], faces: usize) -> u32[]!:
let touched = try new bool[faces] --- in memory.heap
defer free(touched) in memory.heap
memory.set(u8[]((u8*)touched.data, touched.length), 0)
var count: usize = 0
for point in moved:
for at in (usize)shape.incident_offsets[(usize)point]..<(usize)shape.incident_offsets[(usize)point + 1]:
let face = (usize)shape.incident_faces[at]
if not touched[face]:
touched[face] = true
count += 1
let list = try new u32[count] --- in memory.heap
var written: usize = 0
for face in 0..<faces:
if touched[face]:
list[written] = (u32)face
written += 1
return list
struct NormalWork:
let shape: const Shape*
## The faces to redo, or every face (`every`).
let list: const u32[]
let every: bool
let previous: const Float3[]
let normals: Float3[]
let rigid: bool
## Whether any triangle folded.
var folded: @u32
func face_normals(context: void*, first: usize, end: usize, worker: usize):
let work = (NormalWork*)context
for at in first..<end:
let face = at if work.every else (usize)work.list[at]
if let normal = quick_normal(work.shape, face):
work.normals[face] = normal
else:
# A face without an area is legal (its points met): a zero normal, and its
# display triangles become a fan if they folded.
work.normals[face] = Float3()
if not work.rigid and folded(work.shape, face): work.folded.store(1, .relaxed)
continue
if not work.rigid and folded(work.shape, face):
work.folded.store(1, .relaxed)
## The face's unit area normal from its positions, or none for a face without an area.
## Points are read as `Float3` values, which stay in registers.
func quick_normal(shape: const Shape*, face: usize) -> Float3?:
let start = (usize)shape.offsets[face]
let count = (usize)shape.offsets[face + 1] - start
let corners = shape.corners[start..<start + count]
let positions = shape.positions
let o = positions[(usize)corners[0]]
let ox = (f64)o.x
let oy = (f64)o.y
let oz = (f64)o.z
var ax: f64 = 0.0
var ay: f64 = 0.0
var az: f64 = 0.0
var extent2: f64 = 0.0
var dx: f64 = 0.0
var dy: f64 = 0.0
var dz: f64 = 0.0
for at in 0..<count:
let next = positions[(usize)corners[at + 1 if at + 1 < count else 0]]
let ex = (f64)next.x - ox
let ey = (f64)next.y - oy
let ez = (f64)next.z - oz
extent2 = math.max(extent2, dx * dx + dy * dy + dz * dz)
ax = ax + (dy * ez - dz * ey)
ay = ay + (dz * ex - dx * ez)
az = az + (dx * ey - dy * ex)
dx = ex
dy = ey
dz = ez
let length = math.sqrt(ax * ax + ay * ay + az * az)
if not math.is_finite(length) or not math.is_finite(extent2) or length <= math.max(1e-30, extent2 * 1e-14):
return none
let scale = 1.0 / length
return Float3((f32)(ax * scale), (f32)(ay * scale), (f32)(az * scale))
## A kept triangle folds when it degenerates or turns against its old facing
## (lengths compared squared).
func folded(shape: const Shape*, face: usize) -> bool:
let start = (usize)shape.offsets[face]
let count = (usize)shape.offsets[face + 1] - start
let first = (start - face * 2) * 3
let before = shape.previous
let after = shape.positions
let triangles = shape.triangles[first..<first + (count - 2) * 3]
for at in 0..<count - 2:
let a = (usize)shape.corners[(usize)triangles[at * 3]]
let b = (usize)shape.corners[(usize)triangles[at * 3 + 1]]
let c = (usize)shape.corners[(usize)triangles[at * 3 + 2]]
let pa = before[a]
let pb = before[b]
let pc = before[c]
let qa = after[a]
let qb = after[b]
let qc = after[c]
let bx = (f64)pb.x - (f64)pa.x
let by = (f64)pb.y - (f64)pa.y
let bz = (f64)pb.z - (f64)pa.z
let cx = (f64)pc.x - (f64)pa.x
let cy = (f64)pc.y - (f64)pa.y
let cz = (f64)pc.z - (f64)pa.z
let ux = (f64)qb.x - (f64)qa.x
let uy = (f64)qb.y - (f64)qa.y
let uz = (f64)qb.z - (f64)qa.z
let vx = (f64)qc.x - (f64)qa.x
let vy = (f64)qc.y - (f64)qa.y
let vz = (f64)qc.z - (f64)qa.z
let wx = uy * vz - uz * vy
let wy = uz * vx - ux * vz
let wz = ux * vy - uy * vx
let facing = (by * cz - bz * cy) * wx + (bz * cx - bx * cz) * wy + (bx * cy - by * cx) * wz
let limit = math.max(1e-30, math.max(ux * ux + uy * uy + uz * uz, vx * vx + vy * vy + vz * vz) * 1e-14)
if wx * wx + wy * wy + wz * wz <= limit * limit or facing <= 0.0:
return true
return false
## Re-triangulate a folded face in place (triangulation never refuses a
## face: a folded one is finished as a fan). Only running out of memory fails.
func retriangulate(shape: const Shape*, face: usize, normal: Vector3, triangles: i32[]) -> !:
if not folded(shape, face): return
let start = (usize)shape.offsets[face]
let count = (usize)shape.offsets[face + 1] - start
let size = (count - 2) * 3
# Small faces work on the stack, larger ones in heap scratch.
var point_stack: Vector3[256] = ---
var index_stack: i64[256] = ---
var output_stack: i64[762] = ---
let points = try face_scratch.take[Vector3](point_stack, count, count)
defer face_scratch.release[Vector3](point_stack, points)
let indices = try face_scratch.take[i64](index_stack, count, count)
defer face_scratch.release[i64](index_stack, indices)
let output = try face_scratch.take[i64](output_stack, count, size)
defer face_scratch.release[i64](output_stack, output)
for at in 0..<count:
points[at] = shape.positions[(usize)shape.corners[start + at]].vector()
indices[at] = (i64)at
try triangulate(points, indices, 0, count, normal, output)
let first = (start - face * 2) * 3
for at in 0..<size: triangles[first + at] = (i32)((i64)start + output[at])
## Shading normals follow an affine placement by the inverse transpose, and
## rotations (Role.rotation, such as `orient`) turn by its polar rotation.
## The columns are written copy-on-write, so snapshots sharing them keep
## theirs.
pub func transform_normals(attributes: AttributeStore*, matrix: Matrix4) -> !:
for index in 0..<attributes.count():
let entry = attributes.entry(index)
if entry.width == 4 and entry.role == Role.rotation and entry.storage == Storage.array and (entry.kind == DataType.float32 or entry.kind == DataType.float64):
let kind = entry.kind
let tuples = entry.elements
turn_rotations(try attributes.writable(index), kind, tuples, LinearPart.of(matrix).rotation)
continue
if entry.name() != "N" or entry.width != 3 or (entry.kind != DataType.float64 and entry.kind != DataType.float32):
continue
let wide = entry.kind == DataType.float64
let bytes = try attributes.writable(index)
let count = bytes.length // (24 if wide else 12)
for at in 0..<count:
var n = Vector3()
if wide:
let values = typed_mut[f64](bytes)
n = Vector3(values[at * 3], values[at * 3 + 1], values[at * 3 + 2])
else:
let values = typed_mut[f32](bytes)
n = Vector3((f64)values[at * 3], (f64)values[at * 3 + 1], (f64)values[at * 3 + 2])
if n.length() <= 0.000000001:
continue
let transformed = try matrix.transform_normal(n)
if wide:
let values = typed_mut[f64](bytes)
values[at * 3] = transformed.x
values[at * 3 + 1] = transformed.y
values[at * 3 + 2] = transformed.z
else:
let values = typed_mut[f32](bytes)
values[at * 3] = (f32)transformed.x
values[at * 3 + 1] = (f32)transformed.y
values[at * 3 + 2] = (f32)transformed.z