Skip to main content

cadkit_gml/
geometry.rs

1//! Work-bounded diagnostics for polygons and solid shells.
2
3use crate::{
4    CityGmlDocument, ValidationOptions,
5    native::{Element, GML, XLINK},
6    validate::{elements, polygon, validate},
7};
8use cadkit_core::LimitKind;
9use cadkit_core::{Error, Point3, Result};
10use serde::{Deserialize, Serialize};
11use std::collections::HashMap;
12
13/// A geometry diagnostic that omits source identifiers and coordinate values.
14#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
15pub struct GeometryIssue {
16    /// Byte offset in the source XML input, or zero for programmatically built elements.
17    pub offset: u64,
18    /// Stable machine-readable diagnostic code.
19    pub code: String,
20    /// Human-readable description of the issue.
21    pub message: String,
22}
23
24/// Collects all polygon and solid-shell geometry issues after structural validation.
25/// Shell edge matching welds vertices within `options.tolerance` and does not test inter-solid volumetric intersections.
26pub fn geometry_issues(
27    doc: &CityGmlDocument,
28    options: &ValidationOptions,
29) -> Result<Vec<GeometryIssue>> {
30    validate(
31        doc,
32        &ValidationOptions {
33            geometry: false,
34            ..options.clone()
35        },
36    )?;
37    inspect(&elements(doc, &options.limits)?, options)
38}
39
40pub(crate) fn inspect(
41    nodes: &[(&Element, usize)],
42    options: &ValidationOptions,
43) -> Result<Vec<GeometryIssue>> {
44    let mut issues = vec![];
45    let mut work = options.max_geometry_work;
46    let ids: HashMap<_, _> = nodes
47        .iter()
48        .filter_map(|&(e, d)| e.attribute(GML, "id").map(|id| (id, (e, d))))
49        .collect();
50    for &(e, dim) in nodes {
51        if e.name.is(GML, "Polygon") {
52            let p = polygon(e, dim, &options.limits)?;
53            let checked = cadkit_core::polygon::validate(
54                &p.exterior,
55                &p.interiors,
56                options.planarity_tolerance,
57                options.tolerance,
58                &mut work,
59            );
60            match checked {
61                Err(Error::Invalid { message, .. }) => issues.push(GeometryIssue {
62                    offset: e.offset,
63                    code: "gml.polygon_geometry".into(),
64                    message,
65                }),
66                Err(other) => return Err(other),
67                Ok(()) => {
68                    if let Some(n) = cadkit_core::polygon::normal(&p.exterior)
69                        && p.interiors
70                            .iter()
71                            .filter_map(|r| cadkit_core::polygon::normal(r))
72                            .any(|h| n.x * h.x + n.y * h.y + n.z * h.z >= 0.0)
73                    {
74                        issues.push(GeometryIssue {
75                            offset: e.offset,
76                            code: "gml.ring_orientation".into(),
77                            message: "interior ring orientation must oppose exterior".into(),
78                        });
79                    }
80                }
81            }
82        }
83        if e.name.is(GML, "Solid") {
84            let mut exterior = 0;
85            for boundary in e
86                .elements()
87                .filter(|b| b.name.is(GML, "exterior") || b.name.is(GML, "interior"))
88            {
89                let outer = boundary.name.is(GML, "exterior");
90                exterior += usize::from(outer);
91                if let Some(message) = shell(boundary, dim, outer, &ids, options, &mut work)? {
92                    issues.push(GeometryIssue {
93                        offset: boundary.offset,
94                        code: "gml.solid_shell".into(),
95                        message,
96                    });
97                }
98            }
99            if exterior != 1 {
100                issues.push(GeometryIssue {
101                    offset: e.offset,
102                    code: "gml.solid_shell".into(),
103                    message: "Solid requires exactly one exterior shell".into(),
104                });
105            }
106        }
107    }
108    Ok(issues)
109}
110
111struct VertexWelder {
112    tol: f64,
113    tol2: f64,
114    points: Vec<Point3>,
115    grid: HashMap<(i64, i64, i64), Vec<u32>>,
116}
117
118impl VertexWelder {
119    fn new(tolerance: f64) -> Self {
120        let tol = if tolerance.is_finite() && tolerance > 0.0 {
121            tolerance
122        } else {
123            0.0
124        };
125        Self {
126            tol,
127            tol2: tol * tol,
128            points: Vec::new(),
129            grid: HashMap::new(),
130        }
131    }
132
133    fn cell(&self, p: Point3) -> (i64, i64, i64) {
134        let step = self.tol.max(1e-12);
135        let q = |v: f64| {
136            (v / step)
137                .floor()
138                .clamp(i64::MIN as f64 + 2.0, i64::MAX as f64 - 2.0) as i64
139        };
140        (q(p.x), q(p.y), q(p.z))
141    }
142
143    fn intern(&mut self, p: Point3, work: &mut u64) -> Result<u32> {
144        let (cx, cy, cz) = self.cell(p);
145        for dx in -1..=1 {
146            for dy in -1..=1 {
147                for dz in -1..=1 {
148                    // f64 cannot represent a one-cell margin at i64 bounds. A saturated
149                    // coordinate has no neighbor beyond the boundary, so skip that key.
150                    let (Some(x), Some(y), Some(z)) =
151                        (cx.checked_add(dx), cy.checked_add(dy), cz.checked_add(dz))
152                    else {
153                        continue;
154                    };
155                    if let Some(bucket) = self.grid.get(&(x, y, z)) {
156                        for &idx in bucket {
157                            charge(work)?;
158                            if let Some(&q) = self.points.get(idx as usize) {
159                                let (ux, uy, uz) = (p.x - q.x, p.y - q.y, p.z - q.z);
160                                let d2 = ux * ux + uy * uy + uz * uz;
161                                if d2 <= self.tol2 && (self.tol > 0.0 || p == q) {
162                                    return Ok(idx);
163                                }
164                            }
165                        }
166                    }
167                }
168            }
169        }
170        let idx = u32::try_from(self.points.len())
171            .map_err(|_| Error::limit(LimitKind::Capacity, "GML shell vertices".into()))?;
172        self.points.push(p);
173        self.grid.entry((cx, cy, cz)).or_default().push(idx);
174        Ok(idx)
175    }
176}
177
178fn charge(work: &mut u64) -> Result<()> {
179    *work = work
180        .checked_sub(1)
181        .ok_or_else(|| Error::limit(LimitKind::Work, "GML geometry work".into()))?;
182    Ok(())
183}
184
185fn shell(
186    start: &Element,
187    dim: usize,
188    outer: bool,
189    ids: &HashMap<&str, (&Element, usize)>,
190    options: &ValidationOptions,
191    work: &mut u64,
192) -> Result<Option<String>> {
193    let mut welder = VertexWelder::new(options.tolerance);
194    let mut edges: HashMap<(u32, u32), (u32, i32)> = HashMap::new();
195    let mut todo = vec![(start, dim, 1i32, 0u32)];
196    let mut volume = 0.0;
197    let mut origin = None;
198    while let Some((e, dim, sign, depth)) = todo.pop() {
199        charge(work)?;
200        if depth >= options.limits.max_depth.min(256) {
201            return Err(Error::limit(LimitKind::Depth, "GML shell depth".into()));
202        }
203        let dim = crate::validate::dimension(e, dim)?;
204        let sign =
205            if e.name.is(GML, "OrientableSurface") && e.attribute("", "orientation") == Some("-") {
206                -sign
207            } else {
208                sign
209            };
210        if let Some(id) = e.attribute(XLINK, "href").and_then(|h| h.strip_prefix('#')) {
211            let &(target, d) = ids
212                .get(id)
213                .ok_or_else(|| Error::invalid(e.offset, "unresolved shell reference"))?;
214            todo.push((target, d, sign, depth + 1));
215        }
216        if e.name.is(GML, "Polygon") {
217            let p = polygon(e, dim, &options.limits)?;
218            for ring in std::iter::once(&p.exterior).chain(p.interiors.iter()) {
219                for pair in ring.windows(2) {
220                    charge(work)?;
221                    if let (Some(&a), Some(&b)) = (pair.first(), pair.get(1)) {
222                        let a_key = welder.intern(a, work)?;
223                        let b_key = welder.intern(b, work)?;
224                        if a_key == b_key {
225                            continue;
226                        }
227                        let (edge, direction) = if a_key < b_key {
228                            ((a_key, b_key), sign)
229                        } else {
230                            ((b_key, a_key), -sign)
231                        };
232                        let entry = edges.entry(edge).or_default();
233                        if entry.0 >= 2 {
234                            return Ok(Some("shell edge occurs more than twice".into()));
235                        }
236                        entry.0 += 1;
237                        entry.1 += direction;
238                    }
239                }
240                if let Some(&a) = ring.first() {
241                    let o: Point3 = *origin.get_or_insert(a);
242                    for pair in ring.get(1..).unwrap_or(&[]).windows(2) {
243                        if let (Some(b), Some(c)) = (pair.first(), pair.get(1)) {
244                            let (ax, ay, az) = (a.x - o.x, a.y - o.y, a.z - o.z);
245                            let (bx, by, bz) = (b.x - o.x, b.y - o.y, b.z - o.z);
246                            let (cx, cy, cz) = (c.x - o.x, c.y - o.y, c.z - o.z);
247                            volume += f64::from(sign)
248                                * (ax * (by * cz - bz * cy)
249                                    + ay * (bz * cx - bx * cz)
250                                    + az * (bx * cy - by * cx))
251                                / 6.0;
252                        }
253                    }
254                }
255            }
256        } else {
257            for child in e.elements() {
258                todo.push((child, dim, sign, depth + 1));
259            }
260        }
261    }
262    if edges.is_empty()
263        || edges
264            .values()
265            .any(|&(count, balance)| count != 2 || balance != 0)
266    {
267        return Ok(Some(
268            "shell edges must occur exactly twice with opposing directions".into(),
269        ));
270    }
271    if !volume.is_finite() || volume.abs() <= options.tolerance.powi(3) || (volume > 0.0) != outer {
272        return Ok(Some(
273            "shell volume is degenerate or its orientation is reversed".into(),
274        ));
275    }
276    Ok(None)
277}
278
279#[cfg(test)]
280#[allow(clippy::expect_used)]
281mod tests {
282    use super::*;
283
284    #[test]
285    fn vertex_grid_neighbors_handle_saturated_cells() {
286        let mut welder = VertexWelder::new(1e-6);
287        let mut work = 100;
288        for point in [
289            Point3::new(f64::MAX, f64::MAX, f64::MAX),
290            Point3::new(-f64::MAX, -f64::MAX, -f64::MAX),
291            Point3::new(f64::MAX, -f64::MAX, 0.0),
292        ] {
293            let id = welder.intern(point, &mut work).expect("finite vertex");
294            assert_eq!(welder.intern(point, &mut work).expect("same vertex"), id);
295        }
296        assert_eq!(welder.points.len(), 3);
297        let origin = welder.intern(Point3::default(), &mut work).expect("origin");
298        assert_eq!(
299            welder
300                .intern(Point3::new(5e-7, 0.0, 0.0), &mut work)
301                .expect("near origin"),
302            origin
303        );
304    }
305}