shambler 0.2.0

A rusty, hulking, lighting-tossing geometry processor.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

use std::collections::{BTreeSet, VecDeque};

use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
use usage::Usage;

use super::{FaceCenters, FaceId, FaceNormals};
use crate::{
    face::FaceLines,
    line::{LineFaceConnections, NonManifoldLines},
    Faces,
};

pub enum InteriorFacesTag {}

pub type InteriorFaces = Usage<InteriorFacesTag, BTreeSet<FaceId>>;

pub fn interior_faces(
    faces: &Faces,
    face_lines: &FaceLines,
    face_normals: &FaceNormals,
    face_centers: &FaceCenters,
    non_manifold_lines: &NonManifoldLines,
    line_face_connections: &LineFaceConnections,
) -> InteriorFaces {
    let mut interior_faces = BTreeSet::default();

    // Find faces whose lines are all non-manifold
    let starting_faces = faces
        .par_iter()
        .flat_map(|face| {
            let lines = face_lines.get(&face).unwrap();

            let non_manifold: usize = lines
                .par_iter()
                .map(|line_id| non_manifold_lines.contains(line_id) as usize)
                .sum();

            if non_manifold == lines.len() {
                Some(*face)
            } else {
                None
            }
        })
        .collect::<BTreeSet<_>>();

    // Initialize the traversal queue with the non-manifold faces
    let mut traversal_queue = starting_faces.iter().copied().collect::<VecDeque<_>>();

    // Traverse
    while let Some(face) = traversal_queue.pop_front() {
        if interior_faces.contains(&face) {
            continue;
        }

        interior_faces.insert(face);

        let face_normal = face_normals[&face][0];

        for line_id in &face_lines[&face] {
            let mut connected_faces = line_face_connections[line_id]
                .iter()
                .filter(|candidate| **candidate != face);

            let non_manifold = non_manifold_lines.contains(line_id);
            if non_manifold {
                // Pick closest face via normal
                let mut connected_faces = connected_faces.copied().collect::<Vec<_>>();
                connected_faces.sort_unstable_by(|lhs, rhs| {
                    let lhs_face_center = face_centers[lhs] - face_centers[&face];
                    let rhs_face_center = face_centers[rhs] - face_centers[&face];

                    face_normal
                        .dot(&rhs_face_center)
                        .partial_cmp(&face_normal.dot(&lhs_face_center))
                        .unwrap()
                });
                traversal_queue.push_back(connected_faces[0]);
            } else {
                // Traverse directly
                if let Some(connected_face) = connected_faces.next() {
                    traversal_queue.push_back(*connected_face);
                }
            }
        }
    }

    interior_faces.into()
}