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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
use crate::mesh::{DefaultEdgePayload, DefaultFacePayload, HalfEdge, MeshTypeHalfEdge};
// TODO: Adjust this to not be halfedge-specific
/// A trait for lofting a mesh.
pub trait MeshLoft<T: MeshTypeHalfEdge<Mesh = Self>>
where
T::EP: DefaultEdgePayload,
T::FP: DefaultFacePayload,
{
/// This will walk clockwise (backwards) along the given boundary and add a "hem" made from triangles.
/// The payloads are given using the iterator.
///
/// `start` must be an edge on the boundary pointing to the first vertex to be connected with the hem.
///
/// Returns the edge pointing from the first inserted vertex to the target of `start`.
/// If the iterator is empty, return `start` instead.
///
/// If `shift` is true, the first inserted triangle will be with the tip pointing to the target of `start`.
/// Otherwise, the first triangle will include the edge `start`.
/// This doesn't affect the number of triangles but shifts the "hem" by one.
fn loft_tri_back(
&mut self,
start: T::E,
shift: bool,
vp: impl IntoIterator<Item = T::VP>,
) -> T::E {
// TODO: a more efficient implementation could bulk-insert everything at once
// TODO: assertions
let mut input = start;
let mut first = true;
let mut iter = vp.into_iter();
let mut pos = iter.next();
let mut ret = start;
if shift && pos.is_some() {
let output = self.edge(input).next_id();
self.add_vertex_via_edge_default(input, output, pos.unwrap());
first = false;
ret = self.edge(output).prev_id();
pos = iter.next();
}
while pos.is_some() {
let output = self.edge(input).next_id();
self.add_vertex_via_edge_default(input, output, pos.unwrap());
let input_next = self.edge(input).next_id();
input = self.edge(input).prev_id();
// the first one shouldn't connect to the previous
if !first {
self.close_face_default(output, input_next, false);
} else {
ret = self.edge(output).prev_id();
}
pos = iter.next();
// the last one also shouldn't connect to the next
if pos.is_some() || shift {
self.close_face_default(input_next, input, false);
}
first = false;
}
ret
}
/// Like `loft_tri_back` but closes the "hem" with a face.
fn loft_tri_back_closed(&mut self, start: T::E, vp: impl IntoIterator<Item = T::VP>) -> T::E {
let e = self.loft_tri_back(start, false, vp);
let outside = self.edge(e).prev_id();
self.close_face_default(self.edge(e).next(self).next_id(), e, false);
self.close_face_default(self.edge(e).next_id(), outside, false);
e
}
/// This will walk counter-clockwise along the given boundary and add a "hem" made from triangles.
/// The payloads are given using the iterator.
///
/// `start` must be an edge on the boundary pointing to the first vertex to be connected with the hem.
///
/// Returns the edge pointing from the first inserted vertex to the target of `start`.
/// If the iterator is empty, return `start` instead.
///
/// If `shift` is true, the first inserted triangle will be with the tip pointing to the target of `start`.
/// Otherwise, the first triangle will include the edge `start`.
/// This doesn't affect the number of triangles but shifts the "hem" by one.
fn loft_tri(&mut self, start: T::E, shift: bool, vp: impl IntoIterator<Item = T::VP>) -> T::E {
// TODO: a more efficient implementation could bulk-insert everything at once
// TODO: assertions
// output will walk forward around the boundary
let mut output = start;
let mut first = true;
let mut iter = vp.into_iter();
let mut pos = iter.next();
let mut ret = start;
if shift && pos.is_some() {
let input = self.edge(output).prev_id();
self.add_vertex_via_edge_default(input, output, pos.unwrap());
first = false;
ret = self.edge(output).prev_id();
pos = iter.next();
}
while pos.is_some() {
let input = self.edge(output).prev_id();
self.add_vertex_via_edge_default(input, output, pos.unwrap());
// the first one shouldn't connect to the previous
if !first {
self.close_face_default(
self.edge(input).next_id(),
self.edge(input).prev_id(),
false,
);
} else {
ret = self.edge(output).prev_id();
}
let new_output = self.edge(output).next_id();
// only continue if there are more vertices
pos = iter.next();
// the last one also shouldn't connect to the next
if pos.is_some() || shift {
self.close_face_default(output, self.edge(output).prev(self).prev_id(), false);
}
// advance output to the next edge on the boundary
output = new_output;
first = false;
}
ret
}
/// Like `loft_tri` but closes the "hem" with a face.
/// Returns the edge pointing from the first inserted vertex to the second inserted vertex.
fn loft_tri_closed(&mut self, start: T::E, vp: impl IntoIterator<Item = T::VP>) -> T::E {
let e = self.loft_tri(start, false, vp);
let inside = self.edge(e).twin(self).prev_id();
let outside = self.edge(inside).prev(self).prev_id();
self.close_face_default(inside, outside, false);
self.close_face_default(self.edge(e).twin_id(), outside, false);
self.edge(outside).next(self).next_id()
}
/// Walks clockwise along the boundary given by `start` and adds a "hem" made from polygon faces.
/// Each face consists of `n` vertices from the iterator
/// and `m` vertices from the boundary of the existing mesh.
/// Hence, it will create polygon faces with `n+m` vertices each.
///
/// If the iterator is exactly the right length to go once around the mesh, the "hem" will be closed.
///
/// Returns the edge pointing from the second inserted vertex to the first inserted vertex.
///
/// For example, to create a quad loft, use `loft_polygon(start, 2, 2, vp)`.
/// Pentagons with the tip pointing to the boundary can be created with `loft_polygon(start, 3, 2, vp)`
/// while pentagons with the tip pointing away from the boundary can be created with `loft_polygon(start, 2, 3, vp)`.
fn loft_polygon_back(
&mut self,
start: T::E,
n: usize,
m: usize,
vp: impl IntoIterator<Item = T::VP>,
) -> T::E {
assert!(n >= 2);
assert!(m >= 2);
// TODO: implement the special cases of n=1 (insert one vertex only and generate tip) and m=1 (use only one vertex of the boundary and create a fan around it), and even n=0 (without iterator; bridge every second edge with a face) and m=0 (without start; generate a line strip)
// TODO: replace all loft methods with this one. Quad is just n=2, m=2, triangle is two lofts: n=2, m=1 and n=0, m=2
let mut iter = vp.into_iter();
let mut input = start;
let start_vertex = self.edge(start).target_id(self);
if let Some(vp) = iter.next() {
self.add_vertex_via_edge_default(input, self.edge(start).next_id(), vp);
}
let mut ret = start;
loop {
input = self.edge(input).prev_id();
let mut inside = self.edge(input).next(self).next_id();
for _ in 2..n {
let Some(vp) = iter.next() else {
return ret;
};
let (_, e1, _) =
self.add_vertex_via_edge_default(inside, self.edge(inside).next_id(), vp);
inside = e1;
// the edge pointing to the first generated vertex
if ret == start {
ret = self.edge(e1).twin_id();
}
}
for _ in 2..m {
input = self.edge(input).prev_id();
}
let Some(vp) = iter.next() else {
if start_vertex == self.edge(input).target_id(self) {
// reached the start again - close the last vertex!
self.close_face_default(inside, self.edge(input).prev_id(), false);
}
return ret;
};
self.add_vertex_via_edge_default(input, self.edge(input).next_id(), vp);
self.close_face_default(inside, self.edge(input).next_id(), false);
// when n==2, we cannot set the `ret` until now
if ret == start {
ret = self.edge(inside).next(self).twin_id();
}
}
}
/// Walks counter-clockwise along the given boundary and adds a "hem" made from polygon faces.
/// Each face consists of `n` vertices from the iterator
/// and `m` vertices from the boundary of the existing mesh.
/// Hence, it will create polygon faces with `n+m` vertices each.
///
/// If the iterator is exactly the right length to go once around the mesh, the "hem" will be closed.
///
/// Returns the edge pointing from the second inserted vertex to the first inserted vertex.
///
/// For example, to create a quad loft, use `loft_polygon(start, 2, 2, vp)`.
/// Pentagons with the tip pointing to the boundary can be created with `loft_polygon(start, 3, 2, vp)`
/// while pentagons with the tip pointing away from the boundary can be created with `loft_polygon(start, 2, 3, vp)`.
fn loft_polygon(
&mut self,
start: T::E,
n: usize,
m: usize,
vp: impl IntoIterator<Item = T::VP>,
) -> T::E {
assert!(n >= 2);
assert!(m >= 2);
// TODO: implement the special cases of n=1 (insert one vertex only and generate tip) and m=1 (use only one vertex of the boundary and create a fan around it), and even n=0 (without iterator; bridge every second edge with a face) and m=0 (without start; generate a line strip)
// TODO: replace all loft methods with this one. Quad is just n=2, m=2, triangle is two lofts: n=2, m=1 and n=0, m=2
let mut iter = vp.into_iter();
let mut input = start;
let start_vertex = self.edge(start).origin_id();
if let Some(vp) = iter.next() {
self.add_vertex_via_edge_default(self.edge(start).prev_id(), input, vp);
}
let mut ret = start;
loop {
// Move `input` forward along the boundary
input = self.edge(input).next_id();
// TODO: only provisory impl!
assert!(n == 2);
// Initialize `inside` edge
let mut inside = self.edge(input).prev(self).prev_id();
for _ in 2..n {
let Some(vp) = iter.next() else {
return ret;
};
// Insert vertex between `inside`'s previous edge and `inside`
let prev_edge = self.edge(inside).prev_id();
let (_, e1, _) = self.add_vertex_via_edge_default(prev_edge, inside, vp);
inside = e1;
// Set `ret` to the edge pointing to the first generated vertex
if ret == start {
ret = self.edge(e1).twin_id();
}
}
// TODO: only provisory impl!
assert!(m == 2);
// Move `input` forward along the boundary for `m - 2` steps
for _ in 2..m {
input = self.edge(input).next_id();
}
let Some(vp) = iter.next() else {
if start_vertex == self.edge(input).origin_id() {
// Reached the start again - close the last face
self.close_face_default(input, self.edge(inside).prev_id(), false);
}
return ret;
};
// Insert a new vertex between the previous edge of `input` and `input`
self.add_vertex_via_edge_default(self.edge(input).prev_id(), input, vp);
// Close the face between `inside` and the new vertex
self.close_face_default(
self.edge(input).prev(self).twin_id(),
self.edge(inside).prev_id(),
false,
);
// When `n == 2`, we cannot set `ret` until now
if ret == start {
ret = self.edge(inside).prev(self).twin_id();
}
}
}
}
// TODO: tests!