Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.6

0.7.6 / src / verbs / dissolve.lucb

## Dissolve, Delete Edge Loop and Limited Dissolve: faces joined across
## edges into one face per region, after Blender's Dissolve, Delete Edge
## Loops and Limited Dissolve. A region is walked round its one boundary
## loop; a region with a hole or a pinch is left as it was and counted in
## the warning. Points left between two edges go (Blender's Dissolve
## Vertices): with Dissolve's Clean points, those of the dissolved edges;
## a point group's always; Delete Edge Loop's always (the faces either side
## of a loop become one row); Limited Dissolve's where their two edges run
## on within the angle. Points no face uses any more go. When nothing
## applies the input passes through with a warning.
##
## Limited Dissolve joins faces flatter than Angle, flattest first, after
## Blender's: each join only when the two regions' normals (area-weighted)
## stay within Angle of each other, so a gently curved surface keeps its
## facets instead of joining all round. Delimits (sharp marks, seams,
## materials, UVs) keep edges.

let dissolve_parms: ParmSpec[1] = [
    ParmSpec("Clean points", ParmKind.toggle, 1.0, 0.0, 1.0, 1, "", "Take out points left between two edges once the faces join (Blender's Dissolve Vertices).")]

## Points dissolve as they are; other groups become edges.
let dissolve_also: Domain[1] = [Domain.point]

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, dissolve_parms, true, cook_dissolve, false, dissolve_also, true, section = "Modify", family = "Delete", icon = "dissolve", picks = pick_components)

func delete_loop_verb() -> Verb:
    return Verb("Delete Edge Loop", "Modeling", "Remove the group's edge loops: the faces either side join and the loop's points go", Domain.edge, true, dissolve_parms[..<0], true, cook_delete_loop, false, no_domains[..<0], true, section = "Modify", family = "Delete", icon = "remove-faces", picks = pick_edges)

let limited_parms: ParmSpec[6] = [
    ParmSpec("Angle", ParmKind.number, 5.0, 0.0, 180.0, 1, "", "Faces meeting flatter than this many degrees join; points whose two edges bend less go.", 30.0),
    ParmSpec("Boundaries", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Take out points on the mesh's boundary too, where it runs straight."),
    ParmSpec("Delimit sharp", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges marked sharp.", more = true),
    ParmSpec("Delimit seams", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges marked as seams.", more = true),
    ParmSpec("Delimit materials", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges between faces of different materials.", more = true),
    ParmSpec("Delimit UVs", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges where the UVs part.", more = true)]

func limited_dissolve_verb() -> Verb:
    return Verb("Limited Dissolve", "Modeling", "Join the group's faces where they meet flatter than an angle, and take out the points left on straight runs", Domain.edge, true, limited_parms, true, cook_limited_dissolve, false, dissolve_also, false, section = "Modify", family = "Delete", icon = "set-planar", picks = pick_pieces, drag = 0, drag_mode = "amount", whole = true)

func cook_dissolve(input: const VerbInput*, output: VerbOutput*) -> !:
    let clean = input.parms.at(0) != 0.0
    let by_points = input.domain == Domain.point
    try dissolve_edges(input, output, clean or by_points, by_points)

func cook_delete_loop(input: const VerbInput*, output: VerbOutput*) -> !:
    try dissolve_edges(input, output, true, false)

## Dissolve the group's edges (a point group's: every edge at its points),
## points left between two edges going when `clean`.
func dissolve_edges(input: const VerbInput*, output: VerbOutput*, clean: bool, by_points: bool) -> !:
    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()
    for edge in 0..<topology.edges():
        var chosen = input.group.get(edge) if not by_points else false
        if by_points: chosen = input.group.get((usize)topology.edge_points[edge * 2]) or input.group.get((usize)topology.edge_points[edge * 2 + 1])
        if not chosen: continue
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let a = find(parent[..<faces], topology.corner_faces[(usize)topology.edge_corners[first]])
        let b = find(parent[..<faces], 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[..<faces], (i32)face)
    var candidates = try BitsBuilder.zeros(topology.points)
    defer candidates.close()
    if by_points:
        candidates.unite(input.group)
    elif clean:
        for edge in 0..<topology.edges():
            if not dissolved.view().get(edge): continue
            candidates.set((usize)topology.edge_points[edge * 2])
            candidates.set((usize)topology.edge_points[edge * 2 + 1])
    try join_regions(mesh, &topology, parent[..<faces], &dissolved, candidates.view(), by_points, none, (void*)0, output)

## What Limited Dissolve's point test reads.
struct LimitedWork:
    let mesh: const Mesh*
    let cosine: f64
    let boundaries: bool

## Whether point `point`, left with two edges, runs straight enough to go:
## its edges bend less than the angle, and it is inside the surface unless
## boundaries go too.
func straight_enough(context: void*, topology: const Topology*, dissolved: Bits, point: usize) -> bool:
    let work = (LimitedWork*)context
    var ends: Vector3[2] = [Vector3(), Vector3()]
    var count: usize = 0
    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
        if topology.edge_corner_offsets[edge + 1] - topology.edge_corner_offsets[edge] < 2 and not work.boundaries: return false
        let other = topology.edge_points[edge * 2] if (usize)topology.edge_points[edge * 2 + 1] == point else topology.edge_points[edge * 2 + 1]
        if count < 2: ends[count] = point_of(work.mesh, other)
        count += 1
    if count != 2: return false
    let here = point_of(work.mesh, (i32)point)
    let a = here.subtract(ends[0])
    let b = ends[1].subtract(here)
    let lengths = a.length() * b.length()
    return lengths > 0.0 and a.dot(b) / lengths >= work.cosine

## An edge Limited Dissolve may join across, by its face angle.
struct Flat:
    let angle: f64
    let edge: i32

func flatter(a: Flat, b: Flat) -> bool:
    return a.angle < b.angle or (a.angle == b.angle and a.edge < b.edge)

func cook_limited_dissolve(input: const VerbInput*, output: VerbOutput*) -> !:
    let limit = math.max(0.0, math.min(180.0, input.parms.at(0)))
    let boundaries = input.parms.at(1) != 0.0
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    let faces = topology.faces()
    let delimits = try delimits_for(mesh, input.parms.at(3) != 0.0, input.parms.at(2) != 0.0, input.parms.at(4) != 0.0, input.parms.at(5) != 0.0, false, 0.0)
    # The group's faces (an edge group: the faces along its edges; points:
    # the faces round them) and the edges between two of them, flattest first.
    var faces_in = try converted(&topology, input.group, input.domain, Domain.face, false)
    defer faces_in.close()
    var flats = Growing[Flat]()
    defer flats.close()
    for edge in 0..<topology.edges():
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let a = (usize)topology.corner_faces[(usize)topology.edge_corners[first]]
        let b = (usize)topology.corner_faces[(usize)topology.edge_corners[first + 1]]
        if not faces_in.view().get(a) or not faces_in.view().get(b): continue
        let angle = fold_angle(mesh, a, b)
        if angle > limit or delimits.stops(mesh, &topology, edge): continue
        try flats.push(Flat(angle, (i32)edge))
    sort.by[Flat](flats.items[..<flats.count], flatter)
    # Regions grow flattest first while their area-weighted normals agree.
    let parent = try new i32[faces] --- in memory.heap
    defer free(parent) in memory.heap
    let normals = try new Vector3[faces] --- in memory.heap
    defer free(normals) in memory.heap
    for face in 0..<faces:
        parent[face] = (i32)face
        normals[face] = face_vector_area(mesh, &topology, face)
    let cosine = math.cos(limit * math.pi / 180.0)
    for flat in flats.view():
        let first = (usize)topology.edge_corner_offsets[(usize)flat.edge]
        let a = find(parent[..<faces], topology.corner_faces[(usize)topology.edge_corners[first]])
        let b = find(parent[..<faces], topology.corner_faces[(usize)topology.edge_corners[first + 1]])
        if a == b: continue
        let p = normals[(usize)a]
        let q = normals[(usize)b]
        let lengths = p.length() * q.length()
        if lengths > 0.0 and p.dot(q) / lengths < cosine - 0.000000000001: continue
        let low = a if a < b else b
        let high = b if a < b else a
        parent[(usize)high] = low
        normals[(usize)low] = p.add(q)
    for face in 0..<faces: parent[face] = find(parent[..<faces], (i32)face)
    # Every edge between two faces of one region dissolves.
    var dissolved = try BitsBuilder.zeros(topology.edges())
    defer dissolved.close()
    var candidates = try BitsBuilder.zeros(topology.points)
    defer candidates.close()
    for edge in 0..<topology.edges():
        let first = (usize)topology.edge_corner_offsets[edge]
        let count = (usize)topology.edge_corner_offsets[edge + 1] - first
        if count == 2 and parent[(usize)topology.corner_faces[(usize)topology.edge_corners[first]]] == parent[(usize)topology.corner_faces[(usize)topology.edge_corners[first + 1]]]:
            dissolved.set(edge)
        # Points of the group's faces may go where they run straight.
        if count >= 1 and faces_in.view().get((usize)topology.corner_faces[(usize)topology.edge_corners[first]]):
            candidates.set((usize)topology.edge_points[edge * 2])
            candidates.set((usize)topology.edge_points[edge * 2 + 1])
    var work = LimitedWork(mesh, cosine, boundaries)
    try join_regions(mesh, &topology, parent[..<faces], &dissolved, candidates.view(), true, straight_enough, (void*)&work, output)

## The angle between faces `a` and `b`'s normals, in degrees.
func fold_angle(mesh: const Mesh*, a: usize, b: usize) -> f64:
    let normals = mesh.face_normal_span()
    return math.acos(math.max(-1.0, math.min(1.0, normals[a].vector().dot(normals[b].vector())))) * 180.0 / math.pi

## Face `face`'s normal scaled by its area (Newell's).
func face_vector_area(mesh: const Mesh*, topology: const Topology*, face: usize) -> Vector3:
    var sum = Vector3()
    let start = (usize)topology.offsets[face]
    let end = (usize)topology.offsets[face + 1]
    for corner in start..<end:
        let p = point_of(mesh, topology.corners[corner])
        let q = point_of(mesh, topology.corners[corner + 1 if corner + 1 < end else start])
        sum = sum.add(p.cross(q))
    return sum.multiply_scalar(0.5)

## Join the faces of each region of `parent` (every face's region root,
## its lowest face) across the `dissolved` edges into one face, round its
## one boundary loop; a region with a hole or a pinch is left as it was.
## Points of `candidates` left with two edges go (where `takes` agrees);
## with `by_points` they go though no edge of theirs dissolved. The joined
## faces are the output selection.
func join_regions(mesh: const Mesh*, topology: const Topology*, parent: const i32[], dissolved: BitsBuilder*, candidates: Bits, by_points: bool, takes: (func(void*, const Topology*, Bits, usize) -> bool)?, context: void*, output: VerbOutput*) -> !:
    let faces = topology.faces()
    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
    # Each region's boundary corners, walked into one loop when it is simple.
    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
    # Edges inside a region left as it was stay; points whose two edges
    # are all that stay (and that `takes` lets go) go from the faces round
    # them.
    for edge in 0..<topology.edges():
        if not dissolved.view().get(edge): continue
        let region = (usize)parent[(usize)topology.corner_faces[(usize)topology.edge_corners[(usize)topology.edge_corner_offsets[edge]]]]
        if loop_of[region] < 0: dissolved.clear(edge)
    let removable = try new u8[topology.points] --- in memory.heap
    defer free(removable) in memory.heap
    memory.set(removable, 0)
    var removals: usize = 0
    for point in 0..<topology.points:
        if not candidates.get(point): continue
        var kept: usize = 0
        var touched = false
        for slot in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
            if dissolved.view().get((usize)topology.point_edges[slot]):
                touched = true
            else:
                kept += 1
        if kept != 2 or not (touched or by_points): continue
        if let check = takes:
            if not check(context, topology, dissolved.view(), point): continue
        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