Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / geometries / polygon / edits.lucb

## Operators that publish new meshes: remapping through parent maps, position
## edits, placement and merging. Position edits copy the positions once, share
## the topology, its caches, the triangles and every attribute, recompute only
## the faces around moved points, and refit the spatial index.

extend Mesh:
    ## All operators publish new meshes. Parent maps are output-to-input indices;
    ## -1 means a genuinely new element (zero-valued attributes). Empty maps mean
    ## unchanged indexing, valid only when domain cardinality is unchanged. Edge
    ## attributes follow their corners. The result is precise when this mesh
    ## is, or when `precise` asks.
    pub func remapped(points: const Vector3[], sizes: const i64[], corners: const i64[],
                      point_parents: const i64[], face_parents: const i64[], corner_parents: const i64[], preserve_normals: bool = false, display: const i64[]? = none, precise: bool = false) -> interop.Reference[Mesh]!:
        try validate_map(point_parents, points.length, self.positions.count())
        try validate_map(face_parents, sizes.length, self.offsets.count() - 1)
        try validate_map(corner_parents, corners.length, self.corners.count())
        let result = try make_mesh(points, sizes, corners, display, precise or self.is_precise())
        errdefer result.release()
        let output = result.value()
        var unchanged_geometry = points.length == self.positions.count() and sizes.length == self.offsets.count() - 1 and corners.length == self.corners.count()
        if unchanged_geometry and not preserve_normals:
            let old_offsets = self.offsets.view()
            let old_corners = self.corners.view()
            for at in 0..<points.length:
                let old = self.point_at(at)
                unchanged_geometry = unchanged_geometry and points[at].x == old.x and points[at].y == old.y and points[at].z == old.z
            for at in 0..<sizes.length:
                unchanged_geometry = unchanged_geometry and sizes[at] == (i64)(old_offsets[at + 1] - old_offsets[at])
            for at in 0..<corners.length:
                unchanged_geometry = unchanged_geometry and corners[at] == (i64)old_corners[at]
        let pp = try narrowed(point_parents)
        defer free(pp) in memory.heap
        let fp = try narrowed(face_parents)
        defer free(fp) in memory.heap
        let cp = try narrowed(corner_parents)
        defer free(cp) in memory.heap
        try self.transfer_attributes(output, pp, fp, cp, unchanged_geometry or preserve_normals)
        return result

    ## Put every attribute of this mesh on `output` through the parent maps
    ## (empty: unchanged indexing); edge attributes follow `edge_parents_of`.
    ## An authored N is dropped unless `keep_normals`: after an arbitrary edit
    ## the derived normals are right and the old ones stale.
    func transfer_attributes(output: Mesh*, point_parents: const i32[], face_parents: const i32[], corner_parents: const i32[], keep_normals: bool) -> !:
        var edge_map: i32[]
        defer:
            if edge_map.length > 0: free(edge_map) in memory.heap
        for index in 0..<self.attributes.count():
            let entry = self.attributes.entry(index)
            if entry.name() == "N" and not keep_normals:
                continue
            if entry.domain == Domain.edge and edge_map.length == 0 and corner_parents.length > 0:
                edge_map = try self.edge_parents_of(output, corner_parents)
            let parents = point_parents if entry.domain == Domain.point else (corner_parents if entry.domain == Domain.corner else (edge_map if entry.domain == Domain.edge else face_parents))
            try output.attributes.put(try attribute_ops.remapped(entry, parents, (try output.domain_size(entry.domain))))

    ## The old edge each of `output`'s edges continues, or -1 for a new edge.
    ## An output corner and the next one in its face continue an old edge when
    ## their parents are neighbors in an old face (in either direction): the
    ## bottom of an extrusion wall continues its old edge, while the wall's
    ## sides, whose ends share one parent, are new.
    func edge_parents_of(output: const Mesh*, corner_parents: const i32[]) -> i32[]!:
        let new_edges = (try output.edge_arrays()).1
        let old_edges = (try self.edge_arrays()).1
        let old_faces = try self.corner_faces()
        let old_offsets = self.offsets.view()
        let offsets = output.offsets.view()
        let parents = try new i32[(usize)(try output.edge_count())] --- in memory.heap
        for at in 0..<parents.length: parents[at] = -1
        for face in 0..<offsets.length - 1:
            let start = (usize)offsets[face]
            let end = (usize)offsets[face + 1]
            for corner in start..<end:
                let edge = (usize)new_edges[corner]
                if parents[edge] >= 0: continue
                let a = corner_parents[corner]
                let b = corner_parents[corner + 1 if corner + 1 < end else start]
                if a < 0 or b < 0 or a == b: continue
                let old_face = (usize)old_faces[(usize)a]
                if old_face != (usize)old_faces[(usize)b]: continue
                let old_start = old_offsets[old_face]
                let size = old_offsets[old_face + 1] - old_start
                if old_start + (a - old_start + 1) % size == b:
                    parents[edge] = old_edges[(usize)a]
                elif old_start + (b - old_start + 1) % size == a:
                    parents[edge] = old_edges[(usize)b]
        return parents

    ## Position-only edits keep this mesh's topology, its caches and its
    ## triangle indices, recomputing moved faces' normals and the bounds. The
    ## spatial index refits lazily on the first query. Authored normals ("N")
    ## around the moved points take the new shape's smooth normals; the rest
    ## keep theirs (normal_refresh.lucb).
    pub func with_positions(points: const Vector3[]) -> interop.Reference[Mesh]!:
        if points.length != self.positions.count(): error(errors.invalid, "a position edit keeps the point count")
        if self.is_precise(): return try self.precise_moved(points, self.origin, false)
        let previous = self.positions.view()
        var fresh = try Column[Float3].allocate(points.length)
        defer fresh.release()
        let output = fresh.span()
        for at in 0..<points.length:
            if not points[at].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
            output[at] = Float3.of(points[at].subtract(self.origin))
        let moved = try changed_points(previous, output)
        defer free(moved) in memory.heap
        return try self.repositioned(fresh, self.origin, moved, false)

    pub func moved_points(selection: const i64[], delta: Vector3) -> interop.Reference[Mesh]!:
        if not delta.is_finite():
            error(errors.invalid, "point displacement must be finite")
        let count = self.positions.count()
        let marked = try new bool[count] --- in memory.heap
        defer free(marked) in memory.heap
        memory.set(u8[]((u8*)marked.data, count), 0)
        var unique: usize = 0
        for index in selection:
            try checked(index, count)
            if not marked[(usize)index]:
                marked[(usize)index] = true
                unique += 1
        if self.is_precise():
            # Moved in f64 (a displacement below f32 spacing stays): the f64
            # and f32 columns copied, only the marked points written.
            var standing = try self.exact_points()
            defer standing.release()
            var exact = try Column[Vector3].copy_of(standing.view())
            defer exact.release()
            var positions = self.positions.share()
            defer positions.release()
            let rounded = try positions.writable()
            let world = exact.span()
            let changed = try new u32[unique] --- in memory.heap
            defer free(changed) in memory.heap
            var listed: usize = 0
            for point in 0..<count:
                if not marked[point]: continue
                world[point] = world[point].add(delta)
                if not world[point].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
                let next = Float3.of(world[point].subtract(self.origin))
                if next.x != rounded[point].x or next.y != rounded[point].y or next.z != rounded[point].z:
                    rounded[point] = next
                    changed[listed] = (u32)point
                    listed += 1
            return try self.with_precise(&exact, &positions, self.origin, changed[..<listed], false)
        var fresh = self.positions.share()
        defer fresh.release()
        let output = try fresh.writable()
        let moved = try new u32[unique] --- in memory.heap
        defer free(moved) in memory.heap
        var written: usize = 0
        for point in 0..<count:
            if not marked[point]: continue
            let next = Float3.of(output[point].vector().add(delta))
            if next.x != output[point].x or next.y != output[point].y or next.z != output[point].z:
                output[point] = next
                moved[written] = (u32)point
                written += 1
        return try self.repositioned(fresh, self.origin, moved[..<written], false)

    ## Whether this mesh differs from `previous` only in its positions and
    ## its output selection: a verb's moved positions can then be made over
    ## `previous` (verbs' finish, a drag's last frame).
    pub func repositions(previous: const Mesh*) -> bool:
        if previous.corners.id() != self.corners.id() or previous.offsets.id() != self.offsets.id() or previous.origin != self.origin: return false
        if previous.precise.id() != self.precise.id() or previous.positions.count() != self.positions.count(): return false
        var kept: usize = 0
        for index in 0..<self.attributes.count():
            let entry = self.attributes.entry(index)
            if entry.name() == ".selection": continue
            let found = previous.attributes.find(entry.name(), entry.domain)
            if found < 0: return false
            let other = previous.attributes.entry((usize)found)
            if other.data.id() != entry.data.id() or other.table.id() != entry.table.id(): return false
            kept += 1
        var before: usize = 0
        for index in 0..<previous.attributes.count():
            if previous.attributes.entry(index).name() != ".selection": before += 1
        return kept == before

    ## Share `fresh` (positions relative to `origin`) whose points `moved`
    ## changed; the caller keeps its own reference. `rigid` promises an orientation-preserving affine map: no
    ## triangle folds and shading normals stay valid.
    func repositioned(fresh: Column[Float3], origin: Vector3, moved: const u32[], rigid: bool) -> interop.Reference[Mesh]!:
        # Once filled, the storage belongs to adopt, which disposes it on failure.
        return try adopt_storage(try self.repositioned_storage(fresh, origin, moved, rigid))

    func repositioned_storage(fresh: Column[Float3], origin: Vector3, moved: const u32[], rigid: bool, keep_normals: bool = false) -> Mesh*!:
        var owned = fresh.share()
        if moved.length == 0 and origin == self.origin:
            owned.release()
            return try self.snapshot_storage()
        errdefer owned.release()
        let incidence = try self.incidence()
        let shape = position_edit.Shape(self.positions.view(), owned.view(), origin, self.offsets.view(), self.corners.view(), self.triangles.view(), incidence.0, incidence.1)
        # The bounds grow from this mesh's when the origin stays.
        let before: Bounds? = self.extent if origin == self.origin else none
        var edit = try position_edit.reposition(&shape, self.normals, moved, rigid, before)
        errdefer edit.close()
        var attributes = try self.attributes.shared()
        errdefer attributes.close()
        if not rigid and not keep_normals:
            let surface = Surface(owned.view(), self.offsets.view(), self.corners.view(), edit.normals.view(), incidence.0, incidence.1)
            try refresh_normals(&attributes, &surface, moved)
        let reuse_triangles = edit.triangles.is_empty()
        let queries = try QueryCache.after(self.queries)
        errdefer release_query(queries)
        let shading = try ShadingCache.after(self.shading, moved)
        errdefer release_shading(shading)
        # A precise mesh's f64 points are shared: a moved point's f32
        # position is no longer its f64 point's rounding, so it reads as
        # that position plus the origin (Mesh.point_at); the rest stay exact.
        let storage = try new Mesh[1] --- in memory.heap
        storage[0] = self.shared_columns()
        # Record provenance: caches keyed on the old positions update in place.
        owned.set_parent(self.positions.id())
        if moved.length > 0 and moved.length < owned.count():
            owned.set_changed((usize)min_of(moved), (usize)max_of(moved) + 1)
        storage[0].positions.release()
        storage[0].positions = owned
        # New positions: the trail (if any) described the old ones.
        storage[0].trail.release()
        var no_trail: Column[u32]
        storage[0].trail = no_trail
        storage[0].trail_base = 0
        storage[0].trail_of = 0
        storage[0].origin = origin
        storage[0].normals.release()
        storage[0].normals = edit.normals
        if not reuse_triangles:
            storage[0].triangles.release()
            storage[0].triangles = edit.triangles
        storage[0].extent = edit.extent
        storage[0].attributes = attributes
        storage[0].queries = queries
        storage[0].shading = shading
        _ = self.topology.users.add(1, .relaxed)
        return storage.data

    ## A display mesh: `fresh` positions (relative to this mesh's origin, the
    ## caller keeping its reference) whose points `moved` changed, with this
    ## mesh's triangles and every other column shared. Face normals of the
    ## faces around `moved` are recomputed; a face that collapses keeps a zero
    ## normal instead of failing (a subdivided limit surface may pinch).
    func displayed_storage(fresh: Column[Float3], moved: const u32[]) -> Mesh*!:
        var owned = fresh.share()
        errdefer owned.release()
        let incidence = try self.incidence()
        var normals = self.normals.share()
        errdefer normals.release()
        let output = try normals.writable()
        # The faces around the moved points, listed as they are met.
        let faces = self.offsets.count() - 1
        var touched = try BitsBuilder.zeros(faces)
        defer touched.close()
        var list = Growing[u32]()
        defer list.close()
        for point in moved:
            for at in (usize)incidence.0[(usize)point]..<(usize)incidence.0[(usize)point + 1]:
                let face = (usize)incidence.1[at]
                if touched.view().get(face): continue
                touched.set(face)
                try list.push((u32)face)
        var work = DisplayNormals(owned.view(), self.offsets.view(), self.corners.view(), list.view(), output)
        try parallel.for_each_range(list.count, 4096, (void*)&work, display_normals)
        var attributes = try self.attributes.shared()
        errdefer attributes.close()
        let queries = try QueryCache.after(self.queries)
        errdefer release_query(queries)
        let shading = try ShadingCache.after(self.shading, moved)
        errdefer release_shading(shading)
        # The bounds grow from this mesh's unless a point that held one moved in.
        let shape = position_edit.Shape(self.positions.view(), owned.view(), self.origin, self.offsets.view(), self.corners.view(), self.triangles.view(), incidence.0, incidence.1)
        let extent = try position_edit.moved_bounds(&shape, moved, self.extent)
        let storage = try new Mesh[1] --- in memory.heap
        storage[0] = self.shared_columns()
        owned.set_parent(self.positions.id())
        if moved.length > 0 and moved.length < owned.count():
            owned.set_changed((usize)min_of(moved), (usize)max_of(moved) + 1)
        storage[0].positions.release()
        storage[0].positions = owned
        # New positions: the trail (if any) described the old ones.
        storage[0].trail.release()
        var no_trail: Column[u32]
        storage[0].trail = no_trail
        storage[0].trail_base = 0
        storage[0].trail_of = 0
        storage[0].normals.release()
        storage[0].normals = normals
        storage[0].extent = extent
        storage[0].attributes = attributes
        storage[0].queries = queries
        storage[0].shading = shading
        _ = self.topology.users.add(1, .relaxed)
        return storage.data

    pub func transformed(translation: Vector3, rotation: Vector3, scale: Vector3) -> interop.Reference[Mesh]!:
        if not translation.is_finite() or not rotation.is_finite() or not scale.is_finite() or math.abs(scale.x) < 0.000001 or math.abs(scale.y) < 0.000001 or math.abs(scale.z) < 0.000001:
            error(errors.invalid, "mesh transform must be finite and nonsingular")
        let matrix = Matrix4.compose(translation, rotation, scale)
        return try self.placed(matrix)

    ## Affine placement preserves attributes and inverse-transposes normals.
    pub func placed(matrix: Matrix4) -> interop.Reference[Mesh]!:
        if not matrix.is_finite() or math.abs(matrix.determinant()) < 0.000000000001:
            error(errors.invalid, "mesh placement must be finite and nonsingular")
        # Without a reflection, placement is a position-only edit: topology and
        # triangles are shared, and no triangle can fold. The origin moves with
        # the mesh, so positions only take the linear part.
        if matrix.determinant() > 0.0 and self.is_precise():
            let points = try self.world_points(matrix)
            defer free(points) in memory.heap
            let result = try self.precise_moved(points, matrix.transform_point(self.origin), true)
            errdefer result.release()
            try position_edit.transform_normals(&result.value().attributes, matrix)
            return result
        if matrix.determinant() > 0.0:
            let origin = matrix.transform_point(self.origin)
            let previous = self.positions.view()
            var fresh = try Column[Float3].allocate(previous.length)
            defer fresh.release()
            let output = fresh.span()
            for at in 0..<previous.length:
                output[at] = Float3.of(matrix.transform_direction(previous[at].vector()))
            let moved = try new u32[previous.length] --- in memory.heap
            defer free(moved) in memory.heap
            for at in 0..<moved.length: moved[at] = (u32)at
            let placed_mesh = try self.repositioned(fresh, origin, moved, true)
            errdefer placed_mesh.release()
            try position_edit.transform_normals(&placed_mesh.value().attributes, matrix)
            return placed_mesh
        # Reversing corners preserves outward normals under a reflection.
        let points = try self.world_points(matrix)
        defer free(points) in memory.heap
        let old_corners = self.corners.view()
        let offsets = self.offsets.view()
        let faces = offsets.length - 1
        let sizes = try new i64[faces] --- in memory.heap
        defer free(sizes) in memory.heap
        let corners = try new i64[old_corners.length] --- in memory.heap
        defer free(corners) in memory.heap
        let parents = try new i64[old_corners.length] --- in memory.heap
        defer free(parents) in memory.heap
        for face in 0..<faces:
            let start = (usize)offsets[face]
            let count = (usize)offsets[face + 1] - start
            sizes[face] = (i64)count
            for at in 0..<count:
                corners[start + at] = (i64)old_corners[start + count - 1 - at]
                parents[start + at] = (i64)(start + count - 1 - at)
        var unchanged: i64[]
        let old_triangles = self.triangles.view()
        let display = try new i64[old_triangles.length] --- in memory.heap
        defer free(display) in memory.heap
        for triangle in 0..<display.length // 3:
            for at in 0..<(usize)3:
                let old = (usize)old_triangles[triangle * 3 + (2 - at)]
                display[triangle * 3 + at] = parents[old]
        let result = try self.remapped(points, sizes, corners, unchanged, unchanged, parents, true, display)
        errdefer result.release()
        try position_edit.transform_normals(&result.value().attributes, matrix)
        return result

    ## Every point placed by `matrix`, in f64; the caller frees them.
    func world_points(matrix: Matrix4) -> Vector3[]!:
        let points = try new Vector3[self.positions.count()] --- in memory.heap
        for at in 0..<points.length:
            points[at] = matrix.transform_point(self.point_at(at))
        return points

    ## A precise mesh over new f64 `points` (world), its f32 positions their
    ## rounding relative to `origin`: a position edit like any other (the
    ## topology, its caches and the triangles shared, normals redone around
    ## the points that moved), with a new f64 column. `rigid` as for
    ## `repositioned`.
    func precise_moved(points: const Vector3[], origin: Vector3, rigid: bool) -> interop.Reference[Mesh]!:
        var exact = try Column[Vector3].copy_of(points)
        defer exact.release()
        var fresh = try Column[Float3].allocate(points.length)
        defer fresh.release()
        let output = fresh.span()
        for at in 0..<points.length:
            if not points[at].is_finite(): error(errors.invalid, "mesh points must be finite and bounded to 1e6")
            output[at] = Float3.of(points[at].subtract(origin))
        var moved: u32[]
        if origin == self.origin:
            moved = try changed_points(self.positions.view(), output)
        else:
            moved = try new u32[points.length] --- in memory.heap
            for at in 0..<moved.length: moved[at] = (u32)at
        defer free(moved) in memory.heap
        return try self.with_precise(&exact, &fresh, origin, moved, rigid)

    ## `fresh` positions (relative to `origin`) whose points `moved` changed,
    ## over this mesh's topology, with `exact` as the f64 points.
    func with_precise(exact: const Column[Vector3]*, fresh: const Column[Float3]*, origin: Vector3, moved: const u32[], rigid: bool) -> interop.Reference[Mesh]!:
        let storage = try self.repositioned_storage(*fresh, origin, moved, rigid)
        storage.precise.release()
        storage.precise = exact.share()
        return try adopt_storage(storage)

    ## This mesh's points and faces, then `other`'s (see concatenated).
    pub func merged(other: interop.Reference[Mesh]) -> interop.Reference[Mesh]!:
        let parts: MeshPart[2] = [MeshPart(&self, Matrix4()), MeshPart(try other.get(), Matrix4())]
        return try concatenated(parts)

## A parent map in i32 (the caller frees it); empty stays empty.
func narrowed(parents: const i64[]) -> i32[]!:
    let result = try new i32[parents.length] --- in memory.heap
    for at in 0..<parents.length: result[at] = (i32)parents[at]
    return result

## The points whose stored positions differ between `previous` and `next`.
## The caller frees the list.
pub func changed_points(previous: const Float3[], next: const Float3[]) -> u32[]!:
    # Counted per chunk in parallel, then written per chunk at its offset.
    let chunks = (next.length + 65535) // 65536
    let counts = try new usize[chunks + 1] --- in memory.heap
    defer free(counts) in memory.heap
    var none_yet: u32[]
    var work = ChangedWork(previous, next, counts, none_yet)
    try parallel.for_each_range(chunks, 1, (void*)&work, count_changed)
    var total: usize = 0
    for chunk in 0..<chunks:
        let count = counts[chunk]
        counts[chunk] = total
        total += count
    let moved = try new u32[total] --- in memory.heap
    errdefer free(moved) in memory.heap
    work.moved = moved
    try parallel.for_each_range(chunks, 1, (void*)&work, write_changed)
    return moved

struct ChangedWork:
    let previous: const Float3[]
    let next: const Float3[]
    let counts: usize[]
    var moved: u32[]

func count_changed(context: void*, first: usize, end: usize, worker: usize):
    let work = (ChangedWork*)context
    for chunk in first..<end:
        let start = chunk * 65536
        let stop = start + 65536 if work.next.length - start > 65536 else work.next.length
        var count: usize = 0
        for at in start..<stop:
            let a = work.previous[at]
            let b = work.next[at]
            if a.x != b.x or a.y != b.y or a.z != b.z: count += 1
        work.counts[chunk] = count

func write_changed(context: void*, first: usize, end: usize, worker: usize):
    let work = (ChangedWork*)context
    for chunk in first..<end:
        let start = chunk * 65536
        let stop = start + 65536 if work.next.length - start > 65536 else work.next.length
        var written = work.counts[chunk]
        for at in start..<stop:
            let a = work.previous[at]
            let b = work.next[at]
            if a.x != b.x or a.y != b.y or a.z != b.z:
                work.moved[written] = (u32)at
                written += 1

func min_of(values: const u32[]) -> u32:
    var least = values[0]
    for value in values: least = value if value < least else least
    return least

func max_of(values: const u32[]) -> u32:
    var most = values[0]
    for value in values: most = value if value > most else most
    return most

struct DisplayNormals:
    let positions: const Float3[]
    let offsets: const i32[]
    let corners: const i32[]
    let faces: const u32[]
    let normals: Float3[]

func display_normals(context: void*, first: usize, end: usize, worker: usize):
    let work = (DisplayNormals*)context
    for listed in first..<end:
        let face = (usize)work.faces[listed]
        let start = (usize)work.offsets[face]
        let size = (usize)work.offsets[face + 1] - start
        var normal = Vector3()
        for at in 0..<size:
            let p = work.positions[(usize)work.corners[start + at]].vector()
            let q = work.positions[(usize)work.corners[start + (at + 1) % size]].vector()
            normal = normal.add(p.cross(q))
        let length = normal.length()
        work.normals[face] = Float3.of(normal.multiply_scalar(1.0 / length) if length > 0.0 else Vector3())