1use crate::input::PositionReader;
3use crate::workspace::{checked_bytes, topology, Work};
4use crate::{Error, Positions, Workspace};
5use alloc::vec::Vec;
6
7#[derive(Clone, Copy, Debug, Default, PartialEq)]
9pub struct OverdrawStatistics {
10 pub pixels_covered: u32,
12 pub pixels_shaded: u32,
14 pub overdraw: f32,
16}
17
18#[derive(Clone, Copy, Debug, Default, PartialEq)]
20pub struct CoverageStatistics {
21 pub coverage: [f32; 3],
23 pub extent: f32,
25}
26
27#[derive(Clone, Copy, Default)]
28struct Pixel {
29 depth: [f32; 2],
30 overdraw: [u32; 2],
31}
32const VIEWPORT: usize = 256;
33
34fn reserve<T: Default + Clone>(count: usize) -> Result<Vec<T>, Error> {
35 checked_bytes(count, core::mem::size_of::<T>())?;
36 let mut value = Vec::new();
37 value
38 .try_reserve_exact(count)
39 .map_err(|_| Error::AllocationFailed)?;
40 value.resize(count, T::default());
41 Ok(value)
42}
43
44fn transform(
45 indices: &[u32],
46 positions: impl PositionReader,
47 work: &mut Work,
48) -> Result<(Vec<[f32; 3]>, f32), Error> {
49 let mut minv = [f32::MAX; 3];
50 let mut maxv = [-f32::MAX; 3];
51 work.scan(0..positions.len(), |i| {
52 let value = positions.read(i);
53 for j in 0..3 {
54 if !value[j].is_finite() {
55 return Err(Error::NumericalFailure);
56 }
57 minv[j] = if minv[j] > value[j] {
58 value[j]
59 } else {
60 minv[j]
61 };
62 maxv[j] = if maxv[j] < value[j] {
63 value[j]
64 } else {
65 maxv[j]
66 };
67 }
68 Ok(())
69 })?;
70 let mut extent = 0.0f32;
71 for j in 0..3 {
72 let d = maxv[j] - minv[j];
73 extent = if d < extent { extent } else { d };
74 }
75 if !extent.is_finite() {
76 return Err(Error::NumericalFailure);
77 }
78 let scale = if extent == 0.0 {
79 0.0
80 } else {
81 VIEWPORT as f32 / extent
82 };
83 checked_bytes(indices.len(), core::mem::size_of::<[f32; 3]>())?;
84 let mut transformed = Vec::new();
85 transformed
86 .try_reserve_exact(indices.len())
87 .map_err(|_| Error::AllocationFailed)?;
88 let transform_position = |index: u32| {
89 let value = positions.read(index as usize);
91 [
92 (value[0] - minv[0]) * scale,
93 (value[1] - minv[1]) * scale,
94 (value[2] - minv[2]) * scale,
95 ]
96 };
97 if work.covers(indices.len())? {
98 work.add(indices.len())?;
99 transformed.extend(indices.iter().copied().map(transform_position));
102 } else {
103 for &index in indices {
104 work.add(1)?;
105 transformed.push(transform_position(index));
106 }
107 }
108 Ok((transformed, extent))
109}
110
111fn rasterize(buffer: &mut [Pixel], mut p: [[f32; 3]; 3], work: &mut Work) -> Result<(), Error> {
112 let det = (p[1][0] - p[0][0]) * (p[2][1] - p[0][1]) - (p[1][1] - p[0][1]) * (p[2][0] - p[0][0]);
113 let invdet = if det == 0.0 { 0.0 } else { 1.0 / det };
114 let mut dzx = ((p[1][2] - p[0][2]) * (p[2][1] - p[0][1])
115 - (p[1][1] - p[0][1]) * (p[2][2] - p[0][2]))
116 * invdet;
117 let mut dzy = ((p[1][0] - p[0][0]) * (p[2][2] - p[0][2])
118 - (p[1][2] - p[0][2]) * (p[2][0] - p[0][0]))
119 * invdet;
120 let side = usize::from(det > 0.0);
121 if side != 0 {
122 let (a, b) = p.split_at_mut(2);
123 core::mem::swap(&mut a[1][0], &mut b[0][0]);
124 core::mem::swap(&mut a[1][1], &mut b[0][1]);
125 p[0][2] = VIEWPORT as f32 - p[0][2];
126 dzx = -dzx;
127 dzy = -dzy;
128 }
129 let x = p.map(|v| (16.0 * v[0] + 0.5) as i32);
130 let y = p.map(|v| (16.0 * v[1] + 0.5) as i32);
131 let minx = ((x[0].min(x[1]).min(x[2]) + 7) >> 4).max(0);
132 let miny = ((y[0].min(y[1]).min(y[2]) + 7) >> 4).max(0);
133 let maxx = ((x[0].max(x[1]).max(x[2]) + 7) >> 4).min(VIEWPORT as i32);
134 let maxy = ((y[0].max(y[1]).max(y[2]) + 7) >> 4).min(VIEWPORT as i32);
135 let visits = (maxx - minx).max(0) as usize * (maxy - miny).max(0) as usize;
136 let bulk_pixels = work.covers(visits)?;
137 if bulk_pixels {
138 work.add(visits)?;
139 }
140 if minx >= maxx || miny >= maxy {
141 return Ok(());
142 }
143 let (dx12, dx23, dx31) = (x[0] - x[1], x[1] - x[2], x[2] - x[0]);
144 let (dy12, dy23, dy31) = (y[0] - y[1], y[1] - y[2], y[2] - y[0]);
145 let tl1 = i32::from(dy12 < 0 || (dy12 == 0 && dx12 > 0));
146 let tl2 = i32::from(dy23 < 0 || (dy23 == 0 && dx23 > 0));
147 let tl3 = i32::from(dy31 < 0 || (dy31 == 0 && dx31 > 0));
148 let (fx, fy) = ((minx << 4) + 8, (miny << 4) + 8);
149 let mut cy1 = dx12 * (fy - y[0]) - dy12 * (fx - x[0]) + tl1 - 1;
150 let mut cy2 = dx23 * (fy - y[1]) - dy23 * (fx - x[1]) + tl2 - 1;
151 let mut cy3 = dx31 * (fy - y[2]) - dy31 * (fx - x[2]) + tl3 - 1;
152 let mut zy = p[0][2] + (dzx * (fx - x[0]) as f32 + dzy * (fy - y[0]) as f32) * (1.0 / 16.0);
153 for yy in miny..maxy {
154 let (mut cx1, mut cx2, mut cx3) = (cy1, cy2, cy3);
155 let mut zx = zy;
156 let row_start = yy as usize * VIEWPORT + minx as usize;
157 let row_end = yy as usize * VIEWPORT + maxx as usize;
158 for pixel in &mut buffer[row_start..row_end] {
159 if !bulk_pixels {
160 work.add(1)?;
161 }
162 if (cx1 | cx2 | cx3) >= 0 && zx >= pixel.depth[side] {
163 pixel.depth[side] = zx;
164 pixel.overdraw[side] += 1;
165 }
166 cx1 -= dy12 << 4;
167 cx2 -= dy23 << 4;
168 cx3 -= dy31 << 4;
169 zx += dzx;
170 }
171 cy1 += dx12 << 4;
172 cy2 += dx23 << 4;
173 cy3 += dx31 << 4;
174 zy += dzy;
175 }
176 Ok(())
177}
178
179fn scan_pixels<const COVERAGE: bool, const CHARGE: bool>(
182 buffer: &[Pixel],
183 overdraw: &mut OverdrawStatistics,
184 work: &mut Work,
185) -> Result<u32, Error> {
186 let mut covered = 0;
187 for pixel in buffer {
188 if CHARGE {
189 work.add(1)?;
190 }
191 if COVERAGE {
192 covered += u32::from((pixel.overdraw[0] | pixel.overdraw[1]) > 0);
193 } else {
194 for &value in &pixel.overdraw {
195 overdraw.pixels_covered += u32::from(value > 0);
196 overdraw.pixels_shaded += value;
197 }
198 }
199 }
200 Ok(covered)
201}
202
203fn analyze(
204 indices: &[u32],
205 positions: Positions<'_>,
206 workspace: &mut Workspace,
207 coverage: bool,
208) -> Result<(OverdrawStatistics, CoverageStatistics), Error> {
209 let mut work = workspace.begin();
210 let result = (|| {
211 topology(indices, positions.len(), &mut work)?;
212 let bytes = checked_bytes(indices.len(), 12)?
213 .checked_add(checked_bytes(
214 VIEWPORT * VIEWPORT,
215 core::mem::size_of::<Pixel>(),
216 )?)
217 .ok_or(Error::SizeOverflow)?;
218 workspace.account_codec(bytes)?;
219 let (triangles, extent) = if let Some(packed) = positions.packed_values() {
220 transform(indices, packed, &mut work)?
221 } else {
222 transform(indices, positions, &mut work)?
223 };
224 let mut buffer = reserve::<Pixel>(VIEWPORT * VIEWPORT)?;
225 let mut overdraw = OverdrawStatistics::default();
226 let mut result_coverage = CoverageStatistics {
227 extent,
228 ..CoverageStatistics::default()
229 };
230 for axis in 0..3 {
231 if axis != 0 {
233 buffer.fill(Pixel::default());
234 }
235 for tri in triangles.as_chunks::<3>().0 {
236 work.add(1)?;
237 let [a, b, c] = *tri;
238 let reordered = match axis {
239 0 => [[a[2], a[1], a[0]], [b[2], b[1], b[0]], [c[2], c[1], c[0]]],
240 1 => [[a[0], a[2], a[1]], [b[0], b[2], b[1]], [c[0], c[2], c[1]]],
241 _ => [[a[1], a[0], a[2]], [b[1], b[0], b[2]], [c[1], c[0], c[2]]],
242 };
243 rasterize(&mut buffer, reordered, &mut work)?;
244 }
245 let bulk_scan = work.covers(buffer.len())?;
246 if bulk_scan {
247 work.add(buffer.len())?;
248 }
249 let covered = match (coverage, bulk_scan) {
250 (true, true) => scan_pixels::<true, false>(&buffer, &mut overdraw, &mut work)?,
251 (true, false) => scan_pixels::<true, true>(&buffer, &mut overdraw, &mut work)?,
252 (false, true) => scan_pixels::<false, false>(&buffer, &mut overdraw, &mut work)?,
253 (false, false) => scan_pixels::<false, true>(&buffer, &mut overdraw, &mut work)?,
254 };
255 if coverage {
256 result_coverage.coverage[axis] = covered as f32 / (VIEWPORT * VIEWPORT) as f32;
257 }
258 }
259 overdraw.overdraw = if overdraw.pixels_covered == 0 {
260 0.0
261 } else {
262 overdraw.pixels_shaded as f32 / overdraw.pixels_covered as f32
263 };
264 Ok((overdraw, result_coverage))
265 })();
266 workspace.finish(&work);
267 result
268}
269
270#[inline]
277pub fn analyze_overdraw_generic<I: crate::Index>(
278 indices: &[I],
279 positions: Positions<'_>,
280 workspace: &mut Workspace,
281) -> Result<OverdrawStatistics, Error> {
282 I::with_input(indices, workspace, |indices, workspace| {
283 analyze_overdraw_u32(indices, positions, workspace)
284 })
285}
286
287fn analyze_overdraw_u32(
288 indices: &[u32],
289 positions: Positions<'_>,
290 workspace: &mut Workspace,
291) -> Result<OverdrawStatistics, Error> {
292 Ok(analyze(indices, positions, workspace, false)?.0)
293}
294
295#[inline]
302pub fn analyze_coverage_generic<I: crate::Index>(
303 indices: &[I],
304 positions: Positions<'_>,
305 workspace: &mut Workspace,
306) -> Result<CoverageStatistics, Error> {
307 I::with_input(indices, workspace, |indices, workspace| {
308 analyze_coverage_u32(indices, positions, workspace)
309 })
310}
311
312fn analyze_coverage_u32(
313 indices: &[u32],
314 positions: Positions<'_>,
315 workspace: &mut Workspace,
316) -> Result<CoverageStatistics, Error> {
317 Ok(analyze(indices, positions, workspace, true)?.1)
318}
319
320#[inline]
322pub fn analyze_overdraw(
323 indices: &[u32],
324 positions: Positions<'_>,
325 workspace: &mut Workspace,
326) -> Result<OverdrawStatistics, Error> {
327 analyze_overdraw_generic::<u32>(indices, positions, workspace)
328}
329
330#[inline]
332pub fn analyze_coverage(
333 indices: &[u32],
334 positions: Positions<'_>,
335 workspace: &mut Workspace,
336) -> Result<CoverageStatistics, Error> {
337 analyze_coverage_generic::<u32>(indices, positions, workspace)
338}
339
340#[cfg(test)]
341mod tests {
342 use super::*;
343 use crate::Limits;
344
345 #[test]
346 fn empty_views_keep_triangle_and_scan_work() {
347 let storage = [
350 [1.01, 1.01, 1.01],
351 [1.03, 1.01, 1.02],
352 [1.01, 1.03, 1.03],
353 [0.0, 0.0, 0.0],
354 [256.0, 256.0, 256.0],
355 ];
356 let positions = Positions::from_packed(&storage);
357 let indices = [0, 1, 2, 0, 1, 2];
358 let total = 6 + 5 + 6 + 3 * (2 + VIEWPORT * VIEWPORT);
359 for fuel in [
360 0,
361 5,
362 6,
363 10,
364 11,
365 16,
366 17,
367 18,
368 19,
369 65555,
370 65556,
371 65557,
372 total - 1,
373 total,
374 ] {
375 for coverage in [false, true] {
376 let mut workspace = Workspace::new(Limits {
377 max_bytes: 2 << 20,
378 max_work: fuel as u64,
379 });
380 let result = analyze(&indices, positions, &mut workspace, coverage);
381 assert_eq!(workspace.usage().work, fuel as u64);
382 if fuel == total {
383 assert_eq!(
384 result,
385 Ok((
386 OverdrawStatistics::default(),
387 CoverageStatistics {
388 coverage: [0.0; 3],
389 extent: 256.0,
390 }
391 ))
392 );
393 } else {
394 assert_eq!(result, Err(Error::LimitExceeded));
395 }
396 }
397 }
398 }
399
400 #[test]
401 fn packed_transform_keeps_logical_mapped_positions() {
402 let storage = [
403 [0.0, 0.0, 0.0],
404 [1.0, 0.0, 0.0],
405 [0.0, 1.0, 0.0],
406 [f32::NAN; 3],
407 ];
408 let mapping = [2, 0, 1];
409 let ordered = mapping.map(|i| storage[i as usize]);
410 let mapped = Positions::from_packed(&storage).mapped(&mapping);
411 let reference = Positions::from_packed(&ordered);
412 let mut actual_ws = Workspace::default();
413 let mut reference_ws = Workspace::default();
414 assert_eq!(
415 analyze_overdraw(&[0, 1, 2], mapped, &mut actual_ws),
416 analyze_overdraw(&[0, 1, 2], reference, &mut reference_ws)
417 );
418 assert_eq!(actual_ws.usage(), reference_ws.usage());
419 assert_eq!(
420 analyze_coverage(&[0, 1, 2], mapped, &mut actual_ws),
421 analyze_coverage(&[0, 1, 2], reference, &mut reference_ws)
422 );
423 assert_eq!(actual_ws.usage(), reference_ws.usage());
424 }
425
426 #[test]
427 fn pixel_scan_keeps_tight_fuel_and_statistics_prefixes() {
428 let buffer = [[0, 0], [3, 0], [0, 5], [7, 11]].map(|overdraw| Pixel {
429 overdraw,
430 ..Pixel::default()
431 });
432 for limit in 0..=5 {
433 for coverage in [false, true] {
434 let mut workspace = Workspace::new(Limits {
435 max_bytes: 1024,
436 max_work: limit,
437 });
438 let mut work = workspace.begin();
439 let mut stats = OverdrawStatistics::default();
440 let result = if work.covers(buffer.len()).unwrap() {
441 work.add(buffer.len()).unwrap();
442 if coverage {
443 scan_pixels::<true, false>(&buffer, &mut stats, &mut work)
444 } else {
445 scan_pixels::<false, false>(&buffer, &mut stats, &mut work)
446 }
447 } else if coverage {
448 scan_pixels::<true, true>(&buffer, &mut stats, &mut work)
449 } else {
450 scan_pixels::<false, true>(&buffer, &mut stats, &mut work)
451 };
452 workspace.finish(&work);
453 assert_eq!(workspace.usage().work, limit.min(4));
454 assert_eq!(result.is_ok(), limit >= 4);
455 if coverage {
456 assert_eq!(
457 result,
458 if limit >= 4 {
459 Ok(3)
460 } else {
461 Err(Error::LimitExceeded)
462 }
463 );
464 assert_eq!((stats.pixels_covered, stats.pixels_shaded), (0, 0));
465 } else {
466 let expected = [(0, 0), (0, 0), (1, 3), (2, 8), (4, 26), (4, 26)];
467 assert_eq!(
468 (stats.pixels_covered, stats.pixels_shaded),
469 expected[limit as usize]
470 );
471 assert_eq!(
472 result,
473 if limit >= 4 {
474 Ok(0)
475 } else {
476 Err(Error::LimitExceeded)
477 }
478 );
479 }
480 }
481 }
482 }
483}