1use 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#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
15pub struct GeometryIssue {
16 pub offset: u64,
18 pub code: String,
20 pub message: String,
22}
23
24pub 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 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}