Skip to main content

sim_engine/renderer/mesh3d/surface/
mod.rs

1//! Bounded homogeneous surface clipping and its authoritative frame preflight.
2
3use super::{
4    Arc, Camera3dUniform, Mesh3d, Mesh3dRenderError, Mesh3dSurfaceError, MeshColorGpu, Object3dId,
5    Scene3d, ShaderValueRange, SurfaceLightingVertex, SurfaceRasterization3d, SurfaceTransport,
6    clip_plane_ranges, interval_lerp_range, is_portable_shader_source, material,
7    rounded_f32_add_range, shader_clip_point_ranges, validate_edge_projection,
8    validate_mesh_identity, validate_points_for_policy, validate_projected_triangle_orientation,
9    validation, wgsl_signed_division_range,
10};
11
12mod culling;
13mod inside;
14#[cfg(test)]
15mod tests;
16#[cfg(test)]
17pub(super) use tests::{
18    assert_gpu_clipped_recovery, assert_gpu_native_edge_validation,
19    assert_gpu_native_surface_policy, assert_gpu_offscreen_culling,
20    assert_gpu_offscreen_culling_recovery, assert_gpu_preflight_scratch,
21    assert_gpu_source_cache_contract, assert_gpu_surface_contract, test_read_pixels, test_target,
22};
23
24/// Limits submitted surfaces and additional clip-space topology in one 3D draw.
25///
26/// Retained, wholly inside objects need no generated vertices. A crossing
27/// object's surfaces are transformed and clipped together so one draw preserves
28/// their shared depth interpolation. Limits apply before GPU writes or clearing
29/// the target, and may be zero to disallow generated topology. The total surface
30/// limit includes both retained indices and newly generated triangles.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct Mesh3dRenderBudget {
33    max_generated_vertices: usize,
34    max_generated_triangles: usize,
35    max_generated_upload_bytes: usize,
36    max_surface_triangles: usize,
37    surface_policy: SurfaceRasterization3d,
38    max_sorting_bytes: usize,
39    offscreen_surface_culling: bool,
40}
41
42impl Mesh3dRenderBudget {
43    /// Sets exact generated surface vertex, triangle, and total upload-byte
44    /// ceilings. Upload bytes include optional vertex colors, lighting/depth attributes and canonical
45    /// display-edge endpoints. The
46    /// total submitted surface count is unlimited unless explicitly bounded by
47    /// [`Self::with_max_surface_triangles`].
48    pub const fn new(vertices: usize, triangles: usize, upload_bytes: usize) -> Self {
49        Self {
50            max_generated_vertices: vertices,
51            max_generated_triangles: triangles,
52            max_generated_upload_bytes: upload_bytes,
53            max_surface_triangles: usize::MAX,
54            surface_policy: SurfaceRasterization3d::StrictPortable,
55            max_sorting_bytes: 16 * 1024 * 1024,
56            offscreen_surface_culling: false,
57        }
58    }
59
60    /// Limits active order-record capacity in frames containing Blend objects.
61    /// Zero rejects such frames. Opaque/masked-only frames use no order records,
62    /// but may retain idle storage from earlier frames outside this active limit.
63    /// Oversized retained storage is replaced before ordering under a smaller
64    /// budget; actual active Vec capacity is checked before GPU writes or clearing.
65    pub const fn with_max_sorting_bytes(mut self, bytes: usize) -> Self {
66        self.max_sorting_bytes = bytes;
67        self
68    }
69    /// Maximum active sorting-array capacity, independent of generated geometry.
70    pub const fn max_sorting_bytes(self) -> usize {
71        self.max_sorting_bytes
72    }
73
74    /// Chooses surface raster portability for this draw. The default preserves
75    /// strict cross-backend topology proofs. Display-edge validation remains
76    /// independent of the selected surface policy.
77    pub const fn with_surface_policy(mut self, policy: SurfaceRasterization3d) -> Self {
78        self.surface_policy = policy;
79        self
80    }
81
82    /// Returns the explicitly selected surface rasterization policy.
83    pub const fn surface_policy(self) -> SurfaceRasterization3d {
84        self.surface_policy
85    }
86
87    /// Optionally omits Native surface-only objects proven wholly outside one
88    /// frustum plane. Disabled by default; StrictPortable and objects with any
89    /// active wireframe keep their original submissions. Inconclusive bounds
90    /// keep drawing. This is not occlusion culling or host visibility mutation.
91    ///
92    /// All original validation and budgets run first, including the unculled
93    /// triangle limit. Actual submission and explicit culled counts are reported
94    /// separately. Instance staging, sorting and retained memory are unchanged.
95    /// Omission can split instanced draw runs; measure the tradeoff for the scene
96    /// before enabling this option, especially for many small repeated meshes.
97    pub const fn with_offscreen_surface_culling(mut self, enabled: bool) -> Self {
98        self.offscreen_surface_culling = enabled;
99        self
100    }
101
102    /// Whether conservative Native surface omission is requested for this draw.
103    pub const fn offscreen_surface_culling(self) -> bool {
104        self.offscreen_surface_culling
105    }
106
107    /// Limits combined retained and generated surface triangles before optional
108    /// culling. Zero permits edge-only or empty submissions. Retained indices
109    /// still submitted for hardware clipping count even when outside the view.
110    /// Optional offscreen culling does not discount this admission limit; its
111    /// omission happens only after all unculled validation/budgets succeed.
112    /// Failure occurs before generated staging allocations, uploads or target
113    /// mutation and returns [`Mesh3dRenderError::SurfaceTriangleBudgetExceeded`].
114    pub const fn with_max_surface_triangles(mut self, triangles: usize) -> Self {
115        self.max_surface_triangles = triangles;
116        self
117    }
118
119    /// Returns the maximum combined retained/generated pre-culling submissions.
120    pub const fn max_surface_triangles(self) -> usize {
121        self.max_surface_triangles
122    }
123
124    /// Returns the maximum generated clip-space vertices in one frame.
125    pub const fn max_generated_vertices(self) -> usize {
126        self.max_generated_vertices
127    }
128
129    /// Returns the maximum generated triangle-list primitives in one frame.
130    pub const fn max_generated_triangles(self) -> usize {
131        self.max_generated_triangles
132    }
133
134    /// Returns maximum bytes uploaded for generated surfaces and their edges.
135    pub const fn max_generated_upload_bytes(self) -> usize {
136        self.max_generated_upload_bytes
137    }
138}
139
140impl Default for Mesh3dRenderBudget {
141    fn default() -> Self {
142        Self::new(1_048_575, 349_525, 16_777_200)
143    }
144}
145
146/// Non-mutating preflight counts for the exact scene, camera, target and budget.
147#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
148pub struct Mesh3dPreflightReport {
149    pub(super) surface_policy: SurfaceRasterization3d,
150    pub(super) submitted_triangles: usize,
151    pub(super) generated_objects: usize,
152    pub(super) generated_vertices: usize,
153    pub(super) generated_color_vertices: usize,
154    pub(super) sorting_capacity_bytes: usize,
155    pub(super) generated_triangles: usize,
156    pub(super) generated_upload_bytes: usize,
157    pub(super) generated_edges: usize,
158    pub(super) generated_lighting_vertices: usize,
159    pub(super) clipped_source_triangles: usize,
160    pub(super) discarded_source_triangles: usize,
161    pub(super) culled_objects: usize,
162    pub(super) culled_triangles: usize,
163}
164
165impl Mesh3dPreflightReport {
166    /// Returns the surface policy used by this authoritative preflight.
167    pub const fn surface_policy(self) -> SurfaceRasterization3d {
168        self.surface_policy
169    }
170
171    /// Actual active draw-order capacity, zero for opaque/masked-only frames.
172    /// A reused renderer may retain a larger compliant allocation than a fresh
173    /// immutable preflight. Idle storage is included in retained frame CPU bytes.
174    pub const fn sorting_capacity_bytes(self) -> usize {
175        self.sorting_capacity_bytes
176    }
177
178    /// Returns exact retained plus generated surface triangles submitted to
179    /// the GPU. This is not a visible-fragment count: wholly outside retained
180    /// index ranges still count when they are submitted for hardware clipping.
181    pub const fn submitted_triangle_count(self) -> usize {
182        self.submitted_triangles
183    }
184
185    /// Native surface-only objects omitted by optional conservative frustum
186    /// culling after successful unculled validation. Not host-hidden objects,
187    /// generated clipping, or a measurement of fragments produced by the GPU.
188    pub const fn culled_object_count(self) -> usize {
189        self.culled_objects
190    }
191
192    /// Retained triangles omitted with wholly offscreen surface-only objects.
193    /// These still count against the unculled surface admission budget.
194    pub const fn culled_triangle_count(self) -> usize {
195        self.culled_triangles
196    }
197
198    /// Returns objects whose retained surfaces are replaced with generated
199    /// clip-space geometry for this draw, including empty generated ranges.
200    /// Optional Native culling is counted separately, not as CPU generation.
201    pub const fn generated_object_count(self) -> usize {
202        self.generated_objects
203    }
204
205    /// Returns uploaded clip-space vertices, including unchanged triangles in
206    /// objects that also contain crossing triangles.
207    pub const fn generated_vertex_count(self) -> usize {
208        self.generated_vertices
209    }
210
211    /// Returns generated triangle-list primitives submitted to the GPU.
212    pub const fn generated_triangle_count(self) -> usize {
213        self.generated_triangles
214    }
215
216    /// Returns exact additional surface, optional color/lighting and display-edge upload bytes.
217    pub const fn generated_upload_bytes(self) -> usize {
218        self.generated_upload_bytes
219    }
220
221    /// Returns canonical clip-space display edges uploaded for crossing objects.
222    /// Their two endpoints share the surface's CPU-defined transform so legal
223    /// shader dot associations cannot shift edges away from their own faces.
224    pub const fn generated_edge_count(self) -> usize {
225        self.generated_edges
226    }
227
228    /// Returns original triangles that intersect the frustum boundary and
229    /// produce a nonempty clipped polygon under strict CPU classification.
230    /// Native rasterization returns `None`: hardware clipping is not observed.
231    pub const fn clipped_source_triangle_count(self) -> Option<usize> {
232        match self.surface_policy {
233            SurfaceRasterization3d::StrictPortable => Some(self.clipped_source_triangles),
234            SurfaceRasterization3d::Native => None,
235        }
236    }
237
238    /// Returns original triangles proven entirely outside the frustum by CPU
239    /// classification. Native rasterization returns `None`, not a visibility count.
240    pub const fn discarded_source_triangle_count(self) -> Option<usize> {
241        match self.surface_policy {
242            SurfaceRasterization3d::StrictPortable => Some(self.discarded_source_triangles),
243            SurfaceRasterization3d::Native => None,
244        }
245    }
246}
247
248#[repr(C)]
249#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
250pub(super) struct SurfaceClipVertex {
251    pub(super) clip: [f32; 4],
252    pub(super) uv: [f32; 2],
253}
254
255impl SurfaceClipVertex {
256    const ATTRIBUTES: [wgpu::VertexAttribute; 1] = wgpu::vertex_attr_array![0 => Float32x4];
257    pub(super) const LAYOUT: wgpu::VertexBufferLayout<'static> = wgpu::VertexBufferLayout {
258        array_stride: std::mem::size_of::<Self>() as wgpu::BufferAddress,
259        step_mode: wgpu::VertexStepMode::Vertex,
260        attributes: &Self::ATTRIBUTES,
261    };
262    const TEXTURED_ATTRIBUTES: [wgpu::VertexAttribute; 2] =
263        wgpu::vertex_attr_array![0 => Float32x4, 5 => Float32x2];
264    pub(super) const TEXTURED_LAYOUT: wgpu::VertexBufferLayout<'static> =
265        wgpu::VertexBufferLayout {
266            array_stride: std::mem::size_of::<Self>() as u64,
267            step_mode: wgpu::VertexStepMode::Vertex,
268            attributes: &Self::TEXTURED_ATTRIBUTES,
269        };
270}
271
272#[derive(Default)]
273pub(super) struct SurfaceFrame {
274    pub(super) report: Mesh3dPreflightReport,
275    pub(super) vertices: Vec<SurfaceClipVertex>,
276    pub(super) colors: Vec<MeshColorGpu>,
277    pub(super) lighting: Vec<SurfaceLightingVertex>,
278    pub(super) edges: Vec<SurfaceClipEdge>,
279    pub(super) objects: Vec<SurfaceObject>,
280    pub(super) order: Vec<material::SurfaceDraw>,
281}
282
283impl SurfaceFrame {
284    /// Discards every active record while retaining reusable allocations.
285    pub(super) fn reset(&mut self) {
286        self.reset_geometry();
287        self.order.clear();
288    }
289
290    fn reset_geometry(&mut self) {
291        self.report = Mesh3dPreflightReport::default();
292        self.vertices.clear();
293        self.colors.clear();
294        self.lighting.clear();
295        self.edges.clear();
296        self.objects.clear();
297    }
298
299    /// Includes idle high-water allocations, not only this frame's active data.
300    pub(super) fn retained_cpu_bytes(&self) -> usize {
301        self.capacity_bytes()
302            .into_iter()
303            .fold(0usize, usize::saturating_add)
304    }
305
306    /// Vertex, color, lighting, edge, object and order allocations, respectively.
307    pub(super) fn capacity_bytes(&self) -> [usize; 6] {
308        [
309            self.vertices
310                .capacity()
311                .saturating_mul(std::mem::size_of::<SurfaceClipVertex>()),
312            self.colors
313                .capacity()
314                .saturating_mul(std::mem::size_of::<MeshColorGpu>()),
315            self.lighting
316                .capacity()
317                .saturating_mul(std::mem::size_of::<SurfaceLightingVertex>()),
318            self.edges
319                .capacity()
320                .saturating_mul(std::mem::size_of::<SurfaceClipEdge>()),
321            self.objects
322                .capacity()
323                .saturating_mul(std::mem::size_of::<SurfaceObject>()),
324            self.order
325                .capacity()
326                .saturating_mul(std::mem::size_of::<material::SurfaceDraw>()),
327        ]
328    }
329}
330
331pub(super) struct SurfaceObject {
332    // After complete preflight, an empty range can also suppress a conservatively
333    // culled retained object. It emits no generated attributes or edges.
334    pub(super) generated: Option<std::ops::Range<u32>>,
335    pub(super) generated_colors: Option<std::ops::Range<u32>>,
336    pub(super) generated_lighting: Option<std::ops::Range<u32>>,
337    pub(super) transport: SurfaceTransport,
338    pub(super) model_rows: [[f32; 4]; 3],
339    pub(super) generated_edges: Option<std::ops::Range<u32>>,
340}
341
342#[repr(C)]
343#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
344pub(super) struct SurfaceClipEdge {
345    pub(super) start: [f32; 4],
346    pub(super) end: [f32; 4],
347}
348
349impl SurfaceClipEdge {
350    const ATTRIBUTES: [wgpu::VertexAttribute; 2] =
351        wgpu::vertex_attr_array![0 => Float32x4, 1 => Float32x4];
352    pub(super) const LAYOUT: wgpu::VertexBufferLayout<'static> = wgpu::VertexBufferLayout {
353        array_stride: std::mem::size_of::<Self>() as wgpu::BufferAddress,
354        step_mode: wgpu::VertexStepMode::Instance,
355        attributes: &Self::ATTRIBUTES,
356    };
357}
358
359/// Reuses generated staging after draw ordering has already succeeded. Source
360/// validation cannot disturb its error precedence by preparing ordering later.
361/// Failure clears every active array and report, including the prepared order.
362pub(super) fn preflight_into(
363    renderer_identity: &Arc<()>,
364    scene: &Scene3d,
365    camera: Camera3dUniform,
366    budget: Mesh3dRenderBudget,
367    max_buffer_size: u64,
368    frame: &mut SurfaceFrame,
369) -> Result<(), Mesh3dRenderError> {
370    frame.reset_geometry();
371    frame.report.surface_policy = budget.surface_policy();
372    frame.report.sorting_capacity_bytes = if frame.order.is_empty() {
373        0
374    } else {
375        frame.order.capacity() * std::mem::size_of::<material::SurfaceDraw>()
376    };
377    let result = generate_preflight(
378        renderer_identity,
379        scene,
380        camera,
381        budget,
382        max_buffer_size,
383        frame,
384    );
385    if result.is_err() {
386        frame.reset();
387    } else if budget.offscreen_surface_culling()
388        && budget.surface_policy() == SurfaceRasterization3d::Native
389    {
390        culling::omit_offscreen_surfaces(scene, camera, frame);
391    }
392    result
393}
394
395fn generate_preflight(
396    renderer_identity: &Arc<()>,
397    scene: &Scene3d,
398    camera: Camera3dUniform,
399    budget: Mesh3dRenderBudget,
400    max_buffer_size: u64,
401    frame: &mut SurfaceFrame,
402) -> Result<(), Mesh3dRenderError> {
403    let capacity_error = Mesh3dRenderError::GeneratedGeometryCapacityTooLarge;
404    let visible_count = scene.visible_object_count();
405    let object_bytes = visible_count
406        .checked_mul(std::mem::size_of::<SurfaceObject>())
407        .ok_or(Mesh3dRenderError::InstanceCapacityTooLarge)?;
408    if u64::try_from(object_bytes).map_or(true, |bytes| bytes > max_buffer_size) {
409        return Err(Mesh3dRenderError::InstanceCapacityTooLarge);
410    }
411    frame
412        .objects
413        .try_reserve_exact(visible_count)
414        .map_err(|_| Mesh3dRenderError::InstanceCapacityTooLarge)?;
415    for instance in scene.instances().iter().filter(|instance| instance.visible) {
416        validate_mesh_identity(renderer_identity, &instance.mesh)?;
417        let object_result = (|| {
418            let model = instance
419                .transform
420                .model_rows()
421                .map_err(|_| Mesh3dRenderError::InvalidGeometryTransform)?;
422            let transport = SurfaceTransport::new(instance, camera.environment)?;
423            transport.validate(instance, model)?;
424            validate_points_for_policy(
425                instance.mesh.source(),
426                model,
427                camera.rows(),
428                budget.surface_policy(),
429                instance.id,
430            )?;
431            if let Some(style) = instance.wireframe() {
432                validate_edge_projection(
433                    instance.mesh.source(),
434                    model,
435                    camera.rows(),
436                    style,
437                    camera.viewport,
438                )?;
439            }
440            let mut crossing = false;
441            let mut vertex_count = 0usize;
442            if instance.style.surface_style().is_some()
443                && budget.surface_policy() == SurfaceRasterization3d::StrictPortable
444            {
445                classify_surface_for_object(
446                    instance.mesh.source(),
447                    model,
448                    camera.rows(),
449                    instance.id,
450                    transport,
451                    |_, vertices, _, _, clipped| {
452                        crossing |= clipped;
453                        vertex_count = vertex_count
454                            .checked_add(vertices.len())
455                            .ok_or(capacity_error)?;
456                        if vertices.is_empty() {
457                            frame.report.discarded_source_triangles = frame
458                                .report
459                                .discarded_source_triangles
460                                .checked_add(1)
461                                .ok_or(capacity_error)?;
462                        } else if clipped {
463                            frame.report.clipped_source_triangles = frame
464                                .report
465                                .clipped_source_triangles
466                                .checked_add(1)
467                                .ok_or(capacity_error)?;
468                        }
469                        Ok(())
470                    },
471                )?;
472            }
473            let submitted_triangles = if instance.style.surface_style().is_none() {
474                0
475            } else if crossing {
476                vertex_count / 3
477            } else {
478                instance.mesh.triangle_count()
479            };
480            record_surface_submission(&mut frame.report, submitted_triangles, crossing, budget)?;
481            if crossing {
482                let start = frame.report.generated_vertices;
483                let count = start.checked_add(vertex_count).ok_or(capacity_error)?;
484                let vertex_bytes = count
485                    .checked_mul(std::mem::size_of::<SurfaceClipVertex>())
486                    .ok_or(capacity_error)?;
487                let color_start = frame.report.generated_color_vertices;
488                let has_colors = !instance.mesh.source().vertex_colors().is_empty();
489                let color_count = if has_colors { vertex_count } else { 0 };
490                let color_end = color_start.checked_add(color_count).ok_or(capacity_error)?;
491                let color_bytes = color_end
492                    .checked_mul(std::mem::size_of::<MeshColorGpu>())
493                    .ok_or(capacity_error)?;
494                let lighting_start = frame.report.generated_lighting_vertices;
495                let lighting_end = lighting_start
496                    .checked_add(if transport.generated_attributes {
497                        vertex_count
498                    } else {
499                        0
500                    })
501                    .ok_or(capacity_error)?;
502                let lighting_bytes = lighting_end
503                    .checked_mul(std::mem::size_of::<SurfaceLightingVertex>())
504                    .ok_or(capacity_error)?;
505                let edge_start = frame.report.generated_edges;
506                let edge_count = if instance.wireframe().is_some() {
507                    instance.mesh.source().display_edges().len()
508                } else {
509                    0
510                };
511                let edge_end = edge_start.checked_add(edge_count).ok_or(capacity_error)?;
512                let edge_bytes = edge_end
513                    .checked_mul(std::mem::size_of::<SurfaceClipEdge>())
514                    .ok_or(capacity_error)?;
515                let bytes = vertex_bytes
516                    .checked_add(edge_bytes)
517                    .and_then(|bytes| bytes.checked_add(color_bytes))
518                    .and_then(|bytes| bytes.checked_add(lighting_bytes))
519                    .ok_or(capacity_error)?;
520                if count > budget.max_generated_vertices
521                    || count / 3 > budget.max_generated_triangles
522                    || bytes > budget.max_generated_upload_bytes
523                    || u64::try_from(
524                        vertex_bytes
525                            .max(edge_bytes)
526                            .max(color_bytes)
527                            .max(lighting_bytes),
528                    )
529                    .map_or(true, |bytes| bytes > max_buffer_size)
530                    || count > u32::MAX as usize
531                    || edge_end > u32::MAX as usize
532                {
533                    return Err(capacity_error);
534                }
535                frame.report.generated_vertices = count;
536                frame.report.generated_color_vertices = color_end;
537                frame.report.generated_lighting_vertices = lighting_end;
538                frame.report.generated_triangles = count / 3;
539                frame.report.generated_upload_bytes = bytes;
540                frame.report.generated_edges = edge_end;
541                frame.objects.push(SurfaceObject {
542                    generated: Some(start as u32..count as u32),
543                    generated_colors: has_colors.then_some(color_start as u32..color_end as u32),
544                    generated_lighting: transport
545                        .generated_attributes
546                        .then_some(lighting_start as u32..lighting_end as u32),
547                    transport,
548                    model_rows: model,
549                    generated_edges: Some(edge_start as u32..edge_end as u32),
550                });
551            } else {
552                frame.objects.push(SurfaceObject {
553                    generated: None,
554                    generated_colors: None,
555                    generated_lighting: None,
556                    transport,
557                    model_rows: model,
558                    generated_edges: None,
559                });
560            }
561            Ok(())
562        })();
563        object_result.map_err(|error: Mesh3dRenderError| error.for_object(instance.id))?;
564    }
565    // Reserve generated streams only after all source proofs and exact aggregate
566    // budgets succeed. Failure clears lengths without losing reusable capacity.
567    frame
568        .vertices
569        .try_reserve_exact(frame.report.generated_vertices)
570        .map_err(|_| capacity_error)?;
571    frame
572        .colors
573        .try_reserve_exact(frame.report.generated_color_vertices)
574        .map_err(|_| capacity_error)?;
575    frame
576        .lighting
577        .try_reserve_exact(frame.report.generated_lighting_vertices)
578        .map_err(|_| capacity_error)?;
579    frame
580        .edges
581        .try_reserve_exact(frame.report.generated_edges)
582        .map_err(|_| capacity_error)?;
583    for (instance, object) in scene
584        .instances()
585        .iter()
586        .filter(|instance| instance.visible)
587        .zip(&frame.objects)
588    {
589        if object.generated.is_none() {
590            continue;
591        }
592        classify_surface_for_object(
593            instance.mesh.source(),
594            object.model_rows,
595            camera.rows(),
596            instance.id,
597            object.transport,
598            |_, vertices, colors, lighting, _| {
599                frame.vertices.extend_from_slice(vertices);
600                if object.generated_lighting.is_some() {
601                    frame.lighting.extend_from_slice(lighting);
602                }
603                if object.generated_colors.is_some() {
604                    frame.colors.extend_from_slice(colors);
605                }
606                Ok(())
607            },
608        )
609        .map_err(|error| error.for_object(instance.id))?;
610        if instance.wireframe().is_some() {
611            for edge in instance.mesh.source().display_edges() {
612                let endpoints = [edge.start(), edge.end()];
613                let mut clips = [[0.0; 4]; 2];
614                for (clip, vertex) in clips.iter_mut().zip(endpoints) {
615                    *clip = shader_clip_point_ranges(
616                        instance.mesh.source().vertices()[vertex as usize],
617                        object.model_rows,
618                        camera.rows(),
619                    )
620                    .map_err(|error| error.for_object(instance.id))?
621                    .map(|component| component.fixed);
622                }
623                frame.edges.push(SurfaceClipEdge {
624                    start: clips[0],
625                    end: clips[1],
626                });
627            }
628        }
629    }
630    Ok(())
631}
632
633fn record_surface_submission(
634    report: &mut Mesh3dPreflightReport,
635    submitted_triangles: usize,
636    generated_object: bool,
637    budget: Mesh3dRenderBudget,
638) -> Result<(), Mesh3dRenderError> {
639    let capacity_error = Mesh3dRenderError::GeneratedGeometryCapacityTooLarge;
640    let submitted_triangles = report
641        .submitted_triangles
642        .checked_add(submitted_triangles)
643        .ok_or(capacity_error)?;
644    if submitted_triangles > budget.max_surface_triangles {
645        return Err(Mesh3dRenderError::SurfaceTriangleBudgetExceeded {
646            limit: budget.max_surface_triangles,
647            actual: submitted_triangles,
648        });
649    }
650    let generated_objects = report
651        .generated_objects
652        .checked_add(usize::from(generated_object))
653        .ok_or(capacity_error)?;
654    report.submitted_triangles = submitted_triangles;
655    report.generated_objects = generated_objects;
656    Ok(())
657}
658
659// A triangle intersected with six convex half-spaces has at most nine vertices.
660const MAX_POLYGON_VERTICES: usize = 9;
661
662#[derive(Clone, Copy)]
663struct ClipVertex {
664    ranges: [ShaderValueRange; 4],
665    planes: u8,
666    provenance: u8,
667    uv: [f32; 2],
668    color: [f32; 4],
669    lighting: [f32; 4],
670}
671
672impl ClipVertex {
673    fn same_proven_vertex(self, other: Self) -> bool {
674        self.provenance == other.provenance
675            && self.planes == other.planes
676            && self.uv == other.uv
677            && self.color == other.color
678            && self.lighting == other.lighting
679            && self
680                .ranges
681                .into_iter()
682                .zip(other.ranges)
683                .all(|(left, right)| {
684                    left.fixed == right.fixed
685                        && left.minimum == right.minimum
686                        && left.maximum == right.maximum
687                })
688    }
689    fn plane_range(self, plane: usize) -> Result<(f64, f64), Mesh3dRenderError> {
690        if self.planes & (1 << plane) != 0 {
691            Ok((0.0, 0.0))
692        } else {
693            clip_plane_ranges(self.ranges).map(|ranges| ranges[plane])
694        }
695    }
696
697    fn plane_value(self, plane: usize) -> f64 {
698        if self.planes & (1 << plane) != 0 {
699            return 0.0;
700        }
701        let [x, y, z, w] = self.ranges.map(|range| f64::from(range.fixed));
702        [w + x, w - x, w + y, w - y, z, w - z][plane]
703    }
704}
705
706#[derive(Clone, Copy)]
707struct ClippedTriangle {
708    vertices: [ClipVertex; MAX_POLYGON_VERTICES],
709    count: usize,
710    crossing: bool,
711}
712
713fn inside(vertex: ClipVertex, plane: usize) -> Result<bool, Mesh3dSurfaceError> {
714    let range = vertex
715        .plane_range(plane)
716        .map_err(|_| Mesh3dSurfaceError::TransformArithmetic)?;
717    if range.0 >= 0.0 {
718        Ok(true)
719    } else if range.1 <= -f64::from(f32::MIN_POSITIVE) {
720        Ok(false)
721    } else {
722        Err(Mesh3dSurfaceError::ClipPlaneClassification)
723    }
724}
725
726fn intersection(
727    start: ClipVertex,
728    end: ClipVertex,
729    plane: usize,
730    provenance: u8,
731) -> Result<ClipVertex, Mesh3dSurfaceError> {
732    let error = Mesh3dSurfaceError::ClipIntersection;
733    let start_distance = start.plane_range(plane).map_err(|_| error)?;
734    let end_distance = end.plane_range(plane).map_err(|_| error)?;
735    if start_distance == (0.0, 0.0) {
736        return Ok(start);
737    }
738    if end_distance == (0.0, 0.0) {
739        return Ok(end);
740    }
741    let denominator = rounded_f32_add_range(start_distance, end_distance, true).ok_or(error)?;
742    let amount = wgsl_signed_division_range(start_distance, denominator).ok_or(error)?;
743    if amount.0 < 0.0 || amount.1 > 1.0 {
744        return Err(error);
745    }
746    // The emitted position has a single CPU-defined representation. Intervals
747    // still prove topology for all legal transform associations, so baking the
748    // position is not permission to accept an ambiguous source triangle.
749    let distance = start.plane_value(plane);
750    let fixed_amount = distance / (distance - end.plane_value(plane));
751    let mut ranges = [ShaderValueRange::exact(0.0); 4];
752    for (axis, range) in ranges.iter_mut().enumerate() {
753        let left = start.ranges[axis];
754        let right = end.ranges[axis];
755        let (minimum, maximum) = interval_lerp_range(
756            (left.minimum, left.maximum),
757            (right.minimum, right.maximum),
758            amount,
759        )
760        .ok_or(error)?;
761        let fixed = (f64::from(left.fixed)
762            + (f64::from(right.fixed) - f64::from(left.fixed)) * fixed_amount)
763            as f32;
764        if !is_portable_shader_source(fixed) {
765            return Err(error);
766        }
767        *range = ShaderValueRange {
768            fixed,
769            minimum: minimum.min(f64::from(fixed)),
770            maximum: maximum.max(f64::from(fixed)),
771        };
772    }
773    let planes = (start.planes & end.planes) | (1 << plane);
774    let uv = std::array::from_fn(|axis| {
775        (f64::from(start.uv[axis])
776            + (f64::from(end.uv[axis]) - f64::from(start.uv[axis])) * fixed_amount) as f32
777    });
778    if uv
779        .into_iter()
780        .any(|value| !is_portable_shader_source(value) || !(0.0..=1.0).contains(&value))
781    {
782        return Err(error);
783    }
784    let color = std::array::from_fn(|channel| {
785        (f64::from(start.color[channel])
786            + (f64::from(end.color[channel]) - f64::from(start.color[channel])) * fixed_amount)
787            as f32
788    });
789    if color
790        .into_iter()
791        .any(|value| !value.is_finite() || !(0.0..=1.0).contains(&value))
792    {
793        return Err(error);
794    }
795    let lighting = std::array::from_fn(|channel| {
796        (f64::from(start.lighting[channel])
797            + (f64::from(end.lighting[channel]) - f64::from(start.lighting[channel]))
798                * fixed_amount) as f32
799    });
800    if lighting.into_iter().any(|value| !value.is_finite()) {
801        return Err(error);
802    }
803    // Preserve the exact plane relation, including corners shared by two
804    // previously clipped planes. This prevents a second hardware clip caused
805    // only by independently rounding x and w at the boundary.
806    for boundary in 0..6 {
807        if planes & (1 << boundary) == 0 {
808            continue;
809        }
810        let w = ranges[3];
811        let (axis, negative) = match boundary {
812            0 => (0, true),
813            1 => (0, false),
814            2 => (1, true),
815            3 => (1, false),
816            4 => {
817                ranges[2] = ShaderValueRange::exact(0.0);
818                continue;
819            }
820            _ => (2, false),
821        };
822        ranges[axis] = if negative {
823            ShaderValueRange {
824                fixed: -w.fixed,
825                minimum: -w.maximum,
826                maximum: -w.minimum,
827            }
828        } else {
829            w
830        };
831    }
832    Ok(ClipVertex {
833        ranges,
834        planes,
835        provenance,
836        uv,
837        color,
838        lighting,
839    })
840}
841
842#[cfg(test)]
843fn clipped_triangle(
844    clips: [[ShaderValueRange; 4]; 3],
845) -> Result<ClippedTriangle, Mesh3dRenderError> {
846    clipped_triangle_with_uv(clips, [[0.0; 2]; 3]).map_err(Mesh3dSurfaceError::legacy)
847}
848
849#[cfg(test)]
850fn clipped_triangle_with_uv(
851    clips: [[ShaderValueRange; 4]; 3],
852    uv: [[f32; 2]; 3],
853) -> Result<ClippedTriangle, Mesh3dSurfaceError> {
854    clipped_triangle_with_attributes(clips, uv, [[1.0; 4]; 3], [[0.0; 4]; 3])
855}
856
857fn clipped_triangle_with_attributes(
858    clips: [[ShaderValueRange; 4]; 3],
859    uv: [[f32; 2]; 3],
860    colors: [[f32; 4]; 3],
861    lighting: [[f32; 4]; 3],
862) -> Result<ClippedTriangle, Mesh3dSurfaceError> {
863    let empty = ClipVertex {
864        ranges: [ShaderValueRange::exact(0.0); 4],
865        planes: 0,
866        provenance: 0,
867        uv: [0.0; 2],
868        color: [1.0; 4],
869        lighting: [0.0; 4],
870    };
871    let mut result = ClippedTriangle {
872        vertices: [empty; MAX_POLYGON_VERTICES],
873        count: 3,
874        crossing: false,
875    };
876    let mut all_planes_inside = true;
877    for (provenance, (destination, ranges)) in result.vertices.iter_mut().zip(clips).enumerate() {
878        let plane_ranges =
879            clip_plane_ranges(ranges).map_err(|_| Mesh3dSurfaceError::TransformArithmetic)?;
880        all_planes_inside = all_planes_inside && plane_ranges.iter().all(|range| range.0 >= 0.0);
881        let planes = plane_ranges
882            .iter()
883            .enumerate()
884            .fold(0, |mask, (plane, range)| {
885                mask | if *range == (0.0, 0.0) { 1 << plane } else { 0 }
886            });
887        *destination = ClipVertex {
888            ranges,
889            planes,
890            provenance: provenance as u8,
891            uv: uv[provenance],
892            color: colors[provenance],
893            lighting: lighting[provenance],
894        };
895    }
896    // Common-plane rejection does not need a projected orientation proof.
897    let mut next_provenance = 3u8;
898    for plane in 0..6 {
899        if result.vertices[..3]
900            .iter()
901            .all(|vertex| vertex.plane_range(plane).is_ok_and(|range| range.1 < 0.0))
902        {
903            result.count = 0;
904            return Ok(result);
905        }
906    }
907    if all_planes_inside && inside::accepts(&result.vertices, all_planes_inside) {
908        return Ok(result);
909    }
910    for plane in 0..6 {
911        if result.count == 0 {
912            break;
913        }
914        let input = result;
915        result.count = 0;
916        let mut previous = input.vertices[input.count - 1];
917        let mut previous_inside = inside(previous, plane)?;
918        for current in input.vertices[..input.count].iter().copied() {
919            let current_inside = inside(current, plane)?;
920            let intersection = if previous_inside != current_inside {
921                let intersection = intersection(previous, current, plane, next_provenance)?;
922                next_provenance += 1;
923                Some(intersection)
924            } else {
925                None
926            };
927            result.crossing |= !current_inside;
928            for vertex in intersection
929                .into_iter()
930                .chain(current_inside.then_some(current))
931            {
932                if result.count > 0
933                    && result.vertices[result.count - 1]
934                        .ranges
935                        .map(|value| value.fixed)
936                        == vertex.ranges.map(|value| value.fixed)
937                {
938                    // Only identical, proven boundary endpoints may collapse.
939                    // An uncertainty envelope is never discarded as zero area.
940                    if !result.vertices[result.count - 1].same_proven_vertex(vertex) {
941                        return Err(Mesh3dSurfaceError::ClippedVertexIdentity);
942                    }
943                    continue;
944                }
945                if result.count == MAX_POLYGON_VERTICES {
946                    return Err(Mesh3dSurfaceError::ClippedPolygonCapacity);
947                }
948                result.vertices[result.count] = vertex;
949                result.count += 1;
950            }
951            previous = current;
952            previous_inside = current_inside;
953        }
954        if result.count > 1
955            && result.vertices[0].ranges.map(|value| value.fixed)
956                == result.vertices[result.count - 1]
957                    .ranges
958                    .map(|value| value.fixed)
959        {
960            if !result.vertices[0].same_proven_vertex(result.vertices[result.count - 1]) {
961                return Err(Mesh3dSurfaceError::ClippedVertexIdentity);
962            }
963            result.count -= 1;
964        }
965    }
966    if result.count > 0 && result.count < 3 {
967        return Err(Mesh3dSurfaceError::ClippedPolygonDegenerate);
968    }
969    for index in 1..result.count.saturating_sub(1) {
970        let vertices = [
971            result.vertices[0],
972            result.vertices[index],
973            result.vertices[index + 1],
974        ];
975        for vertex in vertices {
976            if vertex.ranges[3].minimum < f64::from(f32::MIN_POSITIVE) {
977                return Err(Mesh3dSurfaceError::PerspectiveDivide);
978            }
979            for plane in 0..6 {
980                if !inside(vertex, plane)? || vertex.plane_value(plane) < 0.0 {
981                    return Err(Mesh3dSurfaceError::ClippedVertexOutside);
982                }
983            }
984        }
985        validate_projected_triangle_orientation(vertices.map(|vertex| vertex.ranges))
986            .map_err(|_| Mesh3dSurfaceError::ProjectedOrientation)?;
987    }
988    Ok(result)
989}
990
991#[cfg(test)]
992pub(super) fn classify_surface(
993    mesh: &Mesh3d,
994    model_rows: [[f32; 4]; 3],
995    camera_rows: [[f32; 4]; 4],
996    mut visit: impl FnMut(usize, &[SurfaceClipVertex], bool) -> Result<(), Mesh3dRenderError>,
997) -> Result<(), Mesh3dRenderError> {
998    classify_surface_impl(
999        mesh,
1000        model_rows,
1001        camera_rows,
1002        SurfaceTransport::default(),
1003        |_, reason| reason.legacy(),
1004        |index, vertices, _, _, clipped| visit(index, vertices, clipped),
1005    )
1006}
1007
1008fn classify_surface_for_object(
1009    mesh: &Mesh3d,
1010    model_rows: [[f32; 4]; 3],
1011    camera_rows: [[f32; 4]; 4],
1012    object_id: Object3dId,
1013    transport: SurfaceTransport,
1014    visit: impl FnMut(
1015        usize,
1016        &[SurfaceClipVertex],
1017        &[MeshColorGpu],
1018        &[SurfaceLightingVertex],
1019        bool,
1020    ) -> Result<(), Mesh3dRenderError>,
1021) -> Result<(), Mesh3dRenderError> {
1022    classify_surface_impl(
1023        mesh,
1024        model_rows,
1025        camera_rows,
1026        transport,
1027        |index, reason| reason.for_triangle(object_id, index),
1028        visit,
1029    )
1030}
1031
1032mod source_cache;
1033
1034fn classify_surface_impl(
1035    mesh: &Mesh3d,
1036    model_rows: [[f32; 4]; 3],
1037    camera_rows: [[f32; 4]; 4],
1038    transport: SurfaceTransport,
1039    failure: impl Fn(usize, Mesh3dSurfaceError) -> Mesh3dRenderError,
1040    visit: impl FnMut(
1041        usize,
1042        &[SurfaceClipVertex],
1043        &[MeshColorGpu],
1044        &[SurfaceLightingVertex],
1045        bool,
1046    ) -> Result<(), Mesh3dRenderError>,
1047) -> Result<(), Mesh3dRenderError> {
1048    if source_cache::worthwhile(mesh) {
1049        classify_surface_with_cache::<{ source_cache::CAPACITY }>(
1050            mesh,
1051            model_rows,
1052            camera_rows,
1053            transport,
1054            failure,
1055            visit,
1056        )
1057    } else {
1058        classify_surface_with_cache::<0>(mesh, model_rows, camera_rows, transport, failure, visit)
1059    }
1060}
1061
1062fn classify_surface_with_cache<const CACHE_SLOTS: usize>(
1063    mesh: &Mesh3d,
1064    model_rows: [[f32; 4]; 3],
1065    camera_rows: [[f32; 4]; 4],
1066    transport: SurfaceTransport,
1067    failure: impl Fn(usize, Mesh3dSurfaceError) -> Mesh3dRenderError,
1068    mut visit: impl FnMut(
1069        usize,
1070        &[SurfaceClipVertex],
1071        &[MeshColorGpu],
1072        &[SurfaceLightingVertex],
1073        bool,
1074    ) -> Result<(), Mesh3dRenderError>,
1075) -> Result<(), Mesh3dRenderError> {
1076    let mut cache =
1077        source_cache::SourceCache::<CACHE_SLOTS>::new(mesh, model_rows, camera_rows, transport);
1078    for (index, triangle) in mesh.triangle_indices().chunks_exact(3).enumerate() {
1079        let mut clips = [[ShaderValueRange::exact(0.0); 4]; 3];
1080        for (destination, vertex) in clips.iter_mut().zip(triangle) {
1081            *destination = cache
1082                .clip(*vertex)
1083                .map_err(|reason| failure(index, reason))?;
1084        }
1085        let uv = std::array::from_fn(|index| {
1086            mesh.texture_coordinates()
1087                .get(triangle[index] as usize)
1088                .map_or([0.0, 0.0], |coordinate| [coordinate.u(), coordinate.v()])
1089        });
1090        let colors = std::array::from_fn(|index| {
1091            mesh.vertex_colors()
1092                .get(triangle[index] as usize)
1093                .map_or([1.0; 4], |color| color.to_array())
1094        });
1095        let mut auxiliary = [[0.0; 4]; 3];
1096        for (value, vertex) in auxiliary.iter_mut().zip(triangle) {
1097            *value = cache
1098                .auxiliary(*vertex)
1099                .map_err(|reason| failure(index, reason))?;
1100        }
1101        let polygon = clipped_triangle_with_attributes(clips, uv, colors, auxiliary)
1102            .map_err(|reason| failure(index, reason))?;
1103        let mut emitted = [SurfaceClipVertex {
1104            clip: [0.0; 4],
1105            uv: [0.0; 2],
1106        }; 21];
1107        let mut emitted_colors = [MeshColorGpu { color: [1.0; 4] }; 21];
1108        let mut emitted_lighting = [SurfaceLightingVertex::default(); 21];
1109        let mut count = 0;
1110        for fan in 1..polygon.count.saturating_sub(1) {
1111            for vertex in [
1112                polygon.vertices[0],
1113                polygon.vertices[fan],
1114                polygon.vertices[fan + 1],
1115            ] {
1116                emitted[count] = SurfaceClipVertex {
1117                    clip: vertex.ranges.map(|range| range.fixed),
1118                    uv: vertex.uv,
1119                };
1120                emitted_colors[count] = MeshColorGpu {
1121                    color: vertex.color,
1122                };
1123                emitted_lighting[count] = SurfaceLightingVertex {
1124                    normal_depth: vertex.lighting,
1125                };
1126                count += 1;
1127            }
1128        }
1129        visit(
1130            index,
1131            &emitted[..count],
1132            &emitted_colors[..count],
1133            &emitted_lighting[..count],
1134            polygon.crossing,
1135        )?;
1136    }
1137    Ok(())
1138}