导航网格-基础概念&数据结构

编程 , 评论

recastnavigation 导读，看了很多大佬写的博客，自己进行一下总结

本文中提到的数据结构都在 Recast.h 中

RecastNavigation 项目地址

basic

AABB(Axis-aligned bounding box)

  • 坐标轴对齐的包围盒，它被定义为包含该对象，且边平行于坐标轴的最小六面体

AABB

  • AABB内的点满足以下条件：

    1
    2
    3
    xmin≤x≤xmax
    ymin≤y≤ymax
    zmin≤z≤zmax

  • 特别重要的两个顶点为：Pmin = [Xmin Ymin Zmin]，Pmax = [ Xmax Ymax Zmax]

  • recast项目中用float bmin[3], bmax[3];来描述一个AABB

如何理解体素？

  • 从数据结构上来理解也许非常简单。
  • 一般模型存储的是顶点和面等数据，每个顶点在无限空间的任意一个位置。而体素空间是一个有限空间，包含了 widthdepthheight 个体素，每个体素大小是固定的，在Recast中由CellSize和CellHeight决定。可想象一个魔方，每一块大小为cellSizecellHeight，一共有widthheightdepth大小。
  • 体素化的过程就是求得模型的包围盒，在xz轴上以CellSize划分，在y轴上以CellHeight划分，得到一个[x][z][y]体素数组，再根据这个体素是否包含原模型的面，决定这个体素是实心还是空心，可行走还是不可行走等属性。

区间 rcSpan

  • 一列（xz平面投影相同）连续的体素盒子
  • 由rcSpan这个结构体来表示
  • smin和smax表示连续体素的最低y坐标和最高y坐标（底面和顶面）
  • next指针实现了一个链表，方便管理投影相同的所有区间（区间与区域之前不连续）
  • xz的坐标记录在高度场中，结构体本身没有记
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Recast.h -> struct rcSpan
// line: 276~282

/// Defines the number of bits allocated to rcSpan::smin and rcSpan::smax.
static const int RC_SPAN_HEIGHT_BITS = 13;

/// Represents a span in a heightfield.
/// @see rcHeightfield
struct rcSpan
{
	unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax]
	unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
	unsigned int area : 6;                   ///< The area id assigned to the span.
	rcSpan* next;                            ///< The next span higher up in column.
};

高度场 heightfield

  • 容纳所有地图元素的空间容器
  • 高度场维护了一个二维数组来记录空间(特指span)集合，二维数组的单个元素是在xz平面投影相同的span的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Recast.h -> struct rcHeightfield
// line: 294~313

/// A dynamic heightfield representing obstructed space.
/// @ingroup recast
struct rcHeightfield
{
	rcHeightfield();
	~rcHeightfield();

	int width;			///< The width of the heightfield. (Along the x-axis in cell units.)
	int height;			///< The height of the heightfield. (Along the z-axis in cell units.)
	float bmin[3];  	///< The minimum bounds in world space. [(x, y, z)]
	float bmax[3];		///< The maximum bounds in world space. [(x, y, z)]
	float cs;			///< The size of each cell. (On the xz-plane.)
	float ch;			///< The height of each cell. (The minimum increment along the y-axis.)
	rcSpan** spans;		///< Heightfield of spans (width*height).
	rcSpanPool* pools;	///< Linked list of span pools.
	rcSpan* freelist;	///< The next free span.

private:
	// Explicitly-disabled copy constructor and copy assignment operator.
	rcHeightfield(const rcHeightfield&);
	rcHeightfield& operator=(const rcHeightfield&);
};

紧缩空间

  • 高度场中的span是三角面的体素集，是“实心”的部分
  • 紧缩空间是将实心区域之间的“空心”部分取出来
  • y是起始高度，也是“实心”空间的可行走的上表面
  • h是空心的连续高度
  • con用一个uint来表示与4个邻居的联通情况（二进制位压缩表示）
1
2
3
4
5
6
7
8
9
10
11
// Recast.h -> struct rcCompactSpan
// line: 323~329

/// Represents a span of unobstructed space within a compact heightfield.
struct rcCompactSpan
{
	unsigned short y;			///< The lower extent of the span. (Measured from the heightfield's base.)
	unsigned short reg;			///< The id of the region the span belongs to. (Or zero if not in a region.)
	unsigned int con : 24;		///< Packed neighbor connection data.
	unsigned int h : 8;			///< The height of the span.  (Measured from #y.)
};

紧缩空间

紧缩高度场

  • 场景内的紧缩空间集合

rcCompactCell

  • 这个结构记录了投影坐标为xz的这一列上CompactSpan的个数以及在数组中的起始id
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // Recast.h -> struct rcCompactCell
    // line: 316~320

    /// Provides information on the content of a cell column in a compact heightfield.
    struct rcCompactCell
    {
    	unsigned int index : 24;	///< Index to the first span in the column.
    	unsigned int count : 8;		///< Number of spans in the column.
    };

rcCompactHeightfield

  • rcCompactSpan* spans 是一个一维数组，按id递增的顺序记录了高度场内的所有CompactSpan
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // Recast.h -> struct rcCompactHeightfield
    // line: 333~353

    /// A compact, static heightfield representing unobstructed space.
    /// @ingroup recast
    struct rcCompactHeightfield
    {
    	rcCompactHeightfield();
    	~rcCompactHeightfield();
    	int width;					///< The width of the heightfield. (Along the x-axis in cell units.)
    	int height;					///< The height of the heightfield. (Along the z-axis in cell units.)
    	int spanCount;				///< The number of spans in the heightfield.
    	int walkableHeight;			///< The walkable height used during the build of the field.  (See: rcConfig::walkableHeight)
    	int walkableClimb;			///< The walkable climb used during the build of the field. (See: rcConfig::walkableClimb)
    	int borderSize;				///< The AABB border size used during the build of the field. (See: rcConfig::borderSize)
    	unsigned short maxDistance;	///< The maximum distance value of any span within the field.
    	unsigned short maxRegions;	///< The maximum region id of any span within the field.
    	float bmin[3];				///< The minimum bounds in world space. [(x, y, z)]
    	float bmax[3];				///< The maximum bounds in world space. [(x, y, z)]
    	float cs;					///< The size of each cell. (On the xz-plane.)
    	float ch;					///< The height of each cell. (The minimum increment along the y-axis.)
    	rcCompactCell* cells;		///< Array of cells. [Size: #width*#height]
    	rcCompactSpan* spans;		///< Array of spans. [Size: #spanCount]
    	unsigned short* dist;		///< Array containing border distance data. [Size: #spanCount]
    	unsigned char* areas;		///< Array containing area id data. [Size: #spanCount]
    };

BVH(Bounding volume hierarchy)

  • 包围体层次结构，是一种用树形结构组织管理空间内物体（几何体）的方法，在项目的代码注释中也被称为AABB Tree。

分水岭算法

  • 分水岭算法是一种图像区域分割法，在分割的过程中，它会把跟临近像素间的相似性作为重要的参考依据，从而将在空间位置上相近并且灰度值相近的像素点互相连接起来构成一个封闭的轮廓
  • 分水岭算法的目标就是找出不同区域之间的分水线，其过程就是让水位不断上升满满淹没汇水盆地，同时构建水坝阻挡不同的盆地交汇。这些水坝就是最终连接好的单像素边缘

生成navmesh时面板上输入的参数

  • 所有的参数都对应在下面的 struct 中
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    // Recast.h -> struct rcCompactHeightfield
    // line: 196~263

    /// Specifies a configuration to use when performing Recast builds.
    /// @ingroup recast
    struct rcConfig
    {
    	/// The width of the field along the x-axis. [Limit: >= 0] [Units: vx]
    	int width;

    	/// The height of the field along the z-axis. [Limit: >= 0] [Units: vx]
    	int height;

    	/// The width/height size of tile's on the xz-plane. [Limit: >= 0] [Units: vx]
    	int tileSize;

    	/// The size of the non-navigable border around the heightfield. [Limit: >=0] [Units: vx]
    	int borderSize;

    	/// The xz-plane cell size to use for fields. [Limit: > 0] [Units: wu]
    	float cs;

    	/// The y-axis cell size to use for fields. [Limit: > 0] [Units: wu]
    	float ch;

    	/// The minimum bounds of the field's AABB. [(x, y, z)] [Units: wu]
    	float bmin[3];

    	/// The maximum bounds of the field's AABB. [(x, y, z)] [Units: wu]
    	float bmax[3];

    	/// The maximum slope that is considered walkable. [Limits: 0 <= value < 90] [Units: Degrees]
    	float walkableSlopeAngle;

    	/// Minimum floor to 'ceiling' height that will still allow the floor area to
    	/// be considered walkable. [Limit: >= 3] [Units: vx]
    	int walkableHeight;

    	/// Maximum ledge height that is considered to still be traversable. [Limit: >=0] [Units: vx]
    	int walkableClimb;

    	/// The distance to erode/shrink the walkable area of the heightfield away from
    	/// obstructions.  [Limit: >=0] [Units: vx]
    	int walkableRadius;

    	/// The maximum allowed length for contour edges along the border of the mesh. [Limit: >=0] [Units: vx]
    	int maxEdgeLen;

    	/// The maximum distance a simplfied contour's border edges should deviate
    	/// the original raw contour. [Limit: >=0] [Units: vx]
    	float maxSimplificationError;

    	/// The minimum number of cells allowed to form isolated island areas. [Limit: >=0] [Units: vx]
    	int minRegionArea;

    	/// Any regions with a span count smaller than this value will, if possible,
    	/// be merged with larger regions. [Limit: >=0] [Units: vx]
    	int mergeRegionArea;

    	/// The maximum number of vertices allowed for polygons generated during the
    	/// contour to polygon conversion process. [Limit: >= 3]
    	int maxVertsPerPoly;

    	/// Sets the sampling distance to use when generating the detail mesh.
    	/// (For height detail only.) [Limits: 0 or >= 0.9] [Units: wu]
    	float detailSampleDist;

    	/// The maximum distance the detail mesh surface should deviate from heightfield
    	/// data. (For height detail only.) [Limit: >=0] [Units: wu]
    	float detailSampleMaxError;
    };

生成导航网格

  • Recast部分的功能就是生成整个导航网格，其核心方法是 Sample_SoloMesh::handleBuild
  • class Sample_SoloMesh 是 头文件Sample.h 中的 class Sample 的实现
    这个函数注释非常友好地揭露了生成整个NavMesh导航网格的8个步骤，分别是：
    • Step 1. Initialize build config
    • Step 2. Rasterize input polygon soup
    • Step 3. Filter walkables surfaces
    • Step 4. Partition walkable surface to simple regions
    • Step 5. Trace and simplify region contours
    • Step 6. Build polygons mesh from contours
    • Step 7. Create detail mesh which allows to access approximate height on each polygon
    • Step 8. Create Detour data from Recast poly mesh

读入数据

  • 构建方式选择，一共三种
    AABB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// RecastDemo/main.cpp
// line:60~70

Sample* createSolo() { return new Sample_SoloMesh(); }
Sample* createTile() { return new Sample_TileMesh(); }
Sample* createTempObstacle() { return new Sample_TempObstacles(); }

static SampleItem g_samples[] =
{
	{ createSolo, "Solo Mesh" },
	{ createTile, "Tile Mesh" },
	{ createTempObstacle, "Temp Obstacles" },
};

static const int g_nsamples = sizeof(g_samples) / sizeof(SampleItem);

  • recastDemo编辑器使用SDL来做编辑器

  • 其创建[Choose Sample]GUI列表和对应的选择响应函数在RecastDemo/main.cpp line:611~666

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    // RecastDemo/main.cpp
    // line:611~666

    if (showSample)
    {
        // 显示choose sample列表
        static int levelScroll = 0;
        if (imguiBeginScrollArea("Choose Sample", width-10-250-10-200, height-10-250, 200, 250, &levelScroll))
            mouseOverMenu = true;

        Sample* newSample = 0;
        for (int i = 0; i < g_nsamples; ++i)
        {
            if (imguiItem(g_samples[i].name.c_str()))
            {
                newSample = g_samples[i].create(); // 这里是点击选中响应代码，会创建对应的Sample，在上下文中是Sample_SoloMesh
                if (newSample)
                    sampleName = g_samples[i].name;
            }
        }
        if (newSample)
        {
            delete sample;
            sample = newSample;
            sample->setContext(&ctx); // m_ctx = ctx，ctx是个全局上下文环境，主要用于计时、Log等。
            if (geom) // geom是模型数据，在选择模型之后切换Sample方式才会进入这里
            {
                sample->handleMeshChanged(geom);
            }
        }

        if (geom || sample)
        {
            //...做一些编辑器的更新工作
            //...计算相机位置，由于这个函数循环在跑，所以如果showSample是True的时候相机会被无限拉回，感觉条件改为newSample更合理一点？
            //...设置GL_FOG_START和GL_FOG_END
        }

        imguiEndScrollArea();
    }

  • 接着再点击界面的[Choose Mesh]，选择一个.obj文件

  • 由v/vt/f/vn等key开头，后面跟相应的数据，以空格分开

  • 其中v表示顶点，f表示面，即顶点索引

QinHanGame Developer & Designer

当你发现自己的才华撑不起野心时，就请安静下来学习吧！