dymokomi/luce-geocore
Source of release 0.7.2
0.7.2 / src / groups / convert.lucb
## Selection kernels over a mesh's connectivity: converting bits between the
## point, corner, face and edge domains, and growing, shrinking, bordering,
## flood filling, edge loops and edge rings. They read the topology caches
## (edges, point-face, point-edge and edge-corner lists), which every mesh
## with the same connectivity shares, and write fresh bits.
## Bits of `source` elements converted to `destination` elements. With `all`, an element
## is selected when every related element is (a face whose points all are);
## otherwise when any is (a point of any selected face). Faces relate to
## their corners, points and edges; edges to their two points, their corners
## and their faces; corners to their point, face and edge.
pub func converted(topology: const Topology*, bits: Bits, source: Domain, destination: Domain, all: bool) -> BitsBuilder!:
let size = topology.size(destination)
var out = try BitsBuilder.zeros(size)
errdefer out.close()
if source == destination:
memory.copy(out.words(), bits.words, bits.words.length)
return out
if source == Domain.detail:
if bits.get(0): out.set_range(0, size)
return out
if destination == Domain.detail:
if (all and bits.population() == bits.count) or (not all and bits.any()): out.set(0)
return out
let hits = try new u32[size] --- in memory.heap
defer free(hits) in memory.heap
let totals = try new u32[size] --- in memory.heap
defer free(totals) in memory.heap
memory.set(u8[]((u8*)hits.data, size * 4), 0)
memory.set(u8[]((u8*)totals.data, size * 4), 0)
# Every relation is a list of (from, to) pairs over corners or edges.
if (source == Domain.point and destination == Domain.edge) or (source == Domain.edge and destination == Domain.point):
for edge in 0..<topology.edges():
for side in 0..<(usize)2:
let point = (usize)topology.edge_points[edge * 2 + side]
relate(bits, source == Domain.point, point, edge, hits, totals)
else:
for corner in 0..<topology.corners.length:
let a = element_of(topology, corner, source)
let b = element_of(topology, corner, destination)
let target = b
totals[target] += 1
if bits.get(a): hits[target] += 1
for element in 0..<size:
if totals[element] > 0 and (hits[element] == totals[element] if all else hits[element] > 0): out.set(element)
return out
## Count one (point, edge) relation in the direction of the conversion.
func relate(bits: Bits, point_first: bool, point: usize, edge: usize, hits: u32[], totals: u32[]):
let source = point if point_first else edge
let target = edge if point_first else point
totals[target] += 1
if bits.get(source): hits[target] += 1
## The element of `domain` a corner belongs to.
func element_of(topology: const Topology*, corner: usize, domain: Domain) -> usize:
match domain:
.point: return (usize)topology.corners[corner]
.face: return (usize)topology.corner_faces[corner]
.edge: return (usize)topology.corner_edges[corner]
_: return corner
## Neighbors across the domain's connector: faces through edges, points and
## edges through points, corners through points.
func connector(domain: Domain) -> Domain:
return Domain.edge if domain == Domain.face else Domain.point
## `bits` and every element next to one of them, `steps` times.
pub func grown(topology: const Topology*, bits: Bits, domain: Domain, steps: usize) -> BitsBuilder!:
var current = try BitsBuilder.copy_of(bits)
errdefer current.close()
let link = connector(domain)
for _ in 0..<steps:
var linked = try converted(topology, current.view(), domain, link, false)
defer linked.close()
var next = try converted(topology, linked.view(), link, domain, false)
current.close()
current = next
return current
## `bits` without the elements next to an unselected one, `steps` times.
pub func shrunk(topology: const Topology*, bits: Bits, domain: Domain, steps: usize) -> BitsBuilder!:
var current = try BitsBuilder.copy_of(bits)
errdefer current.close()
for _ in 0..<steps:
var outside = try BitsBuilder.copy_of(current.view())
defer outside.close()
outside.invert()
var reach = try grown(topology, outside.view(), domain, 1)
defer reach.close()
current.subtract(reach.view())
return current
## The selected elements next to an unselected one.
pub func bordered(topology: const Topology*, bits: Bits, domain: Domain) -> BitsBuilder!:
var outside = try BitsBuilder.copy_of(bits)
defer outside.close()
outside.invert()
var reach = try grown(topology, outside.view(), domain, 1)
errdefer reach.close()
reach.intersect(bits)
return reach
## Everything connected to `bits`: a breadth-first flood over faces sharing
## edges, or points and edges sharing points (corners through their points).
pub func connected(topology: const Topology*, bits: Bits, domain: Domain) -> BitsBuilder!:
if domain == Domain.corner or domain == Domain.detail:
var points = try converted(topology, bits, domain, Domain.point, false)
defer points.close()
var filled = try connected(topology, points.view(), Domain.point)
defer filled.close()
return try converted(topology, filled.view(), Domain.point, domain, false)
var out = try BitsBuilder.copy_of(bits)
errdefer out.close()
let queue = try new u32[topology.size(domain)] --- in memory.heap
defer free(queue) in memory.heap
var head: usize = 0
var tail: usize = 0
for word in 0..<bits.words.length:
var pending = bits.words[word]
while pending != 0:
queue[tail] = (u32)(word * 64 + (usize)trailing_zeros(pending))
tail += 1
pending = pending & (pending - 1)
while head < tail:
let element = (usize)queue[head]
head += 1
if domain == Domain.face:
for corner in (usize)topology.offsets[element]..<(usize)topology.offsets[element + 1]:
let edge = (usize)topology.corner_edges[corner]
for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
let face = (usize)topology.corner_faces[(usize)topology.edge_corners[at]]
if not out.view().get(face):
out.set(face)
queue[tail] = (u32)face
tail += 1
else:
# Points reach points through their edges; edges reach edges
# through their points.
let ends: usize[2] = [element, 0] if domain == Domain.point else [(usize)topology.edge_points[element * 2], (usize)topology.edge_points[element * 2 + 1]]
let count: usize = 1 if domain == Domain.point else 2
for side in 0..<count:
let point = ends[side]
for at in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
let edge = (usize)topology.point_edges[at]
var next = edge
if domain == Domain.point:
let a = (usize)topology.edge_points[edge * 2]
next = (usize)topology.edge_points[edge * 2 + 1] if a == point else a
if not out.view().get(next):
out.set(next)
queue[tail] = (u32)next
tail += 1
return out
## Edge loops through the selected edges: across each four-edge point to the
## edge that shares no face, until a pole, a boundary or the loop closes.
pub func looped(topology: const Topology*, edges: Bits) -> BitsBuilder!:
var out = try BitsBuilder.copy_of(edges)
errdefer out.close()
for word in 0..<edges.words.length:
var pending = edges.words[word]
while pending != 0:
let edge = word * 64 + (usize)trailing_zeros(pending)
pending = pending & (pending - 1)
let first = (usize)topology.edge_corner_offsets[edge]
if first == (usize)topology.edge_corner_offsets[edge + 1]: continue
let corner = (usize)topology.edge_corners[first]
walk_loop(topology, corner, &out, edge)
# The other direction: through the edge's first point.
walk_back(topology, corner, &out, edge)
return out
## From half-edge `corner`, keep crossing its end point.
func walk_loop(topology: const Topology*, start: usize, out: BitsBuilder*, seed: usize):
var corner = start
for _ in 0..<topology.edges():
let point = (usize)topology.corners[topology.next(corner)]
if topology.valence(point) != 4: return
let across = topology.twin(topology.next(corner))
if across < 0: return
corner = topology.next((usize)across)
let edge = (usize)topology.corner_edges[corner]
if edge == seed or out.view().get(edge): return
out.set(edge)
## The same walk leaving through the edge's start point.
func walk_back(topology: const Topology*, start: usize, out: BitsBuilder*, seed: usize):
let reverse = topology.twin(start)
if reverse >= 0:
walk_loop(topology, (usize)reverse, out, seed)
return
# A boundary edge: step back through its first point instead.
var corner = start
for _ in 0..<topology.edges():
let point = (usize)topology.corners[corner]
if topology.valence(point) != 4: return
let across = topology.twin(topology.previous(corner))
if across < 0: return
corner = topology.previous((usize)across)
let edge = (usize)topology.corner_edges[corner]
if edge == seed or out.view().get(edge): return
out.set(edge)
## Edge rings through the selected edges: across each quad to its opposite
## edge, until a face that is not a quad or a boundary.
pub func ringed(topology: const Topology*, edges: Bits) -> BitsBuilder!:
var out = try BitsBuilder.copy_of(edges)
errdefer out.close()
for word in 0..<edges.words.length:
var pending = edges.words[word]
while pending != 0:
let edge = word * 64 + (usize)trailing_zeros(pending)
pending = pending & (pending - 1)
for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
walk_ring(topology, (usize)topology.edge_corners[at], &out, edge)
return out
func walk_ring(topology: const Topology*, start: usize, out: BitsBuilder*, seed: usize):
var corner = start
for _ in 0..<topology.edges():
let face = (usize)topology.corner_faces[corner]
if topology.offsets[face + 1] - topology.offsets[face] != 4: return
let opposite = topology.next(topology.next(corner))
let edge = (usize)topology.corner_edges[opposite]
if edge == seed or out.view().get(edge): return
out.set(edge)
let across = topology.twin(opposite)
if across < 0: return
corner = (usize)across