dymokomi/luce-geocore
Source of release 0.7.5
0.7.5 / 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.")]
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)
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