geop_core_topology/validation/
disjointness_check.rs

1use geop_core_geometry::intersection::{curve_curve_intersect, curve_surface_intersect};
2use geop_core_math::{
3    geop_error::{GeopError, GeopResult},
4    vector::Vector3,
5};
6
7use crate::{
8    Body, EdgeId, FaceId, Model, VertexId,
9    contains::face::{PointClassification, face_contains},
10    validation::{ValidationParameters, body_groups},
11};
12
13/// Fixed seed for the ray casting behind the edge-inside-face-trim test.
14/// `face_contains` retries until it finds a ray grazing nothing, so the
15/// answer is seed-independent; a constant keeps validation reproducible.
16const EDGE_ON_FACE_SEED: u64 = 0x0EDF_ACE0_0000_0001;
17
18/// Whether `point` lands on an existing vertex — `point` must be evaluated
19/// on the intersection search's own *full* returned `t` interval, not
20/// collapsed to its midpoint first: both the search's converged `t` and the
21/// vertex's own position already carry an honest uncertainty bound (that's
22/// the whole point of interval arithmetic), and for a genuine shared vertex
23/// those two bounds should simply overlap on their own — no separate
24/// distance-epsilon fudge needed. Collapsing to a single representative
25/// point first would throw that width away and require compensating for it
26/// artificially, which is exactly the kind of epsilon this codebase avoids
27/// (see `AGENTS.md`).
28fn coincides_with_a_vertex(model: &Model, point: &Vector3) -> bool {
29    model
30        .vertices
31        .values()
32        .any(|v| point.could_be_equal(&v.point))
33}
34
35/// Checks that no two (distinct) vertices of one body could overlap — every
36/// vertex is meant to occupy a genuinely distinct position; a shared
37/// position should be represented by reusing the same `VertexId`, not by
38/// two coincident ones.
39pub fn check_vertices_disjoint(
40    _params: &ValidationParameters,
41    errors: &mut Vec<GeopError>,
42    model: &Model,
43) {
44    for group in body_groups(model) {
45        check_vertices_of_body_disjoint(errors, model, &group.vertices);
46    }
47}
48
49fn check_vertices_of_body_disjoint(errors: &mut Vec<GeopError>, model: &Model, ids: &[VertexId]) {
50    for i in 0..ids.len() {
51        for j in (i + 1)..ids.len() {
52            let a = model.vertices[&ids[i]].point;
53            let b = model.vertices[&ids[j]].point;
54            if a.could_be_equal(&b) {
55                errors.push(GeopError::new(format!(
56                    "vertex {} and vertex {} could overlap — they should be the same vertex, or genuinely disjoint",
57                    ids[i].0, ids[j].0
58                )));
59            }
60        }
61    }
62}
63
64/// Checks every distinct pair of edges of one body: two edges that are (at
65/// least partly) coincident — `Intersections::Coincident` — always fail;
66/// otherwise, every intersection point found must coincide with an existing
67/// vertex (edges are only allowed to touch each other at shared vertices,
68/// never crossing through some other point).
69pub fn check_edges_disjoint(
70    params: &ValidationParameters,
71    errors: &mut Vec<GeopError>,
72    model: &Model,
73) {
74    for group in body_groups(model) {
75        check_edges_of_body_disjoint(params, errors, model, &group.edges);
76    }
77}
78
79fn check_edges_of_body_disjoint(
80    params: &ValidationParameters,
81    errors: &mut Vec<GeopError>,
82    model: &Model,
83    ids: &[EdgeId],
84) {
85    for i in 0..ids.len() {
86        for j in (i + 1)..ids.len() {
87            let edge_a = &model.edges[&ids[i]];
88            let edge_b = &model.edges[&ids[j]];
89            let intersections = match curve_curve_intersect(
90                &edge_a.curve,
91                &edge_b.curve,
92                params.max_edge_edge_intersection_samples,
93                params.max_nodes,
94                params.min_subdivision_size,
95            ) {
96                Ok(v) => v,
97                Err(e) => {
98                    errors.push(e.with_context(format!("edge {} x edge {}", ids[i], ids[j])));
99                    continue;
100                }
101            };
102
103            if intersections.is_coincident() {
104                errors.push(GeopError::new(format!(
105                    "edge {} and edge {} are coincident along an arc: {:?}, of domains {:?} and {:?}",
106                    ids[i].0,
107                    ids[j].0,
108                    intersections,
109                    edge_a.curve.domain(),
110                    edge_b.curve.domain(),
111                )));
112                continue;
113            }
114
115            for (t_a, _t_b) in intersections.into_vec() {
116                let point = match edge_a.curve.evaluate(t_a) {
117                    Ok(p) => p,
118                    Err(e) => {
119                        errors.push(e.with_context(format!("edge {} x edge {}", ids[i], ids[j])));
120                        continue;
121                    }
122                };
123                if !coincides_with_a_vertex(model, &point) {
124                    errors.push(GeopError::new(format!(
125                        "edge {} and edge {} intersect at a point that is not an existing vertex",
126                        ids[i].0, ids[j].0
127                    )));
128                }
129            }
130        }
131    }
132}
133
134/// Checks every edge x face pair of one body: every intersection point found
135/// must coincide with an existing vertex (an edge may only pierce a face's
136/// surface at a shared vertex, never elsewhere).
137///
138/// A pair where the edge is *already* a declared boundary coedge of the
139/// face is skipped rather than run through `curve_surface_intersect` at
140/// all: a curve entirely embedded in a surface is a continuum of
141/// coincidence, not a finite set of points, and empirically the search
142/// doesn't reliably resolve that to either "hit the cap" or "found no
143/// points" — it can converge to some wide, still-unresolved sub-interval
144/// instead, whose midpoint lands nowhere meaningful. Declared boundary
145/// relationships don't need re-verifying geometrically here anyway (that's
146/// `check_curves_and_surfaces_vertices`'s and the sampling check's job).
147pub fn check_edges_and_faces_consistent(
148    params: &ValidationParameters,
149    errors: &mut Vec<GeopError>,
150    model: &Model,
151) {
152    for group in body_groups(model) {
153        for &edge_id in &group.edges {
154            for &face_id in &group.faces {
155                check_edge_and_face_consistent(params, errors, model, edge_id, face_id);
156            }
157        }
158    }
159}
160
161fn check_edge_and_face_consistent(
162    params: &ValidationParameters,
163    errors: &mut Vec<GeopError>,
164    model: &Model,
165    edge_id: EdgeId,
166    face_id: FaceId,
167) {
168    match edge_crosses_face(params, model, edge_id, face_id) {
169        Err(e) => errors.push(e),
170        Ok(Some(point)) => errors.push(GeopError::new(format!(
171            "edge {} crosses face {}'s trimmed region at {point:?}, which is not an existing vertex — the edge should have been split there",
172            edge_id.0, face_id.0
173        ))),
174        Ok(None) => {}
175    }
176}
177
178/// Where the edge `edge_id` crosses the trimmed region of the face
179/// `face_id`, away from every vertex, if it does — never for an edge that
180/// bounds the face (see [`check_edges_and_faces_consistent`]).
181pub fn edge_crosses_face(
182    params: &ValidationParameters,
183    model: &Model,
184    edge_id: EdgeId,
185    face_id: FaceId,
186) -> GeopResult<Option<Vector3>> {
187    let ctx = |e: GeopError| e.with_context(format!("edge {edge_id} x face {face_id}"));
188    let (edge, face) = (&model.edges[&edge_id], &model.faces[&face_id]);
189    if model.face_edges(face_id).any(|e| e == edge_id) {
190        return Ok(None);
191    }
192    let intersections = curve_surface_intersect(
193        &edge.curve,
194        &face.surface,
195        params.max_edge_face_intersection_samples,
196        params.max_nodes,
197        params.min_subdivision_size,
198    )
199    .map_err(ctx)?;
200    // No "does this edge lie on the face" test here. Whether a coedge's
201    // pcurve actually traces its edge across that face is
202    // `curve_and_surface_sampling_check`'s job, and it answers the same
203    // question directly rather than by re-deriving it from the surface.
204    // What is left for this check is the crossings.
205    for (t, uv) in intersections.into_vec() {
206        let point = edge.curve.evaluate(t).map_err(ctx)?;
207        // Only a crossing *inside the face's trim* is a violation. The
208        // surface is untrimmed and extends well past the face: an edge of
209        // one lobe of a figure-8 crosses the plane of a coplanar face on
210        // the other lobe every time, nowhere near it. The search already
211        // returns where the crossing lands in `(u, v)`, so the trim test is
212        // free.
213        let inside_trim = matches!(
214            face_contains(
215                model,
216                face_id,
217                uv[0],
218                uv[1],
219                params.max_nodes,
220                params.min_subdivision_size,
221                EDGE_ON_FACE_SEED,
222            ),
223            Ok(PointClassification::Inside)
224        );
225        if inside_trim && !coincides_with_a_vertex(model, &point) {
226            return Ok(Some(point));
227        }
228    }
229    Ok(None)
230}
231
232/// An edge of the bodies `bodies` that crosses the trimmed region of one
233/// of their faces away from every vertex, with where: a body running into
234/// itself or into another. `None` if no edge does — which does not rule
235/// out two faces crossing along a curve no edge of either reaches.
236pub fn body_crossing(
237    params: &ValidationParameters,
238    model: &Model,
239    bodies: &[Body],
240) -> GeopResult<Option<(EdgeId, FaceId, Vector3)>> {
241    let mut faces = Vec::new();
242    for &body in bodies {
243        faces.extend(model.body_faces(body)?);
244    }
245    faces.sort_by_key(|f| f.0);
246    let mut edges: Vec<EdgeId> = faces.iter().flat_map(|&f| model.face_edges(f)).collect();
247    edges.sort_by_key(|e| e.0);
248    edges.dedup();
249    for &edge in &edges {
250        for &face in &faces {
251            if let Some(point) = edge_crosses_face(params, model, edge, face)? {
252                return Ok(Some((edge, face, point)));
253            }
254        }
255    }
256    Ok(None)
257}
258
259#[cfg(test)]
260mod tests {
261    use super::{check_edges_and_faces_consistent, check_edges_disjoint, check_vertices_disjoint};
262    use crate::test_fixtures::{check_errors, line3, test_cube_solid};
263    use crate::{
264        Coedge, CoedgeGeometry, CoedgeId, Edge, EdgeId, Face, FaceId, Model, Sense, Vertex,
265        boundary::BoundaryType, validation::ValidationParameters,
266    };
267    use geop_core_geometry::{
268        nurb_curve::{NurbCurve, NurbCurve2D},
269        nurb_surface::NurbSurface3D,
270    };
271    use geop_core_math::{
272        geop_error::GeopError,
273        scalars::Scalar,
274        vector::{Vector3, Vector4},
275    };
276
277    // `ValidationParameters::default()`'s `min_subdivision_size` (1e-7) is
278    // tuned for `curve_could_contain`'s single-curve BFS — with
279    // `curve_curve_intersect`/`curve_surface_intersect`'s pairwise search it
280    // is too tight to converge at all (confirmed empirically: it returns
281    // *zero* solutions even for a clean single crossing, regardless of
282    // `max_nodes`), so these tests use a looser tolerance to actually
283    // exercise the logic.
284    fn params() -> ValidationParameters {
285        // These hand-built fixtures use small, simple-scale geometry where
286        // even the (already loosened) default `min_subdivision_size` isn't
287        // quite enough for `curve_curve_intersect`/`curve_surface_intersect`
288        // to reliably resolve a genuine mid-curve crossing; loosen further
289        // just for these tests of the check's own logic.
290        ValidationParameters {
291            min_subdivision_size: Scalar::from_f64(1e-2),
292            ..ValidationParameters::default()
293        }
294    }
295
296    #[test]
297    fn welded_cube_passes_all_three() {
298        let mut model = Model::new();
299        test_cube_solid(&mut model);
300
301        let mut errors = Vec::new();
302        check_vertices_disjoint(&params(), &mut errors, &model);
303        assert!(errors.is_empty(), "vertices: {errors:?}");
304
305        let mut errors = Vec::new();
306        check_edges_disjoint(&params(), &mut errors, &model);
307        assert!(errors.is_empty(), "edges: {errors:?}");
308
309        let mut errors = Vec::new();
310        check_edges_and_faces_consistent(&params(), &mut errors, &model);
311        assert!(errors.is_empty(), "edges x faces: {errors:?}");
312    }
313
314    fn point3(p: (f64, f64, f64)) -> Vector3 {
315        Vector3::from_array([
316            Scalar::from_f64(p.0),
317            Scalar::from_f64(p.1),
318            Scalar::from_f64(p.2),
319        ])
320    }
321
322    // ── vertices disjoint ─────────────────────────────────────────────────
323
324    #[test]
325    fn distinct_vertices_pass() {
326        let mut model = Model::new();
327        model.insert_vertex(Vertex {
328            point: point3((0.0, 0.0, 0.0)),
329        });
330        model.insert_vertex(Vertex {
331            point: point3((1.0, 0.0, 0.0)),
332        });
333        let errors = check_errors(check_vertices_disjoint, &model);
334        assert!(errors.is_empty());
335    }
336
337    #[test]
338    fn coincident_vertices_fail() {
339        let mut model = Model::new();
340        model.insert_vertex(Vertex {
341            point: point3((0.0, 0.0, 0.0)),
342        });
343        model.insert_vertex(Vertex {
344            point: point3((0.0, 0.0, 0.0)),
345        });
346        let errors = check_errors(check_vertices_disjoint, &model);
347        assert_eq!(errors.len(), 1);
348    }
349
350    // ── edges disjoint ────────────────────────────────────────────────────
351
352    #[test]
353    fn edges_sharing_a_vertex_pass() {
354        let mut model = Model::new();
355        let v0 = model.insert_vertex(Vertex {
356            point: point3((0.0, 0.0, 0.0)),
357        });
358        let v1 = model.insert_vertex(Vertex {
359            point: point3((1.0, 0.0, 0.0)),
360        });
361        let v2 = model.insert_vertex(Vertex {
362            point: point3((0.0, 1.0, 0.0)),
363        });
364        model.insert_edge(Edge {
365            curve: line3((0.0, 0.0, 0.0), (1.0, 0.0, 0.0)),
366            start_vertex: v0,
367            end_vertex: v1,
368        });
369        model.insert_edge(Edge {
370            curve: line3((0.0, 0.0, 0.0), (0.0, 1.0, 0.0)),
371            start_vertex: v0,
372            end_vertex: v2,
373        });
374        let mut errors = Vec::new();
375        check_edges_disjoint(&params(), &mut errors, &model);
376        assert!(errors.is_empty());
377    }
378
379    #[test]
380    fn edges_crossing_at_non_vertex_fail() {
381        let mut model = Model::new();
382        let v0 = model.insert_vertex(Vertex {
383            point: point3((-1.0, 0.0, 0.0)),
384        });
385        let v1 = model.insert_vertex(Vertex {
386            point: point3((1.0, 0.0, 0.0)),
387        });
388        let v2 = model.insert_vertex(Vertex {
389            point: point3((0.0, -1.0, 0.0)),
390        });
391        let v3 = model.insert_vertex(Vertex {
392            point: point3((0.0, 1.0, 0.0)),
393        });
394        // Two segments crossing at the origin, which is not itself a vertex.
395        model.insert_edge(Edge {
396            curve: line3((-1.0, 0.0, 0.0), (1.0, 0.0, 0.0)),
397            start_vertex: v0,
398            end_vertex: v1,
399        });
400        model.insert_edge(Edge {
401            curve: line3((0.0, -1.0, 0.0), (0.0, 1.0, 0.0)),
402            start_vertex: v2,
403            end_vertex: v3,
404        });
405        let mut errors = Vec::new();
406        check_edges_disjoint(&params(), &mut errors, &model);
407        assert_eq!(errors.len(), 1);
408    }
409
410    /// Two edges meeting only at their shared vertex are not coincident —
411    /// not even with a cap of 1, which the old search used to misread as
412    /// coincidence the moment it found that one crossing.
413    #[test]
414    fn shared_vertex_at_the_cap_is_not_coincident() {
415        let mut model = Model::new();
416        let v0 = model.insert_vertex(Vertex {
417            point: point3((0.0, 0.0, 0.0)),
418        });
419        let v1 = model.insert_vertex(Vertex {
420            point: point3((1.0, 0.0, 0.0)),
421        });
422        let v2 = model.insert_vertex(Vertex {
423            point: point3((0.0, 1.0, 0.0)),
424        });
425        model.insert_edge(Edge {
426            curve: line3((0.0, 0.0, 0.0), (1.0, 0.0, 0.0)),
427            start_vertex: v0,
428            end_vertex: v1,
429        });
430        model.insert_edge(Edge {
431            curve: line3((0.0, 0.0, 0.0), (0.0, 1.0, 0.0)),
432            start_vertex: v0,
433            end_vertex: v2,
434        });
435        let mut low_cap = params();
436        low_cap.max_edge_edge_intersection_samples = 1;
437        let mut errors = Vec::new();
438        check_edges_disjoint(&low_cap, &mut errors, &model);
439        assert!(errors.is_empty(), "{errors:?}");
440    }
441
442    /// Two edges overlapping along part of their length fail as coincident.
443    #[test]
444    fn overlapping_edges_fail() {
445        let mut model = Model::new();
446        let vs: Vec<_> = [0.0, 0.5, 1.0, 1.5]
447            .iter()
448            .map(|&x| {
449                model.insert_vertex(Vertex {
450                    point: point3((x, 0.0, 0.0)),
451                })
452            })
453            .collect();
454        model.insert_edge(Edge {
455            curve: line3((0.0, 0.0, 0.0), (1.0, 0.0, 0.0)),
456            start_vertex: vs[0],
457            end_vertex: vs[2],
458        });
459        model.insert_edge(Edge {
460            curve: line3((0.5, 0.0, 0.0), (1.5, 0.0, 0.0)),
461            start_vertex: vs[1],
462            end_vertex: vs[3],
463        });
464        let mut errors = Vec::new();
465        check_edges_disjoint(&params(), &mut errors, &model);
466        assert_eq!(errors.len(), 1, "{errors:?}");
467        assert!(
468            format!("{:?}", errors[0]).contains("coincident"),
469            "{errors:?}"
470        );
471    }
472
473    // ── edges x faces ─────────────────────────────────────────────────────
474
475    /// A unit-square face on the XY plane with a single quad boundary loop
476    /// through `corners`, each edge independently vertexed.
477    fn quad_face(model: &mut Model, corners: [(f64, f64, f64); 4]) -> (FaceId, [EdgeId; 4]) {
478        let p4 = |q: (f64, f64, f64)| {
479            Vector4::from_array([
480                Scalar::from_f64(q.0),
481                Scalar::from_f64(q.1),
482                Scalar::from_f64(q.2),
483                Scalar::ONE,
484            ])
485        };
486        let surface = NurbSurface3D::try_new(
487            1,
488            1,
489            vec![
490                p4(corners[0]),
491                p4(corners[3]),
492                p4(corners[1]),
493                p4(corners[2]),
494            ],
495            vec![Scalar::ZERO, Scalar::ZERO, Scalar::ONE, Scalar::ONE],
496            vec![Scalar::ZERO, Scalar::ZERO, Scalar::ONE, Scalar::ONE],
497        )
498        .unwrap();
499        let face_id = model.insert_face(Face {
500            surface,
501            outer: BoundaryType::Vertex(crate::VertexId(0)),
502            holes: Vec::new(),
503            shell: crate::ShellId(999),
504        });
505
506        let verts: Vec<_> = corners
507            .iter()
508            .map(|&(x, y, z)| {
509                model.insert_vertex(Vertex {
510                    point: point3((x, y, z)),
511                })
512            })
513            .collect();
514        let edges: [EdgeId; 4] = std::array::from_fn(|i| {
515            model.insert_edge(Edge {
516                curve: line3(corners[i], corners[(i + 1) % 4]),
517                start_vertex: verts[i],
518                end_vertex: verts[(i + 1) % 4],
519            })
520        });
521        let uv = [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)];
522        let pc = |a: (f64, f64), b: (f64, f64)| -> NurbCurve2D {
523            NurbCurve::try_new(
524                1,
525                vec![
526                    Vector3::from_array([
527                        Scalar::from_f64(a.0),
528                        Scalar::from_f64(a.1),
529                        Scalar::ONE,
530                    ]),
531                    Vector3::from_array([
532                        Scalar::from_f64(b.0),
533                        Scalar::from_f64(b.1),
534                        Scalar::ONE,
535                    ]),
536                ],
537                vec![Scalar::ZERO, Scalar::ZERO, Scalar::ONE, Scalar::ONE],
538            )
539            .unwrap()
540        };
541        let coedges: [CoedgeId; 4] = std::array::from_fn(|i| {
542            model.insert_coedge(Coedge {
543                geometry: CoedgeGeometry::Edge(edges[i]),
544                sense: Sense::Forward,
545                pcurve: pc(uv[i], uv[(i + 1) % 4]),
546                next: CoedgeId(0),
547                prev: CoedgeId(0),
548                face: face_id,
549            })
550        });
551        for i in 0..4 {
552            model.coedges.get_mut(&coedges[i]).unwrap().next = coedges[(i + 1) % 4];
553            model.coedges.get_mut(&coedges[i]).unwrap().prev = coedges[(i + 3) % 4];
554        }
555        model.faces.get_mut(&face_id).unwrap().outer = BoundaryType::Loop(coedges[0]);
556
557        (face_id, edges)
558    }
559
560    fn run_edge_face(model: &Model) -> Vec<GeopError> {
561        let mut errors = Vec::new();
562        check_edges_and_faces_consistent(&params(), &mut errors, model);
563        errors
564    }
565
566    #[test]
567    fn face_boundary_edges_pass() {
568        let mut model = Model::new();
569        quad_face(
570            &mut model,
571            [
572                (0.0, 0.0, 0.0),
573                (1.0, 0.0, 0.0),
574                (1.0, 1.0, 0.0),
575                (0.0, 1.0, 0.0),
576            ],
577        );
578        assert!(run_edge_face(&model).is_empty());
579    }
580
581    #[test]
582    fn edge_piercing_face_at_non_vertex_fails() {
583        let mut model = Model::new();
584        quad_face(
585            &mut model,
586            [
587                (0.0, 0.0, 0.0),
588                (1.0, 0.0, 0.0),
589                (1.0, 1.0, 0.0),
590                (0.0, 1.0, 0.0),
591            ],
592        );
593        // An edge crossing straight through the face's plane at its center
594        // (0.5, 0.5, 0.0), not an existing vertex.
595        let va = model.insert_vertex(Vertex {
596            point: point3((0.5, 0.5, -1.0)),
597        });
598        let vb = model.insert_vertex(Vertex {
599            point: point3((0.5, 0.5, 1.0)),
600        });
601        model.insert_edge(Edge {
602            curve: line3((0.5, 0.5, -1.0), (0.5, 0.5, 1.0)),
603            start_vertex: va,
604            end_vertex: vb,
605        });
606        assert!(!run_edge_face(&model).is_empty());
607    }
608
609    #[test]
610    fn edge_piercing_face_at_a_vertex_passes() {
611        let mut model = Model::new();
612        quad_face(
613            &mut model,
614            [
615                (0.0, 0.0, 0.0),
616                (1.0, 0.0, 0.0),
617                (1.0, 1.0, 0.0),
618                (0.0, 1.0, 0.0),
619            ],
620        );
621        // An edge piercing the face's plane exactly at one of its corners
622        // (an existing vertex).
623        let va = model.insert_vertex(Vertex {
624            point: point3((0.0, 0.0, -1.0)),
625        });
626        let vb = model.insert_vertex(Vertex {
627            point: point3((0.0, 0.0, 1.0)),
628        });
629        model.insert_edge(Edge {
630            curve: line3((0.0, 0.0, -1.0), (0.0, 0.0, 1.0)),
631            start_vertex: va,
632            end_vertex: vb,
633        });
634        assert!(run_edge_face(&model).is_empty());
635    }
636}
geop_core_topology/validation/disjointness_check.rs

geop_core_topology/validation/
disjointness_check.rs
