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
//! Geometry computation methods for surface meshes.
//!
//! This module contains methods for computing derived mesh data from raw vertices and faces:
//! - Triangulation (fan triangulation for arbitrary polygons)
//! - Face and vertex normals
//! - Corner normals for shading
//! - Edge extraction and classification for wireframe rendering
//! - Tangent basis computation for intrinsic vectors
use glam::Vec3;
use std::collections::HashSet;
use super::{ShadeStyle, SurfaceMesh};
impl SurfaceMesh {
// === Computation methods ===
/// Recomputes all derived data (triangulation, normals, edges).
pub(super) fn recompute(&mut self) {
if !self.needs_recompute {
return;
}
self.compute_triangulation();
self.compute_face_normals();
self.compute_vertex_normals();
self.compute_corner_normals();
self.compute_edges();
self.compute_edge_is_real();
self.needs_recompute = false;
}
/// Computes triangulation using fan triangulation.
///
/// For a polygon with vertices [v0, v1, v2, v3, ...], creates triangles:
/// [v0, v1, v2], [v0, v2, v3], [v0, v3, v4], ...
fn compute_triangulation(&mut self) {
self.triangulation.clear();
self.face_to_tri_range.clear();
for face in &self.faces {
let start_tri = self.triangulation.len();
if face.len() >= 3 {
let v0 = face[0];
// Fan triangulation: create (n-2) triangles for n-gon
for i in 1..(face.len() - 1) {
self.triangulation.push([v0, face[i], face[i + 1]]);
}
}
let end_tri = self.triangulation.len();
self.face_to_tri_range.push(start_tri..end_tri);
}
}
/// Computes face normals using cross product of first two edges.
fn compute_face_normals(&mut self) {
self.face_normals.clear();
self.face_normals.reserve(self.faces.len());
for face in &self.faces {
if face.len() >= 3 {
let v0 = self.vertices[face[0] as usize];
let v1 = self.vertices[face[1] as usize];
let v2 = self.vertices[face[2] as usize];
let e1 = v1 - v0;
let e2 = v2 - v0;
let normal = e1.cross(e2).normalize_or_zero();
self.face_normals.push(normal);
} else {
self.face_normals.push(Vec3::ZERO);
}
}
}
/// Computes vertex normals as area-weighted average of incident face normals.
fn compute_vertex_normals(&mut self) {
self.vertex_normals.clear();
self.vertex_normals.resize(self.vertices.len(), Vec3::ZERO);
for (face_idx, face) in self.faces.iter().enumerate() {
if face.len() < 3 {
continue;
}
let face_normal = self.face_normals[face_idx];
// Compute face area using triangulation
let v0 = self.vertices[face[0] as usize];
let mut area = 0.0;
for i in 1..(face.len() - 1) {
let v1 = self.vertices[face[i] as usize];
let v2 = self.vertices[face[i + 1] as usize];
let e1 = v1 - v0;
let e2 = v2 - v0;
area += e1.cross(e2).length() * 0.5;
}
// Add weighted normal to each vertex of this face
let weighted_normal = face_normal * area;
for &vi in face {
self.vertex_normals[vi as usize] += weighted_normal;
}
}
// Normalize all vertex normals
for normal in &mut self.vertex_normals {
*normal = normal.normalize_or_zero();
}
}
/// Computes corner normals (per-corner of each triangle).
pub(super) fn compute_corner_normals(&mut self) {
self.corner_normals.clear();
self.corner_normals.reserve(self.triangulation.len() * 3);
for (face_idx, range) in self.face_to_tri_range.iter().enumerate() {
let face_normal = self.face_normals[face_idx];
for tri_idx in range.clone() {
let tri = self.triangulation[tri_idx];
for vi in tri {
// For tri-flat, we use face normals; for smooth, we use vertex normals
// Store both options - the shader will choose based on shade_style
match self.shade_style {
ShadeStyle::Smooth => {
self.corner_normals.push(self.vertex_normals[vi as usize]);
}
ShadeStyle::Flat | ShadeStyle::TriFlat => {
self.corner_normals.push(face_normal);
}
}
}
}
}
}
/// Computes `edge_is_real` flags for wireframe rendering.
/// Marks which edges in the triangulation are real polygon edges vs internal.
fn compute_edge_is_real(&mut self) {
self.edge_is_real.clear();
self.edge_is_real.reserve(self.triangulation.len() * 3);
for range in &self.face_to_tri_range {
let num_tris = range.end - range.start;
for (j, _tri_idx) in range.clone().enumerate() {
// For fan triangulation from v0:
// Triangle j has vertices [v0, v_{j+1}, v_{j+2}]
// Edge 0 (v0 -> v_{j+1}): real only if j == 0
// Edge 1 (v_{j+1} -> v_{j+2}): always real (it's a polygon edge)
// Edge 2 (v_{j+2} -> v0): real only if j == num_tris - 1
let edge0_real = if j == 0 { 1.0 } else { 0.0 };
let edge1_real = 1.0; // middle edge always real
let edge2_real = if j == num_tris - 1 { 1.0 } else { 0.0 };
// Each triangle corner gets the edge_is_real for all three edges
// This matches C++ Polyscope's approach
let edge_real = Vec3::new(edge0_real, edge1_real, edge2_real);
self.edge_is_real.push(edge_real);
self.edge_is_real.push(edge_real);
self.edge_is_real.push(edge_real);
}
}
}
/// Computes unique edges as sorted pairs.
fn compute_edges(&mut self) {
let mut edge_set: HashSet<(u32, u32)> = HashSet::new();
for face in &self.faces {
let n = face.len();
for i in 0..n {
let v0 = face[i];
let v1 = face[(i + 1) % n];
// Store as sorted pair to avoid duplicates
let edge = if v0 < v1 { (v0, v1) } else { (v1, v0) };
edge_set.insert(edge);
}
}
self.edges = edge_set.into_iter().collect();
self.edges.sort_unstable(); // Sort for deterministic ordering
}
/// Compute default per-face tangent basis from first edge direction.
#[must_use]
pub fn compute_face_tangent_basis(&self) -> (Vec<Vec3>, Vec<Vec3>) {
let mut basis_x = Vec::with_capacity(self.faces.len());
let mut basis_y = Vec::with_capacity(self.faces.len());
for (face_idx, face) in self.faces.iter().enumerate() {
if face.len() >= 3 {
let v0 = self.vertices[face[0] as usize];
let v1 = self.vertices[face[1] as usize];
let normal = self.face_normals[face_idx];
let bx = (v1 - v0).normalize_or_zero();
let by = normal.cross(bx).normalize_or_zero();
basis_x.push(bx);
basis_y.push(by);
} else {
basis_x.push(Vec3::X);
basis_y.push(Vec3::Y);
}
}
(basis_x, basis_y)
}
/// Compute default per-vertex tangent basis from area-weighted face bases.
#[must_use]
pub fn compute_vertex_tangent_basis(&self) -> (Vec<Vec3>, Vec<Vec3>) {
let (face_bx, _face_by) = self.compute_face_tangent_basis();
let mut vert_bx = vec![Vec3::ZERO; self.vertices.len()];
for (face_idx, face) in self.faces.iter().enumerate() {
if face.len() < 3 {
continue;
}
// Compute face area
let v0 = self.vertices[face[0] as usize];
let mut area = 0.0f32;
for i in 1..(face.len() - 1) {
let v1 = self.vertices[face[i] as usize];
let v2 = self.vertices[face[i + 1] as usize];
area += (v1 - v0).cross(v2 - v0).length() * 0.5;
}
let weighted_bx = face_bx[face_idx] * area;
for &vi in face {
vert_bx[vi as usize] += weighted_bx;
}
}
// Orthonormalize against vertex normals
let mut basis_x = Vec::with_capacity(self.vertices.len());
let mut basis_y = Vec::with_capacity(self.vertices.len());
for (i, normal) in self.vertex_normals.iter().enumerate() {
let mut bx = vert_bx[i];
// Project out normal component and normalize
bx -= *normal * normal.dot(bx);
bx = bx.normalize_or_zero();
// If degenerate, pick an arbitrary tangent
if bx.length_squared() < 1e-6 {
bx = if normal.x.abs() < 0.9 {
Vec3::X
} else {
Vec3::Y
};
bx -= *normal * normal.dot(bx);
bx = bx.normalize_or_zero();
}
let by = normal.cross(bx).normalize_or_zero();
basis_x.push(bx);
basis_y.push(by);
}
(basis_x, basis_y)
}
}