geop_core_topology/validation/face_orientation.rs
1use geop_core_math::{
2 geop_error::{GeopError, GeopResult, WithContext},
3 scalars::Scalar,
4 vector::Vector3,
5};
6
7use crate::{
8 FaceId, Model, ShellId, SolidId,
9 boundary::BoundaryType,
10 contains::{
11 face::face_interior_point_where,
12 shell::{Beside, on_solid_boundary_besides, solid_contains_beside},
13 },
14 uv_loop::loop_signed_area,
15 validation::ValidationParameters,
16};
17
18/// Fixed seed for the ray casting behind both checks. `solid_contains_beside`
19/// and `face_interior_point` retry until they find a ray grazing nothing, so
20/// their answers are seed-independent; a constant keeps validation
21/// reproducible run to run.
22const SEED: u64 = 0x0F1E_0D1E_0000_0001;
23
24/// Checks that every face's outer boundary runs counter-clockwise in
25/// `(u, v)` and every hole runs clockwise.
26///
27/// This is the convention the kernel *computes with*, not merely a tidiness
28/// rule: `Model::splice_edge_into_face` uses a ring's signed area to decide
29/// whether splitting a hole produced a new face or another hole — the two
30/// rings pass through the same vertices and share the same edge, so nothing
31/// weaker can tell them apart — and the debug renderer uses it to inset a
32/// coedge's trim curve inward. A face whose winding is inverted is
33/// structurally perfect and every other check accepts it, while every
34/// operation that asks which side the material is on gets the opposite
35/// answer.
36pub fn check_loop_winding(
37 _params: &ValidationParameters,
38 errors: &mut Vec<GeopError>,
39 model: &Model,
40) {
41 for (&face_id, face) in &model.faces {
42 for (which, boundary, want_positive) in
43 std::iter::once(("outer".to_string(), face.outer, true)).chain(
44 face.holes
45 .iter()
46 .enumerate()
47 .map(|(i, &h)| (format!("hole {i}"), h, false)),
48 )
49 {
50 // A bare-vertex boundary encloses nothing and has no winding.
51 let BoundaryType::Loop(anchor) = boundary else {
52 continue;
53 };
54 // A ring that walks every one of its edges twice — out along
55 // each and back — encloses no area by construction, so it has no
56 // winding to check. `Model::splice_edge_into_face` builds exactly
57 // these: an imprinted edge whose endpoints are not yet on the
58 // face becomes a two-coedge dangling loop, and a spur inserts the
59 // same pair into an existing ring. Both are "wire" topology
60 // rather than a trim boundary, and demanding a sign from them
61 // reports every imprint as broken.
62 if traverses_each_edge_twice(model, anchor) {
63 continue;
64 }
65 let area = match loop_signed_area(model, anchor) {
66 Ok(area) => area,
67 Err(e) => {
68 errors.push(e.with_context(format!(
69 "face {face_id}'s {which} boundary, measuring its winding"
70 )));
71 continue;
72 }
73 };
74 let ok = if want_positive {
75 area.definitely_greater(Scalar::ZERO)
76 } else {
77 area.definitely_less(Scalar::ZERO)
78 };
79 if !ok {
80 let expected = if want_positive {
81 "counter-clockwise (positive)"
82 } else {
83 "clockwise (negative)"
84 };
85 errors.push(GeopError::new(format!(
86 "face {face_id}'s {which} boundary has signed area {area:?}, but must be {expected} — an outer loop bounds material and a hole removes it, and that is what the sign records"
87 )));
88 }
89 }
90 }
91}
92
93/// Whether every edge in the ring anchored at `anchor` is traversed twice —
94/// the signature of a dangling loop or a spur, which encloses no area.
95fn traverses_each_edge_twice(model: &Model, anchor: crate::CoedgeId) -> bool {
96 let mut counts: std::collections::HashMap<crate::EdgeId, usize> =
97 std::collections::HashMap::new();
98 let cap = model.coedges.len() + 1;
99 let mut seen = 0usize;
100 for coedge_id in model.iterate_loop_coedges(anchor).take(cap) {
101 seen += 1;
102 let Some(coedge) = model.coedges.get(&coedge_id) else {
103 return false;
104 };
105 match coedge.geometry {
106 crate::CoedgeGeometry::Edge(edge_id) => {
107 *counts.entry(edge_id).or_default() += 1;
108 }
109 // A degenerate vertex coedge bounds nothing either way.
110 crate::CoedgeGeometry::Vertex(_) => {}
111 }
112 }
113 seen < cap && !counts.is_empty() && counts.values().all(|&n| n == 2)
114}
115
116/// Checks that every face's normal points *out* of the solid it bounds.
117///
118/// A face's normal comes from its surface's parametrization (`Su x Sv`), and
119/// nothing about a well-formed loop constrains which way it ends up facing.
120/// An inverted face still validates structurally, still renders, and still
121/// has a perfectly good boundary — but every operation that asks which side
122/// the material is on gets the wrong answer, which for a boolean means the
123/// face is kept when it should be dropped, or kept facing into the result.
124///
125/// Decided at an interior point of the face, by which side of the face the
126/// solid is on there (see [`normal_points_outward`]).
127pub fn check_normals_point_outward(
128 params: &ValidationParameters,
129 errors: &mut Vec<GeopError>,
130 model: &Model,
131) {
132 // A sheet bounds nothing, so either side of it may face anywhere.
133 for (&shell_id, shell) in &model.shells {
134 // Measured against the whole solid: a void's faces point into the
135 // void, out of the material around it.
136 let Some(solid_id) = shell.solid else {
137 continue;
138 };
139 for &face_id in &shell.faces {
140 match normal_points_outward(params, model, solid_id, shell_id, face_id) {
141 Ok(Some(Outward::No(inward))) => {
142 let Inward {
143 point,
144 uv,
145 derivatives,
146 normal,
147 ray,
148 } = *inward;
149 errors.push(GeopError::new(format!(
150 "face {face_id}'s normal points into solid {solid_id} (from its shell {shell_id}) rather than out of it: at its interior point {point:?}, (u, v) = {uv:?} where (S_u, S_v) = {derivatives:?}, the normal is {normal:?}, and the solid is on the normal's side of the face there: the ray along {:?} from it crosses {} face(s) past it, {:?}",
151 ray.direction,
152 ray.crossings.len(),
153 ray.crossings
154 )));
155 }
156 Ok(_) => {}
157 Err(e) => errors.push(e.with_context(format!(
158 "face {face_id} of shell {shell_id}, deciding which side of it solid {solid_id} is on"
159 ))),
160 }
161 }
162 }
163}
164
165/// Whether a face's normal points out of its solid, as
166/// [`normal_points_outward`] found it.
167#[derive(Clone, Debug)]
168pub enum Outward {
169 Yes,
170 /// It points in: at `point`, inside the face, the normal is `normal`,
171 /// and `ray`, leaving the face to that side, found the solid.
172 No(Box<Inward>),
173}
174
175/// Where and how a normal was found pointing in (see [`Outward::No`]).
176#[derive(Clone, Debug)]
177pub struct Inward {
178 pub point: Vector3,
179 pub uv: (Scalar, Scalar),
180 /// `(S_u, S_v)` there: the parametrization the normal comes from.
181 pub derivatives: (Vector3, Vector3),
182 pub normal: Vector3,
183 pub ray: Beside,
184}
185
186/// Whether the normal of face `face_id` of shell `shell_id` points out of
187/// the solid `solid_id` — `None` for a face without an interior point, which
188/// `check_faces_have_interior` reports, or without one clear of the rest of
189/// the solid's boundary.
190///
191/// Decided at an interior point of the face: the normal points out exactly
192/// when the solid is not on its side of the face there
193/// ([`solid_contains_beside`]). That is a local fact, the limit as the
194/// distance off the face goes to zero, and it is decided by a ray leaving
195/// the face, not by a point some distance off it: on a non-convex solid a
196/// point any fixed distance off the face may lie in another part of it.
197///
198/// The interior point is a free choice, and one on the solid's boundary
199/// elsewhere too is a bad one: a ray from the pole of an inscribed sphere,
200/// lying in the cube's face, passes through that vertex at its start. The
201/// first point offered that is on nothing else is taken
202/// ([`on_solid_boundary_besides`]).
203pub fn normal_points_outward(
204 params: &ValidationParameters,
205 model: &Model,
206 solid_id: SolidId,
207 shell_id: ShellId,
208 face_id: FaceId,
209) -> GeopResult<Option<Outward>> {
210 let Some(face) = model.faces.get(&face_id) else {
211 return Ok(None);
212 };
213 let clear = |u: Scalar, v: Scalar| -> GeopResult<bool> {
214 Ok(!on_solid_boundary_besides(
215 model,
216 solid_id,
217 face_id,
218 &face.surface.evaluate(u, v)?,
219 params.max_nodes,
220 params.min_subdivision_size,
221 SEED,
222 )?)
223 };
224 let Ok(Some((u, v))) = face_interior_point_where(
225 model,
226 face_id,
227 params.max_nodes,
228 params.min_subdivision_size,
229 SEED,
230 clear,
231 ) else {
232 return Ok(None);
233 };
234 let (point, normal) = (face.surface.evaluate(u, v)?, face.surface.normal(u, v)?);
235 let beside = solid_contains_beside(
236 model,
237 solid_id,
238 shell_id,
239 face_id,
240 point,
241 normal,
242 params.max_nodes,
243 params.min_subdivision_size,
244 SEED,
245 )
246 .with_context(&|e: GeopError| {
247 e.with_context(format!(
248 "normal_points_outward(face={face_id}, at (u, v) = ({u:?}, {v:?}) of a surface over {:?} x {:?})",
249 face.surface.domain_u(),
250 face.surface.domain_v()
251 ))
252 })?;
253 Ok(Some(if beside.inside {
254 Outward::No(Box::new(Inward {
255 point,
256 uv: (u, v),
257 derivatives: face.surface.derivatives(u, v)?,
258 normal,
259 ray: beside,
260 }))
261 } else {
262 Outward::Yes
263 }))
264}