Luce packages
LuceLuce BaseLuciaOS

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