Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / code / apply.lucb

# Applying a cook's queued edits to the mesh the run made: new points and polygons in lane
# order, attribute sets, then removals; attributes follow their elements (new ones start
# at zero), and a removed point takes the polygons using it.

func point_before(a: PointAdd, b: PointAdd) -> bool:
    return a.key < b.key

func prim_before(a: PrimAdd, b: PrimAdd) -> bool:
    return a.key < b.key

## The index a provisional number `number` is among `adds` (ascending), or none.
func added_point(adds: const PointAdd[], number: i64) -> usize?:
    var low: usize = 0
    var high = adds.length
    while low < high:
        let middle = (low + high) // 2
        if adds[middle].provisional < number: low = middle + 1
        else: high = middle
    if low < adds.length and adds[low].provisional == number: return low
    return none

func added_prim(adds: const PrimAdd[], number: i64) -> usize?:
    var low: usize = 0
    var high = adds.length
    while low < high:
        let middle = (low + high) // 2
        if adds[middle].provisional < number: low = middle + 1
        else: high = middle
    if low < adds.length and adds[low].provisional == number: return low
    return none

## Old element numbers, then new ones in lane order: where a snippet's number lands
## before removals, or none.
struct Numbering:
    let old_points: usize
    let old_prims: usize
    let point_adds: const PointAdd[]
    let prim_adds: const PrimAdd[]

    func point(number: i64) -> usize?:
        if number >= 0 and (usize)number < self.old_points: return (usize)number
        let at = added_point(self.point_adds, number) else return none
        return self.old_points + at

    func prim(number: i64) -> usize?:
        if number >= 0 and (usize)number < self.old_prims: return (usize)number
        let at = added_prim(self.prim_adds, number) else return none
        return self.old_prims + at

## The mesh `edits` make of `source` (none: no input mesh).
func applied(source: const Mesh*?, edits: Edits*) -> Mesh*!:
    if let old = source:
        if edits.point_adds.length() + edits.prim_adds.length() + edits.removals.length() == 0 and not edits.masked.load(.acquire):
            return try with_sets(old, edits)
    sort.stable(edits.point_adds.items(), point_before)
    sort.stable(edits.prim_adds.items(), prim_before)
    var old_points: usize = 0
    var old_prims: usize = 0
    var origin = Vector3()
    var old_offsets = no_ints()
    var old_corners = no_ints()
    var old_triangles = no_ints()
    var old_positions = no_floats()
    if let old = source:
        old_points = (usize)old.point_count()
        old_prims = (usize)old.face_count()
        origin = old.position_origin()
        old_offsets = old.offset_span()
        old_corners = old.corner_span()
        old_triangles = old.triangle_span()
        old_positions = old.point_span()
    let numbering = Numbering(old_points = old_points, old_prims = old_prims, point_adds = edits.point_adds.view(), prim_adds = edits.prim_adds.view())
    let all_points = old_points + edits.point_adds.length()
    let all_prims = old_prims + edits.prim_adds.length()
    var scratch = Scratch()
    defer scratch.close()
    let point_gone = try scratch.bytes(all_points)
    let prim_gone = try scratch.bytes(all_prims)
    if edits.masked.load(.acquire):
        memory.copy(point_gone, edits.points_gone, old_points)
        memory.copy(prim_gone, edits.prims_gone, old_prims)
    # Removals of added elements (any order: removing is idempotent).
    for removal in edits.removals.view():
        if removal.domain == .point:
            let at = numbering.point(removal.index) else error(errors.invalid, "remove_point names a point that does not exist")
            point_gone[at] = 1
        else:
            let at = numbering.prim(removal.index) else error(errors.invalid, "remove_prim names a primitive that does not exist")
            prim_gone[at] = 1
    # The new polygons' points, before removals.
    let prim_points = i64_view(try scratch.bytes(edits.prim_adds.length() * 16 * 8))
    for (at, add) in edits.prim_adds.view().indexed():
        for k in 0..<add.count:
            let point = numbering.point((i64)add.points[k]) else error(errors.invalid, "add_prim names a point that does not exist")
            prim_points[at * 16 + k] = (i64)point
    # Which points and polygons stay, and their new numbers.
    let point_map = i64_view(try scratch.bytes(all_points * 8))
    var points: usize = 0
    for at in 0..<all_points:
        point_map[at] = -1 if point_gone[at] != 0 else (i64)points
        if point_gone[at] == 0: points += 1
    # Input polygons losing a point go too (in parallel: there may be millions).
    var dropping = Dropping(old_offsets, old_corners, point_map, prim_gone)
    try parallel.for_each_range(old_prims, 32768, (void*)&dropping, drop_polygons)
    var faces: usize = 0
    var corners: usize = 0
    var triangle_entries: usize = 0
    for face in 0..<all_prims:
        if prim_gone[face] != 0: continue
        let size = prim_size(face, old_prims, old_offsets, edits.prim_adds.view())
        if face >= old_prims and not prim_kept(face, old_prims, old_offsets, old_corners, prim_points, size, point_map):
            prim_gone[face] = 1
            continue
        faces += 1
        corners += size
        triangle_entries += (size - 2) * 3
    let prim_map = i64_view(try scratch.bytes(all_prims * 8))
    var survivors: i64 = 0
    for face in 0..<all_prims:
        prim_map[face] = -1 if prim_gone[face] != 0 else survivors
        if prim_gone[face] == 0: survivors += 1
    var positions = try SharedColumn[Float3].allocate(points)
    errdefer positions.release()
    var offsets = try SharedColumn[i32].allocate(faces + 1)
    errdefer offsets.release()
    var corner_column = try SharedColumn[i32].allocate(corners)
    errdefer corner_column.release()
    var triangles = try SharedColumn[i32].allocate(triangle_entries)
    errdefer triangles.release()
    let point_parents = i32_view(try scratch.bytes(points * 4))
    let face_parents = i32_view(try scratch.bytes(faces * 4))
    let corner_parents = i32_view(try scratch.bytes(corners * 4))
    for at in 0..<all_points:
        let to = point_map[at]
        if to < 0: continue
        if at < old_points:
            positions.span()[(usize)to] = old_positions[at]
            point_parents[(usize)to] = (i32)at
        else:
            positions.span()[(usize)to] = Float3.of(edits.point_adds.at(at - old_points).position.subtract(origin))
            point_parents[(usize)to] = -1
    var face_at: usize = 0
    var corner_at: usize = 0
    var triangle_at: usize = 0
    for face in 0..<all_prims:
        if prim_gone[face] != 0: continue
        let size = prim_size(face, old_prims, old_offsets, edits.prim_adds.view())
        offsets.span()[face_at] = (i32)corner_at
        for k in 0..<size:
            if face < old_prims:
                let old = (usize)old_offsets[face] + k
                corner_column.span()[corner_at + k] = (i32)point_map[(usize)old_corners[old]]
                corner_parents[corner_at + k] = (i32)old
            else:
                corner_column.span()[corner_at + k] = (i32)point_map[(usize)prim_points[(face - old_prims) * 16 + k]]
                corner_parents[corner_at + k] = -1
        if face < old_prims:
            # Keep the old triangulation, its corners renumbered.
            let start = (usize)old_offsets[face]
            let base = (start - face * 2) * 3
            for entry in 0..<(size - 2) * 3:
                triangles.span()[triangle_at + entry] = old_triangles[base + entry] - (i32)start + (i32)corner_at
            face_parents[face_at] = (i32)face
        else:
            # A first index of -1 asks assembly to triangulate the new polygon.
            for entry in 0..<(size - 2) * 3: triangles.span()[triangle_at + entry] = -1
            face_parents[face_at] = -1
        face_at += 1
        corner_at += size
        triangle_at += (size - 2) * 3
    offsets.span()[faces] = (i32)corners
    let made = try assembled(positions.take(), origin, offsets.take(), corner_column.take(), triangles.take(), SharedColumn[Float3](), SharedColumn[Vector3]())
    errdefer mesh_dispose(made)
    if let old = source:
        try transfer_attributes(old, made, point_parents, face_parents, corner_parents, true)
    try apply_sets(made, edits, &numbering, point_map, prim_map)
    try apply_text_sets(made, edits, &numbering, point_map, prim_map)
    if edits.array_set_count() > 0:
        # The new corner of each old corner (-1: gone), for vertex array writes.
        let old_corners_count = old_corners.length
        let corner_map = i64_view(try scratch.bytes(old_corners_count * 8))
        for at in 0..<old_corners_count: corner_map[at] = -1
        for (at, parent) in corner_parents.indexed():
            if parent >= 0: corner_map[(usize)parent] = (i64)at
        try apply_array_sets(made, edits, &numbering, point_map, prim_map, corner_map)
    return made

## Only attribute sets: the input's columns shared, the sets put on them with every
## element keeping its number (a full rebuild costs tens of ms on 1M points).
func with_sets(source: const Mesh*, edits: const Edits*) -> Mesh*!:
    let made = try mesh_share(source)
    errdefer mesh_dispose(made)
    let points = (usize)source.point_count()
    let prims = (usize)source.face_count()
    let corners = source.corner_span().length
    let numbering = Numbering(old_points = points, old_prims = prims, point_adds = edits.point_adds.view(), prim_adds = edits.prim_adds.view())
    var scratch = Scratch()
    defer scratch.close()
    # Numbers stay: empty point and primitive maps read as the identity.
    let same = no_map()
    try apply_sets(made, edits, &numbering, same, same)
    try apply_text_sets(made, edits, &numbering, same, same)
    if edits.array_set_count() > 0:
        let corner_map = i64_view(try scratch.bytes(corners * 8))
        for at in 0..<corners: corner_map[at] = (i64)at
        try apply_array_sets(made, edits, &numbering, same, same, corner_map)
    return made

func prim_size(face: usize, old_prims: usize, offsets: const i32[], adds: const PrimAdd[]) -> usize:
    if face < old_prims: return (usize)(offsets[face + 1] - offsets[face])
    return adds[face - old_prims].count

## Whether every point of polygon `face` stays.
func prim_kept(face: usize, old_prims: usize, offsets: const i32[], corners: const i32[], prim_points: const i64[], size: usize, point_map: const i64[]) -> bool:
    for k in 0..<size:
        let point = (usize)corners[(usize)offsets[face] + k] if face < old_prims else (usize)prim_points[(face - old_prims) * 16 + k]
        if point_map[point] < 0: return false
    return true

struct Dropping:
    let offsets: const i32[]
    let corners: const i32[]
    let point_map: const i64[]
    let prim_gone: u8[]

func drop_polygons(context: void*, first: usize, end: usize, worker: usize):
    let work = (Dropping*)context
    for face in first..<end:
        if work.prim_gone[face] != 0: continue
        for corner in (usize)work.offsets[face]..<(usize)work.offsets[face + 1]:
            if work.point_map[(usize)work.corners[corner]] < 0:
                work.prim_gone[face] = 1
                break

func no_floats() -> const Float3[]:
    var none_given: const Float3[]
    return none_given

## Each attribute the sets name, made (or widened) on `mesh`; an element set more than
## once takes the set with the highest key (its highest lane, then that lane's last).
func apply_sets(mesh: Mesh*, edits: const Edits*, numbering: const Numbering*, point_map: const i64[], prim_map: const i64[]) -> !:
    # The distinct (domain, name) pairs: a few, however many sets.
    var named: collections.List[AttributeSet]
    defer named.destroy()
    for queue in edits.sets.view():
        for set in queue.view():
            var seen = false
            for earlier in named.view():
                if earlier.domain == set.domain and earlier.name == set.name:
                    seen = true
                    break
            if not seen: try named.append(set)
    for set in named.view():
        try apply_named(mesh, edits, set, numbering, point_map, prim_map)

## The element a set lands on after removals (-1: removed), or an error for a number
## that never existed.
func target_of(set: const AttributeSet*, numbering: const Numbering*, point_map: const i64[], prim_map: const i64[]) -> i64!:
    if set.domain == .point:
        let at = numbering.point(set.index) else error(errors.invalid, "a set_point names a point that does not exist")
        return mapped(point_map, at)
    let at = numbering.prim(set.index) else error(errors.invalid, "a set_prim names a primitive that does not exist")
    return mapped(prim_map, at)

## The sets of the attribute `first` names.
func apply_named(mesh: Mesh*, edits: const Edits*, first: AttributeSet, numbering: const Numbering*, point_map: const i64[], prim_map: const i64[]) -> !:
    # The attribute: the existing one, widened to the widest set, or a new one.
    var width = first.width
    var kind = first.kind
    for queue in edits.sets.view():
        for set in queue.view():
            if set.domain == first.domain and set.name == first.name and set.width > width: width = set.width
    let elements = try mesh.domain_size(first.domain)
    let found = mesh.find_attribute(first.name, (i64)(u8)first.domain)
    var existing: const Attribute*? = none
    if found >= 0:
        let entry = try mesh.attribute_entry(found)
        if let stored = kind_of_data(entry.kind):
            kind = stored
            if entry.width > width: width = entry.width
            existing = entry
    let data_type = data_type_of(kind) else error(errors.invalid, "a set of a type no attribute stores")
    var attribute = try Attribute.create(first.name, first.domain, data_type, width, elements)
    errdefer attribute.release()
    let bytes = attribute.data.span()
    if let entry = existing:
        fill_from(bytes, kind, width, elements, entry)
    # Each element's winning key (plus one; 0: not set), then the winners' values.
    let winners = try new u64[(usize)elements] in memory.heap
    defer free(winners) in memory.heap
    for queue in edits.sets.view():
        for set in queue.view():
            if set.domain != first.domain or set.name != first.name: continue
            let target = try target_of(&set, numbering, point_map, prim_map)
            if target >= 0 and set.key + 1 > winners[(usize)target]: winners[(usize)target] = set.key + 1
    for queue in edits.sets.view():
        for set in queue.view():
            if set.domain != first.domain or set.name != first.name: continue
            let target = try target_of(&set, numbering, point_map, prim_map)
            if target < 0 or winners[(usize)target] != set.key + 1: continue
            for k in 0..<set.width: put_number(bytes, kind, (usize)target * width + k, set.values[k])
    try put_attribute(mesh, attribute)

## An element's new number through `map`; an empty map keeps numbers.
func mapped(map: const i64[], at: usize) -> i64:
    return map[at] if map.length > 0 else (i64)at

func no_map() -> const i64[]:
    var none_given: const i64[]
    return none_given