Skip to main content

dayzmake_core/navmesh/detour/
create.rs

1//
2// Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
3//
4// This software is provided 'as-is', without any express or implied
5// warranty.  In no event will the authors be held liable for any damages
6// arising from the use of this software.
7// Permission is granted to anyone to use this software for any purpose,
8// including commercial applications, and to alter it and redistribute it
9// freely, subject to the following restrictions:
10// 1. The origin of this software must not be misrepresented; you must not
11//    claim that you wrote the original software. If you use this software
12//    in a product, an acknowledgment in the product documentation would be
13//    appreciated but is not required.
14// 2. Altered source versions must be plainly marked as such, and must not be
15//    misrepresented as being the original software.
16// 3. This notice may not be removed or altered from any source distribution.
17//
18// Ported to Rust and altered for DayZ (see the dayzmake navmesh spec); this is not the original software.
19//
20
21//! `dtCreateNavMeshData`, the DayZ variant (spec 7.3, 9.3 and 10.2): one Detour tile blob from a
22//! Recast poly mesh.
23//!
24//! Stock Detour, except for: tile version 12, the extra header field, 44-byte off-mesh connections,
25//! no detail mesh, a trailing extra section, and the off-mesh link accounting of spec 7.3.
26
27use 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
36/// The polygon vertex list terminator of a Recast poly mesh.
37const MESH_NULL_IDX: u16 = 0xffff;
38/// `DT_EXT_LINK`: the neighbour is in another tile.
39const EXT_LINK: u16 = 0x8000;
40/// The largest number of vertices of one polygon.
41const VERTS_PER_POLYGON: usize = 6;
42
43/// One off-mesh connection of the input (a jump, climb or ladder link).
44#[derive(Debug, Clone, Default, PartialEq)]
45#[non_exhaustive]
46pub struct OffMeshInput {
47    /// Start point, in world coordinates.
48    pub start: [f32; 3],
49    /// End point, in world coordinates.
50    pub end: [f32; 3],
51    /// The measured obstacle height at the midpoint, relative to the start.
52    pub center_height: f32,
53    /// Snap radius used when the tile is linked.
54    pub radius: f32,
55    /// Polygon flags of the connection.
56    pub flags: u16,
57    /// Area id of the connection.
58    pub area: u8,
59    /// `true` when the connection can be used in both directions.
60    pub bidirectional: bool,
61    /// User id (the index of the link class).
62    pub user_id: u32,
63}
64
65/// The inputs of [`create_tile_data`], mirroring `dtNavMeshCreateParams`.
66///
67/// Build it with [`CreateParams::new`] and set the scalars by field assignment.
68#[derive(Debug, Clone)]
69#[non_exhaustive]
70pub struct CreateParams<'a> {
71    /// Poly mesh vertices in cell coordinates (relative to `bmin`).
72    pub verts: &'a [[u16; 3]],
73    /// Polygons: `nvp * 2` values each, the vertex indices (terminated by `0xffff`) followed by
74    /// the neighbour codes.
75    pub polys: &'a [u16],
76    /// Polygon flags, one per polygon.
77    pub flags: &'a [u16],
78    /// Polygon area ids, one per polygon.
79    pub areas: &'a [u8],
80    /// Vertices per polygon of the poly mesh (at most 6).
81    pub nvp: usize,
82    /// The off-mesh connections that touch the tile.
83    pub off_mesh: &'a [OffMeshInput],
84    /// The extra section stored after the off-mesh connections.
85    pub extra: &'a TileExtra,
86    /// Tile grid x.
87    pub tile_x: i32,
88    /// Tile grid y (the z grid index).
89    pub tile_y: i32,
90    /// Tile bounds minimum.
91    pub bmin: [f32; 3],
92    /// Tile bounds maximum.
93    pub bmax: [f32; 3],
94    /// Agent height in metres.
95    pub walkable_height: f32,
96    /// Agent radius in metres.
97    pub walkable_radius: f32,
98    /// Agent climb height in metres.
99    pub walkable_climb: f32,
100    /// Cell size.
101    pub cs: f32,
102    /// Cell height.
103    pub ch: f32,
104}
105
106impl<'a> CreateParams<'a> {
107    /// Parameters for the given poly mesh. The scalars start as zero, except for `cs = 0.25` and
108    /// `ch = 0.1`.
109    #[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
140/// `classifyOffMeshPoint`: the side of the tile `bmin`-`bmax` (xz) the point is on, as a
141/// `dtNavMesh` side 0 to 7, or 0xff when it is inside.
142pub(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/// An item of the bounding volume tree build (`BVItem`).
174#[derive(Clone, Copy)]
175struct BvItem {
176    bmin: [u16; 3],
177    bmax: [u16; 3],
178    i: i32,
179}
180
181/// Saturating conversion of a computed, integral `f32` to `u16` (C's cast on in-range values).
182fn 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
199/// Grows `bmin`/`bmax` to contain `vmin`/`vmax`.
200fn 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
225/// `subdivide`. The items are sorted on the split axis by [`msvc_qsort`] with no tie-break, as
226/// upstream's `qsort` call does, so the order of items with equal keys is that of the MSVC runtime.
227fn 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
259/// `createBVTree` for a poly mesh without a detail mesh.
260fn 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        // Remap y from ch to cs units.
286        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
303/// The `(start, end)` classes of the off-mesh connections, the number that is stored and the
304/// number of endpoints inside the tile.
305struct OffMeshClasses {
306    classes: Vec<(u8, u8)>,
307    stored: usize,
308    link_count: usize,
309}
310
311/// Classifies the off-mesh connection points. Only connections whose start is inside the tile
312/// (and inside its height band) are stored; the link count includes every inside endpoint.
313fn 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    // Tight height bounds, used for culling out off-mesh start locations.
323    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        // Zero out off-mesh start positions which are not even potentially touching the mesh.
340        if start == 0xff && (c.start[1] < bmin[1] || c.start[1] > bmax[1]) {
341            start = 0;
342        }
343        // Count how many links should be allocated for off-mesh connections.
344        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
356/// Which of the off-mesh connections of `params` are stored in the tile: those that start inside it,
357/// in order. The stored connections become the polygons after the ground polygons.
358pub(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
366/// Checks the slice lengths and limits; returns the polygon count.
367fn 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
404/// The number of polygon edges and of portal edges (`dir != 0xf`).
405fn 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
424/// The Detour neighbour code of a Recast one (spec 9.3): portals x-, z+, x+, z- become 4, 2, 0, 6.
425fn neighbour_code(n: u16) -> u16 {
426    if n & EXT_LINK == 0 {
427        // Normal connection (`n` is at most 0x7fff here).
428        return n + 1;
429    }
430    match n & 0xf {
431        0 => EXT_LINK | 4, // portal x-
432        1 => EXT_LINK | 2, // portal z+
433        2 => EXT_LINK,     // portal x+
434        3 => EXT_LINK | 6, // portal z-
435        _ => 0,            // border (0xf), and the codes stock Detour leaves unset
436    }
437}
438
439/// The ground polygons.
440fn 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
476/// The stored off-mesh polygons and connections; their vertices are appended to `verts`.
477fn 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
524/// Builds one Detour tile (version 12) from a poly mesh, the DayZ way (spec 7.3).
525///
526/// No detail mesh is produced. Off-mesh connections are stored only when their start point is
527/// inside the tile; `max_link_count` also reserves slots for every endpoint inside the tile of
528/// every passed connection. The BV tree is built over the ground polygons. The links are zeroed
529/// (linking happens when the tile is added to a mesh) and the extra section is a copy of
530/// `params.extra`.
531///
532/// # Errors
533///
534/// Returns an error for an empty vertex or polygon list, `nvp` above 6 or zero, 65535 or more
535/// vertices, slices of inconsistent lengths, vertex indices outside the vertex list, a polygon
536/// without vertices, or more off-mesh polygons or vertices than 16 bits can index.
537pub 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    // Vertices of the mesh, then the off-mesh ones.
544    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    // BV tree over the ground polygons, in a 2n-node array.
559    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}