Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.6

0.7.6 / 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