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
use super::basics::FaceBasics;
use crate::{
math::{LineSegment2D, Polygon, Scalar, TransformTrait, Vector, Vector3D, Vector3DIteratorExt},
mesh::{IndexedVertex2D, MeshType3D, VertexBasics},
};
use itertools::Itertools;
// TODO: Many Face3d functions should be part of n dimensions, not just 3d.
/// A face with vertices that have 3d positions.
pub trait Face3d<T: MeshType3D<Face = Self>>: FaceBasics<T> {
/// Get an iterator over the cross products of the vertices of the face.
fn vertices_crossed<'a>(
&'a self,
mesh: &'a T::Mesh,
) -> impl Iterator<Item = T::Vec> + 'a + Clone + ExactSizeIterator
where
T::Vertex: 'a,
{
self.vertices(mesh)
.circular_tuple_windows::<(_, _, _)>()
.map(|(a, b, c)| (b.pos() - a.pos()).cross(&(c.pos() - a.pos())))
}
/// Whether the face is convex. Ignores order.
fn is_convex(&self, mesh: &T::Mesh) -> bool {
// TODO: is this correct?
// TODO: collinear points cause problems
self.vertices_crossed(mesh)
.circular_tuple_windows::<(_, _)>()
.map(|w| w.0.dot(&w.1).is_positive())
.all_equal()
}
/// Whether the face is planar.
fn is_planar(&self, mesh: &T::Mesh, eps: T::S) -> bool {
// TODO: is this correct?
// TODO: collinear points cause problems
let three: Vec<_> = self.vertices(mesh).take(3).map(|v| v.pos()).collect();
let n = (three[1] - three[0]).cross(&(three[2] - three[0]));
self.vertices(mesh).skip(2).all(|v| {
let v = v.pos();
(v - three[0]).dot(&n).abs() < eps
})
}
/// Whether the face is planar.
fn is_planar2(&self, mesh: &T::Mesh) -> bool {
// TODO: eps?
self.is_planar(mesh, T::S::EPS.sqrt())
}
/// Whether the face is self-intersecting.
/// This is a quite slow O(n^2) method. Use with caution.
fn has_self_intersections(&self, mesh: &T::Mesh) -> bool {
// TODO: Test this
self.vertices_2d(mesh)
.circular_tuple_windows::<(_, _)>()
.tuple_combinations::<(_, _)>()
.any(|(((a1, _), (a2, _)), ((b1, _), (b2, _)))| {
let l1 = LineSegment2D::<T::Vec2>::new(a1, a2);
let l2 = LineSegment2D::<T::Vec2>::new(b1, b2);
let res = l1.intersect_line(&l2, T::S::EPS, -T::S::EPS);
res.is_some()
})
}
/// Whether the face is simple, i.e., doesn't self-intersect or have holes.
/// Testing this is quite slow O(n^2). Use with caution.
fn is_simple(&self, mesh: &T::Mesh) -> bool {
!self.has_holes() && !self.has_self_intersections(mesh)
}
/// A fast methods to get the surface normal, but will only work for convex faces.
fn normal_naive(&self, mesh: &T::Mesh) -> T::Vec {
debug_assert!(self.is_planar2(mesh));
debug_assert!(self.is_convex(mesh));
let three: Vec<_> = self.vertices(mesh).take(3).map(|v| v.pos()).collect();
three[1].normal(three[0], three[2])
}
/// Get the normal of the face. Assumes the face is planar.
/// Uses Newell's method to handle concave faces.
/// PERF: Why not faster? Can't we find the normal using 3 vertices?
fn normal(&self, mesh: &T::Mesh) -> T::Vec {
// TODO: overload this in a way that allows different dimensions
// TODO: allows only for slight curvature...
debug_assert!(
self.may_be_curved() || self.is_planar2(mesh),
"Face is not planar {:?}",
self
);
let normal = self.vertices(mesh).map(|v| v.pos()).normal();
/* assert!(
normal.length_squared() >= T::S::EPS,
"Degenerated face {} {:?}",
self.id(),
self.vertices(mesh).map(|v| v.pos()).collect::<Vec<_>>()
);*/
normal
}
// TODO: check for degenerated faces; empty triangles, collinear points etc...
/*pub fn vertices_2d<'a, V: IndexType, P: Payload>(
&'a self,
mesh: &'a Mesh<E, usize, F, P>,
) -> impl Iterator<Item = T::Vec> + Clone + ExactSizeIterator + 'a
where
T::Vec: Vector2D<S = T::S>,
{
assert!(self.is_planar2(mesh));
assert!(T::Vec::dimensions() == 2);
self.vertices(mesh).map(|v| *v.vertex())
}*/
/// Get an iterator over the 2d vertices of the face rotated to the XY plane.
fn vertices_2d<'a>(
&'a self,
mesh: &'a T::Mesh,
) -> impl Iterator<Item = (T::Vec2, T::V)> + Clone + ExactSizeIterator + 'a {
// PERF: Calculating the normal from all vertices in the face is slow. Maybe use a faster normal impl? Also, we're traversing the face twice!
let z_axis = T::Vec::new(0.0.into(), 0.0.into(), 1.0.into());
let rotation = <T::Trans as TransformTrait<T::S, 3>>::from_rotation_arc(
Face3d::normal(self, mesh).normalize(),
z_axis.normalize(),
);
self.vertices(mesh)
.map(move |v| (rotation.apply(v.pos()).vec2(), v.id()))
}
/// Get a vector of 2d vertices of the face rotated to the XY plane.
fn vec2s<'a>(&'a self, mesh: &'a T::Mesh) -> Vec<IndexedVertex2D<T::V, T::Vec2>> {
self.vertices_2d(mesh)
.map(|(p, i)| IndexedVertex2D::<T::V, T::Vec2>::new(p, i))
.collect()
}
/// Returns the polygon of the face rotated to the XY plane.
fn as_polygon(&self, mesh: &T::Mesh) -> T::Poly {
<T::Poly as Polygon<T::Vec2>>::from_iter(self.vec2s(mesh).iter().map(|v| v.vec))
}
}