dymokomi/luce-geocore
Source of release 0.7.1
0.7.1 / 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
import core.parallel
from core.geometry import Bounds
from core.float3 import Float3
from core.shared import Column
from core.attributes import AttributeStore, DataType
from core.attribute_ops import typed_mut
from math.vector import Vector3
from math.matrix import Matrix4
from geometries.polygon_triangulation import triangulate, area_normal, is_degenerate
import geometries.face_scratch
## 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)
parallel.parallel_for(chunks, 1, chunk_extent, (void*)&work)
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):
let work = (ExtentWork*)(context else return)
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
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
defer free(list) in memory.heap
var written: usize = 0
for face in 0..<faces:
if touched[face]:
list[written] = (u32)face
written += 1
var fresh = normals.share()
errdefer fresh.release()
let output = try fresh.writable()
var work = NormalWork(shape, list, output, rigid)
parallel.parallel_for(list.length, 2048, face_normals, (void*)&work)
if work.failed.load(.acquire) != 0:
# A serial pass reports the first failing face's own error.
for face in list:
if not is_degenerate(output[(usize)face].vector()): _ = try face_normal(shape, (usize)face)
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 face in list:
try retriangulate(shape, (usize)face, output[(usize)face].vector(), copy)
return Repositioned(fresh, triangles, extent)
struct NormalWork:
let shape: const Shape*
let list: const u32[]
let normals: Float3[]
let rigid: bool
## Whether any face's normal failed, and whether any triangle folded.
var failed: @u32
var folded: @u32
func face_normals(context: void*?, first: usize, end: usize):
let work = (NormalWork*)(context else return)
for at in first..<end:
let face = (usize)work.list[at]
let normal = face_normal(work.shape, face) catch failure:
_ = failure
# A face that had no area keeps its zero normal; one that
# collapses now fails the edit.
if not is_degenerate(work.normals[face].vector()): work.failed.store(1, .relaxed)
continue
work.normals[face] = Float3.of(normal)
if not work.rigid and folded(work.shape, face):
work.folded.store(1, .relaxed)
## The unit area normal of `face` from the new positions.
pub func face_normal(shape: const Shape*, face: usize) -> Vector3!:
let start = (usize)shape.offsets[face]
let count = (usize)shape.offsets[face + 1] - start
let origin = shape.positions[(usize)shape.corners[start]].vector()
var area = Vector3()
var extent2: f64 = 0.0
for at in 0..<count:
let delta = shape.positions[(usize)shape.corners[start + at]].vector().subtract(origin)
extent2 = math.max(extent2, delta.dot(delta))
area = area.add(delta.cross(shape.positions[(usize)shape.corners[start + (at + 1) % count]].vector().subtract(origin)))
return try area_normal(area, extent2)
## A kept triangle folds when it degenerates or turns against its old facing.
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
for at in 0..<count - 2:
let a = (usize)shape.corners[(usize)shape.triangles[first + at * 3]]
let b = (usize)shape.corners[(usize)shape.triangles[first + at * 3 + 1]]
let c = (usize)shape.corners[(usize)shape.triangles[first + at * 3 + 2]]
let pa = shape.previous[a].vector()
let before = shape.previous[b].vector().subtract(pa).cross(shape.previous[c].vector().subtract(pa))
let na = shape.positions[a].vector()
let ab = shape.positions[b].vector().subtract(na)
let ac = shape.positions[c].vector().subtract(na)
let after = ab.cross(ac)
if after.length() <= math.max(1e-30, math.max(ab.dot(ab), ac.dot(ac)) * 1e-14) or after.dot(before) <= 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. The
## N 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.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