ogeom_hlr/
project.rs

1//! Polygonal hidden line removal: project, classify, draw.
2//!
3//! The mesh does the occlusion work. The drawing's curves come from two
4//! places: the model's own edges, discretized by the same machinery every
5//! face boundary uses, and the tessellation's silhouettes, the mesh edges
6//! where the surface turns away from the eye. Every sampled segment is
7//! classified by casting its midpoint toward the eye against the whole
8//! mesh: a triangle strictly in front hides it. Runs of same-classified
9//! segments merge back into polylines, so a curve that dips behind a boss
10//! comes out as visible, hidden, visible: three curves, which is what a
11//! drawing shows.
12//!
13//! Polygonal, not exact: the classification is as fine as the tessellation
14//! and the sampling. That is the honest half of `HLRBRep`; the exact half
15//! (curve/surface interference resolved analytically) is deferred and the
16//! parity ledger says so; see docs/PARITY.md, hlr.projection.
17
18use ogeom_core::{OgeomResult, Tolerances, ogeom_bail};
19use ogeom_math::{Direction, Frame, Point, Point2, Vector};
20use ogeom_mesh::Deflection;
21use ogeom_topo::{Filter, Model, Shape, ShapeType, Triangulation, explore};
22
23/// Which side of the pencil a curve lands on.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum Visibility {
26    /// Nothing stands between the curve and the eye.
27    Visible,
28    /// Something does: drawn dashed, or not at all.
29    Hidden,
30}
31
32/// Where a drawn curve came from.
33#[derive(Debug, Clone)]
34pub enum Source {
35    /// A model edge, with the occurrence that produced it.
36    Edge(Shape),
37    /// A silhouette: the tessellation turning away from the eye.
38    Silhouette,
39}
40
41/// One polyline of the drawing, in view-plane coordinates.
42#[derive(Debug, Clone)]
43pub struct DrawnCurve {
44    /// The projected points, in order.
45    pub points: Vec<Point2>,
46    /// Visible or hidden.
47    pub visibility: Visibility,
48    /// What it is a picture of.
49    pub source: Source,
50}
51
52/// A 2D drawing: the classified projection of a shape.
53#[derive(Debug, Clone, Default)]
54pub struct Drawing {
55    /// Curves nothing occludes.
56    pub visible: Vec<DrawnCurve>,
57    /// Curves something does.
58    pub hidden: Vec<DrawnCurve>,
59}
60
61impl Drawing {
62    /// Every curve, visible first.
63    pub fn curves(&self) -> impl Iterator<Item = &DrawnCurve> {
64        self.visible.iter().chain(self.hidden.iter())
65    }
66}
67
68/// The view for a drawing: an orthographic camera looking along `-z` of the
69/// frame it carries, with `x` right and `y` up on the sheet.
70#[derive(Debug, Clone, Copy)]
71pub struct View {
72    frame: Frame,
73}
74
75impl View {
76    /// A view looking along `direction`, with `up` steadying the sheet.
77    ///
78    /// # Errors
79    ///
80    /// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if
81    /// `up` is parallel to the view direction.
82    pub fn looking(direction: Vector, up: Vector, tol: Tolerances) -> OgeomResult<Self> {
83        let toward_eye = Direction::new(-direction, tol)?;
84        let right = Direction::new(up.cross(toward_eye.vector()), tol)?;
85        Ok(Self {
86            frame: Frame::new(Point::ORIGIN, toward_eye, right, tol)?,
87        })
88    }
89
90    /// Sheet coordinates of a world point: `x` right, `y` up.
91    #[must_use]
92    pub fn project(&self, p: Point) -> Point2 {
93        let local = self.frame.to_local(p);
94        Point2::new(local.x, local.y)
95    }
96
97    /// Depth of a world point: greater is nearer the eye.
98    #[must_use]
99    pub fn depth(&self, p: Point) -> f64 {
100        self.frame.to_local(p).z
101    }
102
103    /// The world direction toward the eye.
104    #[must_use]
105    pub fn toward_eye(&self) -> Vector {
106        self.frame.z().vector()
107    }
108}
109
110/// Project a shape into a classified 2D drawing.
111///
112/// The model's edges and the tessellation's silhouettes, each split into
113/// visible and hidden runs by occlusion against the shape's own mesh.
114/// Segments that project to nothing (an edge running straight along the
115/// view direction) are dropped: a point is not a line in a drawing.
116///
117/// # Errors
118///
119/// As [`ogeom_mesh::triangulate()`]; and
120/// [`OgeomError::Construction`](ogeom_core::OgeomError::Construction) if the
121/// shape has no faces to draw.
122pub fn project(
123    model: &Model,
124    shape: &Shape,
125    view: &View,
126    deflection: Deflection,
127    tol: Tolerances,
128) -> OgeomResult<Drawing> {
129    let mesh = ogeom_mesh::triangulate(model, shape, deflection, tol)?;
130    if mesh.is_empty() {
131        ogeom_bail!(Construction, "the shape tessellates to nothing to draw");
132    }
133    // A segment on the exact surface sits up to a sagitta outside the
134    // inscribed mesh, and a sample on a front face must not be occluded by
135    // that face's own triangles: the clearance a hit must beat.
136    let clearance = deflection.chord.max(tol.confusion() * 1e3) * 4.0;
137
138    let mut drawing = Drawing::default();
139
140    // The model's own edges.
141    let mut seen = std::collections::HashSet::new();
142    for edge in explore(model, shape, Filter::OfType(ShapeType::Edge))? {
143        let key = (edge.node(), edge.location().clone());
144        if !seen.insert(key) {
145            continue;
146        }
147        let Ok(points) = ogeom_mesh::polyline_of_edge(model, &edge, deflection, tol) else {
148            continue;
149        };
150        classify_into(
151            &mut drawing,
152            &points,
153            Source::Edge(edge.clone()),
154            view,
155            &mesh,
156            clearance,
157            tol,
158        );
159    }
160
161    // Silhouettes: interior mesh edges whose triangles disagree about facing
162    // the eye, and border edges, which are their own outline.
163    let toward_eye = view.toward_eye();
164    let mut uses: std::collections::HashMap<(u32, u32), Vec<usize>> =
165        std::collections::HashMap::new();
166    for (t, triangle) in mesh.triangles.iter().enumerate() {
167        for i in 0..3 {
168            let (a, b) = (triangle[i], triangle[(i + 1) % 3]);
169            uses.entry((a.min(b), a.max(b))).or_default().push(t);
170        }
171    }
172    let facing = |t: usize| -> f64 {
173        let [a, b, c] = mesh.triangles[t];
174        let (pa, pb, pc) = (
175            mesh.positions[a as usize],
176            mesh.positions[b as usize],
177            mesh.positions[c as usize],
178        );
179        (pb - pa).cross(pc - pa).dot(toward_eye)
180    };
181    let mut edges: Vec<(&(u32, u32), &Vec<usize>)> = uses.iter().collect();
182    edges.sort_by_key(|&(&(a, b), _)| (a, b));
183    for (&(a, b), triangles) in edges {
184        let silhouette = match triangles.as_slice() {
185            [t] => facing(*t) > 0.0,
186            [s, t] => (facing(*s) > 0.0) != (facing(*t) > 0.0),
187            _ => false,
188        };
189        if !silhouette {
190            continue;
191        }
192        let points = [mesh.positions[a as usize], mesh.positions[b as usize]];
193        classify_into(
194            &mut drawing,
195            &points,
196            Source::Silhouette,
197            view,
198            &mesh,
199            clearance,
200            tol,
201        );
202    }
203    Ok(drawing)
204}
205
206/// Split a polyline into visible and hidden runs against the mesh.
207fn classify_into(
208    drawing: &mut Drawing,
209    points: &[Point],
210    source: Source,
211    view: &View,
212    mesh: &Triangulation,
213    clearance: f64,
214    tol: Tolerances,
215) {
216    let mut run: Vec<Point2> = Vec::new();
217    let mut run_visibility: Option<Visibility> = None;
218    let mut flush = |run: &mut Vec<Point2>, visibility: Option<Visibility>| {
219        if run.len() < 2 {
220            run.clear();
221            return;
222        }
223        let curve = DrawnCurve {
224            points: std::mem::take(run),
225            visibility: visibility.unwrap_or(Visibility::Visible),
226            source: source.clone(),
227        };
228        match visibility {
229            Some(Visibility::Hidden) => drawing.hidden.push(curve),
230            _ => drawing.visible.push(curve),
231        }
232    };
233    for pair in points.windows(2) {
234        let (a, b) = (pair[0], pair[1]);
235        let (pa, pb) = (view.project(a), view.project(b));
236        if pa.distance(pb) <= tol.confusion() {
237            // Projects to a point: not a line in a drawing.
238            flush(&mut run, run_visibility);
239            run_visibility = None;
240            continue;
241        }
242        let mid = Point::new(
243            f64::midpoint(a.x, b.x),
244            f64::midpoint(a.y, b.y),
245            f64::midpoint(a.z, b.z),
246        );
247        let visibility = if occluded(mesh, mid, view, clearance) {
248            Visibility::Hidden
249        } else {
250            Visibility::Visible
251        };
252        if run_visibility != Some(visibility) {
253            flush(&mut run, run_visibility);
254            run_visibility = Some(visibility);
255        }
256        if run.is_empty() {
257            run.push(pa);
258        }
259        run.push(pb);
260    }
261    flush(&mut run, run_visibility);
262}
263
264/// Whether anything in the mesh stands between the point and the eye.
265fn occluded(mesh: &Triangulation, p: Point, view: &View, clearance: f64) -> bool {
266    let toward_eye = view.toward_eye();
267    let depth = view.depth(p);
268    for triangle in &mesh.triangles {
269        let [a, b, c] = *triangle;
270        let (pa, pb, pc) = (
271            mesh.positions[a as usize],
272            mesh.positions[b as usize],
273            mesh.positions[c as usize],
274        );
275        // Möller–Trumbore, orthographic: the ray from p toward the eye.
276        let (e1, e2) = (pb - pa, pc - pa);
277        let h = toward_eye.cross(e2);
278        let det = e1.dot(h);
279        if det.abs() < 1e-14 {
280            continue;
281        }
282        let inv = 1.0 / det;
283        let s = p - pa;
284        let u = s.dot(h) * inv;
285        if !(0.0..=1.0).contains(&u) {
286            continue;
287        }
288        let q = s.cross(e1);
289        let v = toward_eye.dot(q) * inv;
290        if v < 0.0 || u + v > 1.0 {
291            continue;
292        }
293        let t = e2.dot(q) * inv;
294        if t <= clearance {
295            continue;
296        }
297        let hit_depth = depth + t;
298        if hit_depth > depth + clearance {
299            return true;
300        }
301    }
302    false
303}
304
305#[cfg(test)]
306#[allow(clippy::unwrap_used, clippy::expect_used)]
307mod tests {
308    use super::*;
309    use ogeom_math::Frame as MFrame;
310
311    const T: Tolerances = Tolerances::millimetres();
312
313    fn fine() -> Deflection {
314        Deflection {
315            chord: 1e-2,
316            ..Deflection::default()
317        }
318    }
319
320    fn edge_curves(drawing: &Drawing, visibility: Visibility) -> usize {
321        drawing
322            .curves()
323            .filter(|c| c.visibility == visibility && matches!(c.source, Source::Edge(_)))
324            .count()
325    }
326
327    #[test]
328    fn a_box_face_on_shows_its_front_and_hides_its_back() {
329        let mut model = Model::new();
330        let solid = ogeom_algo::make_box(&mut model, MFrame::WORLD, (10.0, 6.0, 4.0), T).unwrap();
331        // Looking down -z: the eye is above, the top face is the front.
332        let view =
333            View::looking(Vector::new(0.0, 0.0, -1.0), Vector::new(0.0, 1.0, 0.0), T).unwrap();
334        let drawing = super::project(&model, &solid.shape, &view, fine(), T).unwrap();
335
336        // Four top edges visible, four bottom edges hidden behind the top
337        // face; the four vertical edges project to points and are dropped.
338        assert_eq!(edge_curves(&drawing, Visibility::Visible), 4);
339        assert_eq!(edge_curves(&drawing, Visibility::Hidden), 4);
340    }
341
342    #[test]
343    fn a_box_in_three_quarter_view_shows_nine_and_hides_three() {
344        let mut model = Model::new();
345        let solid = ogeom_algo::make_box(&mut model, MFrame::WORLD, (10.0, 6.0, 4.0), T).unwrap();
346        // The classic drawing-class view: three faces show, nine edges
347        // visible, the three edges meeting at the far corner hidden.
348        let view =
349            View::looking(Vector::new(-1.0, -1.2, -0.9), Vector::new(0.0, 0.0, 1.0), T).unwrap();
350        let drawing = super::project(&model, &solid.shape, &view, fine(), T).unwrap();
351        assert_eq!(edge_curves(&drawing, Visibility::Visible), 9);
352        assert_eq!(edge_curves(&drawing, Visibility::Hidden), 3);
353    }
354
355    #[test]
356    fn a_cylinder_from_the_side_draws_its_silhouette() {
357        let mut model = Model::new();
358        let solid = ogeom_algo::make_cylinder(&mut model, MFrame::WORLD, 3.0, 8.0, T).unwrap();
359        let view =
360            View::looking(Vector::new(-1.0, 0.0, 0.0), Vector::new(0.0, 0.0, 1.0), T).unwrap();
361        let drawing = super::project(&model, &solid.shape, &view, fine(), T).unwrap();
362
363        // Silhouette runs exist, and the visible drawing spans the
364        // cylinder's height and diameter.
365        let silhouettes = drawing
366            .visible
367            .iter()
368            .filter(|c| matches!(c.source, Source::Silhouette))
369            .count();
370        assert!(silhouettes > 0, "a curved side draws by its silhouette");
371        let (mut min_x, mut max_x) = (f64::INFINITY, f64::NEG_INFINITY);
372        let (mut min_y, mut max_y) = (f64::INFINITY, f64::NEG_INFINITY);
373        for curve in &drawing.visible {
374            for p in &curve.points {
375                min_x = min_x.min(p.x);
376                max_x = max_x.max(p.x);
377                min_y = min_y.min(p.y);
378                max_y = max_y.max(p.y);
379            }
380        }
381        assert!(
382            (max_x - min_x - 6.0).abs() < 0.1,
383            "diameter across the sheet"
384        );
385        assert!((max_y - min_y - 8.0).abs() < 0.1, "height up the sheet");
386    }
387
388    #[test]
389    fn a_small_box_behind_a_large_one_is_entirely_hidden() {
390        let mut model = Model::new();
391        let front = ogeom_algo::make_box(&mut model, MFrame::WORLD, (20.0, 20.0, 2.0), T).unwrap();
392        let behind_frame =
393            MFrame::new(Point::new(8.0, 8.0, -10.0), Direction::Z, Direction::X, T).unwrap();
394        let back = ogeom_algo::make_box(&mut model, behind_frame, (4.0, 4.0, 2.0), T).unwrap();
395        let both = ogeom_algo::build::make_compound(
396            &mut model,
397            &[front.shape.clone(), back.shape.clone()],
398        )
399        .unwrap();
400        let view =
401            View::looking(Vector::new(0.0, 0.0, -1.0), Vector::new(0.0, 1.0, 0.0), T).unwrap();
402        let drawing = super::project(&model, &both.shape, &view, fine(), T).unwrap();
403
404        // Every drawable edge of the back box is hidden by the front plate.
405        let back_edges_visible = drawing
406            .visible
407            .iter()
408            .filter_map(|c| match &c.source {
409                Source::Edge(e) => Some(e),
410                Source::Silhouette => None,
411            })
412            .filter(|e| {
413                ogeom_topo::explore(&model, &back.shape, Filter::OfType(ShapeType::Edge))
414                    .unwrap()
415                    .iter()
416                    .any(|be| be.node() == e.node())
417            })
418            .count();
419        assert_eq!(back_edges_visible, 0, "the plate hides the block");
420    }
421}
ogeom_hlr/project.rs

ogeom_hlr/
project.rs
