1use std::io;
28
29use crate::navmesh::detour::tile::{
30 BvNode, Link, MeshHeader, NAVMESH_MAGIC, NAVMESH_VERSION, OffMeshConnection, Poly, TileData,
31 TileExtra,
32};
33use crate::navmesh::num::{ceil_i32, floor_i32};
34use crate::navmesh::qsort::msvc_qsort;
35
36const MESH_NULL_IDX: u16 = 0xffff;
38const EXT_LINK: u16 = 0x8000;
40const VERTS_PER_POLYGON: usize = 6;
42
43#[derive(Debug, Clone, Default, PartialEq)]
45#[non_exhaustive]
46pub struct OffMeshInput {
47 pub start: [f32; 3],
49 pub end: [f32; 3],
51 pub center_height: f32,
53 pub radius: f32,
55 pub flags: u16,
57 pub area: u8,
59 pub bidirectional: bool,
61 pub user_id: u32,
63}
64
65#[derive(Debug, Clone)]
69#[non_exhaustive]
70pub struct CreateParams<'a> {
71 pub verts: &'a [[u16; 3]],
73 pub polys: &'a [u16],
76 pub flags: &'a [u16],
78 pub areas: &'a [u8],
80 pub nvp: usize,
82 pub off_mesh: &'a [OffMeshInput],
84 pub extra: &'a TileExtra,
86 pub tile_x: i32,
88 pub tile_y: i32,
90 pub bmin: [f32; 3],
92 pub bmax: [f32; 3],
94 pub walkable_height: f32,
96 pub walkable_radius: f32,
98 pub walkable_climb: f32,
100 pub cs: f32,
102 pub ch: f32,
104}
105
106impl<'a> CreateParams<'a> {
107 #[must_use]
110 pub fn new(
111 verts: &'a [[u16; 3]],
112 polys: &'a [u16],
113 flags: &'a [u16],
114 areas: &'a [u8],
115 nvp: usize,
116 off_mesh: &'a [OffMeshInput],
117 extra: &'a TileExtra,
118 ) -> Self {
119 Self {
120 verts,
121 polys,
122 flags,
123 areas,
124 nvp,
125 off_mesh,
126 extra,
127 tile_x: 0,
128 tile_y: 0,
129 bmin: [0.0; 3],
130 bmax: [0.0; 3],
131 walkable_height: 0.0,
132 walkable_radius: 0.0,
133 walkable_climb: 0.0,
134 cs: 0.25,
135 ch: 0.1,
136 }
137 }
138}
139
140pub(crate) fn classify_off_mesh_point(pt: &[f32; 3], bmin: &[f32; 3], bmax: &[f32; 3]) -> u8 {
143 const XP: u8 = 1;
144 const ZP: u8 = 2;
145 const XM: u8 = 4;
146 const ZM: u8 = 8;
147 let mut outcode = 0_u8;
148 if pt[0] >= bmax[0] {
149 outcode |= XP;
150 }
151 if pt[2] >= bmax[2] {
152 outcode |= ZP;
153 }
154 if pt[0] < bmin[0] {
155 outcode |= XM;
156 }
157 if pt[2] < bmin[2] {
158 outcode |= ZM;
159 }
160 match outcode {
161 XP => 0,
162 v if v == XP | ZP => 1,
163 ZP => 2,
164 v if v == XM | ZP => 3,
165 XM => 4,
166 v if v == XM | ZM => 5,
167 ZM => 6,
168 v if v == XP | ZM => 7,
169 _ => 0xff,
170 }
171}
172
173#[derive(Clone, Copy)]
175struct BvItem {
176 bmin: [u16; 3],
177 bmax: [u16; 3],
178 i: i32,
179}
180
181fn clamp_u16(v: i32) -> u16 {
183 u16::try_from(v.clamp(0, i32::from(u16::MAX))).unwrap_or(u16::MAX)
184}
185
186fn longest_axis(x: u16, y: u16, z: u16) -> usize {
187 let mut axis = 0;
188 let mut max_val = x;
189 if y > max_val {
190 axis = 1;
191 max_val = y;
192 }
193 if z > max_val {
194 axis = 2;
195 }
196 axis
197}
198
199fn grow(bmin: &mut [u16; 3], bmax: &mut [u16; 3], vmin: [u16; 3], vmax: [u16; 3]) {
201 for (lo, v) in bmin.iter_mut().zip(vmin) {
202 if v < *lo {
203 *lo = v;
204 }
205 }
206 for (hi, v) in bmax.iter_mut().zip(vmax) {
207 if v > *hi {
208 *hi = v;
209 }
210 }
211}
212
213fn calc_extends(items: &[BvItem]) -> ([u16; 3], [u16; 3]) {
214 let Some(first) = items.first() else {
215 return ([0; 3], [0; 3]);
216 };
217 let mut bmin = first.bmin;
218 let mut bmax = first.bmax;
219 for it in items.iter().skip(1) {
220 grow(&mut bmin, &mut bmax, it.bmin, it.bmax);
221 }
222 (bmin, bmax)
223}
224
225fn subdivide(items: &mut [BvItem], nodes: &mut Vec<BvNode>) {
228 let icur = nodes.len();
229 nodes.push(BvNode::default());
230 let inum = items.len();
231 if let [only] = items {
232 if let Some(node) = nodes.get_mut(icur) {
233 node.bmin = only.bmin;
234 node.bmax = only.bmax;
235 node.i = only.i;
236 }
237 return;
238 }
239 let (bmin, bmax) = calc_extends(items);
240 let axis = longest_axis(
241 bmax[0].saturating_sub(bmin[0]),
242 bmax[1].saturating_sub(bmin[1]),
243 bmax[2].saturating_sub(bmin[2]),
244 );
245 msvc_qsort(items, |a, b| a.bmin.get(axis).cmp(&b.bmin.get(axis)));
246 let isplit = inum / 2;
247 let (left, right) = items.split_at_mut(isplit);
248 subdivide(left, nodes);
249 subdivide(right, nodes);
250 let escape = nodes.len().saturating_sub(icur);
251 let escape = i32::try_from(escape).unwrap_or(i32::MAX);
252 if let Some(node) = nodes.get_mut(icur) {
253 node.bmin = bmin;
254 node.bmax = bmax;
255 node.i = -escape;
256 }
257}
258
259fn create_bv_tree(
261 params: &CreateParams<'_>,
262 nvp: usize,
263 poly_count: usize,
264) -> io::Result<Vec<BvNode>> {
265 let mut items = Vec::with_capacity(poly_count);
266 for (i, p) in params.polys.chunks_exact(nvp * 2).enumerate() {
267 let (idx, _) = p.split_at(nvp);
268 let vertex = |k: u16| -> io::Result<[u16; 3]> {
269 params
270 .verts
271 .get(usize::from(k))
272 .copied()
273 .ok_or_else(|| error!("polygon {i} uses vertex {k} outside the vertex list"))
274 };
275 let first = vertex(idx.first().copied().unwrap_or(MESH_NULL_IDX))?;
276 let mut bmin = first;
277 let mut bmax = first;
278 for &k in idx.iter().skip(1) {
279 if k == MESH_NULL_IDX {
280 break;
281 }
282 let v = vertex(k)?;
283 grow(&mut bmin, &mut bmax, v, v);
284 }
285 bmin[1] = clamp_u16(floor_i32(f32::from(bmin[1]) * params.ch / params.cs));
287 bmax[1] = clamp_u16(ceil_i32(f32::from(bmax[1]) * params.ch / params.cs));
288 items.push(BvItem {
289 bmin,
290 bmax,
291 i: i32::try_from(i).map_err(|_| error!("too many polygons"))?,
292 });
293 }
294 let mut nodes = Vec::with_capacity(poly_count.saturating_mul(2));
295 subdivide(&mut items, &mut nodes);
296 Ok(nodes)
297}
298
299fn count_i32(n: usize, what: &str) -> io::Result<i32> {
300 i32::try_from(n).map_err(|_| error!("too many {what}"))
301}
302
303struct OffMeshClasses {
306 classes: Vec<(u8, u8)>,
307 stored: usize,
308 link_count: usize,
309}
310
311fn classify_off_mesh(params: &CreateParams<'_>) -> OffMeshClasses {
314 let mut out = OffMeshClasses {
315 classes: Vec::with_capacity(params.off_mesh.len()),
316 stored: 0,
317 link_count: 0,
318 };
319 if params.off_mesh.is_empty() {
320 return out;
321 }
322 let mut hmin = f32::MAX;
324 let mut hmax = -f32::MAX;
325 for iv in params.verts {
326 let h = params.bmin[1] + f32::from(iv[1]) * params.ch;
327 hmin = if hmin < h { hmin } else { h };
328 hmax = if hmax > h { hmax } else { h };
329 }
330 hmin -= params.walkable_climb;
331 hmax += params.walkable_climb;
332 let mut bmin = params.bmin;
333 let mut bmax = params.bmax;
334 bmin[1] = hmin;
335 bmax[1] = hmax;
336 for c in params.off_mesh {
337 let mut start = classify_off_mesh_point(&c.start, &bmin, &bmax);
338 let end = classify_off_mesh_point(&c.end, &bmin, &bmax);
339 if start == 0xff && (c.start[1] < bmin[1] || c.start[1] > bmax[1]) {
341 start = 0;
342 }
343 if start == 0xff {
345 out.link_count += 1;
346 out.stored += 1;
347 }
348 if end == 0xff {
349 out.link_count += 1;
350 }
351 out.classes.push((start, end));
352 }
353 out
354}
355
356pub(crate) fn stored_off_mesh(params: &CreateParams<'_>) -> Vec<bool> {
359 classify_off_mesh(params)
360 .classes
361 .iter()
362 .map(|&(start, _)| start == 0xff)
363 .collect()
364}
365
366fn validate(params: &CreateParams<'_>) -> io::Result<usize> {
368 let nvp = params.nvp;
369 if nvp > VERTS_PER_POLYGON {
370 return Err(error!(
371 "{nvp} vertices per polygon (at most {VERTS_PER_POLYGON})"
372 ));
373 }
374 if nvp == 0 {
375 return Err(error!("no vertices per polygon"));
376 }
377 if params.verts.len() >= usize::from(MESH_NULL_IDX) {
378 return Err(error!("too many vertices ({})", params.verts.len()));
379 }
380 if params.verts.is_empty() {
381 return Err(error!("no vertices"));
382 }
383 if params.polys.is_empty() {
384 return Err(error!("no polygons"));
385 }
386 let stride = nvp * 2;
387 if !params.polys.len().is_multiple_of(stride) {
388 return Err(error!(
389 "polygon array of {} values is not a multiple of {stride}",
390 params.polys.len()
391 ));
392 }
393 let poly_count = params.polys.len() / stride;
394 if params.flags.len() != poly_count || params.areas.len() != poly_count {
395 return Err(error!(
396 "{poly_count} polygons but {} flags and {} areas",
397 params.flags.len(),
398 params.areas.len()
399 ));
400 }
401 Ok(poly_count)
402}
403
404fn count_edges(params: &CreateParams<'_>) -> (usize, usize) {
406 let nvp = params.nvp;
407 let mut edge_count = 0_usize;
408 let mut portal_count = 0_usize;
409 for p in params.polys.chunks_exact(nvp * 2) {
410 let (idx, nei) = p.split_at(nvp);
411 for (&k, &n) in idx.iter().zip(nei) {
412 if k == MESH_NULL_IDX {
413 break;
414 }
415 edge_count += 1;
416 if n & EXT_LINK != 0 && n & 0xf != 0xf {
417 portal_count += 1;
418 }
419 }
420 }
421 (edge_count, portal_count)
422}
423
424fn neighbour_code(n: u16) -> u16 {
426 if n & EXT_LINK == 0 {
427 return n + 1;
429 }
430 match n & 0xf {
431 0 => EXT_LINK | 4, 1 => EXT_LINK | 2, 2 => EXT_LINK, 3 => EXT_LINK | 6, _ => 0, }
437}
438
439fn ground_polys(params: &CreateParams<'_>) -> io::Result<Vec<Poly>> {
441 let nvp = params.nvp;
442 let mut polys = Vec::new();
443 for (i, p) in params.polys.chunks_exact(nvp * 2).enumerate() {
444 let (idx, nei) = p.split_at(nvp);
445 let mut poly = Poly {
446 flags: params.flags.get(i).copied().unwrap_or(0),
447 ..Poly::default()
448 };
449 poly.set_area(params.areas.get(i).copied().unwrap_or(0));
450 poly.set_type(0);
451 for (j, (&k, &n)) in idx.iter().zip(nei).enumerate() {
452 if k == MESH_NULL_IDX {
453 break;
454 }
455 if usize::from(k) >= params.verts.len() {
456 return Err(error!(
457 "polygon {i} uses vertex {k} outside the vertex list"
458 ));
459 }
460 if let Some(slot) = poly.verts.get_mut(j) {
461 *slot = k;
462 }
463 if let Some(slot) = poly.neis.get_mut(j) {
464 *slot = neighbour_code(n);
465 }
466 poly.vert_count += 1;
467 }
468 if poly.vert_count == 0 {
469 return Err(error!("polygon {i} has no vertices"));
470 }
471 polys.push(poly);
472 }
473 Ok(polys)
474}
475
476fn off_mesh_parts(
478 params: &CreateParams<'_>,
479 classes: &[(u8, u8)],
480 verts: &mut Vec<[f32; 3]>,
481 polys: &mut Vec<Poly>,
482) -> io::Result<Vec<OffMeshConnection>> {
483 let poly_base = polys.len();
484 let mut cons = Vec::new();
485 for (c, &(start, end)) in params.off_mesh.iter().zip(classes) {
486 if start != 0xff {
487 continue;
488 }
489 let n = cons.len();
490 let first = u16::try_from(verts.len())
491 .map_err(|_| error!("too many vertices with the off-mesh connections"))?;
492 let second = first
493 .checked_add(1)
494 .ok_or_else(|| error!("too many vertices with the off-mesh connections"))?;
495 let poly = u16::try_from(poly_base + n)
496 .map_err(|_| error!("too many polygons with the off-mesh connections"))?;
497 verts.push(c.start);
498 verts.push(c.end);
499 let mut off = Poly {
500 vert_count: 2,
501 flags: c.flags,
502 ..Poly::default()
503 };
504 off.verts = [first, second, 0, 0, 0, 0];
505 off.set_area(c.area);
506 off.set_type(1);
507 polys.push(off);
508 cons.push(OffMeshConnection {
509 pos: [
510 c.start[0], c.start[1], c.start[2], c.end[0], c.end[1], c.end[2],
511 ],
512 center_height: c.center_height,
513 reserved: 0.0,
514 rad: c.radius,
515 poly,
516 flags: u8::from(c.bidirectional),
517 side: end,
518 user_id: c.user_id,
519 });
520 }
521 Ok(cons)
522}
523
524pub fn create_tile_data(params: &CreateParams<'_>) -> io::Result<TileData> {
538 let poly_count = validate(params)?;
539 let off = classify_off_mesh(params);
540 let (edge_count, portal_count) = count_edges(params);
541 let max_link_count = edge_count + portal_count * 2 + off.link_count * 2;
542
543 let mut verts: Vec<[f32; 3]> = params
545 .verts
546 .iter()
547 .map(|iv| {
548 [
549 params.bmin[0] + f32::from(iv[0]) * params.cs,
550 params.bmin[1] + f32::from(iv[1]) * params.ch,
551 params.bmin[2] + f32::from(iv[2]) * params.cs,
552 ]
553 })
554 .collect();
555 let mut polys = ground_polys(params)?;
556 let off_mesh = off_mesh_parts(params, &off.classes, &mut verts, &mut polys)?;
557
558 let mut bv_tree = create_bv_tree(params, params.nvp, poly_count)?;
560 bv_tree.resize(poly_count * 2, BvNode::default());
561
562 let header = MeshHeader {
563 magic: NAVMESH_MAGIC,
564 version: NAVMESH_VERSION,
565 x: params.tile_x,
566 y: params.tile_y,
567 layer: 0,
568 user_id: 0,
569 poly_count: count_i32(polys.len(), "polygons")?,
570 vert_count: count_i32(verts.len(), "vertices")?,
571 max_link_count: count_i32(max_link_count, "links")?,
572 detail_mesh_count: 0,
573 detail_vert_count: 0,
574 detail_tri_count: 0,
575 bv_node_count: count_i32(poly_count * 2, "polygons")?,
576 off_mesh_con_count: count_i32(off_mesh.len(), "off-mesh connections")?,
577 off_mesh_base: count_i32(poly_count, "polygons")?,
578 walkable_height: params.walkable_height,
579 walkable_radius: params.walkable_radius,
580 walkable_climb: params.walkable_climb,
581 bmin: params.bmin,
582 bmax: params.bmax,
583 bv_quant_factor: 1.0 / params.cs,
584 extra_data_size: count_i32(params.extra.byte_size(), "extra section bytes")?,
585 };
586 Ok(TileData {
587 header,
588 verts,
589 polys,
590 links: vec![Link::default(); max_link_count],
591 detail_meshes: Vec::new(),
592 detail_verts: Vec::new(),
593 detail_tris: Vec::new(),
594 bv_tree,
595 off_mesh,
596 extra: Some(params.extra.clone()),
597 })
598}