1use bytemuck::{Pod, Zeroable};
2use glam::Vec3;
3
4use crate::Mesh;
5
6const UNIT: f32 = 65535.0;
7const NARROW_LIMIT: usize = u16::MAX as usize;
8
9#[repr(C)]
10#[derive(Clone, Copy, Debug, PartialEq, Eq, Pod, Zeroable)]
11pub struct PackedVertex {
12 position: [u16; 3],
13 normal: [u16; 2],
14}
15
16impl PackedVertex {
17 pub fn new(position: [u16; 3], normal: [u16; 2]) -> Self {
18 Self { position, normal }
19 }
20
21 pub fn position(self) -> [u16; 3] {
22 self.position
23 }
24
25 pub fn normal(self) -> [u16; 2] {
26 self.normal
27 }
28}
29
30#[derive(Clone, Copy, Debug, PartialEq)]
31pub struct GeometryGroup {
32 min: [f32; 3],
33 scale: [f32; 3],
34 first_vertex: u32,
35 vertex_count: u32,
36 first_index: u32,
37 index_count: u32,
38 wide: bool,
39}
40
41impl GeometryGroup {
42 pub fn new(
43 min: [f32; 3],
44 scale: [f32; 3],
45 first_vertex: u32,
46 vertex_count: u32,
47 first_index: u32,
48 index_count: u32,
49 wide: bool,
50 ) -> Self {
51 Self {
52 min,
53 scale,
54 first_vertex,
55 vertex_count,
56 first_index,
57 index_count,
58 wide,
59 }
60 }
61
62 pub fn min(self) -> [f32; 3] {
63 self.min
64 }
65
66 pub fn scale(self) -> [f32; 3] {
67 self.scale
68 }
69
70 pub fn first_vertex(self) -> u32 {
71 self.first_vertex
72 }
73
74 pub fn vertex_count(self) -> u32 {
75 self.vertex_count
76 }
77
78 pub fn first_index(self) -> u32 {
79 self.first_index
80 }
81
82 pub fn index_count(self) -> u32 {
83 self.index_count
84 }
85
86 pub fn wide(self) -> bool {
87 self.wide
88 }
89}
90
91#[derive(Clone, Debug, Default, PartialEq)]
92pub struct PackedMesh {
93 groups: Vec<GeometryGroup>,
94 vertices: Vec<PackedVertex>,
95 narrow: Vec<u16>,
96 wide: Vec<u32>,
97}
98
99impl PackedMesh {
100 pub fn new(mesh: Mesh) -> Self {
101 let vertices = mesh.vertices();
102 let indices = mesh.indices();
103 if indices.is_empty() {
104 assert!(vertices.is_empty(), "an empty mesh carries no vertices");
105 return Self::default();
106 }
107 let objects = vertices
108 .iter()
109 .map(|vertex| vertex.object() as usize)
110 .max()
111 .map_or(0, |object| object + 1);
112 assert!(objects > 0, "a non empty mesh names an object");
113 let mut counts = vec![0u32; objects];
114 let mut low = vec![[f32::INFINITY; 3]; objects];
115 let mut high = vec![[f32::NEG_INFINITY; 3]; objects];
116 for vertex in vertices {
117 let object = vertex.object() as usize;
118 assert!(object < objects, "a mesh vertex names an object");
119 counts[object] += 1;
120 for (axis, value) in vertex.position().into_iter().enumerate() {
121 low[object][axis] = low[object][axis].min(value);
122 high[object][axis] = high[object][axis].max(value);
123 }
124 }
125 assert!(
126 counts.iter().all(|count| *count > 0),
127 "every mesh object carries vertices"
128 );
129 let mut first = vec![0u32; objects];
130 let mut next = 0u32;
131 for (slot, count) in first.iter_mut().zip(&counts) {
132 assert!((next as u64) + u64::from(*count) <= u64::from(u32::MAX));
133 *slot = next;
134 next += *count;
135 }
136 let mut scale = vec![[0.0f32; 3]; objects];
137 for object in 0..objects {
138 for axis in 0..3 {
139 let extent = high[object][axis] - low[object][axis];
140 scale[object][axis] = if extent > 0.0 { extent / UNIT } else { 0.0 };
141 }
142 }
143 let mut local = vec![0u32; vertices.len()];
144 let mut packed = vec![PackedVertex::new([0; 3], [0; 2]); vertices.len()];
145 let mut cursor = first.clone();
146 for (index, vertex) in vertices.iter().enumerate() {
147 let object = vertex.object() as usize;
148 let at = cursor[object] as usize;
149 cursor[object] += 1;
150 local[index] = at as u32;
151 let position = [0, 1, 2].map(|axis| {
152 quantize(
153 vertex.position()[axis],
154 low[object][axis],
155 scale[object][axis],
156 )
157 });
158 packed[at] = PackedVertex::new(position, encode_normal(vertex.normal()));
159 }
160 let mut triangles = vec![0u32; objects];
161 for triangle in indices.as_chunks::<3>().0 {
162 let object = vertices[triangle[0] as usize].object() as usize;
163 assert!(
164 triangle
165 .iter()
166 .all(|index| vertices[*index as usize].object() as usize == object),
167 "a mesh triangle belongs to one object"
168 );
169 triangles[object] += 1;
170 }
171 assert!(
172 triangles.iter().all(|count| *count > 0),
173 "every mesh object carries triangles"
174 );
175 let mut first_index = vec![0u32; objects];
176 let mut next_narrow = 0u32;
177 let mut next_wide = 0u32;
178 for object in 0..objects {
179 if counts[object] > NARROW_LIMIT as u32 {
180 first_index[object] = next_wide;
181 next_wide += triangles[object] * 3;
182 } else {
183 first_index[object] = next_narrow;
184 next_narrow += triangles[object] * 3;
185 }
186 }
187 let mut narrow = vec![0u16; next_narrow as usize];
188 let mut wide = vec![0u32; next_wide as usize];
189 let mut narrow_cursor = first_index.clone();
190 let mut wide_cursor = first_index.clone();
191 for triangle in indices.as_chunks::<3>().0 {
192 let object = vertices[triangle[0] as usize].object() as usize;
193 if counts[object] > NARROW_LIMIT as u32 {
194 let start = wide_cursor[object] as usize;
195 wide_cursor[object] += 3;
196 for (offset, index) in triangle.iter().enumerate() {
197 wide[start + offset] = local[*index as usize] - first[object];
198 }
199 } else {
200 let start = narrow_cursor[object] as usize;
201 narrow_cursor[object] += 3;
202 for (offset, index) in triangle.iter().enumerate() {
203 narrow[start + offset] = (local[*index as usize] - first[object]) as u16;
204 }
205 }
206 }
207 let groups = (0..objects)
208 .map(|object| {
209 GeometryGroup::new(
210 low[object],
211 scale[object],
212 first[object],
213 counts[object],
214 first_index[object],
215 triangles[object] * 3,
216 counts[object] > NARROW_LIMIT as u32,
217 )
218 })
219 .collect();
220 Self {
221 groups,
222 vertices: packed,
223 narrow,
224 wide,
225 }
226 }
227
228 pub fn from_parts(
229 groups: Vec<GeometryGroup>,
230 vertices: Vec<PackedVertex>,
231 narrow: Vec<u16>,
232 wide: Vec<u32>,
233 ) -> Option<Self> {
234 let mut next_vertex = 0usize;
235 let mut next_narrow = 0usize;
236 let mut next_wide = 0usize;
237 for group in &groups {
238 if group.vertex_count == 0
239 || group.index_count == 0
240 || !group.index_count.is_multiple_of(3)
241 {
242 return None;
243 }
244 if group.first_vertex as usize != next_vertex {
245 return None;
246 }
247 next_vertex = next_vertex.checked_add(group.vertex_count as usize)?;
248 if next_vertex > vertices.len() {
249 return None;
250 }
251 if group
252 .min
253 .iter()
254 .chain(&group.scale)
255 .any(|value| !value.is_finite())
256 || group.scale.iter().any(|value| *value < 0.0)
257 || (0..3).any(|axis| !(group.min[axis] + UNIT * group.scale[axis]).is_finite())
258 {
259 return None;
260 }
261 if group.wide {
262 if group.first_index as usize != next_wide {
263 return None;
264 }
265 let end = next_wide.checked_add(group.index_count as usize)?;
266 if end > wide.len()
267 || wide[next_wide..end]
268 .iter()
269 .any(|index| *index >= group.vertex_count)
270 {
271 return None;
272 }
273 next_wide = end;
274 } else {
275 if group.vertex_count > u32::from(u16::MAX) {
276 return None;
277 }
278 if group.first_index as usize != next_narrow {
279 return None;
280 }
281 let end = next_narrow.checked_add(group.index_count as usize)?;
282 if end > narrow.len()
283 || narrow[next_narrow..end]
284 .iter()
285 .any(|index| u32::from(*index) >= group.vertex_count)
286 {
287 return None;
288 }
289 next_narrow = end;
290 }
291 }
292 if next_vertex != vertices.len() || next_narrow != narrow.len() || next_wide != wide.len() {
293 return None;
294 }
295 Some(Self {
296 groups,
297 vertices,
298 narrow,
299 wide,
300 })
301 }
302
303 pub fn groups(&self) -> &[GeometryGroup] {
304 &self.groups
305 }
306
307 pub fn vertices(&self) -> &[PackedVertex] {
308 &self.vertices
309 }
310
311 pub fn narrow(&self) -> &[u16] {
312 &self.narrow
313 }
314
315 pub fn wide(&self) -> &[u32] {
316 &self.wide
317 }
318
319 pub fn object_count(&self) -> usize {
320 self.groups.len()
321 }
322
323 pub fn vertex_count(&self) -> usize {
324 self.vertices.len()
325 }
326
327 pub fn triangle_count(&self) -> usize {
328 self.groups
329 .iter()
330 .map(|group| group.index_count as usize / 3)
331 .sum()
332 }
333
334 pub fn is_empty(&self) -> bool {
335 self.groups.is_empty()
336 }
337
338 pub fn bytes(&self) -> u64 {
339 (self.groups.len() * size_of::<GeometryGroup>()
340 + self.vertices.len() * size_of::<PackedVertex>()
341 + self.narrow.len() * size_of::<u16>()
342 + self.wide.len() * size_of::<u32>()) as u64
343 }
344
345 pub fn triangle(&self, object: usize, triangle: usize) -> [[f32; 3]; 3] {
346 let group = self
347 .groups
348 .get(object)
349 .expect("the triangle names a packed object");
350 assert!(
351 triangle < group.index_count as usize / 3,
352 "the triangle lies inside its packed object"
353 );
354 let start = group.first_index as usize + triangle * 3;
355 [0, 1, 2].map(|corner| {
356 let index = if group.wide {
357 self.wide[start + corner]
358 } else {
359 u32::from(self.narrow[start + corner])
360 };
361 let vertex = self.vertices[group.first_vertex as usize + index as usize];
362 [0, 1, 2]
363 .map(|axis| group.min[axis] + f32::from(vertex.position[axis]) * group.scale[axis])
364 })
365 }
366}
367
368fn quantize(value: f32, min: f32, scale: f32) -> u16 {
369 if scale <= 0.0 {
370 return 0;
371 }
372 ((value - min) / scale).round().clamp(0.0, UNIT) as u16
373}
374
375fn encode_normal(normal: [f32; 3]) -> [u16; 2] {
376 let normal = Vec3::from(normal).normalize_or_zero();
377 let normal = if normal == Vec3::ZERO {
378 Vec3::Z
379 } else {
380 normal
381 };
382 let sum = normal.x.abs() + normal.y.abs() + normal.z.abs();
383 let mut x = normal.x / sum;
384 let mut y = normal.y / sum;
385 if normal.z < 0.0 {
386 let across = (1.0 - y.abs()) * sign(x);
387 let down = (1.0 - x.abs()) * sign(y);
388 x = across;
389 y = down;
390 }
391 [quantize_unit(x), quantize_unit(y)]
392}
393
394fn quantize_unit(value: f32) -> u16 {
395 (((value * 0.5 + 0.5).clamp(0.0, 1.0)) * UNIT).round() as u16
396}
397
398fn sign(value: f32) -> f32 {
399 if value < 0.0 { -1.0 } else { 1.0 }
400}