Skip to main content

sim_engine/renderer/
mesh3d_surface.rs

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