1use meshoptimizer_rs::*;
3use std::{error::Error as StdError, time::Instant};
4struct Reader<'a>(&'a [u8]);
5impl Reader<'_> {
6 fn u(&mut self) -> u32 {
7 let (v, rest) = self.0.split_at(4);
8 self.0 = rest;
9 u32::from_le_bytes(v.try_into().expect("four bytes"))
10 }
11 fn f(&mut self) -> f32 {
12 f32::from_bits(self.u())
13 }
14 fn points(&mut self, n: usize) -> Vec<[f32; 3]> {
15 (0..n).map(|_| core::array::from_fn(|_| self.f())).collect()
16 }
17}
18fn compact<T: Copy>(values: &[T], stride: usize, representatives: &[usize]) -> Vec<T> {
19 representatives
20 .iter()
21 .flat_map(|&i| values[i * stride..(i + 1) * stride].iter().copied())
22 .collect()
23}
24fn maximum(values: &[f64]) -> f64 {
25 values.iter().copied().fold(0., f64::max)
26}
27fn p95(values: &[f64]) -> f64 {
28 if values.is_empty() {
29 return 0.;
30 }
31 let mut sorted = values.to_vec();
32 sorted.sort_by(f64::total_cmp);
33 sorted[(sorted.len() * 95).div_ceil(100) - 1]
34}
35fn time_mesh(
37 mut action: impl FnMut() -> Result<SimplifiedMesh, Error>,
38 max_batch: usize,
39) -> Result<(SimplifiedMesh, f64), Error> {
40 fn batch(
41 action: &mut impl FnMut() -> Result<SimplifiedMesh, Error>,
42 count: usize,
43 reference: &SimplifiedMesh,
44 ) -> Result<f64, Error> {
45 let mut meshes = Vec::with_capacity(count);
46 let start = Instant::now();
47 for _ in 0..count {
48 meshes.push(std::hint::black_box(action())?);
49 }
50 let elapsed = start.elapsed().as_secs_f64();
51 for mesh in meshes {
52 assert_eq!(mesh.indices, reference.indices);
53 assert_eq!(mesh.error.to_bits(), reference.error.to_bits());
54 }
55 Ok(elapsed)
56 }
57 let reference = std::hint::black_box(action())?;
58 let mut count = 1;
59 loop {
60 let elapsed = batch(&mut action, count, &reference)?;
61 if elapsed >= 0.01 || count >= max_batch {
62 break;
63 }
64 count = count.saturating_mul(2).min(max_batch);
65 }
66 let mut timings = [0.; 3];
67 for ms in &mut timings {
68 *ms = batch(&mut action, count, &reference)? * 1000. / count as f64;
69 }
70 timings.sort_by(f64::total_cmp);
71 Ok((reference, timings[1]))
72}
73
74fn main() -> Result<(), Box<dyn StdError>> {
75 let path = std::env::args().nth(1).ok_or("input required")?;
76 let timing_only = std::env::args().any(|arg| arg == "--timing-only");
77 let bytes = std::fs::read(&path)?;
78 let mut r = Reader(&bytes);
79 let [n, ni, nb, ns, np, na, influences, aw, kw] =
80 core::array::from_fn::<_, 9, _>(|_| r.u() as usize);
81 let p = r.points(n);
82 let indices: Vec<_> = (0..ni).map(|_| r.u()).collect();
83 let joints: Vec<_> = (0..n * influences).map(|_| r.u()).collect();
84 let weights: Vec<_> = (0..n * influences).map(|_| r.f()).collect();
85 let shapes: Vec<_> = (0..ns).map(|_| r.points(n)).collect();
86 let attr: Vec<_> = (0..n * aw).map(|_| r.f()).collect();
87 let keys = &r.0[..n * kw];
88 r.0 = &r.0[n * kw..];
89 let importance: Vec<_> = (0..nb).map(|_| r.f()).collect();
90 let samples: Vec<_> = (0..np).map(|_| r.points(n)).collect();
91 assert!(r.0.is_empty());
92 let mut ws = Workspace::default();
93 let streams: Vec<_> = (0..kw)
95 .step_by(256)
96 .map(|offset| VertexStream::new(keys, n, (kw - offset).min(256), kw, offset))
97 .collect::<Result<_, _>>()?;
98 let remap = generate_vertex_remap_multi(Some(&indices), &streams, &mut ws)?;
99 let mut representatives = vec![usize::MAX; remap.vertex_count];
100 for (i, &j) in remap.remap.iter().enumerate() {
101 if j != u32::MAX {
102 representatives[j as usize] = i;
103 }
104 }
105 let indices = remap_index_buffer(Some(&indices), &remap.remap, &mut ws)?;
106 let p = compact(&p, 1, &representatives);
107 let joints = compact(&joints, influences, &representatives);
108 let weights = compact(&weights, influences, &representatives);
109 let attr = compact(&attr, aw, &representatives);
110 let shapes: Vec<_> = shapes
111 .iter()
112 .map(|s| compact(s, 1, &representatives))
113 .collect();
114 let samples: Vec<_> = samples
115 .iter()
116 .map(|s| compact(s, 1, &representatives))
117 .collect();
118 eprintln!(
119 "weld vertices {n}->{} triangles {}->{} channels {}",
120 p.len(),
121 ni / 3,
122 indices.len() / 3,
123 nb + ns * 3
124 );
125 let shape_refs: Vec<_> = shapes.iter().map(Vec::as_slice).collect();
126 let unit = vec![1.; nb];
127 let mut data = CharacterInputs::new();
128 data.blend_shapes = &shape_refs;
129 let ratios = if ni / 3 >= 10000 {
130 vec![0.5, 0.25, 0.1, 0.05]
131 } else {
132 vec![0.5, 0.25, 0.1]
133 };
134 if std::env::args().any(|arg| arg == "--best-of") {
135 ws = Workspace::new(Limits {
138 max_work: 1 << 42,
139 ..Limits::default()
140 });
141 data.skin = if nb == 0 {
142 None
143 } else {
144 Some(CharacterSkin::new(&joints, &weights, influences, &unit))
145 };
146 let sample_refs: Vec<_> = samples.iter().map(Vec::as_slice).collect();
147 data.sample_poses = &sample_refs;
148 println!(
149 "target,chosen,triangles,plain_max,character_max,selected_max,character_ms,bestof_ms"
150 );
151 for ratio in ratios {
152 let counts = [((ni / 3) as f64 * ratio) as usize * 3];
153 let mut co =
154 LodChainOptions::new(LodTargets::Counts(&counts), LodErrors::Uniform(100.));
155 let attr_weights = vec![1.; aw];
156 if aw != 0 {
157 co.attributes = Some(LodChainAttributes::new(
158 Attributes::from_interleaved(&attr, p.len(), aw, aw, 0)?,
159 &attr_weights,
160 ));
161 }
162 let extent = samples
163 .iter()
164 .chain(std::iter::once(&p))
165 .map(|s| simplify_scale(Positions::from_packed(s)))
166 .collect::<Result<Vec<_>, _>>()?
167 .into_iter()
168 .fold(0.0f32, f32::max);
169 let mut qo = LodQualityOptions::default();
170 qo.samples_per_unit_area = if extent > 0. {
171 1e-6 / f64::from(extent).powi(2)
172 } else {
173 0.
174 };
175 let mut character_co = co;
176 character_co.attributes = None;
177 eprintln!("target {ratio}: character chain");
178 let start = Instant::now();
179 let character = build_character_lod_chain(
180 &indices,
181 Positions::from_packed(&p),
182 &data,
183 &CharacterOptions::default(),
184 &character_co,
185 &qo,
186 &mut ws,
187 )?;
188 let character_ms = start.elapsed().as_secs_f64() * 1000.;
189 eprintln!(
190 "target {ratio}: character {character_ms:.3} ms, usage {:?}",
191 ws.usage()
192 );
193 let mut options = CharacterOptions::default();
194 options.best_of = true;
195 eprintln!("target {ratio}: best-of chain");
196 let start = Instant::now();
197 let selected = build_character_lod_chain(
198 &indices,
199 Positions::from_packed(&p),
200 &data,
201 &options,
202 &co,
203 &qo,
204 &mut ws,
205 )?;
206 let bestof_ms = start.elapsed().as_secs_f64() * 1000.;
207 eprintln!(
208 "target {ratio}: best-of {bestof_ms:.3} ms, usage {:?}",
209 ws.usage()
210 );
211 let report = selected.selections[0];
212 let max = selected
213 .quality
214 .iter()
215 .fold(0.0f64, |v, q| v.max(q[0].symmetric.max));
216 let char_max = character
217 .quality
218 .iter()
219 .fold(0.0f64, |v, q| v.max(q[0].symmetric.max));
220 assert_eq!(char_max, report.character_max);
221 assert!(max <= report.plain_max && max <= report.character_max);
222 let chosen = match report.method {
223 CharacterLodMethod::Plain => "plain",
224 CharacterLodMethod::Character => "character",
225 _ => unreachable!(),
226 };
227 println!(
228 "{ratio},{chosen},{},{:.17},{:.17},{max:.17},{character_ms:.6},{bestof_ms:.6}",
229 selected.chain.levels[0].triangle_count, report.plain_max, report.character_max
230 );
231 let out: Vec<_> = selected.chain.levels[0]
232 .indices
233 .iter()
234 .flat_map(|v| v.to_le_bytes())
235 .collect();
236 std::fs::write(format!("{path}.{ratio}.bestof.indices"), out)?;
237 }
238 return Ok(());
239 }
240 println!("ratio,method,vertices,triangles,bind,animation_max,animation_p95,morph_max,morph_p95,ms,worst_pose,status");
241 for ratio in ratios {
242 let settings = SimplifySettings {
243 target_index_count: ((ni / 3) as f64 * ratio) as usize * 3,
244 target_error: 100.,
245 options: SimplifyOptions::EMPTY,
246 };
247 for method in ["plain", "character", "important"] {
248 let imp = if method == "important" {
249 &importance
250 } else {
251 &unit
252 };
253 data.skin = if nb == 0 {
254 None
255 } else {
256 Some(CharacterSkin::new(&joints, &weights, influences, imp))
257 };
258 let result = time_mesh(
259 || {
260 let positions = std::hint::black_box(Positions::from_packed(&p));
261 let settings = std::hint::black_box(settings);
262 let indices = std::hint::black_box(indices.as_slice());
263 if method == "plain" {
264 if aw == 0 {
265 simplify(indices, positions, settings, std::hint::black_box(&mut ws))
266 } else {
267 simplify_with_attributes(
268 indices,
269 positions,
270 Attributes::from_interleaved(&attr, p.len(), aw, aw, 0)?,
271 &vec![1.; aw],
272 None,
273 settings,
274 std::hint::black_box(&mut ws),
275 )
276 }
277 } else {
278 simplify_character(
279 indices,
280 positions,
281 std::hint::black_box(&data),
282 &CharacterOptions::default(),
283 settings,
284 std::hint::black_box(&mut ws),
285 )
286 }
287 },
288 (1_000_000 / indices.len().max(1)).clamp(1, 4096),
289 );
290 let (mesh, ms) = match result {
291 Ok(result) => result,
292 Err(e) => {
293 println!("{ratio},{method},{},,,,,,,,,{e:?}", p.len());
294 continue;
295 }
296 };
297 if timing_only {
298 println!(
299 "{ratio},{method},{},{},,,,,,{ms:.6},,timing_only",
300 p.len(),
301 mesh.indices.len() / 3
302 );
303 let mut out = Vec::new();
304 for index in &mesh.indices {
305 out.extend_from_slice(&index.to_le_bytes());
306 }
307 std::fs::write(format!("{path}.{ratio}.{method}.indices"), out)?;
308 continue;
309 }
310 let measure = |sample: &[[f32; 3]], ws: &mut Workspace| -> Result<f64, Error> {
311 let pos = Positions::from_packed(sample);
312 let extent = f64::from(simplify_scale(pos)?);
313 let mut qo = LodQualityOptions::default();
314 qo.samples_per_unit_area = if extent > 0. {
317 1e-6 / (extent * extent)
318 } else {
319 0.
320 };
321 Ok(measure_lod_quality(
322 LodQualityMesh::new(&indices, pos),
323 LodQualityMesh::new(&mesh.indices, pos),
324 &qo,
325 ws,
326 )?
327 .symmetric
328 .max)
329 };
330 let bind = measure(&p, &mut ws)?;
331 let deviations: Vec<_> = samples
332 .iter()
333 .map(|s| measure(s, &mut ws))
334 .collect::<Result<_, _>>()?;
335 let worst = deviations
336 .iter()
337 .enumerate()
338 .max_by(|a, b| a.1.total_cmp(b.1))
339 .map(|v| v.0)
340 .filter(|&index| deviations[index] > bind);
341 let worst_label = worst.map_or_else(|| "bind".to_owned(), |index| index.to_string());
342 println!(
343 "{ratio},{method},{},{},{bind:.9},{:.9},{:.9},{:.9},{:.9},{:.6},{worst_label},ok",
344 p.len(),
345 mesh.indices.len() / 3,
346 maximum(&deviations[..na]),
347 p95(&deviations[..na]),
348 maximum(&deviations[na..]),
349 p95(&deviations[na..]),
350 ms
351 );
352 let prefix = format!("{path}.{ratio}.{method}");
354 let mut out = Vec::new();
355 for v in &mesh.indices {
356 out.extend_from_slice(&v.to_le_bytes());
357 }
358 std::fs::write(format!("{prefix}.indices"), out)?;
359 let mut out = Vec::new();
360 for point in worst.and_then(|index| samples.get(index)).unwrap_or(&p) {
361 for v in point {
362 out.extend_from_slice(&v.to_le_bytes());
363 }
364 }
365 std::fs::write(format!("{prefix}.pose"), out)?;
366 }
367 }
368 let mut out = Vec::new();
369 for v in &indices {
370 out.extend_from_slice(&v.to_le_bytes());
371 }
372 std::fs::write(format!("{path}.source.indices"), out)?;
373 Ok(())
374}