Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.1

0.7.1 / src / verbs / fill_dissolve.lucb

## Fill and Dissolve over edge groups. Fill caps every closed loop of the
## group's boundary edges with one face (or a fan of triangles around its
## center); Dissolve joins the faces across the group's interior edges into
## one face per connected region. A point group dissolves every edge at its
## points and then the points themselves where two edges are left (Blender's
## Dissolve Vertices); points no face uses any more go. A region or
## loop they cannot make a simple face of (a hole, a pinch) is left as it
## was and counted in the warning; faces of any size are made. When nothing
## applies, the input passes through with a warning rather than an error, so
## a node dropped in with its defaults never fails.

let fill_parms: ParmSpec[1] = [ParmSpec("Mode", ParmKind.menu, 0.0, 0.0, 1.0, 1, "Single face|Fan", "One face per loop, or triangles around a new point at its center.")]

pub func fill_verb() -> Verb:
    return Verb("Fill", "Modeling", "Cap each closed loop of the group's boundary edges", Domain.edge, true, fill_parms, true, cook_fill)

pub func dissolve_verb() -> Verb:
    return Verb("Dissolve", "Modeling", "Join the faces across the group's interior edges (or around its points), one face per region", Domain.edge, true, placeholder_parms[..<0], true, cook_dissolve, false, Domain.point, true)

func cook_fill(input: const VerbInput*, output: VerbOutput*) -> !:
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    let points = topology.points
    # The group's boundary edges, each as the one corner that uses it.
    let starting = try new i32[points] --- in memory.heap
    defer free(starting) in memory.heap
    for at in 0..<points: starting[at] = -1
    var candidates: usize = 0
    for edge in 0..<topology.edges():
        if not input.group.get(edge): continue
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 1: continue
        let corner = topology.edge_corners[first]
        let point = (usize)topology.corners[(usize)corner]
        # Two boundary edges leaving one point: a pinch, which no loop may use.
        starting[point] = corner if starting[point] == -1 else -2
        candidates += 1
    var loops = Growing[i32]()
    defer loops.close()
    var loop_ends = Growing[u32]()
    defer loop_ends.close()
    var visited = try BitsBuilder.zeros(topology.corners.length)
    defer visited.close()
    var skipped: usize = 0
    for point in 0..<points:
        if starting[point] < 0 or visited.view().get((usize)starting[point]): continue
        let begin = loops.count
        var corner = starting[point]
        var closed = false
        while true:
            if visited.view().get((usize)corner): break
            visited.set((usize)corner)
            try loops.push(corner)
            let next = starting[(usize)topology.corners[topology.next((usize)corner)]]
            if next < 0: break
            if next == starting[point]:
                closed = true
                break
            corner = next
        let size = loops.count - begin
        if not closed or size < 3:
            skipped += 1
            loops.count = begin
            continue
        try loop_ends.push((u32)loops.count)
    if loop_ends.count == 0:
        output.warning = "No closed loop of boundary edges in the group to fill; the input passes through"
        return
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    let faces = topology.faces()
    try builder.copy_faces(mesh, 0, faces)
    let fan = input.parms.at(0) == 1.0
    var begin: usize = 0
    var cap_stack: i32[256]
    var parent_stack: i32[256]
    var weight_stack: f32[256]
    for end in loop_ends.view():
        # The cap winds against the boundary: its corners in reverse, each
        # taking the adjacent face's corner at that point. Small loops on
        # the stack, larger ones in heap scratch.
        let length = (usize)end - begin
        let cap = try face_scratch.take[i32](cap_stack, length, length)
        defer face_scratch.release[i32](cap_stack, cap)
        let parents = try face_scratch.take[i32](parent_stack, length, length)
        defer face_scratch.release[i32](parent_stack, parents)
        var size: usize = 0
        var at = (usize)end
        while at > begin:
            at -= 1
            let corner = topology.next((usize)loops.items[at])
            cap[size] = topology.corners[corner]
            parents[size] = (i32)corner
            size += 1
        begin = (usize)end
        if not fan:
            try builder.face(-1)
            for index in 0..<size: try builder.corner(cap[index], parents[index])
            try builder.end_face()
            continue
        # A fan: a point at the loop's center, its values the loop's mean.
        var center = Vector3()
        let weights = try face_scratch.take[f32](weight_stack, size, size)
        defer face_scratch.release[f32](weight_stack, weights)
        for index in 0..<size:
            center = center.add(builder.position(cap[index]))
            weights[index] = 1.0 / (f32)size
        let middle = try builder.mixed_point(center.multiply_scalar(1.0 / (f64)size), cap, weights)
        # Every triangle's center corner shares one mix of the loop's corners.
        let mix = try builder.shared_mix(parents, weights)
        for index in 0..<size:
            let next = (index + 1) % size
            try builder.face(-1)
            try builder.shared_corner(middle, mix)
            try builder.corner(cap[index], parents[index])
            try builder.corner(cap[next], parents[next])
            try builder.end_face()
    output.selection = try BitsBuilder.zeros(builder.face_count())
    output.selection.set_range(faces, builder.face_count())
    output.selection_domain = Domain.face
    if skipped > 0: output.warning = "Some boundary runs in the group are not closed simple loops and were left open"

func cook_dissolve(input: const VerbInput*, output: VerbOutput*) -> !:
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    let faces = topology.faces()
    # Regions: faces joined across dissolved interior edges (union-find).
    let parent = try new i32[faces] --- in memory.heap
    defer free(parent) in memory.heap
    for face in 0..<faces: parent[face] = (i32)face
    var dissolved = try BitsBuilder.zeros(topology.edges())
    defer dissolved.close()
    # A point group: every edge at its points.
    let by_points = input.domain == Domain.point
    var chosen = try BitsBuilder.zeros(topology.edges())
    defer chosen.close()
    for edge in 0..<topology.edges():
        if not by_points:
            if input.group.get(edge): chosen.set(edge)
        elif input.group.get((usize)topology.edge_points[edge * 2]) or input.group.get((usize)topology.edge_points[edge * 2 + 1]):
            chosen.set(edge)
    for edge in 0..<topology.edges():
        if not chosen.view().get(edge): continue
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let a = find(parent, topology.corner_faces[(usize)topology.edge_corners[first]])
        let b = find(parent, topology.corner_faces[(usize)topology.edge_corners[first + 1]])
        dissolved.set(edge)
        if a != b: parent[(usize)(a if a > b else b)] = a if a < b else b
    for face in 0..<faces: parent[face] = find(parent, (i32)face)
    # Each region's boundary corners, walked into one loop when it is simple.
    let members = try new u32[faces] --- in memory.heap
    defer free(members) in memory.heap
    memory.set(u8[]((u8*)members.data, faces * 4), 0)
    for face in 0..<faces: members[(usize)parent[face]] += 1
    var boundary_count = try new u32[faces] --- in memory.heap
    defer free(boundary_count) in memory.heap
    memory.set(u8[]((u8*)boundary_count.data, faces * 4), 0)
    for corner in 0..<topology.corners.length:
        let region = (usize)parent[(usize)topology.corner_faces[corner]]
        if members[region] < 2 or dissolved.view().get((usize)topology.corner_edges[corner]): continue
        boundary_count[region] += 1
    # Walk each region once, from its first boundary corner.
    let loop_of = try new i32[faces] --- in memory.heap
    defer free(loop_of) in memory.heap
    for face in 0..<faces: loop_of[face] = -1
    var loops = Growing[i32]()
    defer loops.close()
    var loop_starts = Growing[u32]()
    defer loop_starts.close()
    var skipped: usize = 0
    for corner in 0..<topology.corners.length:
        let region = (usize)parent[(usize)topology.corner_faces[corner]]
        if members[region] < 2 or loop_of[region] != -1 or dissolved.view().get((usize)topology.corner_edges[corner]): continue
        loop_of[region] = -2
        let begin = loops.count
        var current = (i32)corner
        var closed = false
        for _ in 0..<(usize)boundary_count[region]:
            try loops.push(current)
            let next = next_boundary(&topology, parent, (i32)region, dissolved.view(), (usize)topology.corners[topology.next((usize)current)])
            if next < 0: break
            if next == (i32)corner:
                closed = true
                break
            current = next
        let size = loops.count - begin
        # One loop must use every boundary corner: otherwise the region has a hole.
        if not closed or size != (usize)boundary_count[region] or size < 3:
            skipped += 1
            loops.count = begin
            continue
        loop_of[region] = (i32)loop_starts.count
        try loop_starts.push((u32)begin)
    try loop_starts.push((u32)loops.count)
    let merged = loop_starts.count - 1
    # Group points left between two edges go from the faces around them.
    let removable = try new u8[topology.points] --- in memory.heap
    defer free(removable) in memory.heap
    memory.set(removable, 0)
    var removals: usize = 0
    if by_points:
        for point in 0..<topology.points:
            if not input.group.get(point): continue
            var kept: usize = 0
            for slot in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
                if not dissolved.view().get((usize)topology.point_edges[slot]): kept += 1
            if kept == 2:
                removable[point] = 1
                removals += 1
    if merged == 0 and removals == 0:
        output.warning = "Nothing to dissolve: the group joins no region of faces into a simple face; the input passes through"
        return
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    var face_total: usize = 0
    for face in 0..<faces:
        let region = (usize)parent[face]
        if members[region] < 2 or loop_of[region] < 0 or region == face: face_total += 1
    output.selection = try BitsBuilder.zeros(face_total)
    output.selection_domain = Domain.face
    var run: usize = 0
    var ring_stack: i32[256]
    for face in 0..<faces:
        let region = (usize)parent[face]
        let joined = members[region] >= 2 and loop_of[region] >= 0
        if not joined and not touches(&topology, removable, face): continue
        try builder.copy_faces(mesh, run, face)
        run = face + 1
        if joined and region != face: continue
        # The region's face at its lowest face's place, from its loop (or
        # an unjoined face's own corners), without removable points. Small
        # faces on the stack, larger ones in heap scratch.
        var corners_in: usize = 0
        if joined:
            let index = (usize)loop_of[region]
            corners_in = (usize)(loop_starts.items[index + 1] - loop_starts.items[index])
        else:
            corners_in = (usize)(topology.offsets[face + 1] - topology.offsets[face])
        let ring = try face_scratch.take[i32](ring_stack, corners_in, corners_in)
        defer face_scratch.release[i32](ring_stack, ring)
        var size: usize = 0
        if joined:
            let index = (usize)loop_of[region]
            for at in (usize)loop_starts.items[index]..<(usize)loop_starts.items[index + 1]:
                ring[size] = loops.items[at]
                size += 1
        else:
            for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
                ring[size] = (i32)corner
                size += 1
        var staying: usize = 0
        for at in 0..<size:
            if removable[(usize)topology.corners[(usize)ring[at]]] == 0: staying += 1
        if joined: output.selection.set(builder.face_count())
        try builder.face((i32)face)
        for at in 0..<size:
            let corner = ring[at]
            if staying >= 3 and removable[(usize)topology.corners[(usize)corner]] != 0: continue
            try builder.corner(topology.corners[(usize)corner], corner)
        try builder.end_face()
    try builder.copy_faces(mesh, run, faces)
    try builder.drop_unused_points()
    if skipped > 0: output.warning = "Regions with holes or pinches were left as they were"

## Whether face `face` has a corner at a removable point.
func touches(topology: const Topology*, removable: const u8[], face: usize) -> bool:
    for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
        if removable[(usize)topology.corners[corner]] != 0: return true
    return false

## The one boundary corner of `region` leaving `point` (its edge not
## dissolved), or -1 for none or a pinch (several).
func next_boundary(topology: const Topology*, parent: const i32[], region: i32, dissolved: Bits, point: usize) -> i32:
    var found: i32 = -1
    for slot in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
        let edge = (usize)topology.point_edges[slot]
        if dissolved.get(edge): continue
        for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
            let corner = topology.edge_corners[at]
            if (usize)topology.corners[(usize)corner] != point or parent[(usize)topology.corner_faces[(usize)corner]] != region: continue
            if found >= 0: return -1
            found = corner
    return found

## The root of `face`'s region, halving paths as it goes.
func find(parent: i32[], face: i32) -> i32:
    var at = face
    while parent[(usize)at] != at:
        parent[(usize)at] = parent[(usize)parent[(usize)at]]
        at = parent[(usize)at]
    return at