1use std::io;
4
5use crate::error::ErrorExt;
6use crate::navmesh::bytes::Reader;
7
8pub const NAVMESH_MAGIC: i32 = i32::from_le_bytes(*b"VAND");
10pub const NAVMESH_VERSION: i32 = 12;
12
13const HEADER_LEN: usize = 104;
14const VERT_LEN: usize = 12;
15const POLY_LEN: usize = 32;
16const LINK_LEN: usize = 16;
17const DETAIL_MESH_LEN: usize = 12;
18const DETAIL_TRI_LEN: usize = 4;
19const BV_NODE_LEN: usize = 16;
20const OFF_MESH_LEN: usize = 44;
21const PART_LEN: usize = 16;
22const PART_POLY_LEN: usize = 8;
23const OBSTACLE_LEN: usize = 16;
24const EXTRA_FIXED_LEN: usize = 12;
26
27#[derive(Debug, Clone, Default, PartialEq)]
32#[non_exhaustive]
33pub struct MeshHeader {
34 pub magic: i32,
36 pub version: i32,
38 pub x: i32,
40 pub y: i32,
42 pub layer: i32,
44 pub user_id: u32,
46 pub poly_count: i32,
48 pub vert_count: i32,
50 pub max_link_count: i32,
52 pub detail_mesh_count: i32,
54 pub detail_vert_count: i32,
56 pub detail_tri_count: i32,
58 pub bv_node_count: i32,
60 pub off_mesh_con_count: i32,
62 pub off_mesh_base: i32,
64 pub walkable_height: f32,
66 pub walkable_radius: f32,
68 pub walkable_climb: f32,
70 pub bmin: [f32; 3],
72 pub bmax: [f32; 3],
74 pub bv_quant_factor: f32,
76 pub extra_data_size: i32,
78}
79
80#[derive(Debug, Clone, Default, PartialEq)]
82#[non_exhaustive]
83pub struct Poly {
84 pub first_link: u32,
86 pub verts: [u16; 6],
88 pub neis: [u16; 6],
90 pub flags: u16,
92 pub vert_count: u8,
94 pub area_and_type: u8,
96}
97
98impl Poly {
99 #[must_use]
101 pub fn area(&self) -> u8 {
102 self.area_and_type & 0x3F
103 }
104
105 #[must_use]
107 pub fn poly_type(&self) -> u8 {
108 self.area_and_type >> 6
109 }
110
111 pub fn set_area(&mut self, area: u8) {
113 self.area_and_type = (self.area_and_type & 0xC0) | (area & 0x3F);
114 }
115
116 pub fn set_type(&mut self, poly_type: u8) {
118 self.area_and_type = (self.area_and_type & 0x3F) | ((poly_type & 0x03) << 6);
119 }
120}
121
122#[derive(Debug, Clone, Default, PartialEq)]
124#[non_exhaustive]
125pub struct Link {
126 pub reference: u64,
128 pub next: u32,
130 pub edge: u8,
132 pub side: u8,
134 pub bmin: u8,
136 pub bmax: u8,
138}
139
140#[derive(Debug, Clone, Default, PartialEq)]
142#[non_exhaustive]
143pub struct BvNode {
144 pub bmin: [u16; 3],
146 pub bmax: [u16; 3],
148 pub i: i32,
150}
151
152#[derive(Debug, Clone, Default, PartialEq)]
154#[non_exhaustive]
155pub struct OffMeshConnection {
156 pub pos: [f32; 6],
158 pub center_height: f32,
160 pub reserved: f32,
162 pub rad: f32,
164 pub poly: u16,
166 pub flags: u8,
168 pub side: u8,
170 pub user_id: u32,
172}
173
174#[derive(Debug, Clone, Default, PartialEq)]
176#[non_exhaustive]
177pub struct TilePart {
178 pub object_id: u64,
180 pub part_index: u32,
182 pub first_poly: i32,
184}
185
186#[derive(Debug, Clone, Default, PartialEq)]
188#[non_exhaustive]
189pub struct TilePartPoly {
190 pub poly: u32,
192 pub next: i32,
194}
195
196#[derive(Debug, Clone, Default, PartialEq)]
198#[non_exhaustive]
199pub struct Obstacle {
200 pub pos: [f32; 3],
202 pub radius: f32,
204}
205
206#[derive(Debug, Clone, Default, PartialEq)]
212#[non_exhaustive]
213pub struct TileExtra {
214 pub parts: Vec<TilePart>,
216 pub part_polys: Vec<TilePartPoly>,
218 pub obstacles: Vec<Obstacle>,
220}
221
222impl TileExtra {
223 #[must_use]
225 pub fn is_empty(&self) -> bool {
226 self.parts.is_empty() && self.part_polys.is_empty() && self.obstacles.is_empty()
227 }
228
229 #[must_use]
232 pub fn byte_size(&self) -> usize {
233 EXTRA_FIXED_LEN
234 .saturating_add(self.parts.len().saturating_mul(PART_LEN))
235 .saturating_add(self.part_polys.len().saturating_mul(PART_POLY_LEN))
236 .saturating_add(self.obstacles.len().saturating_mul(OBSTACLE_LEN))
237 }
238
239 fn parse(bytes: &[u8]) -> io::Result<Self> {
240 let mut r = Reader::new(bytes);
241 let part_count = u32_to_usize(r.u32().map_err(|_| extra_size_error())?);
242 let part_poly_count = u32_to_usize(r.u32().map_err(|_| extra_size_error())?);
243 let needed = part_count
245 .checked_mul(PART_LEN)
246 .zip(part_poly_count.checked_mul(PART_POLY_LEN))
247 .and_then(|(a, b)| a.checked_add(b))
248 .and_then(|n| n.checked_add(4))
249 .ok_or_else(extra_size_error)?;
250 if needed > r.remaining() {
251 return Err(extra_size_error());
252 }
253 let mut parts = Vec::with_capacity(part_count);
254 for _ in 0..part_count {
255 parts.push(TilePart {
256 object_id: r.u64()?,
257 part_index: r.u32()?,
258 first_poly: r.i32()?,
259 });
260 }
261 let mut part_polys = Vec::with_capacity(part_poly_count);
262 for _ in 0..part_poly_count {
263 part_polys.push(TilePartPoly {
264 poly: r.u32()?,
265 next: r.i32()?,
266 });
267 }
268 let obstacle_count = u32_to_usize(r.u32()?);
269 if obstacle_count.checked_mul(OBSTACLE_LEN) != Some(r.remaining()) {
270 return Err(extra_size_error());
271 }
272 let mut obstacles = Vec::with_capacity(obstacle_count);
273 for _ in 0..obstacle_count {
274 obstacles.push(Obstacle {
275 pos: r.f32x3()?,
276 radius: r.f32()?,
277 });
278 }
279 Ok(Self {
280 parts,
281 part_polys,
282 obstacles,
283 })
284 }
285
286 fn write(&self, out: &mut Vec<u8>) {
287 put_u32(out, len_u32(self.parts.len()));
288 put_u32(out, len_u32(self.part_polys.len()));
289 for p in &self.parts {
290 out.extend_from_slice(&p.object_id.to_le_bytes());
291 put_u32(out, p.part_index);
292 put_i32(out, p.first_poly);
293 }
294 for p in &self.part_polys {
295 put_u32(out, p.poly);
296 put_i32(out, p.next);
297 }
298 put_u32(out, len_u32(self.obstacles.len()));
299 for o in &self.obstacles {
300 put_f32s(out, &o.pos);
301 put_f32(out, o.radius);
302 }
303 }
304}
305
306fn extra_size_error() -> io::Error {
307 error!("extra section size does not match its counts")
308}
309
310#[derive(Debug, Clone, Default, PartialEq)]
315#[non_exhaustive]
316pub struct TileData {
317 pub header: MeshHeader,
319 pub verts: Vec<[f32; 3]>,
321 pub polys: Vec<Poly>,
323 pub links: Vec<Link>,
325 pub detail_meshes: Vec<[u8; 12]>,
327 pub detail_verts: Vec<[f32; 3]>,
329 pub detail_tris: Vec<[u8; 4]>,
331 pub bv_tree: Vec<BvNode>,
333 pub off_mesh: Vec<OffMeshConnection>,
335 pub extra: Option<TileExtra>,
338}
339
340fn u32_to_usize(n: u32) -> usize {
341 usize::try_from(n).unwrap_or(usize::MAX)
344}
345
346fn count(what: &str, n: i32) -> io::Result<usize> {
348 usize::try_from(n).map_err(|_| error!("negative {what} {n}"))
349}
350
351fn len_u32(n: usize) -> u32 {
352 u32::try_from(n).unwrap_or(u32::MAX)
355}
356
357fn len_i32(n: usize) -> i32 {
358 i32::try_from(n).unwrap_or(i32::MAX)
359}
360
361fn put_u32(out: &mut Vec<u8>, v: u32) {
362 out.extend_from_slice(&v.to_le_bytes());
363}
364
365fn put_i32(out: &mut Vec<u8>, v: i32) {
366 out.extend_from_slice(&v.to_le_bytes());
367}
368
369fn put_f32(out: &mut Vec<u8>, v: f32) {
370 out.extend_from_slice(&v.to_le_bytes());
371}
372
373fn put_f32s(out: &mut Vec<u8>, v: &[f32]) {
374 for f in v {
375 put_f32(out, *f);
376 }
377}
378
379fn put_u16s(out: &mut Vec<u8>, v: &[u16]) {
380 for n in v {
381 out.extend_from_slice(&n.to_le_bytes());
382 }
383}
384
385impl TileData {
386 pub fn parse(blob: &[u8]) -> io::Result<Self> {
396 let mut r = Reader::new(blob);
397 let header = read_header(&mut r)?;
398 let [
399 polys,
400 verts,
401 links,
402 d_meshes,
403 d_verts,
404 d_tris,
405 bv,
406 off_mesh,
407 extra_size,
408 ] = check_sizes(&header, blob.len())?;
409
410 let mut vs = Vec::with_capacity(verts);
411 for _ in 0..verts {
412 vs.push(r.f32x3()?);
413 }
414 let mut ps = Vec::with_capacity(polys);
415 for _ in 0..polys {
416 ps.push(read_poly(&mut r)?);
417 }
418 let mut ls = Vec::with_capacity(links);
419 for _ in 0..links {
420 ls.push(Link {
421 reference: r.u64()?,
422 next: r.u32()?,
423 edge: r.u8()?,
424 side: r.u8()?,
425 bmin: r.u8()?,
426 bmax: r.u8()?,
427 });
428 }
429 let mut detail_meshes = Vec::with_capacity(d_meshes);
430 for _ in 0..d_meshes {
431 detail_meshes.push(r.array::<12>()?);
432 }
433 let mut detail_verts = Vec::with_capacity(d_verts);
434 for _ in 0..d_verts {
435 detail_verts.push(r.f32x3()?);
436 }
437 let mut detail_tris = Vec::with_capacity(d_tris);
438 for _ in 0..d_tris {
439 detail_tris.push(r.array::<4>()?);
440 }
441 let mut bv_tree = Vec::with_capacity(bv);
442 for _ in 0..bv {
443 bv_tree.push(BvNode {
444 bmin: [r.u16()?, r.u16()?, r.u16()?],
445 bmax: [r.u16()?, r.u16()?, r.u16()?],
446 i: r.i32()?,
447 });
448 }
449 let mut off = Vec::with_capacity(off_mesh);
450 for _ in 0..off_mesh {
451 off.push(OffMeshConnection {
452 pos: [r.f32()?, r.f32()?, r.f32()?, r.f32()?, r.f32()?, r.f32()?],
453 center_height: r.f32()?,
454 reserved: r.f32()?,
455 rad: r.f32()?,
456 poly: r.u16()?,
457 flags: r.u8()?,
458 side: r.u8()?,
459 user_id: r.u32()?,
460 });
461 }
462 let extra = if extra_size == 0 {
463 None
464 } else {
465 Some(TileExtra::parse(r.rest()).prepend_error("Invalid extra section:")?)
466 };
467 Ok(Self {
468 header,
469 verts: vs,
470 polys: ps,
471 links: ls,
472 detail_meshes,
473 detail_verts,
474 detail_tris,
475 bv_tree,
476 off_mesh: off,
477 extra,
478 })
479 }
480
481 pub(crate) fn blob_len(&self) -> Option<usize> {
483 let extra = self.extra.as_ref().map_or(0, TileExtra::byte_size);
484 [
485 self.verts.len().checked_mul(VERT_LEN)?,
486 self.polys.len().checked_mul(POLY_LEN)?,
487 self.links.len().checked_mul(LINK_LEN)?,
488 self.detail_meshes.len().checked_mul(DETAIL_MESH_LEN)?,
489 self.detail_verts.len().checked_mul(VERT_LEN)?,
490 self.detail_tris.len().checked_mul(DETAIL_TRI_LEN)?,
491 self.bv_tree.len().checked_mul(BV_NODE_LEN)?,
492 self.off_mesh.len().checked_mul(OFF_MESH_LEN)?,
493 extra,
494 ]
495 .iter()
496 .try_fold(HEADER_LEN, |acc, &x| acc.checked_add(x))
497 }
498
499 #[must_use]
503 pub fn to_bytes(&self) -> Vec<u8> {
504 let mut out = Vec::with_capacity(self.blob_len().unwrap_or(HEADER_LEN));
505 let h = &self.header;
506 let extra_size = len_i32(self.extra.as_ref().map_or(0, TileExtra::byte_size));
507 for v in [h.magic, h.version, h.x, h.y, h.layer] {
508 put_i32(&mut out, v);
509 }
510 put_u32(&mut out, h.user_id);
511 for n in [
512 self.polys.len(),
513 self.verts.len(),
514 self.links.len(),
515 self.detail_meshes.len(),
516 self.detail_verts.len(),
517 self.detail_tris.len(),
518 self.bv_tree.len(),
519 self.off_mesh.len(),
520 ] {
521 put_i32(&mut out, len_i32(n));
522 }
523 put_i32(&mut out, h.off_mesh_base);
524 put_f32s(
525 &mut out,
526 &[h.walkable_height, h.walkable_radius, h.walkable_climb],
527 );
528 put_f32s(&mut out, &h.bmin);
529 put_f32s(&mut out, &h.bmax);
530 put_f32(&mut out, h.bv_quant_factor);
531 put_i32(&mut out, extra_size);
532
533 for v in &self.verts {
534 put_f32s(&mut out, v);
535 }
536 for p in &self.polys {
537 put_u32(&mut out, p.first_link);
538 put_u16s(&mut out, &p.verts);
539 put_u16s(&mut out, &p.neis);
540 put_u16s(&mut out, &[p.flags]);
541 out.push(p.vert_count);
542 out.push(p.area_and_type);
543 }
544 for l in &self.links {
545 out.extend_from_slice(&l.reference.to_le_bytes());
546 put_u32(&mut out, l.next);
547 out.extend_from_slice(&[l.edge, l.side, l.bmin, l.bmax]);
548 }
549 for d in &self.detail_meshes {
550 out.extend_from_slice(d);
551 }
552 for v in &self.detail_verts {
553 put_f32s(&mut out, v);
554 }
555 for t in &self.detail_tris {
556 out.extend_from_slice(t);
557 }
558 for n in &self.bv_tree {
559 put_u16s(&mut out, &n.bmin);
560 put_u16s(&mut out, &n.bmax);
561 put_i32(&mut out, n.i);
562 }
563 for c in &self.off_mesh {
564 put_f32s(&mut out, &c.pos);
565 put_f32s(&mut out, &[c.center_height, c.reserved, c.rad]);
566 put_u16s(&mut out, &[c.poly]);
567 out.extend_from_slice(&[c.flags, c.side]);
568 put_u32(&mut out, c.user_id);
569 }
570 if let Some(extra) = &self.extra {
571 extra.write(&mut out);
572 }
573 out
574 }
575}
576
577fn check_sizes(header: &MeshHeader, blob_len: usize) -> io::Result<[usize; 9]> {
578 let counts = [
579 ("polyCount", header.poly_count),
580 ("vertCount", header.vert_count),
581 ("maxLinkCount", header.max_link_count),
582 ("detailMeshCount", header.detail_mesh_count),
583 ("detailVertCount", header.detail_vert_count),
584 ("detailTriCount", header.detail_tri_count),
585 ("bvNodeCount", header.bv_node_count),
586 ("offMeshConCount", header.off_mesh_con_count),
587 ("extraDataSize", header.extra_data_size),
588 ];
589 let mut n = [0usize; 9];
590 for (slot, (what, value)) in n.iter_mut().zip(counts) {
591 *slot = count(what, value)?;
592 }
593 let [
594 polys,
595 verts,
596 links,
597 d_meshes,
598 d_verts,
599 d_tris,
600 bv,
601 off_mesh,
602 extra_size,
603 ] = n;
604 let sizes = [
605 (verts, VERT_LEN),
606 (polys, POLY_LEN),
607 (links, LINK_LEN),
608 (d_meshes, DETAIL_MESH_LEN),
609 (d_verts, VERT_LEN),
610 (d_tris, DETAIL_TRI_LEN),
611 (bv, BV_NODE_LEN),
612 (off_mesh, OFF_MESH_LEN),
613 ];
614 let total = sizes
615 .iter()
616 .try_fold(HEADER_LEN, |acc, &(n, len)| {
617 acc.checked_add(n.checked_mul(len)?)
618 })
619 .and_then(|t| t.checked_add(extra_size))
620 .ok_or_else(|| error!("tile blob truncated"))?;
621 if total > blob_len {
622 return Err(error!("tile blob truncated"));
623 }
624 if total < blob_len {
625 return Err(error!("trailing bytes after the tile blob"));
626 }
627 Ok(n)
628}
629
630fn read_header(r: &mut Reader<'_>) -> io::Result<MeshHeader> {
631 let magic = r.i32().map_err(|_| error!("tile blob truncated"))?;
632 if magic != NAVMESH_MAGIC {
633 return Err(error!("Invalid tile header (bad tile magic)"));
634 }
635 let version = r.i32().map_err(|_| error!("tile blob truncated"))?;
636 if version != NAVMESH_VERSION {
637 return Err(error!("Invalid tile version {version}"));
638 }
639 let truncated = |_| error!("tile blob truncated");
640 Ok(MeshHeader {
641 magic,
642 version,
643 x: r.i32().map_err(truncated)?,
644 y: r.i32().map_err(truncated)?,
645 layer: r.i32().map_err(truncated)?,
646 user_id: r.u32().map_err(truncated)?,
647 poly_count: r.i32().map_err(truncated)?,
648 vert_count: r.i32().map_err(truncated)?,
649 max_link_count: r.i32().map_err(truncated)?,
650 detail_mesh_count: r.i32().map_err(truncated)?,
651 detail_vert_count: r.i32().map_err(truncated)?,
652 detail_tri_count: r.i32().map_err(truncated)?,
653 bv_node_count: r.i32().map_err(truncated)?,
654 off_mesh_con_count: r.i32().map_err(truncated)?,
655 off_mesh_base: r.i32().map_err(truncated)?,
656 walkable_height: r.f32().map_err(truncated)?,
657 walkable_radius: r.f32().map_err(truncated)?,
658 walkable_climb: r.f32().map_err(truncated)?,
659 bmin: r.f32x3().map_err(truncated)?,
660 bmax: r.f32x3().map_err(truncated)?,
661 bv_quant_factor: r.f32().map_err(truncated)?,
662 extra_data_size: r.i32().map_err(truncated)?,
663 })
664}
665
666fn read_poly(r: &mut Reader<'_>) -> io::Result<Poly> {
667 let first_link = r.u32()?;
668 let mut verts = [0u16; 6];
669 for v in &mut verts {
670 *v = r.u16()?;
671 }
672 let mut neis = [0u16; 6];
673 for v in &mut neis {
674 *v = r.u16()?;
675 }
676 Ok(Poly {
677 first_link,
678 verts,
679 neis,
680 flags: r.u16()?,
681 vert_count: r.u8()?,
682 area_and_type: r.u8()?,
683 })
684}