///|
priv struct EdgeUse {
face_number : Int
forward : Bool
}
///|
priv struct SurfaceTopology {
faces : Map[(String, String, String), Int]
edges : Map[(String, String), Array[EdgeUse]]
}
///|
fn SurfaceTopology::new() -> SurfaceTopology {
{ faces: Map([]), edges: Map([]), }
}
///|
fn SurfaceTopology::add_face(
self : SurfaceTopology,
vertices : (String, String, String),
face_number : Int,
emit : (Rule, Int?, Array[String], Array[Int]) -> Unit,
) -> Bool {
let (a, b, c) = vertices
let ids = [a, b, c]
ids.sort()
let key = (ids[0], ids[1], ids[2])
if self.faces.get(key) is Some(first) {
emit(DuplicateFace, Some(face_number), ids, [first])
return false
}
self.faces[key] = face_number
self.add_edge(a, b, face_number)
self.add_edge(b, c, face_number)
self.add_edge(c, a, face_number)
true
}
///|
fn SurfaceTopology::add_edge(
self : SurfaceTopology,
start : String,
end : String,
face_number : Int,
) -> Unit {
let forward = start < end
let key = if forward { (start, end) } else { (end, start) }
let usage = EdgeUse::{ face_number, forward, }
match self.edges.get(key) {
Some(uses) => uses.push(usage)
None => self.edges[key] = [usage]
}
}
///|
fn SurfaceTopology::check_edges(
self : SurfaceTopology,
emit : (Rule, Int?, Array[String], Array[Int]) -> Unit,
) -> Unit {
self.edges.each(fn(edge, uses) {
let (a, b) = edge
if uses.length() > 2 {
emit(
NonManifoldEdge,
Some(uses[2].face_number),
[a, b],
uses.filter_map(fn(usage) {
if usage.face_number == uses[2].face_number {
None
} else {
Some(usage.face_number)
}
}),
)
} else if uses.length() == 2 && uses[0].forward == uses[1].forward {
emit(SharedEdgeDirection, Some(uses[1].face_number), [a, b], [
uses[0].face_number,
])
}
})
}
///|
fn SurfaceTopology::summarize(self : SurfaceTopology) -> (Int, Int) {
let mut highest_face = 0
self.faces.each(fn(_, number) { highest_face = highest_face.max(number) })
// A negative entry identifies a root and stores the negated set size.
let parents = FixedArray::make(highest_face + 1, -1)
let mut boundary = 0
let mut components = self.faces.length()
self.edges.each(fn(_, uses) {
if uses.length() == 1 {
boundary += 1
} else {
let mut first = component_root(parents, uses[0].face_number)
for index = 1; index < uses.length(); index = index + 1 {
let other = component_root(parents, uses[index].face_number)
if first != other {
first = merge_components(parents, first, other)
components -= 1
}
}
}
})
(boundary, components)
}
///|
fn component_root(parents : FixedArray[Int], face : Int) -> Int {
let mut root = face
while parents[root] >= 0 {
root = parents[root]
}
let mut child = face
while child != root {
let parent = parents[child]
parents[child] = root
child = parent
}
root
}
///|
fn merge_components(
parents : FixedArray[Int],
first : Int,
second : Int,
) -> Int {
let (large, small) = if parents[first] <= parents[second] {
(first, second)
} else {
(second, first)
}
parents[large] += parents[small]
parents[small] = large
large
}