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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
use fj_math::{Scalar, Winding};
use pretty_assertions::assert_eq;
use crate::{path::SurfacePath, stores::Handle};
use super::{HalfEdge, Surface};
/// A cycle of connected half-edges
#[derive(Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
pub struct Cycle {
surface: Handle<Surface>,
half_edges: Vec<HalfEdge>,
}
impl Cycle {
/// Create a new cycle
///
/// # Panics
///
/// Panic, if the end of each half-edge does not connect to the beginning of
/// the next one.
pub fn new(
surface: Handle<Surface>,
half_edges: impl IntoIterator<Item = HalfEdge>,
) -> Self {
let half_edges = half_edges.into_iter().collect::<Vec<_>>();
// Verify, that the curves of all edges are defined in the correct
// surface.
for edge in &half_edges {
assert_eq!(
surface.id(),
edge.curve().surface().id(),
"Edges in cycle not defined in same surface"
);
}
if half_edges.len() != 1 {
// Verify that all edges connect.
for half_edges in half_edges.windows(2) {
// Can't panic, as we passed `2` to `windows`.
//
// Can be cleaned up, once `array_windows` is stable"
// https://doc.rust-lang.org/std/primitive.slice.html#method.array_windows
let [a, b] = [&half_edges[0], &half_edges[1]];
let [_, prev] = a.vertices();
let [next, _] = b.vertices();
assert_eq!(
prev.surface_form(),
next.surface_form(),
"Edges in cycle do not connect"
);
}
// Verify that the edges form a cycle
if let Some(first) = half_edges.first() {
if let Some(last) = half_edges.last() {
let [first, _] = first.vertices();
let [_, last] = last.vertices();
assert_eq!(
first.surface_form(),
last.surface_form(),
"Edges do not form a cycle"
);
}
}
}
Self {
surface,
half_edges,
}
}
/// Access the surface that this cycle is in
pub fn surface(&self) -> &Handle<Surface> {
&self.surface
}
/// Access the half-edges that make up the cycle
pub fn half_edges(&self) -> impl Iterator<Item = &HalfEdge> + '_ {
self.half_edges.iter()
}
/// Indicate the cycle's winding, assuming a right-handed coordinate system
///
/// Please note that this is not *the* winding of the cycle, only one of the
/// two possible windings, depending on the direction you look at the
/// surface that the cycle is defined on from.
pub fn winding(&self) -> Winding {
// The cycle could be made up of one or two circles. If that is the
// case, the winding of the cycle is determined by the winding of the
// first circle.
if self.half_edges.len() < 3 {
let first = self
.half_edges()
.next()
.expect("Invalid cycle: expected at least one half-edge");
let [a, b] = first.vertices();
let edge_direction_positive = a.position() < b.position();
let circle = match first.curve().path() {
SurfacePath::Circle(circle) => circle,
SurfacePath::Line(_) => unreachable!(
"Invalid cycle: less than 3 edges, but not all are circles"
),
};
let cross_positive = circle.a().cross2d(&circle.b()) > Scalar::ZERO;
if edge_direction_positive == cross_positive {
return Winding::Ccw;
} else {
return Winding::Cw;
}
}
// Now that we got the special case out of the way, we can treat the
// cycle as a polygon:
// https://stackoverflow.com/a/1165943
let mut sum = Scalar::ZERO;
for half_edge in self.half_edges.windows(2) {
// Can't panic, as we passed `2` to `windows`.
//
// Can be cleaned up, once `array_windows` is stable:
// https://doc.rust-lang.org/std/primitive.slice.html#method.array_windows
let [a, b] = [&half_edge[0], &half_edge[1]];
let [a, b] = [a, b].map(|half_edge| {
let [vertex, _] = half_edge.vertices();
vertex.surface_form().position()
});
sum += (b.u - a.u) * (b.v + a.v);
}
if sum > Scalar::ZERO {
return Winding::Cw;
}
if sum < Scalar::ZERO {
return Winding::Ccw;
}
unreachable!("Encountered invalid cycle: {self:#?}");
}
/// Consume the cycle and return its half-edges
pub fn into_half_edges(self) -> impl Iterator<Item = HalfEdge> {
self.half_edges.into_iter()
}
}