axiolid_hidden_lines/
provider.rs

1//! The scalar exact hidden-line provider.
2
3use axiolid_contracts::{
4    Backend, BackendDescriptor, BackendId, CancellationGranularity, ExecutionOptions,
5    ExecutionTarget, GeomError, ScratchRequirement,
6};
7use axiolid_mesh_hidden_lines_contract::{
8    HiddenLineError, HiddenLineEvidence, HiddenLineOutcome, HiddenLineRequest, HiddenLineSegment,
9    MeshHiddenLines, SourceEdge, ViewProjection, Visibility,
10};
11
12use crate::broad::{Broad, BroadPhase};
13use crate::edges::{collect, DrawEdge, MeshEdges};
14use crate::groups::resolve_groups;
15use crate::occlusion::{resolve, Resolved, Scene, Work};
16use crate::output::endpoint;
17use crate::prepare::{prepare, Prepared, ResourceNames, SharedLimits};
18
19/// Portable exact hidden-line provider for orthographic and perspective views.
20///
21/// Visibility is decided exactly in the view's affine frame: nothing is
22/// rounded before a decision, only the endpoints of the output pieces are
23/// (each the exact point rounded once). For every edge it examines the
24/// triangles whose view-space bounding box can matter, found in an
25/// `axiolid-spatial` BVH; in the worst case (everything overlaps in the
26/// image) the cost still grows with edges times triangles, and
27/// `max_candidate_pairs` bounds it.
28///
29/// A near clipping plane that cuts a [`MeshRole::Solid`](axiolid_mesh_hidden_lines_contract::MeshRole::Solid) leaves a cap that
30/// occludes (decided by ray parity with a symbolic perturbation of the image
31/// point); a solid wholly beyond the plane is removed: it neither occludes
32/// nor is drawn. A failure to produce an endpoint (a coordinate beyond the
33/// binary64 range) is `Degenerate` and names the mesh of the edge.
34#[derive(Debug, Default, Clone, Copy)]
35pub struct ScalarHiddenLines;
36
37impl ScalarHiddenLines {
38    /// Stable identity of this provider.
39    pub const ID: BackendId = BackendId::new("scalar-hidden-lines");
40
41    /// Construct the provider.
42    #[must_use]
43    pub const fn new() -> Self {
44        Self
45    }
46}
47
48impl Backend for ScalarHiddenLines {
49    fn descriptor(&self) -> BackendDescriptor {
50        BackendDescriptor::new(Self::ID, ExecutionTarget::PortableCpu)
51    }
52}
53
54impl MeshHiddenLines for ScalarHiddenLines {
55    fn scratch_requirement(&self) -> ScratchRequirement {
56        // Exact view-space vertices, triangles, edge records and the spans
57        // of one edge.
58        ScratchRequirement::PerElement {
59            bytes_per_element: 1024,
60        }
61    }
62
63    fn cancellation_granularity(&self) -> CancellationGranularity {
64        CancellationGranularity::Incremental
65    }
66
67    fn supports_projection(&self, projection: ViewProjection) -> bool {
68        matches!(
69            projection,
70            ViewProjection::Orthographic | ViewProjection::Perspective
71        )
72    }
73
74    fn hidden_lines(
75        &self,
76        request: &HiddenLineRequest<'_>,
77        options: &ExecutionOptions,
78    ) -> Result<HiddenLineOutcome, HiddenLineError> {
79        draw(BroadPhase::Tree, request, options)
80    }
81}
82
83fn draw(
84    phase: BroadPhase,
85    request: &HiddenLineRequest<'_>,
86    options: &ExecutionOptions,
87) -> Result<HiddenLineOutcome, HiddenLineError> {
88    options.check_cancelled()?;
89    if request
90        .edges
91        .crease_cosine
92        .is_some_and(|cosine| !(-1.0..=1.0).contains(&cosine))
93    {
94        return Err(GeomError::InvalidInput(
95            "hidden-line crease cosine must lie in [-1, 1]".into(),
96        )
97        .into());
98    }
99    let limits = request.limits;
100    let Prepared {
101        verts,
102        tris,
103        caps,
104        ranges,
105        mut escalations,
106        total_triangles,
107        ..
108    } = prepare(
109        request.meshes,
110        &request.view,
111        request.region,
112        SharedLimits {
113            max_meshes: limits.max_meshes,
114            max_source_vertices: limits.max_source_vertices,
115            max_source_triangles: limits.max_source_triangles,
116        },
117        &ResourceNames::HIDDEN_LINES,
118        options,
119    )?;
120    let memory = || HiddenLineError::from(GeomError::BudgetExceeded { resource: "memory" });
121    let mut edges: Vec<DrawEdge> = Vec::new();
122    for (index, (entry, range)) in request.meshes.iter().zip(&ranges).enumerate() {
123        // Groups are read only when their boundaries are drawn.
124        let groups = if request.edges.group_boundary {
125            Some(resolve_groups(entry, options, &mut escalations)?)
126        } else {
127            None
128        };
129        let input = MeshEdges {
130            index,
131            id: entry.id,
132            role: entry.role,
133            mesh: entry.mesh,
134            base: range.base,
135            first_tri: range.triangles.start,
136            groups: groups.as_deref(),
137        };
138        collect(
139            &input,
140            &verts,
141            &tris,
142            &request.edges,
143            options,
144            &mut escalations,
145            &mut edges,
146        )?;
147    }
148
149    let broad = Broad::build_view(
150        &tris,
151        phase,
152        request.view.projection == ViewProjection::Perspective,
153    );
154    let scene = Scene {
155        verts: &verts,
156        tris: &tris,
157        near: request.view.near,
158        far: request.view.far,
159        region: request.region,
160        caps: &caps,
161        broad: &broad,
162        edge_on_occludes: true,
163        perspective: request.view.projection == ViewProjection::Perspective,
164    };
165    let mut evidence = HiddenLineEvidence::input_mesh(request.meshes.len(), total_triangles);
166    evidence.selected_edges = edges.len();
167    let mut work = Work::default();
168    let mut segments: Vec<HiddenLineSegment> = Vec::new();
169    for edge in &edges {
170        options.check_cancelled()?;
171        let id = request.meshes[edge.mesh].id;
172        let resolved = resolve(&scene, edge, request.limits.max_candidate_pairs, &mut work)
173            .map_err(|error| match error {
174                GeomError::Degenerate(_) => HiddenLineError::mesh(id, error),
175                other => HiddenLineError::from(other),
176            })?;
177        let pieces = match resolved {
178            Resolved::Point => {
179                evidence.point_edges += 1;
180                continue;
181            }
182            Resolved::Clipped => {
183                evidence.clipped_edges += 1;
184                continue;
185            }
186            Resolved::Pieces(pieces) => pieces,
187        };
188        let [start, end] = edge.ends;
189        let source = SourceEdge {
190            mesh: id,
191            vertices: edge.local,
192        };
193        let first = segments.len();
194        // A collapsed piece since the last pushed segment: its neighbours
195        // of one visibility are one piece after rounding.
196        let mut collapsed = false;
197        for piece in pieces {
198            if piece.hidden && !request.edges.hidden {
199                collapsed = false;
200                continue;
201            }
202            let round = |param| {
203                endpoint(&verts, start, end, param)
204                    .map_err(|error| HiddenLineError::mesh(id, error))
205            };
206            let (from, to) = (round(piece.lo)?, round(piece.hi)?);
207            if from == to {
208                evidence.collapsed_segments += 1;
209                collapsed = true;
210                continue;
211            }
212            let visibility = if piece.hidden {
213                Visibility::Hidden
214            } else {
215                Visibility::Visible
216            };
217            if collapsed && segments.len() > first {
218                let count = segments.len();
219                let last = &mut segments[count - 1];
220                if last.visibility == visibility {
221                    last.end = to;
222                    collapsed = false;
223                    continue;
224                }
225            }
226            collapsed = false;
227            if segments.len() >= request.limits.max_output_segments {
228                return Err(GeomError::BudgetExceeded {
229                    resource: "hidden-line output segments",
230                }
231                .into());
232            }
233            segments.try_reserve(1).map_err(|_| memory())?;
234            segments.push(HiddenLineSegment::new(
235                source, edge.kind, visibility, from, to,
236            ));
237        }
238    }
239    for segment in &segments {
240        match segment.visibility {
241            Visibility::Hidden => evidence.hidden_segments += 1,
242            _ => evidence.visible_segments += 1,
243        }
244    }
245    evidence.candidate_pairs = work.candidate_pairs;
246    evidence.exact_escalations = work.escalations + escalations;
247    Ok(HiddenLineOutcome::new(request.view, segments, evidence))
248}
249
250/// The scalar provider with a linear-scan broad phase: the baseline the
251/// benchmark times the BVH against, and the reference its candidates must
252/// equal. Its output is identical to [`ScalarHiddenLines`]; it is slower on
253/// large scenes. Not part of the supported API.
254#[doc(hidden)]
255#[derive(Debug, Default, Clone, Copy)]
256pub struct ScanHiddenLines;
257
258impl Backend for ScanHiddenLines {
259    fn descriptor(&self) -> BackendDescriptor {
260        BackendDescriptor::new(
261            BackendId::new("scalar-hidden-lines-scan"),
262            ExecutionTarget::PortableCpu,
263        )
264    }
265}
266
267impl MeshHiddenLines for ScanHiddenLines {
268    fn scratch_requirement(&self) -> ScratchRequirement {
269        ScalarHiddenLines.scratch_requirement()
270    }
271
272    fn cancellation_granularity(&self) -> CancellationGranularity {
273        CancellationGranularity::Incremental
274    }
275
276    fn supports_projection(&self, projection: ViewProjection) -> bool {
277        matches!(
278            projection,
279            ViewProjection::Orthographic | ViewProjection::Perspective
280        )
281    }
282
283    fn hidden_lines(
284        &self,
285        request: &HiddenLineRequest<'_>,
286        options: &ExecutionOptions,
287    ) -> Result<HiddenLineOutcome, HiddenLineError> {
288        draw(BroadPhase::Scan, request, options)
289    }
290}
axiolid_hidden_lines/provider.rs

axiolid_hidden_lines/
provider.rs
