axiolid_hidden_lines/faces/
provider.rs

1//! The scalar exact visible-face provider.
2
3use std::cmp::Ordering;
4
5use axiolid_contracts::{
6    Backend, BackendDescriptor, BackendId, CancellationGranularity, ExecutionOptions,
7    ExecutionTarget, GeomError, Operation, ScratchRequirement,
8};
9use axiolid_exact_arrangement::{arrange, PairBudget, Segment};
10use axiolid_mesh_hidden_lines_contract::{
11    FaceGroups, HiddenLineError, MeshVisibleFaces, VisibleFaceEvidence, VisibleFaceOutcome,
12    VisibleFaceRequest,
13};
14
15use super::intersect::intersection_segments;
16use super::label::label_piece;
17use super::points::Points;
18use super::regions::{build, OutputLimits};
19use super::segments::{clip_segments, crop_segments, edge_segments, PAIRS};
20use super::{Faces, Work};
21use crate::broad::{Broad, BroadPhase};
22use crate::prepare::{prepare, Prepared, ResourceNames, SharedLimits};
23use crate::view::require_orthographic;
24
25/// Bytes of scratch per source triangle that the provider declares.
26const SCRATCH_PER_ELEMENT: usize = 3072;
27
28/// Portable exact orthographic visible-face provider.
29///
30/// Visibility is decided exactly (module docs of `faces`): the image is
31/// cut by an exact arrangement of the visible mesh edges, the clip segments,
32/// the cross-sections of interpenetrating triangles and the crop box; each
33/// side of each piece is labelled with the sources frontmost just beside it;
34/// and the pieces between different labels bound the regions. Nothing is
35/// rounded before a decision. The regions are then snap-rounded to the
36/// binary64 grid (ADR 0100): each vertex is the exact point rounded once, so
37/// it equals the hidden-line endpoint of the same point, unless an edge
38/// passes through the rounding cell of another vertex, in which case the
39/// edge is routed through it.
40///
41/// Where several sources are at equal depth over an area they all get it
42/// and the evidence counts the tied sides. A triangle seen edge-on covers no
43/// area and makes no region. A near plane that cuts a
44/// [`MeshRole::Solid`](axiolid_mesh_hidden_lines_contract::MeshRole::Solid)
45/// leaves a [`FaceSource::Cap`](axiolid_mesh_hidden_lines_contract::FaceSource::Cap)
46/// region. A region that collapses under rounding is dropped and counted in
47/// the evidence, never refused.
48#[derive(Debug, Default, Clone, Copy)]
49pub struct ScalarVisibleFaces;
50
51impl ScalarVisibleFaces {
52    /// Stable identity of this provider.
53    pub const ID: BackendId = BackendId::new("scalar-visible-faces");
54
55    /// Construct the provider.
56    #[must_use]
57    pub const fn new() -> Self {
58        Self
59    }
60}
61
62impl Backend for ScalarVisibleFaces {
63    fn descriptor(&self) -> BackendDescriptor {
64        BackendDescriptor::new(Self::ID, ExecutionTarget::PortableCpu)
65    }
66}
67
68impl MeshVisibleFaces for ScalarVisibleFaces {
69    fn scratch_requirement(&self) -> ScratchRequirement {
70        ScratchRequirement::PerElement {
71            bytes_per_element: SCRATCH_PER_ELEMENT,
72        }
73    }
74
75    fn cancellation_granularity(&self) -> CancellationGranularity {
76        CancellationGranularity::Incremental
77    }
78
79    fn visible_faces(
80        &self,
81        request: &VisibleFaceRequest<'_>,
82        options: &ExecutionOptions,
83    ) -> Result<VisibleFaceOutcome, HiddenLineError> {
84        require_orthographic(&request.view, Self::ID, Operation::MeshVisibleFaces)?;
85        run(BroadPhase::Tree, true, request, options)
86    }
87}
88
89/// The provider with a linear-scan broad phase. Its outcome equals that of
90/// [`ScalarVisibleFaces`]. Not part of the supported API.
91#[doc(hidden)]
92#[derive(Debug, Default, Clone, Copy)]
93pub struct ScanVisibleFaces;
94
95impl Backend for ScanVisibleFaces {
96    fn descriptor(&self) -> BackendDescriptor {
97        BackendDescriptor::new(
98            BackendId::new("scalar-visible-faces-scan"),
99            ExecutionTarget::PortableCpu,
100        )
101    }
102}
103
104impl MeshVisibleFaces for ScanVisibleFaces {
105    fn scratch_requirement(&self) -> ScratchRequirement {
106        ScalarVisibleFaces.scratch_requirement()
107    }
108
109    fn cancellation_granularity(&self) -> CancellationGranularity {
110        CancellationGranularity::Incremental
111    }
112
113    fn visible_faces(
114        &self,
115        request: &VisibleFaceRequest<'_>,
116        options: &ExecutionOptions,
117    ) -> Result<VisibleFaceOutcome, HiddenLineError> {
118        require_orthographic(
119            &request.view,
120            self.descriptor().id,
121            Operation::MeshVisibleFaces,
122        )?;
123        run(BroadPhase::Scan, true, request, options)
124    }
125}
126
127/// The provider that keeps hidden pieces of edges in the arrangement. Its
128/// regions equal those of [`ScalarVisibleFaces`]; it is the proof that the
129/// pruning is exact and the baseline the benchmark times it against. Not part
130/// of the supported API.
131#[doc(hidden)]
132#[derive(Debug, Default, Clone, Copy)]
133pub struct UnprunedVisibleFaces;
134
135impl Backend for UnprunedVisibleFaces {
136    fn descriptor(&self) -> BackendDescriptor {
137        BackendDescriptor::new(
138            BackendId::new("scalar-visible-faces-unpruned"),
139            ExecutionTarget::PortableCpu,
140        )
141    }
142}
143
144impl MeshVisibleFaces for UnprunedVisibleFaces {
145    fn scratch_requirement(&self) -> ScratchRequirement {
146        ScalarVisibleFaces.scratch_requirement()
147    }
148
149    fn cancellation_granularity(&self) -> CancellationGranularity {
150        CancellationGranularity::Incremental
151    }
152
153    fn visible_faces(
154        &self,
155        request: &VisibleFaceRequest<'_>,
156        options: &ExecutionOptions,
157    ) -> Result<VisibleFaceOutcome, HiddenLineError> {
158        require_orthographic(
159            &request.view,
160            self.descriptor().id,
161            Operation::MeshVisibleFaces,
162        )?;
163        run(BroadPhase::Tree, false, request, options)
164    }
165}
166
167fn run(
168    phase: BroadPhase,
169    prune: bool,
170    request: &VisibleFaceRequest<'_>,
171    options: &ExecutionOptions,
172) -> Result<VisibleFaceOutcome, HiddenLineError> {
173    options.check_cancelled()?;
174    for entry in request.meshes {
175        if let FaceGroups::PerTriangle(groups) = entry.groups {
176            if groups.len() != entry.mesh.triangle_count() {
177                return Err(HiddenLineError::mesh(
178                    entry.id,
179                    GeomError::InvalidInput(format!(
180                        "{} face groups for {} triangles",
181                        groups.len(),
182                        entry.mesh.triangle_count()
183                    )),
184                ));
185            }
186        }
187    }
188    let limits = request.limits;
189    let prepared = prepare(
190        request.meshes,
191        &request.view,
192        request.region,
193        SharedLimits {
194            max_meshes: limits.max_meshes,
195            max_source_vertices: limits.max_source_vertices,
196            max_source_triangles: limits.max_source_triangles,
197        },
198        &ResourceNames::VISIBLE_FACES,
199        options,
200    )?;
201    let Prepared {
202        verts,
203        tris,
204        total_triangles,
205        escalations,
206        ..
207    } = &prepared;
208    let broad = Broad::build(tris, phase);
209    let mut work = Work {
210        budget: PairBudget::new(limits.max_candidate_pairs, PAIRS),
211        escalations: *escalations,
212    };
213    let faces = Faces::new(
214        &prepared,
215        &broad,
216        request.meshes,
217        (request.view.near, request.view.far, request.region),
218        &mut work,
219        options,
220    )?;
221
222    let mut points = Points::new(verts.len());
223    let mut segments: Vec<Segment> = Vec::new();
224    edge_segments(
225        &faces,
226        &mut points,
227        prune,
228        &mut work,
229        options,
230        &mut segments,
231    )?;
232    clip_segments(&faces, &mut points, &mut work, options, &mut segments)?;
233    crop_segments(&faces, &mut points, &mut segments)?;
234    let outline_segments = segments.len();
235    let per_element = SCRATCH_PER_ELEMENT.saturating_mul(*total_triangles);
236    intersection_segments(
237        &faces,
238        &mut points,
239        &mut work,
240        per_element,
241        options,
242        &mut segments,
243    )?;
244    let arrangement = arrange(
245        &mut points.store,
246        &segments,
247        &mut work.budget,
248        per_element,
249        options,
250    )?;
251
252    let mut labels = Vec::with_capacity(arrangement.pieces.len());
253    let mut evidence = VisibleFaceEvidence::input_mesh(request.meshes.len(), *total_triangles);
254    for (index, piece) in arrangement.pieces.iter().enumerate() {
255        if index % 256 == 0 {
256            options.check_cancelled()?;
257        }
258        let ends = piece.ends.map(|v| arrangement.vertices[v.0].point);
259        let label = label_piece(&faces, &points.store, ends, &mut work)?;
260        evidence.tied_sides += label.iter().filter(|l| l.keys.len() > 1).count();
261        if label[0].keys != label[1].keys && piece.segments[0] < outline_segments {
262            evidence.boundary_segments += 1;
263        }
264        labels.push(label);
265    }
266
267    let built = build(
268        &faces,
269        &points.store,
270        &arrangement,
271        &labels,
272        OutputLimits {
273            max_regions: limits.max_regions,
274            max_region_vertices: limits.max_region_vertices,
275        },
276        per_element,
277        &mut work,
278        options,
279    )?;
280    let regions = built.regions;
281
282    evidence.edge_on_triangles = tris.iter().filter(|t| t.sigma == Ordering::Equal).count();
283    evidence.removed_triangles = faces.removed.iter().filter(|&&r| r).count();
284    evidence.intersection_segments = segments.len() - outline_segments;
285    evidence.crossings = arrangement.crossings;
286    evidence.pieces = arrangement.pieces.len();
287    evidence.candidate_pairs = work.budget.used;
288    evidence.exact_escalations = work.escalations + points.store.escalations();
289    evidence.regions = regions.len();
290    evidence.cap_regions = regions
291        .iter()
292        .filter(|r| r.source == axiolid_mesh_hidden_lines_contract::FaceSource::Cap)
293        .count();
294    evidence.snap_displacement = built.snap_displacement;
295    evidence.rerouted_edges = built.rerouted_edges;
296    evidence.collapsed_regions = built.collapsed_regions;
297    evidence.collapsed_holes = built.collapsed_holes;
298    Ok(VisibleFaceOutcome::new(request.view, regions, evidence))
299}
axiolid_hidden_lines/faces/provider.rs

axiolid_hidden_lines/faces/
provider.rs
