Namespaces
namespace	detail

Classes
struct	AABB
	Axis-aligned bounding box. More...
struct	BVHNode
	Node in a per-surface bounding volume hierarchy (BVH). More...
struct	Colors
	Optional per-vertex colors (RGBA, 8-bit per channel). More...
struct	CombineOptions
	Options of combine_layer(). More...
struct	DescriptorParams
	Which descriptors to compute, and over which neighbourhoods. More...
class	DistanceField
	Distance from each NavCel to the nearest seed (seed NavCels and, optionally, the open edges of the mesh), kept up to date incrementally. More...
struct	LayerMeta
	Metadata associated to a layer (optional). More...
class	LayerRegistry
	Registry of named layers (per-NavCel). More...
struct	LayerView
	Typed layer view storing one `T` value per NavCel. More...
struct	LayerViewBase
	Non-templated base for runtime layer handling. More...
struct	NavCel
	Navigation cell (triangle) with geometry and adjacency. More...
class	NavMap
class	OccupancyLayer
	Log-odds occupancy over an int16 layer of a NavMap. More...
struct	OccupancyParams
	Probabilities of the update rule and of the classification (OctoMap defaults). More...
struct	Positions
	Structure-of-arrays for storing 3D vertex positions. More...
struct	Ray
	Simple ray (origin + direction). More...
struct	RayHit
	Result of a raycast against the NavMap. More...
struct	SimplifyParams
	Parameters of simplify(). More...
struct	SimplifyStats
	Sizes before and after simplify(). More...
struct	Surface
	A connected set of NavCels in a common reference frame. More...
struct	SurfaceLink
	Connection between two NavCels that do not share an edge (stairs, an elevator, a door between surfaces that are not welded...). More...
class	TraversalScratch
	Reusable traversal buffers. Not thread-safe: one per thread. More...

Typedefs
using	NavCelId = uint32_t
	Index of a triangle (NavCel) within the global mesh.
using	PointId = uint32_t
	Index into the per-vertex position arrays (SoA).
using	Vec3 = Eigen::Vector3f
	3D vector alias used across NavMap geometry.

Enumerations
enum class	AreaShape { CIRCULAR , RECTANGULAR }
	Shape selector for area-writing APIs. More...
enum class	CombineOp : uint8_t { OVERWRITE , TRUE_OVERWRITE , MAX , MAX_KEEP_UNKNOWN , MIN , ADD }
	How a source value s is combined into the destination value d (as costmap_2d's update modes). More...
enum class	LayerType : uint8_t { U8 = 0 , F32 = 1 , F64 = 2 , I16 = 3 }
	Runtime type tag for a layer's scalar storage. More...
enum class	LinkType : uint8_t { GENERIC = 0 , RAMP = 1 , STAIRS = 2 , ELEVATOR = 3 , DOOR = 4 }
	Main container for navigable surfaces, geometry, and layers. More...
enum class	Metric { EUCLIDEAN , GEODESIC }
	Distance from a centre used to grow a region. More...
enum class	OccupancyState : uint8_t { UNKNOWN = 0 , FREE = 1 , OCCUPIED = 2 }
	Three-state classification of a NavCel. More...

Functions
Vec3	closest_point_on_triangle (const Vec3 &p, const Vec3 &a, const Vec3 &b, const Vec3 &c)
	Compute the closest point on triangle ABC to point P.
std::ptrdiff_t	combine_layer (NavMap &nm, const std::string &dst, const std::string &src, CombineOp op, const CombineOptions &options={})
	Combine layer `src` into layer `dst` cell by cell with `op`.
void	compute_descriptors (NavMap &nm, const DescriptorParams &params={})
	Compute the selected descriptors as F32 layers of `nm` (created or overwritten).
template<class F>
std::size_t	for_each_by_distance (const NavMap &nm, NavCelId seed, const Eigen::Vector3f &center, float max_distance, F &&f, TraversalScratch *scratch=nullptr)
	Visits NavCels by geodesic distance from `center`, up to `max_distance:` a spiral over the surface (nearest free cell, local search...).
template<class F>
std::size_t	for_each_in_aabb (const NavMap &nm, const AABB &box, F &&f, TraversalScratch *scratch=nullptr)
	Visits the NavCels whose bounding box overlaps `box`, on every surface (via the BVH).
template<class F>
std::size_t	for_each_in_disc (const NavMap &nm, const Eigen::Vector3f &center, float radius, F &&f, Metric metric=Metric::EUCLIDEAN, TraversalScratch *scratch=nullptr)
	As above, locating the seed under `center`; visits nothing if the centre is off the map.
template<class F>
std::size_t	for_each_in_disc (const NavMap &nm, NavCelId seed, const Eigen::Vector3f &center, float radius, F &&f, Metric metric=Metric::EUCLIDEAN, TraversalScratch *scratch=nullptr)
	Visits the NavCels within `radius` of `center`, connected to `seed` (which should contain the centre).
template<class F>
std::size_t	for_each_in_polygon (const NavMap &nm, const Eigen::Vector3f &on_surface, const std::vector< Eigen::Vector2f > &poly, F &&f, TraversalScratch *scratch=nullptr)
	As above, locating the seed under `on_surface` (a point of the polygon's level).
template<class F>
std::size_t	for_each_in_polygon (const NavMap &nm, NavCelId seed, const std::vector< Eigen::Vector2f > &poly, F &&f, TraversalScratch *scratch=nullptr)
	Visits the NavCels whose centroid lies inside the XY polygon `poly`, connected to `seed` through NavCels inside it (so only the seed's level).
template<class F>
std::size_t	for_each_in_ring (const NavMap &nm, NavCelId seed, const Eigen::Vector3f &center, float r_in, float r_out, F &&f, Metric metric=Metric::EUCLIDEAN, TraversalScratch *scratch=nullptr)
	Visits the NavCels at distance in [`r_in`, `r_out`] from `center`, connected to `seed` through NavCels within `r_out` (the inner part is crossed, not visited).
template<class F>
bool	for_each_on_segment (const NavMap &nm, const Eigen::Vector3f &a, const Eigen::Vector3f &b, F &&f)
	As above, locating the seed under `a`; false if a is off the map.
template<class F>
bool	for_each_on_segment (const NavMap &nm, NavCelId seed, const Eigen::Vector3f &a, const Eigen::Vector3f &b, F &&f)
	Walks the surface along segment a -> b (in XY), from `seed` (the NavCel under a), visiting each NavCel crossed with the segment parameters where it enters and leaves.
template<typename T>
constexpr LayerType	layer_type_tag ()
	Helper to map C++ scalar type to navmap::LayerType tag.
template<>
constexpr LayerType	layer_type_tag< double > ()
template<>
constexpr LayerType	layer_type_tag< float > ()
template<>
constexpr LayerType	layer_type_tag< int16_t > ()
template<>
constexpr LayerType	layer_type_tag< uint8_t > ()
float	point_segment_distance (const Vec3 &p, const Vec3 &a, const Vec3 &b)
	Distance from point `p` to segment [`a`, `b`] (a point if a == b).
float	point_triangle_squared_distance (const Vec3 &p, const Vec3 &a, const Vec3 &b, const Vec3 &c, Vec3 *closest=nullptr)
	Squared distance between point and triangle, with optional closest pt.
bool	ray_triangle_intersect (const Vec3 &orig, const Vec3 &dir, const Vec3 &v0, const Vec3 &v1, const Vec3 &v2, float &t, float &u, float &v)
	Möller–Trumbore ray–triangle intersection.
SimplifyStats	simplify (NavMap &nm, const SimplifyParams &params={})
	Simplify `nm` in place by half-edge collapses, cheapest first.
float	triangle_area (const Vec3 &a, const Vec3 &b, const Vec3 &c)
	Compute the area of a triangle ABC.
Vec3	triangle_normal (const Vec3 &a, const Vec3 &b, const Vec3 &c)
	Compute a unit normal of triangle ABC.

Variables
constexpr std::uint8_t	FREE_SPACE = 0
	Known free.
constexpr std::uint8_t	INSCRIBED_INFLATED_OBSTACLE = 253
	The robot would touch an obstacle.
constexpr std::uint8_t	LETHAL_OBSTACLE = 254
	Obstacle.
constexpr std::uint8_t	MAX_NON_OBSTACLE = 252
	Highest traversable cost.
constexpr std::uint8_t	NO_INFORMATION = 255
	Unknown, not observed.

Typedef Documentation

◆ NavCelId

using NavCelId = uint32_t

Index of a triangle (NavCel) within the global mesh.

◆ PointId

using PointId = uint32_t

Index into the per-vertex position arrays (SoA).

◆ Vec3

using Vec3 = Eigen::Vector3f

3D vector alias used across NavMap geometry.

Enumeration Type Documentation

◆ AreaShape

enum class AreaShape

strong

Shape selector for area-writing APIs.

Enumerator
CIRCULAR
RECTANGULAR

◆ CombineOp

enum class CombineOp : uint8_t

strong

How a source value s is combined into the destination value d (as costmap_2d's update modes).

Enumerator
OVERWRITE	d = s, except where s is unknown
TRUE_OVERWRITE	d = s, unknown included
MAX	d = max(d, s); s replaces an unknown d; an unknown s is ignored
MAX_KEEP_UNKNOWN	as MAX, but an unknown d stays unknown
MIN	d = min(d, s); s replaces an unknown d; an unknown s is ignored
ADD	d = min(d + s, cap); s replaces an unknown d; an unknown s is ignored

◆ LayerType

enum class LayerType : uint8_t

strong

Runtime type tag for a layer's scalar storage.

The registry currently supports: 8-bit unsigned, 32-bit float, 64-bit double.

Enumerator
U8
F32
F64
I16

◆ LinkType

enum class LinkType : uint8_t

strong

Main container for navigable surfaces, geometry, and layers.

A navmap::NavMap aggregates vertex positions, a list of navmap::NavCel triangles (global indexing), one or more navmap::Surface partitions, and a navmap::LayerRegistry with arbitrary per-NavCel scalar attributes.

Typical workflow

Fill positions, navcels, and surfaces.
Call rebuild_geometry_accels() to compute normals, areas, adjacency, and build per-surface BVHs.
Create layers via add_or_get() sized to navcels.size().
Query with locate_navcel(), raycast(), or closest_navcel(). Kind of a link between NavCels that are not adjacent in the mesh.

Enumerator
GENERIC
RAMP
STAIRS
ELEVATOR
DOOR

◆ Metric

enum class Metric

strong

Distance from a centre used to grow a region.

Enumerator
EUCLIDEAN	3D distance from the centre to each NavCel centroid
GEODESIC	Along the surface: straight lines on it, bent only around borders.

◆ OccupancyState

enum class OccupancyState : uint8_t

strong

Three-state classification of a NavCel.

Enumerator
UNKNOWN
FREE
OCCUPIED

Function Documentation

◆ closest_point_on_triangle()

Vec3 closest_point_on_triangle	(	const Vec3 &	p,
		const Vec3 &	a,
		const Vec3 &	b,
		const Vec3 &	c )

Compute the closest point on triangle ABC to point P.

Robustly handles all Voronoi regions (vertices/edges/interior). Degenerate triangles fall back to nearest vertex.

Parameters

p	Query point.
a	Triangle vertex A.
b	Triangle vertex B.
c	Triangle vertex C.

Returns: Closest point on triangle to p.

◆ combine_layer()

std::ptrdiff_t combine_layer	(	NavMap &	nm,
		const std::string &	dst,
		const std::string &	src,
		CombineOp	op,
		const CombineOptions &	options = {} )

Combine layer src into layer dst cell by cell with op.

Both layers must exist with one value per NavCel; their types may differ (values convert as in NavMap::layer_get: integers are rounded and clamped to their range). Which value is unknown is each layer's own LayerMeta::unknown (NaN allowed). Writing an unknown value into dst writes the unknown of dst; if dst has none, nothing is written.

Cells whose value changes are recorded with mark_changed() in dst. The provenance layer, if requested, gets source_id wherever the result is the source's value (MAX/MIN: it won or tied; ADD: it added something), even if the value was already the same.

Returns: Cells whose dst value changed, or -1 if a layer is missing, sizes differ or dst == src.

◆ compute_descriptors()

void compute_descriptors	(	NavMap &	nm,
		const DescriptorParams &	params = {} )

Compute the selected descriptors as F32 layers of nm (created or overwritten).

Discs grow over the mesh adjacency from each NavCel (navmap/Iterators.hpp), so a descriptor never mixes floors. "clearance" casts a ray up from each centroid against every surface of the map: it is the room up to the next surface the map holds (the floor above), not to a ceiling that is not in the map; +inf when there is none within clearance_max.

◆ for_each_by_distance()

template<class F>

std::size_t for_each_by_distance	(	const NavMap &	nm,
		NavCelId	seed,
		const Eigen::Vector3f &	center,
		float	max_distance,
		F &&	f,
		TraversalScratch *	scratch = nullptr )

Visits NavCels by geodesic distance from center, up to max_distance: a spiral over the surface (nearest free cell, local search...).

The seed comes first, always. The order is non-decreasing up to the distance between neighbour centroids.

Parameters

f	Visitor f(NavCelId, float distance); returning false stops.

Returns: Number of NavCels visited.

◆ for_each_in_aabb()

template<class F>

std::size_t for_each_in_aabb	(	const NavMap &	nm,
		const AABB &	box,
		F &&	f,
		TraversalScratch *	scratch = nullptr )

Visits the NavCels whose bounding box overlaps box, on every surface (via the BVH).

Parameters

f	Visitor f(NavCelId); returning false stops.

Returns: Number of NavCels visited.

◆ for_each_in_disc() [1/2]

template<class F>

std::size_t for_each_in_disc	(	const NavMap &	nm,
		const Eigen::Vector3f &	center,
		float	radius,
		F &&	f,
		Metric	metric = Metric::EUCLIDEAN,
		TraversalScratch *	scratch = nullptr )

As above, locating the seed under center; visits nothing if the centre is off the map.

◆ for_each_in_disc() [2/2]

template<class F>

std::size_t for_each_in_disc	(	const NavMap &	nm,
		NavCelId	seed,
		const Eigen::Vector3f &	center,
		float	radius,
		F &&	f,
		Metric	metric = Metric::EUCLIDEAN,
		TraversalScratch *	scratch = nullptr )

Visits the NavCels within radius of center, connected to seed (which should contain the centre).

The seed is always visited.

Parameters

f	Visitor f(NavCelId); returning false stops.

Returns: Number of NavCels visited.

◆ for_each_in_polygon() [1/2]

template<class F>

std::size_t for_each_in_polygon	(	const NavMap &	nm,
		const Eigen::Vector3f &	on_surface,
		const std::vector< Eigen::Vector2f > &	poly,
		F &&	f,
		TraversalScratch *	scratch = nullptr )

As above, locating the seed under on_surface (a point of the polygon's level).

◆ for_each_in_polygon() [2/2]

template<class F>

std::size_t for_each_in_polygon	(	const NavMap &	nm,
		NavCelId	seed,
		const std::vector< Eigen::Vector2f > &	poly,
		F &&	f,
		TraversalScratch *	scratch = nullptr )

Visits the NavCels whose centroid lies inside the XY polygon poly, connected to seed through NavCels inside it (so only the seed's level).

Even-odd rule.

Parameters

f	Visitor f(NavCelId); returning false stops.

Returns: Number of NavCels visited.

◆ for_each_in_ring()

template<class F>

std::size_t for_each_in_ring	(	const NavMap &	nm,
		NavCelId	seed,
		const Eigen::Vector3f &	center,
		float	r_in,
		float	r_out,
		F &&	f,
		Metric	metric = Metric::EUCLIDEAN,
		TraversalScratch *	scratch = nullptr )

Visits the NavCels at distance in [r_in, r_out] from center, connected to seed through NavCels within r_out (the inner part is crossed, not visited).

Parameters

f	Visitor f(NavCelId); returning false stops.

Returns: Number of NavCels visited.

◆ for_each_on_segment() [1/2]

template<class F>

bool for_each_on_segment	(	const NavMap &	nm,
		const Eigen::Vector3f &	a,
		const Eigen::Vector3f &	b,
		F &&	f )

As above, locating the seed under a; false if a is off the map.

◆ for_each_on_segment() [2/2]

template<class F>

bool for_each_on_segment	(	const NavMap &	nm,
		NavCelId	seed,
		const Eigen::Vector3f &	a,
		const Eigen::Vector3f &	b,
		F &&	f )

Walks the surface along segment a -> b (in XY), from seed (the NavCel under a), visiting each NavCel crossed with the segment parameters where it enters and leaves.

The walk follows the mesh adjacency, so it stays on the seed's level, also on slopes.

Parameters

f	Visitor f(NavCelId, float t_in, float t_out), 0 <= t_in <= t_out <= 1; returning false stops.

Returns: True if the walk reached the NavCel under b; false if it left the surface through a border first (or was stopped).

◆ layer_type_tag()

template<typename T>

LayerType layer_type_tag ( )

constexpr

Helper to map C++ scalar type to navmap::LayerType tag.

◆ layer_type_tag< double >()

template<>

LayerType layer_type_tag< double > ( )

constexpr

◆ layer_type_tag< float >()

template<>

LayerType layer_type_tag< float > ( )

constexpr

◆ layer_type_tag< int16_t >()

template<>

LayerType layer_type_tag< int16_t > ( )

constexpr

◆ layer_type_tag< uint8_t >()

template<>

LayerType layer_type_tag< uint8_t > ( )

constexpr

◆ point_segment_distance()

float point_segment_distance	(	const Vec3 &	p,
		const Vec3 &	a,
		const Vec3 &	b )

Distance from point p to segment [a, b] (a point if a == b).

◆ point_triangle_squared_distance()

float point_triangle_squared_distance	(	const Vec3 &	p,
		const Vec3 &	a,
		const Vec3 &	b,
		const Vec3 &	c,
		Vec3 *	closest = nullptr )

Squared distance between point and triangle, with optional closest pt.

Parameters

p	Query point.
a	Triangle vertex A.
b	Triangle vertex B.
c	Triangle vertex C.
closest	Optional output: closest point on triangle to `p`.

Returns: Squared Euclidean distance from p to triangle ABC.

Note: Squared distance avoids an extra sqrt and is preferred when comparing distances or using as thresholds.

◆ ray_triangle_intersect()

bool ray_triangle_intersect	(	const Vec3 &	orig,
		const Vec3 &	dir,
		const Vec3 &	v0,
		const Vec3 &	v1,
		const Vec3 &	v2,
		float &	t,
		float &	u,
		float &	v )

Möller–Trumbore ray–triangle intersection.

Solves intersection between a ray (orig + t * dir, t > 0) and triangle (v0, v1, v2). Returns true on hit and outputs:

t: parametric distance along the ray (t > 0).
u, v: barycentric coordinates (with w = 1 - u - v).

Parameters

orig	Ray origin.
dir	Ray direction (not necessarily unit length).
v0	First triangle vertex.
v1	Second triangle vertex.
v2	Third triangle vertex.
t	Output ray parameter on hit (> 0).
u	Output barycentric u on hit.
v	Output barycentric v on hit.

Returns: True if the ray intersects the triangle with t > 0.

Warning: Numerical robustness depends on the geometry scale; kEps is set conservatively for typical mapping units (meters).

◆ simplify()

SimplifyStats simplify	(	NavMap &	nm,
		const SimplifyParams &	params = {} )

Simplify nm in place by half-edge collapses, cheapest first.

A vertex is removed only if all its NavCels have the same values in the kept layers and belong to the same surface, so every layer keeps its value at every point of the map: borders between values (an obstacle, unknown space, a different cost) are kept exactly. Open edges keep their shape (within max_error), topology is preserved (no folds, no new holes or bridges), and NavCels that are the end of a link survive. Layers, surfaces, links and vertex colors are carried over; NavCel and vertex ids change. Geometry accelerations are rebuilt.

◆ triangle_area()

float triangle_area	(	const Vec3 &	a,
		const Vec3 &	b,
		const Vec3 &	c )

Compute the area of a triangle ABC.

Parameters

a	First vertex (world coordinates).
b	Second vertex (world coordinates).
c	Third vertex (world coordinates).

Returns: Triangle area (non-negative).

Note: Uses 0.5 * |(b - a) x (c - a)|.

◆ triangle_normal()

Vec3 triangle_normal	(	const Vec3 &	a,
		const Vec3 &	b,
		const Vec3 &	c )

Compute a unit normal of triangle ABC.

The normal is computed as normalized cross product (b - a) x (c - a). If the triangle is degenerate (near-zero area), returns +Z (0, 0, 1).

Parameters

a	First vertex (world coordinates).
b	Second vertex (world coordinates).
c	Third vertex (world coordinates).

Returns: Unit-length normal or +Z fallback for degenerate triangles.

Variable Documentation

◆ FREE_SPACE

std::uint8_t FREE_SPACE = 0

constexpr

Known free.

◆ INSCRIBED_INFLATED_OBSTACLE

std::uint8_t INSCRIBED_INFLATED_OBSTACLE = 253

constexpr

The robot would touch an obstacle.

◆ LETHAL_OBSTACLE

std::uint8_t LETHAL_OBSTACLE = 254

constexpr

Obstacle.

◆ MAX_NON_OBSTACLE

std::uint8_t MAX_NON_OBSTACLE = 252

constexpr

Highest traversable cost.

◆ NO_INFORMATION

std::uint8_t NO_INFORMATION = 255

constexpr

Unknown, not observed.

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

◆ NavCelId

◆ PointId

◆ Vec3

Enumeration Type Documentation

◆ AreaShape

◆ CombineOp

◆ LayerType

◆ LinkType

◆ Metric

◆ OccupancyState

Function Documentation

◆ closest_point_on_triangle()

◆ combine_layer()

◆ compute_descriptors()

◆ for_each_by_distance()

◆ for_each_in_aabb()

◆ for_each_in_disc() [1/2]

◆ for_each_in_disc() [2/2]

◆ for_each_in_polygon() [1/2]

◆ for_each_in_polygon() [2/2]

◆ for_each_in_ring()

◆ for_each_on_segment() [1/2]

◆ for_each_on_segment() [2/2]

◆ layer_type_tag()

◆ layer_type_tag< double >()

◆ layer_type_tag< float >()

◆ layer_type_tag< int16_t >()

◆ layer_type_tag< uint8_t >()

◆ point_segment_distance()

◆ point_triangle_squared_distance()

◆ ray_triangle_intersect()

◆ simplify()

◆ triangle_area()

◆ triangle_normal()

Variable Documentation

◆ FREE_SPACE

◆ INSCRIBED_INFLATED_OBSTACLE

◆ LETHAL_OBSTACLE

◆ MAX_NON_OBSTACLE

◆ NO_INFORMATION