1use std::collections::BTreeMap;
2
3use pfx_geom::{
4 detail::detail_level,
5 lod,
6 mesh::{Bounds, Mesh},
7 shapes::Shape,
8};
9
10use crate::{
11 frame::{Camera, Frame, Instance, Matrix, MeshData, MeshHandle, transform},
12 renderer::Renderer,
13};
14
15pub const LOD_WGSL: &str = r#"
16fn lod_hash(pixel: vec2u, object_id: u32) -> f32 {
17 var value = pixel.x * 1664525u + pixel.y * 1013904223u + object_id * 747796405u;
18 value = (value ^ (value >> 16u)) * 2246822519u;
19 value = (value ^ (value >> 13u)) * 3266489917u;
20 return f32(value ^ (value >> 16u)) * (1.0 / 4294967296.0);
21}
22
23fn lod_keep(pixel: vec2u, object_id: u32, coverage: f32) -> bool {
24 return lod_hash(pixel, object_id) < coverage;
25}
26"#;
27
28const FIRST_BUCKET: i32 = -40;
29const LAST_BUCKET: i32 = 40;
30const ERROR_SAFETY: f32 = 1.25;
31
32pub trait MeshUploader {
33 fn upload_mesh(&mut self, data: MeshData<'_>) -> Result<MeshHandle, String>;
34}
35
36impl MeshUploader for Frame {
37 fn upload_mesh(&mut self, data: MeshData<'_>) -> Result<MeshHandle, String> {
38 Frame::upload_mesh(self, data)
39 }
40}
41
42impl MeshUploader for Renderer {
43 fn upload_mesh(&mut self, data: MeshData<'_>) -> Result<MeshHandle, String> {
44 Renderer::upload_mesh(self, data)
45 }
46}
47
48struct Level {
49 mesh: Mesh,
50 handle: Option<MeshHandle>,
51 error: f32,
52}
53
54enum Source {
55 Chain(Vec<Level>),
56 Analytic {
57 shape: Shape,
58 levels: BTreeMap<i32, Level>,
59 last_bucket: i32,
60 },
61}
62
63struct Object {
64 instance: Instance,
65 bounds: Bounds,
66 source: Source,
67 selected: usize,
68 previous: Option<usize>,
69 distance: f32,
70 ideal_triangles: usize,
71}
72
73#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
74pub struct LodStats {
75 pub triangles: usize,
76 pub ideal_triangles: usize,
77 pub degraded_objects: usize,
78 pub over_budget_triangles: usize,
79 pub cached_levels: usize,
80}
81
82pub struct LodSet {
83 objects: Vec<Object>,
84 triangle_budget: usize,
85 stats: LodStats,
86}
87
88fn bucket_error(bucket: i32) -> f32 {
89 2.0_f32.powf(bucket as f32 * 0.5)
90}
91
92fn level(mesh: Mesh, error: f32) -> Level {
93 Level {
94 mesh,
95 handle: None,
96 error,
97 }
98}
99
100fn world_bounds(bounds: Bounds, model: Matrix) -> Bounds {
101 let mut result = Bounds::empty();
102 for x in [bounds.min[0], bounds.max[0]] {
103 for y in [bounds.min[1], bounds.max[1]] {
104 for z in [bounds.min[2], bounds.max[2]] {
105 let point = transform(model, [x, y, z, 1.0]);
106 result.include([point[0], point[1], point[2]]);
107 }
108 }
109 }
110 result
111}
112
113fn maximum_stretch(model: Matrix) -> f32 {
114 let row = (0..3)
115 .map(|row| (0..3).map(|column| model[column][row].abs()).sum::<f32>())
116 .fold(0.0, f32::max);
117 let column = (0..3)
118 .map(|column| (0..3).map(|row| model[column][row].abs()).sum::<f32>())
119 .fold(0.0, f32::max);
120 (row * column).sqrt().max(1e-6)
121}
122
123impl Object {
124 fn level(&self, index: usize) -> Option<&Level> {
125 match &self.source {
126 Source::Chain(levels) => levels.get(index),
127 Source::Analytic { levels, .. } => levels.get(&(FIRST_BUCKET + index as i32)),
128 }
129 }
130
131 fn level_mut(&mut self, index: usize) -> Option<&mut Level> {
132 match &mut self.source {
133 Source::Chain(levels) => levels.get_mut(index),
134 Source::Analytic { levels, .. } => levels.get_mut(&(FIRST_BUCKET + index as i32)),
135 }
136 }
137
138 fn ensure_level(&mut self, index: usize) {
139 if let Source::Analytic { shape, levels, .. } = &mut self.source {
140 let bucket = FIRST_BUCKET + index as i32;
141 levels
142 .entry(bucket)
143 .or_insert_with(|| level(shape.mesh(bucket_error(bucket)), bucket_error(bucket)));
144 }
145 }
146
147 fn max_index(&self) -> usize {
148 match &self.source {
149 Source::Chain(levels) => levels.len() - 1,
150 Source::Analytic { last_bucket, .. } => (last_bucket - FIRST_BUCKET) as usize,
151 }
152 }
153
154 fn triangle_count(&self) -> usize {
155 self.level(self.selected)
156 .map_or(0, |level| level.mesh.triangle_count())
157 }
158}
159
160impl LodSet {
161 pub fn new(triangle_budget: usize) -> Self {
162 Self {
163 objects: Vec::new(),
164 triangle_budget,
165 stats: LodStats::default(),
166 }
167 }
168
169 pub fn add_mesh(&mut self, instance: Instance, mesh: &Mesh) -> Result<usize, String> {
170 let levels = lod::chain(mesh)
171 .into_iter()
172 .map(|item| level(item.mesh, item.error))
173 .collect::<Vec<_>>();
174 if levels[0].mesh.triangle_count() == 0 {
175 return Err("LOD mesh has no triangles".into());
176 }
177 let index = self.objects.len();
178 self.objects.push(Object {
179 instance,
180 bounds: mesh.bounds,
181 source: Source::Chain(levels),
182 selected: 0,
183 previous: None,
184 distance: 0.0,
185 ideal_triangles: 0,
186 });
187 Ok(index)
188 }
189
190 pub fn add_shape(&mut self, instance: Instance, shape: Shape) -> usize {
191 let bounds = shape.mesh(0.05).bounds;
192 let last_bucket = ((bounds.extent() * 0.1).max(1e-6).log2() * 2.0)
193 .floor()
194 .clamp(FIRST_BUCKET as f32, LAST_BUCKET as f32) as i32;
195 let index = self.objects.len();
196 self.objects.push(Object {
197 instance,
198 bounds,
199 source: Source::Analytic {
200 shape,
201 levels: BTreeMap::new(),
202 last_bucket,
203 },
204 selected: 0,
205 previous: None,
206 distance: 0.0,
207 ideal_triangles: 0,
208 });
209 index
210 }
211
212 pub fn instance_mut(&mut self, index: usize) -> Option<&mut Instance> {
213 self.objects
214 .get_mut(index)
215 .map(|object| &mut object.instance)
216 }
217
218 pub fn selected_level(&self, index: usize) -> Option<(usize, f32, usize)> {
219 self.objects.get(index).and_then(|object| {
220 object
221 .level(object.selected)
222 .map(|level| (object.selected, level.error, level.mesh.triangle_count()))
223 })
224 }
225
226 pub fn selected_mesh(&self, index: usize) -> Option<&Mesh> {
227 self.objects
228 .get(index)
229 .and_then(|object| object.level(object.selected))
230 .map(|level| &level.mesh)
231 }
232
233 pub fn stats(&self) -> LodStats {
234 self.stats
235 }
236
237 pub fn select(&mut self, camera: Camera, viewport_height: u32) -> LodStats {
238 let fov_y = 2.0 * (1.0 / camera.projection[1][1].abs().max(1e-8)).atan();
239 let mut stats = LodStats::default();
240 for object in &mut self.objects {
241 let bounds = world_bounds(object.bounds, object.instance.model);
242 let center = bounds.center();
243 let distance = center
244 .iter()
245 .zip(camera.position)
246 .map(|(a, b)| (*a - b) * (*a - b))
247 .sum::<f32>()
248 .sqrt();
249 object.distance = distance;
250 let scale = maximum_stretch(object.instance.model);
251 let index = match &object.source {
252 Source::Chain(levels) => {
253 let errors = levels
254 .iter()
255 .map(|level| level.error * scale * ERROR_SAFETY)
256 .collect::<Vec<_>>();
257 detail_level(
258 bounds,
259 &errors,
260 distance,
261 fov_y,
262 viewport_height as f32,
263 object.previous,
264 )
265 }
266 Source::Analytic { last_bucket, .. } => {
267 let errors = (FIRST_BUCKET..=*last_bucket)
268 .map(|bucket| bucket_error(bucket) * scale * ERROR_SAFETY)
269 .collect::<Vec<_>>();
270 detail_level(
271 bounds,
272 &errors,
273 distance,
274 fov_y,
275 viewport_height as f32,
276 object.previous,
277 )
278 }
279 };
280 object.selected = index;
281 object.previous = Some(index);
282 object.ensure_level(index);
283 object.ideal_triangles = object.triangle_count();
284 stats.ideal_triangles += object.ideal_triangles;
285 }
286 stats.triangles = stats.ideal_triangles;
287 if stats.triangles > self.triangle_budget {
288 let mut order = (0..self.objects.len()).collect::<Vec<_>>();
289 order.sort_by(|&a, &b| {
290 self.objects[b]
291 .distance
292 .total_cmp(&self.objects[a].distance)
293 .then(a.cmp(&b))
294 });
295 for index in order {
296 let object = &mut self.objects[index];
297 let before = object.selected;
298 while stats.triangles > self.triangle_budget && object.selected < object.max_index()
299 {
300 let old = object.triangle_count();
301 object.selected += 1;
302 object.ensure_level(object.selected);
303 let new = object.triangle_count();
304 stats.triangles = stats.triangles.saturating_sub(old).saturating_add(new);
305 }
306 stats.degraded_objects += usize::from(object.selected != before);
307 if stats.triangles <= self.triangle_budget {
308 break;
309 }
310 }
311 }
312 stats.over_budget_triangles = stats.triangles.saturating_sub(self.triangle_budget);
313 stats.cached_levels = self
314 .objects
315 .iter()
316 .map(|object| match &object.source {
317 Source::Chain(levels) => levels.len(),
318 Source::Analytic { levels, .. } => levels.len(),
319 })
320 .sum();
321 self.stats = stats;
322 stats
323 }
324
325 pub fn upload_selected(
326 &mut self,
327 uploader: &mut impl MeshUploader,
328 ) -> Result<Vec<Instance>, String> {
329 let mut instances = Vec::with_capacity(self.objects.len());
330 for object in &mut self.objects {
331 let index = object.selected;
332 let level = object
333 .level_mut(index)
334 .ok_or("LOD level was not selected")?;
335 let handle = if let Some(handle) = level.handle {
336 handle
337 } else {
338 let mesh = &level.mesh;
339 let handle = uploader.upload_mesh(MeshData {
340 positions: &mesh.positions,
341 normals: &mesh.normals,
342 tangents: &mesh.tangents,
343 uvs: &mesh.uvs,
344 uvs1: None,
345 alpha: None,
346 indices: &mesh.indices,
347 })?;
348 level.handle = Some(handle);
349 handle
350 };
351 let mut instance = object.instance;
352 instance.mesh = handle;
353 instances.push(instance);
354 }
355 Ok(instances)
356 }
357}
358
359#[cfg(test)]
360mod tests {
361 use super::*;
362 use pfx_geom::detail::{SILHOUETTE_PIXELS, projected_pixels};
363 use pfx_gpu::{Gpu, wgpu};
364 use std::f32::consts::PI;
365
366 fn identity() -> Matrix {
367 [
368 [1.0, 0.0, 0.0, 0.0],
369 [0.0, 1.0, 0.0, 0.0],
370 [0.0, 0.0, 1.0, 0.0],
371 [0.0, 0.0, 0.0, 1.0],
372 ]
373 }
374
375 fn camera(z: f32) -> Camera {
376 let mut projection = identity();
377 projection[1][1] = 1.0 / (0.75_f32 * 0.5).tan();
378 Camera {
379 view: identity(),
380 projection,
381 previous_view_projection: identity(),
382 position: [0.0, 0.0, z],
383 }
384 }
385
386 fn instance(z: f32, id: u32) -> Instance {
387 let mut model = identity();
388 model[3][2] = z;
389 Instance::new(MeshHandle(0), model, 0, id)
390 }
391
392 fn slab() -> Shape {
393 Shape::Slab {
394 half_length: 2.8,
395 radius: 1.8,
396 height: 0.16,
397 fillet: 0.12,
398 }
399 }
400
401 #[test]
402 fn close_slab_is_finer_than_far_slab() {
403 let mut set = LodSet::new(2_000_000);
404 set.add_shape(instance(0.0, 1), slab());
405 set.add_shape(instance(-20.0, 2), slab());
406 let stats = set.select(camera(5.0), 2160);
407 let close = set.selected_level(0).unwrap();
408 let far = set.selected_level(1).unwrap();
409 assert!(close.0 < far.0);
410 assert!(close.2 > far.2);
411 assert_eq!(stats.degraded_objects, 0);
412 }
413
414 #[test]
415 fn hysteresis_holds_level_across_threshold() {
416 let mut set = LodSet::new(2_000_000);
417 set.add_shape(instance(0.0, 1), slab());
418 set.select(camera(5.0), 2160);
419 let selected = set.selected_level(0).unwrap().0;
420 let next_error = bucket_error(FIRST_BUCKET + selected as i32 + 1) * ERROR_SAFETY;
421 let bound = world_bounds(set.objects[0].bounds, identity());
422 let fov = 0.75_f32;
423 let threshold = bound.center()[2]
424 + bound.radius()
425 + next_error * 2160.0 / (2.0 * (fov * 0.5).tan() * SILHOUETTE_PIXELS);
426 set.select(camera(threshold * 0.99), 2160);
427 let before = set.selected_level(0).unwrap().0;
428 set.select(camera(threshold * 1.01), 2160);
429 assert_eq!(set.selected_level(0).unwrap().0, before);
430 }
431
432 #[test]
433 fn analytic_cache_reuses_error_bucket() {
434 struct CountingUploader(u32);
435 impl MeshUploader for CountingUploader {
436 fn upload_mesh(&mut self, _data: MeshData<'_>) -> Result<MeshHandle, String> {
437 let handle = MeshHandle(self.0);
438 self.0 += 1;
439 Ok(handle)
440 }
441 }
442 let mut set = LodSet::new(2_000_000);
443 set.add_shape(instance(0.0, 1), slab());
444 let mut uploader = CountingUploader(0);
445 let first = set.select(camera(5.0), 2160);
446 let selected = set.selected_level(0).unwrap().0;
447 set.upload_selected(&mut uploader).unwrap();
448 let second = set.select(camera(5.01), 2160);
449 set.upload_selected(&mut uploader).unwrap();
450 assert_eq!(set.selected_level(0).unwrap().0, selected);
451 assert_eq!(first.cached_levels, second.cached_levels);
452 assert_eq!(second.cached_levels, 1);
453 assert_eq!(uploader.0, 1);
454 }
455
456 #[test]
457 fn budget_degrades_farther_instance_first() {
458 let mut set = LodSet::new(0);
459 set.add_shape(instance(0.0, 1), slab());
460 set.add_shape(instance(-20.0, 2), slab());
461 let stats = set.select(camera(5.0), 2160);
462 assert!(stats.degraded_objects > 0);
463 assert_eq!(set.objects[1].selected, set.objects[1].max_index());
464 assert!(stats.triangles <= stats.ideal_triangles);
465 assert_eq!(stats.over_budget_triangles, stats.triangles);
466 }
467
468 #[test]
469 #[ignore = "needs a GPU; run under pgpu"]
470 fn bench_slab_4k_silhouette_under_half_pixel() {
471 let width = 3840;
472 let height = 2160;
473 let mut set = LodSet::new(2_000_000);
474 set.add_shape(instance(0.0, 1), slab());
475 let stats = set.select(camera(5.0), height);
476 assert_eq!(stats.degraded_objects, 0);
477 let mesh = set.selected_mesh(0).unwrap().clone();
478 let gpu = pollster::block_on(Gpu::headless()).unwrap();
479 let mut frame = Frame::new(gpu, 64, 64).unwrap();
480 let instances = set.upload_selected(&mut frame).unwrap();
481 let (positions, indices, count) = frame.shadow_mesh(instances[0].mesh).unwrap();
482 let target = frame
483 .gpu
484 .offscreen(width, height, wgpu::TextureFormat::Rgba8UnormSrgb)
485 .unwrap();
486 let shader = frame.gpu.device.create_shader_module(wgpu::ShaderModuleDescriptor {
487 label: Some("LOD silhouette test"),
488 source: wgpu::ShaderSource::Wgsl(
489 format!(
490 "{LOD_WGSL}\n@vertex fn vertex(@location(0) position: vec3f) -> @builtin(position) vec4f {{ let f = 1.0 / tan(0.375); return vec4f(position.x * f / (3840.0 / 2160.0), position.y * f, 0.0, 5.0 - position.z); }} @fragment fn fragment(@builtin(position) position: vec4f) -> @location(0) vec4f {{ if !lod_keep(vec2u(position.xy), 1u, 1.0) {{ discard; }} return vec4f(1.0); }}"
491 )
492 .into(),
493 ),
494 });
495 let layout = frame
496 .gpu
497 .device
498 .create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
499 label: Some("LOD silhouette layout"),
500 bind_group_layouts: &[],
501 immediate_size: 0,
502 });
503 let pipeline = frame
504 .gpu
505 .device
506 .create_render_pipeline(&wgpu::RenderPipelineDescriptor {
507 label: Some("LOD silhouette pipeline"),
508 layout: Some(&layout),
509 vertex: wgpu::VertexState {
510 module: &shader,
511 entry_point: Some("vertex"),
512 buffers: &[Some(wgpu::VertexBufferLayout {
513 array_stride: 12,
514 step_mode: wgpu::VertexStepMode::Vertex,
515 attributes: &[wgpu::VertexAttribute {
516 format: wgpu::VertexFormat::Float32x3,
517 offset: 0,
518 shader_location: 0,
519 }],
520 })],
521 compilation_options: Default::default(),
522 },
523 primitive: wgpu::PrimitiveState {
524 cull_mode: None,
525 ..Default::default()
526 },
527 depth_stencil: None,
528 multisample: Default::default(),
529 fragment: Some(wgpu::FragmentState {
530 module: &shader,
531 entry_point: Some("fragment"),
532 targets: &[Some(wgpu::ColorTargetState {
533 format: target.format,
534 blend: None,
535 write_mask: wgpu::ColorWrites::ALL,
536 })],
537 compilation_options: Default::default(),
538 }),
539 multiview_mask: None,
540 cache: None,
541 });
542 let mut encoder =
543 frame
544 .gpu
545 .device
546 .create_command_encoder(&wgpu::CommandEncoderDescriptor {
547 label: Some("LOD silhouette encoder"),
548 });
549 {
550 let mut pass = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
551 multiview_mask: None,
552 label: Some("LOD silhouette"),
553 color_attachments: &[Some(wgpu::RenderPassColorAttachment {
554 view: &target.view,
555 resolve_target: None,
556 ops: wgpu::Operations {
557 load: wgpu::LoadOp::Clear(wgpu::Color::BLACK),
558 store: wgpu::StoreOp::Store,
559 },
560 depth_slice: None,
561 })],
562 depth_stencil_attachment: None,
563 occlusion_query_set: None,
564 timestamp_writes: None,
565 });
566 pass.set_pipeline(&pipeline);
567 pass.set_vertex_buffer(0, positions.slice(..));
568 pass.set_index_buffer(indices.slice(..), wgpu::IndexFormat::Uint32);
569 pass.draw_indexed(0..count, 0, 0..1);
570 }
571 frame.gpu.queue.submit(Some(encoder.finish()));
572 let pixels = frame.gpu.readback_rgba8(&target).unwrap();
573 assert!(pixels.chunks_exact(4).any(|pixel| pixel[0] > 0));
574 assert_eq!(pixels[0], 0);
575 assert!(pixels[((height / 2 * width + width / 2) * 4) as usize] > 0);
576 let straight = 2.8 - 1.8;
577 let mut maximum = 0.0_f32;
578 for side in [-1.0_f32, 1.0] {
579 let mut outer = mesh
580 .positions
581 .iter()
582 .filter(|position| (position[2] - 0.08).abs() < 1e-5)
583 .filter(|position| position[0] * side >= straight - 1e-5)
584 .map(|position| (position[1].atan2(position[0] * side - straight), *position))
585 .collect::<Vec<_>>();
586 outer.sort_by(|a, b| a.0.total_cmp(&b.0));
587 assert!(outer.len() > 4);
588 for pair in outer.windows(2) {
589 if pair[1].0 - pair[0].0 > PI * 0.5 {
590 continue;
591 }
592 let midpoint = [
593 (pair[0].1[0] + pair[1].1[0]) * 0.5,
594 (pair[0].1[1] + pair[1].1[1]) * 0.5,
595 ];
596 let radial = ((midpoint[0] * side - straight).powi(2) + midpoint[1].powi(2)).sqrt();
597 let error = (1.8 - radial).abs();
598 maximum = maximum.max(projected_pixels(error, 5.0 - 0.08, 0.75, height as f32));
599 }
600 }
601 println!("4K bench slab maximum silhouette deviation: {maximum:.4} px");
602 assert!(maximum < 0.5, "{maximum} px");
603 }
604}