Recast-GetStart

Recast-入门

Recast-Navigation 在做3d游戏的时候，用于做导航的在Unity3D、Unreal Engine都可以使用。当前使用 unreal 4.25

1. Recast工程介绍

RecastNavigation 是一个的导航寻路工具集，它包括了几个子集：

Recast：负责根据提供的模型生成导航网格。
Detour：利用导航网格做寻路操作。这里的导航网格可以是 Recast 生成的，也可以是其他工具生成的。
DetourCrowd：提供了群体寻路行为的功能。
Recast Demo：一个很完善的 Demo，基本上将 Recast 、 Detour 提供的功能都很好地展现了出来。弄懂了这个 Demo 的功能，基本也就了解了 RecastNavigation 究竟可以干什么事。

Recast先从几何体构造素模，然后在其上投射导航网格。此过程包括三个步骤：

创建素模(voxel mold)；

通过将三角形栅格化为多层高度场，从输入三角形网格构建体素模具。然后将一些简单的滤镜应用到模具上，以修剪角色无法移动的位置。

将素模划分成简单区域(region)；

模具描述的可行走区域分为简单的2D覆盖区域。生成的区域仅具有不重叠的轮廓，这大大简化了过程的最后一步。

将区域转换成多边形(polygons)；

通过首先跟踪边界，然后对其进行简化，可以将导航多边形从区域中剥离。最终将生成的多边形转换为凸多边形，这使它们非常适合该级的寻路和空间推理。

注：凸多边形的内角均小于或等于180°，边数为n（n属于Z且n大于2）的凸多边形内角和为（n－2）×180°，但任意凸多边形外角和均为360°，并可通过反证法证明凸多边形内角中锐角的个数不能多于3个。

尝试将unreal engine 里面的地图导出成detour能使用的导航网格：

再 UNREAL ENGINE 里面地图是.umap文件。我们用UE打开之后，在菜单栏里面操作： Windows->导出NavMesh。这个步骤将会生成一个.obj文件。这种文件其实是一种文本文件，描述了3D对象模型信息。Unity3D也一样能导出这样的文件。此过程将会生成某个尺寸的模型文件。

我们移植了一些Detour的代码，编写了一个程序 RecastCreator。这个程序能将*.obj文件导出成为一个binary文件。后续就直接使用binary文件来做导航操作。

PS D:\work\trunk\refer\recastnavigation\RecastDemo\Bin\Meshes> .\RecastCreator.exe -cfg -out t3.obj t3.region
----- Create Cfg -----
cellsize = 0.30
cellheight = 0.20
agentheight = 2
agentradius = 0.6
agentmaxclimb = 0.9
agentmaxslope = 45
regionminsize = 8
regionmergesize = 20
edgemaxlen = 12
edgemaxerror = 1.3
vertsperpoly = 6
detailsampledist = 6
detailsamplemaxerror = 1
partitiontype = 1
tilesize = 0
----- End -----
PS D:\work\trunk\refer\recastnavigation\RecastDemo\Bin\Meshes> .\RecastCreator.exe -out t3.obj t3.region
----- Create Bin -----
Building navigation:
 - 1028 x 1135 cells
 - 525.2K verts, 306.2K tris
Build Times
- Rasterize:    176.99ms        (24.5%)
- Build Compact:        39.54ms (5.5%)
- Filter Border:        29.55ms (4.1%)
- Filter Walkable:      5.15ms  (0.7%)
- Erode Area:   19.18ms (2.7%)
- Median Area:  0.00ms  (0.0%)
- Mark Box Area:        0.00ms  (0.0%)
- Mark Convex Area:     0.00ms  (0.0%)
- Mark Cylinder Area:   0.00ms  (0.0%)
- Build Distance Field: 29.01ms (4.0%)
    - Distance: 19.88ms (2.7%)
    - Blur:     8.95ms  (1.2%)
- Build Regions:        105.62ms        (14.6%)
    - Watershed:        97.48ms (13.5%)
      - Expand: 35.47ms (4.9%)
      - Find Basins:    2.93ms  (0.4%)
    - Filter:   6.76ms  (0.9%)
- Build Layers: 0.00ms  (0.0%)
- Build Contours:       13.14ms (1.8%)
    - Trace:    8.87ms  (1.2%)
    - Simplify: 2.00ms  (0.3%)
- Build Polymesh:       6.09ms  (0.8%)
- Build Polymesh Detail:        286.67ms        (39.6%)
- Merge Polymeshes:     0.00ms  (0.0%)
- Merge Polymesh Details:       0.00ms  (0.0%)
=== TOTAL:      723.73ms
>> Polymesh: 2552 vertices  1153 polygons

----- End -----

2.环境搭建

2.1.编译recastnavigation

工具名称	版本信息
visualstudio2019	16.8.3
CMake	3.19.0-rc1
premake	5.0

2.1.1.下载地址

名称	下载地址
SDL	SDL2-devel-2.0.14-VC.zip
premake	premake.github

2.1.2.准备好SDL2的dll

将上述的SDL2-devel-2.0.14--VC.zip文件解压缩，放入到${RecastDemo}\Contrib\SDL目录中。因为在

2.1.3.使用premake5生成工程文件

这个默认生成的是win32位的

D:\work\trunk\refer\recastnavigation\RecastDemo>"premake5" vs2019
Building configurations...
Running action 'vs2019'...
Generated Build/vs2019/recastnavigation.sln...
Generated Build/vs2019/DebugUtils.vcxproj...
Generated Build/vs2019/DebugUtils.vcxproj.filters...
Generated Build/vs2019/Detour.vcxproj...
Generated Build/vs2019/Detour.vcxproj.filters...
Generated Build/vs2019/DetourCrowd.vcxproj...
Generated Build/vs2019/DetourCrowd.vcxproj.filters...
Generated Build/vs2019/DetourTileCache.vcxproj...
Generated Build/vs2019/DetourTileCache.vcxproj.filters...
Generated Build/vs2019/Recast.vcxproj...
Generated Build/vs2019/Recast.vcxproj.filters...
Generated Build/vs2019/RecastDemo.vcxproj...
Generated Build/vs2019/RecastDemo.vcxproj.user...
Generated Build/vs2019/RecastDemo.vcxproj.filters...
Generated Build/vs2019/Tests.vcxproj...
Generated Build/vs2019/Tests.vcxproj.user...
Generated Build/vs2019/Tests.vcxproj.filters...
Done (225ms).

RecastDemo的效果图：

加载一个obj文件：

将obj文件的导航网格生成出来：

生成了之后，地图的颜色将会变化，只需要点击”Build”。有导航网格，才能去测试导航功能。

测试导航功能：

在地图上选择开始结束点；”shift+鼠标左键”

3.Recast 导航网格类型

recastnavigation中提供了3种模式的导航网格：

3.1.SoloMesh

其中SoloMesh模式是静态的导航网格，即对场景build一次之后，将导航网格缓存起来供寻路使用，后续不再允许场景的导航信息发生变化。

文件头：

static const int NAVMESHSET_MAGIC = 'M'<<24 | 'S'<<16 | 'E'<<8 | 'T'; //'MSET';
struct NavMeshSetHeader
{
    uint32_t magic;
    uint32_t version;
    uint32_t numTiles;
    dtNavMeshParams params;
};
    // Store header.
    NavMeshSetHeader header;
    header.magic = NAVMESHSET_MAGIC;
    header.version = NAVMESHSET_VERSION;
    header.numTiles = 0;

3.2.TileMesh

TileMesh也是静态的导航网格，只是与SoloMesh相比它按tile来处理地图，算是介于SoloMesh和TempObstacles之间的一种模式

// 文件名：all_tiles_navmesh.bin
// 文件头： TESM
static const int NAVMESHSET_MAGIC = 'M'<<24 | 'S'<<16 | 'E'<<8 | 'T'; //'MSET';

// 加载文件失败：
dtStatus addTileStatus = m_tileCache->addTile(data, tileHeader.dataSize, DT_COMPRESSEDTILE_FREE_DATA, &tile);
inline bool dtStatusFailed(dtStatus status)
static const unsigned int DT_FAILURE = 1u << 31;            // Operation failed.
static const unsigned int DT_WRONG_MAGIC = 1 << 0;        // Input data is not recognized.
    if (header->magic != DT_TILECACHE_MAGIC)
        return DT_FAILURE | DT_WRONG_MAGIC;

static const int DT_TILECACHE_MAGIC = 'D'<<24 | 'T'<<16 | 'L'<<8 | 'R'; ///< 'DTLR';


Sample::saveAll("all_tiles_navmesh.bin", m_navMesh);

3.3.TempObstacles

TempObstacles模式可以支持向场景中动态添加或移除预设形状的阻挡物，导航网格也会随之更新（不过只支持添加阻挡物，而不支持添加新的可行走区域）在处理动态阻挡时，由于单个阻挡对地图的影响区域是有限的，所以会采用将地图切割成多个固定大小的tile，以tile为单位进行网格的生成。这样在添加或移除阻挡时，只需要处理与阻挡相交的tile，而不需要处理整个地图。

1	static const int TILECACHESET_MAGIC = 'T' << 24 \| 'S' << 16 \| 'E' << 8 \| 'T'; //'TSET';

参考NavMeshDemo源码

3.4.导出Mesh的源码分析

参考官方的代码-RecastDemo部分，在右边的上部，”Sample”中下拉菜单中选择的三类(Solo Mesh、Tile Mesh、Temp Obstacles)导出方式都看明白。

3种导出方式：

1
2
3

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

“Build”按钮将会调用

if (imguiButton("Build"))
{
    ctx.resetLog();
    if (!sample->handleBuild())
    {
        showLog = true;
        logScroll = 0;
    }
    ctx.dumpLog("Build log %s:", meshName.c_str());
    
    // Clear test.
    delete test;
    test = 0;
}

“Save”按钮将会把生成的网格存储到

类型	文件	大小
Solo	solo_navmesh.bin	240kb
Tile	all_tiles_navmesh.bin	479kb
TempObstacle	all_tiles_tilecache.bin	479kb

导出时候需要设置的参数：

变量	基本信息	备注
cellsize	方块尺寸	0.3
cellheight	方块高度	0.2
agentheight	walkableHeight = agentheight/ cellheight	2
agentradius	walkableClimb = agentradius/ cellheight	0.6
agentmaxclimb	walkableRadius = agentmaxclimb/ cellheight	0.9
agentmaxslope	walkableSlopeAngle = agentmaxslope	45
regionminsize	minRegionArea = regionminsize*regionminsize	8
regionmergesize	mergeRegionArea = regionmergesize*regionmergesize	20
edgemaxlen	maxEdgeLen = edgemaxlen/cellheight	12
edgemaxerror	maxSimplificationError = edgemaxerror	1.3
vertsperpoly	maxVertsPerPoly	6
detailsampledist	detailSampleDist = detailsampledist < 0.9f ? 0 : cellsize * detailsampledist;	6
detailsamplemaxerror	detailSampleMaxError = cellheight * detailsamplemaxerror	1
partitiontype		1
tilesize		48

RecastNavigation-rcConfig文档

cellsize

方块尺寸（x,z平面上），和平面有关系。较低的值将产生较高质量的导航，但是图形扫描较慢。在文档里面记作 [vx]

cellheight

方块高度（y高程），和爬坡有关系。记录计算攀爬仰角，攀爬的高度，计算边缘都需要这个。官方文档里面记作 [vy]

agentheight

minRegionArea

最小孤岛所容纳的cell数目；

任意区域小于指定的数目，将会标记成无法行走。这个东西通常用于去删除无用几何体，比如桌子的顶部，盒子的顶部等等。

值域：[Limit: >=0] 作用域：[Units: vx]，vx代表平面；

mergeRegionArea

如果有可能性的话，任意区域如果cell的数目小于它，将会被融合到比它大的区域里面。

值域：[Limit: >=0] 作用域：[Units: vx]

edgemaxlen

沿网格边界的轮廓边缘的最大允许长度。 [Limit: >=0] [Units: vx].

这个将会让边缘更加趋于直线。如果想关闭这个功能将值设置成0。

partitiontype

分区方式

Watershed 分水岭方式

enum SamplePartitionType SAMPLE_PARTITION_WATERSHED = 0

大意就是从地势的最低点开始灌水，水漫过的区间若与原区域相邻则认为是同一区域，否则认为是一个新的区域。分水岭算法通常用于图形处理领域，基于图像的灰度值来分割图像。

Monotone 单调方式

enum SamplePartitionType SAMPLE_PARTITION_MONOTONE = 1

Layers 分层方式

enum SamplePartitionType SAMPLE_PARTITION_LAYERS = 2

原文释义：

Partition the heightfield so that we can use simple algorithm later to triangulate the walkable areas.
There are 3 martitioning methods, each with some pros and cons:
1) Watershed partitioning
  - the classic Recast partitioning
  - creates the nicest tessellation
  - usually slowest
  - partitions the heightfield into nice regions without holes or overlaps
  - the are some corner cases where this method creates produces holes and overlaps
     - holes may appear when a small obstacles is close to large open area (triangulation can handle this)
     - overlaps may occur if you have narrow spiral corridors (i.e stairs), this make triangulation to fail
  * generally the best choice if you precompute the nacmesh, use this if you have large open areas
2) Monotone partioning
  - fastest
  - partitions the heightfield into regions without holes and overlaps (guaranteed)
  - creates long thin polygons, which sometimes causes paths with detours
  * use this if you want fast navmesh generation
3) Layer partitoining
  - quite fast
  - partitions the heighfield into non-overlapping regions
  - relies on the triangulation code to cope with holes (thus slower than monotone partitioning)
  - produces better triangles than monotone partitioning
  - does not have the corner cases of watershed partitioning
  - can be slow and create a bit ugly tessellation (still better than monotone)
    if you have large open areas with small obstacles (not a problem if you use tiles)
  * good choice to use for tiled navmesh with medium and small sized tiles

tilesize

每块tile再xz平面上的size。[Limit: >= 0] [Units: vx].

这个值旨在编译出多tile mesh的时候生效（temp obstacles/tiles）。

4.包围盒分类

4.1.AABB

AABB算法的全称是 - axis aligned bounding box (轴对齐-边界盒)AABB 包围盒是与坐标轴对齐的包围盒, 简单性好, 紧密性较差。

我们在具体使用的时候，发现如果地形上有一些起伏，最好能通过AABB方式来，这样确保地图中的位置被严格的堵住。

4.2.OBB

OBB 包围盒: OBB（oriented bounding box 方向矩形边界框）碰撞检測方法紧密性是较好的, 可以大大降低參与相交測试的包围盒的数目, 因此整体性能要优于AABB 和包围球, 而且实时性程度较高。

OBB在堵路的时候，如果有楼梯类似的地势，将无法做到将导航切割。

Library: ue-recast-detour这个是从 UE 代码中抽取出的 recast detour 库，在 UE 源码的路径下为 Runtime/Navmesh/Detour，主要目的是保证 UE 客户端与外部服务器的验证方法一致。只将solo方式的导航。

其实在UnrealEngine4的源代码中是有一份NavigationSystem，Navmesh。github-UE4-Navmesh。可以直接在ue4的引擎代码里面找到动态阻挡相关的逻辑。

阅读RecastDemo

最近在看recast的阻挡相关知识，其实这块最好能扩展一下工具的绘制功能。具体文件目录在recastnavigation\DebugUtils\Include\DebugDraw.h

能支持的绘制类型

enum duDebugDrawPrimitives
{
  DU_DRAW_POINTS, // 绘制点
  DU_DRAW_LINES, // 绘制线
  DU_DRAW_TRIS, // 三角形
  DU_DRAW_QUADS, // 四边形
};

最终调用的gl函数

switch (prim)
{
  case DU_DRAW_POINTS:
    glPointSize(size);
    glBegin(GL_POINTS);
    break;
  case DU_DRAW_LINES:
    glLineWidth(size);
    glBegin(GL_LINES);
    break;
  case DU_DRAW_TRIS:
    glBegin(GL_TRIANGLES);
    break;
  case DU_DRAW_QUADS:
    glBegin(GL_QUADS);
    break;
};

最终完成绘图的就是底层的SDL_opengl库的函数。我们这里是使用的SDL 2.0.14版本。

Simple DirectMedia Layer is a cross-platform development library designed to provide low level access to audio, keyboard, mouse, joystick, and graphics hardware via OpenGL and Direct3D.

绘制实例

绘制AABB方块

通过四边形来拼凑出来。

if (ob->type == DT_OBSTACLE_BOX)
{
  unsigned int cols[3];// 其实需要输入6种颜色
  cols[0] = duRGBA(255, 0, 0, 128); // 需要输入3种颜色作为参数
  cols[1] = duRGBA(0, 255, 0, 128); 
  cols[2] = duRGBA(0, 0, 255, 128);
  duDebugDrawBox(dd, bmin[0], bmin[1], bmin[2], bmax[0], bmax[1], bmax[2], cols);
}

// 输入参数其实就是AABB的两个顶点位置，fcol是给定颜色
void duDebugDrawBox(struct duDebugDraw* dd, float minx, float miny, float minz,
          float maxx, float maxy, float maxz, const unsigned int* fcol)
{
  if (!dd) return;
  
  dd->begin(DU_DRAW_QUADS);
  duAppendBox(dd, minx,miny,minz, maxx,maxy,maxz, fcol);
  dd->end();
}


// 绘制AABB方式的Box
void duAppendBox(struct duDebugDraw* dd, float minx, float miny, float minz,
         float maxx, float maxy, float maxz, const unsigned int* fcol)
{
  if (!dd) return;
  const float verts[8*3] =
  {
    // 正面4个顶点，按照逆时针顺序
    minx, miny, minz, // 0
    maxx, miny, minz, // 1
    maxx, miny, maxz, // 2
    minx, miny, maxz, // 3

    // 背面4个顶点
    minx, maxy, minz,
    maxx, maxy, minz,
    maxx, maxy, maxz,
    minx, maxy, maxz,
  };

  static const unsigned char inds[6*4] =
  {
    // 每一句话都是从立方体上去一个点，而且刚好是6面体的某个面
    7, 6, 5, 4, // 背面
    0, 1, 2, 3, // 正面
    1, 5, 6, 2, // 右面
    3, 7, 4, 0, // 左面
    2, 6, 7, 3, // 顶面
    0, 4, 5, 1, // 底部
  };
  
  // 一共能支持读取6种颜色
  const unsigned char* in = inds;
  for (int i = 0; i < 6; ++i)
  {
    // 每一句话都是从立方体上去一个点，而且刚好是6面体的某个面
    dd->vertex(&verts[*in*3], fcol[i]); in++;
    dd->vertex(&verts[*in*3], fcol[i]); in++;
    dd->vertex(&verts[*in*3], fcol[i]); in++;
    dd->vertex(&verts[*in*3], fcol[i]); in++;
  }
}

绘制圆柱体

圆柱体绘制的时候，是按照16等分的圆面，然后用三角形拼凑出来的。

else if (ob->type == DT_OBSTACLE_CYLINDER)
{
  // 绘制圆柱体
  duDebugDrawCylinder(dd, bmin[0], bmin[1], bmin[2], bmax[0], bmax[1], bmax[2], col);
  // 绘制圆柱体的线
  duDebugDrawCylinderWire(dd, bmin[0], bmin[1], bmin[2], bmax[0], bmax[1], bmax[2], duDarkenCol(col), 2);

}
// 绘制圆柱体，是按照三角形来绘制
void duDebugDrawCylinder(struct duDebugDraw* dd, float minx, float miny, float minz,
             float maxx, float maxy, float maxz, unsigned int col)
{
  if (!dd) return;
  
  dd->begin(DU_DRAW_TRIS);
  duAppendCylinder(dd, minx,miny,minz, maxx,maxy,maxz, col);
  dd->end();
}
// 绘制圆柱体
void duAppendCylinder(struct duDebugDraw* dd, float minx, float miny, float minz,
            float maxx, float maxy, float maxz, unsigned int col)
{
  if (!dd) return;
  
  // 等分16分
  static const int NUM_SEG = 16;
  static float dir[NUM_SEG*2];
  static bool init = false;
  if (!init)
  {
    init = true;
    for (int i = 0; i < NUM_SEG; ++i)
    {
      const float a = (float)i/(float)NUM_SEG*DU_PI*2;
      dir[i*2] = cosf(a);
      dir[i*2+1] = sinf(a);
    }
  }
  
  unsigned int col2 = duMultCol(col, 160);
  
  const float cx = (maxx + minx)/2; // 计算中心位置
  const float cz = (maxz + minz)/2;
  const float rx = (maxx - minx)/2; // 计算x,z的半径
  const float rz = (maxz - minz)/2;

  // 绘制底部圆，固定第一个点，然后开始在圆面上按照逆时针找圆周上的邻近两个点，连成三角形，最终构成圆面
  for (int i = 2; i < NUM_SEG; ++i)
  {
    const int a = 0, b = i-1, c = i;
    dd->vertex(cx+dir[a*2+0]*rx, miny, cz+dir[a*2+1]*rz, col2);
    dd->vertex(cx+dir[b*2+0]*rx, miny, cz+dir[b*2+1]*rz, col2);
    dd->vertex(cx+dir[c*2+0]*rx, miny, cz+dir[c*2+1]*rz, col2);
  }
  // 绘制顶部圆面
  for (int i = 2; i < NUM_SEG; ++i)
  {
    const int a = 0, b = i, c = i-1;
    dd->vertex(cx+dir[a*2+0]*rx, maxy, cz+dir[a*2+1]*rz, col);
    dd->vertex(cx+dir[b*2+0]*rx, maxy, cz+dir[b*2+1]*rz, col);
    dd->vertex(cx+dir[c*2+0]*rx, maxy, cz+dir[c*2+1]*rz, col);
  }
  // 绘制圆筒，用两个三角形平凑出一个矩形出来
  for (int i = 0, j = NUM_SEG-1; i < NUM_SEG; j = i++)
  {
    dd->vertex(cx+dir[i*2+0]*rx, miny, cz+dir[i*2+1]*rz, col2);
    dd->vertex(cx+dir[j*2+0]*rx, miny, cz+dir[j*2+1]*rz, col2);
    dd->vertex(cx+dir[j*2+0]*rx, maxy, cz+dir[j*2+1]*rz, col);

    dd->vertex(cx+dir[i*2+0]*rx, miny, cz+dir[i*2+1]*rz, col2);
    dd->vertex(cx+dir[j*2+0]*rx, maxy, cz+dir[j*2+1]*rz, col);
    dd->vertex(cx+dir[i*2+0]*rx, maxy, cz+dir[i*2+1]*rz, col);
  }
}
// 绘制线条
void duDebugDrawCylinderWire(struct duDebugDraw* dd, float minx, float miny, float minz,
               float maxx, float maxy, float maxz, unsigned int col, const float lineWidth)
{
  if (!dd) return;
  
  dd->begin(DU_DRAW_LINES, lineWidth);
  duAppendCylinderWire(dd, minx,miny,minz, maxx,maxy,maxz, col);
  dd->end();
}
// 画线条
void duAppendCylinderWire(struct duDebugDraw* dd, float minx, float miny, float minz,
              float maxx, float maxy, float maxz, unsigned int col)
{
  if (!dd) return;

  // 等分16分，计算出对应的标准化后的向量
  static const int NUM_SEG = 16;
  static float dir[NUM_SEG*2];
  static bool init = false;
  if (!init)
  {
    init = true;
    for (int i = 0; i < NUM_SEG; ++i)
    {
      const float a = (float)i/(float)NUM_SEG*DU_PI*2;
      dir[i*2] = dtMathCosf(a);
      dir[i*2+1] = dtMathSinf(a);
    }
  }
  
  const float cx = (maxx + minx)/2; // 算出中心点位置
  const float cz = (maxz + minz)/2;
  const float rx = (maxx - minx)/2; // x,z的半径
  const float rz = (maxz - minz)/2; 
  
  // 循环画圆面
  for (int i = 0, j = NUM_SEG-1; i < NUM_SEG; j = i++)
  {
    // 画底部圆，两点连成线
    dd->vertex(cx+dir[j*2+0]*rx, miny, cz+dir[j*2+1]*rz, col);
    dd->vertex(cx+dir[i*2+0]*rx, miny, cz+dir[i*2+1]*rz, col);
    // 画顶部圆，两点连成线
    dd->vertex(cx+dir[j*2+0]*rx, maxy, cz+dir[j*2+1]*rz, col);
    dd->vertex(cx+dir[i*2+0]*rx, maxy, cz+dir[i*2+1]*rz, col);
  }
  // 绘制圆柱体4个轴线方向的垂直圆通黑线
  for (int i = 0; i < NUM_SEG; i += NUM_SEG/4)
  {
    dd->vertex(cx+dir[i*2+0]*rx, miny, cz+dir[i*2+1]*rz, col);
    dd->vertex(cx+dir[i*2+0]*rx, maxy, cz+dir[i*2+1]*rz, col);
  }
}

依葫芦画瓢OBB

// 绘制OBB立方体
void duDebugDrawOBB(struct duDebugDraw* dd, float cx, float cy, float cz,
  float extendx, float extendy, float extendz, float yaw, const unsigned int* fcol)
{
  if (!dd) return;

  dd->begin(DU_DRAW_TRIS);
  duAppendOBB(dd, cx, cy, cz, extendx, extendy, extendz, yaw, fcol);
  dd->end();
}

// 绘制OBB
void duAppendOBB(struct duDebugDraw* dd, float cx, float cy, float cz,
  float extendx, float extendy, float extendz, float yaw, const unsigned int *fcol)
{
  if (!dd) return;

  mathfu::Vector<float, 3> centerPos(cx, cy, cz);

  // 找到AABB点
  mathfu::Vector<float, 3> p0(-extendx,-extendy, -extendz);
  mathfu::Vector<float, 3> p1(extendx, -extendy, -extendz);
  mathfu::Vector<float, 3> p2(extendx, -extendy, extendz);
  mathfu::Vector<float, 3> p3(-extendx, -extendy, extendz);

  mathfu::Vector<float, 3> p4(-extendx, extendy, -extendz);
  mathfu::Vector<float, 3> p5(extendx, extendy, -extendz);
  mathfu::Vector<float, 3> p6(extendx, extendy, extendz);
  mathfu::Vector<float, 3> p7(-extendx, extendy, extendz);

  // 通过矩阵将点yaw。
  mathfu::Matrix<float, 3> rotation_around_y(mathfu::Matrix<float,3>::RotationY(-yaw));
  p0 = p0 * rotation_around_y + centerPos;
  p1 = p1 * rotation_around_y + centerPos;
  p2 = p2 * rotation_around_y + centerPos;
  p3 = p3 * rotation_around_y + centerPos;
  p4 = p4 * rotation_around_y + centerPos;
  p5 = p5 * rotation_around_y + centerPos;
  p6 = p6 * rotation_around_y + centerPos;
  p7 = p7 * rotation_around_y + centerPos;

  const float verts[8 * 3] =
  {
    // 正面4个顶点，按照逆时针顺序
    p0.x, p0.y, p0.z, // 0
    p1.x, p1.y, p1.z, // 1
    p2.x, p2.y, p2.z, // 2
    p3.x, p3.y, p3.z, // 3

    // 背面4个顶点
    p4.x, p4.y, p4.z,
    p5.x, p5.y, p5.z,
    p6.x, p6.y, p6.z,
    p7.x, p7.y, p7.z,
  };

  static const unsigned char inds[12 * 3] =
  {
    // 将立方体的每个面都使用两个三角形
    0,1,2,
    2,3,0,
    5,4,6,
    4,7,6,
    1,5,6,
    6,2,1,
    0,3,7,
    7,4,0,
    3,2,6,
    6,7,3,
    5,1,0,
    4,5,0,
  };

  // 一共能支持读取6种颜色
  const unsigned char* in = inds;
  for (int i = 0; i < 12; ++i)
  {
    auto colidx = i / 4;
    // 每一句话都是从立方体上去一个点，而且刚好是6面体的某个面
    dd->vertex(verts[inds[i * 3] * 3], verts[inds[i * 3] * 3 + 1], verts[inds[i * 3] * 3 + 2], fcol[colidx]);
    dd->vertex(verts[inds[i * 3 + 1] * 3], verts[inds[i * 3 + 1] * 3 + 1], verts[inds[i * 3 + 1] * 3 + 2], fcol[colidx]);
    dd->vertex(verts[inds[i * 3 + 2] * 3], verts[inds[i * 3 + 2] * 3 + 1], verts[inds[i * 3 + 2] * 3 + 2], fcol[colidx]);
  }
}

// 画出OBB棱角
void duAppendOBBWire(struct duDebugDraw* dd, float cx, float cy, float cz,
  float extendx, float extendy, float extendz, float yaw,
  unsigned int col)
{
  if (!dd) return;

  mathfu::Vector<float, 3> centerPos(cx, cy, cz);

  // 找到AABB点
  mathfu::Vector<float, 3> p0(-extendx, -extendy, -extendz);
  mathfu::Vector<float, 3> p1(extendx, -extendy, -extendz);
  mathfu::Vector<float, 3> p2(extendx, -extendy, extendz);
  mathfu::Vector<float, 3> p3(-extendx, -extendy, extendz);

  mathfu::Vector<float, 3> p4(-extendx, extendy, -extendz);
  mathfu::Vector<float, 3> p5(extendx, extendy, -extendz);
  mathfu::Vector<float, 3> p6(extendx, extendy, extendz);
  mathfu::Vector<float, 3> p7(-extendx, extendy, extendz);

  // 通过矩阵将点yaw。
  mathfu::Matrix<float, 3> rotation_around_y(mathfu::Matrix<float, 3>::RotationY(-yaw));
  p0 = p0 * rotation_around_y + centerPos;
  p1 = p1 * rotation_around_y + centerPos;
  p2 = p2 * rotation_around_y + centerPos;
  p3 = p3 * rotation_around_y + centerPos;
  p4 = p4 * rotation_around_y + centerPos;
  p5 = p5 * rotation_around_y + centerPos;
  p6 = p6 * rotation_around_y + centerPos;
  p7 = p7 * rotation_around_y + centerPos;


  const float verts[8 * 3] =
  {
    // 正面4个顶点，按照逆时针顺序
    p0.x, p0.y, p0.z, // 0
    p1.x, p1.y, p1.z, // 1
    p2.x, p2.y, p2.z, // 2
    p3.x, p3.y, p3.z, // 3

    // 背面4个顶点
    p4.x, p4.y, p4.z,
    p5.x, p5.y, p5.z,
    p6.x, p6.y, p6.z,
    p7.x, p7.y, p7.z,
  };

  // Top
  dd->vertex(p3.x, p3.y, p3.z, col);
  dd->vertex(p2.x, p2.y, p2.z, col);
  dd->vertex(p2.x, p2.y, p2.z, col);
  dd->vertex(p6.x, p6.y, p6.z, col);
  dd->vertex(p6.x, p6.y, p6.z, col);
  dd->vertex(p7.x, p7.y, p7.z, col);
  dd->vertex(p7.x, p7.y, p7.z, col);
  dd->vertex(p3.x, p3.y, p3.z, col);

  // bottom
  dd->vertex(p0.x, p0.y, p0.z, col);
  dd->vertex(p1.x, p1.y, p1.z, col);
  dd->vertex(p1.x, p1.y, p1.z, col);
  dd->vertex(p5.x, p5.y, p5.z, col);
  dd->vertex(p5.x, p5.y, p5.z, col);
  dd->vertex(p4.x, p4.y, p4.z, col);
  dd->vertex(p4.x, p4.y, p4.z, col);
  dd->vertex(p0.x, p0.y, p0.z, col);

  // Sides
  dd->vertex(p0.x, p0.y, p0.z, col);
  dd->vertex(p3.x, p3.y, p3.z, col);
  dd->vertex(p1.x, p1.y, p1.z, col);
  dd->vertex(p2.x, p2.y, p2.z, col);
  dd->vertex(p5.x, p5.y, p5.z, col);
  dd->vertex(p6.x, p6.y, p6.z, col);
  dd->vertex(p4.x, p4.y, p4.z, col);
  dd->vertex(p7.x, p7.y, p7.z, col);
}

阅读导出时系数

agent

修改了agent的半径之后，就能让AABB方式的动态墙切断navimesh。

imgui用法

如何使用单选框

class Sample {
  int m_partitionType; // 先定义一个选项类型
}

// 定义选项类型
enum SamplePartitionType
{
  SAMPLE_PARTITION_WATERSHED,
  SAMPLE_PARTITION_MONOTONE,
  SAMPLE_PARTITION_LAYERS,
};

// 绑定ui关系
void Sample::handleCommonSettings()
{
  imguiSeparator();
  imguiLabel("Partitioning");
  if (imguiCheck("Watershed", m_partitionType == SAMPLE_PARTITION_WATERSHED))
    m_partitionType = SAMPLE_PARTITION_WATERSHED;
  if (imguiCheck("Monotone", m_partitionType == SAMPLE_PARTITION_MONOTONE))
    m_partitionType = SAMPLE_PARTITION_MONOTONE;
  if (imguiCheck("Layers", m_partitionType == SAMPLE_PARTITION_LAYERS))
    m_partitionType = SAMPLE_PARTITION_LAYERS;
}

obb如何被导出

问题描述

相同体型的阻挡信息，长宽高为 10m2m6.5m。AABB动态阻挡能隔断mesh，但是OBB动态阻挡（旋转90°）无法阻断mesh。

使用OBB的时候，将会在获取触碰到的titles有21个。

使用AABB的时候，将会获取触碰到的titles只有6个。

源码里面只能让一个阻挡点碰撞到8个tiltes。

static const int DT_MAX_TOUCHED_TILES = 8;
struct dtTileCacheObstacle
{
  union
  {
    dtObstacleCylinder cylinder;
    dtObstacleBox box;
    dtObstacleOrientedBox orientedBox;
  };

  dtCompressedTileRef touched[DT_MAX_TOUCHED_TILES];
  dtCompressedTileRef pending[DT_MAX_TOUCHED_TILES];
  unsigned short salt;
  unsigned char type;
  unsigned char state;
  unsigned char ntouched;
  unsigned char npending;
  dtTileCacheObstacle* next;
};

所以OBB少去检查了titles造成了问题。如果我们将缓冲区加大之后就不会有问题。

为啥OBB需要碰撞这么多点？原因还是在于这些代码：

const dtObstacleOrientedBox &orientedBox = ob->orientedBox;

float maxr = 1.41f*dtMax(orientedBox.halfExtents[0], orientedBox.halfExtents[2]);
bmin[0] = orientedBox.center[0] - maxr;
bmax[0] = orientedBox.center[0] + maxr;
bmin[1] = orientedBox.center[1] - orientedBox.halfExtents[1];
bmax[1] = orientedBox.center[1] + orientedBox.halfExtents[1];
bmin[2] = orientedBox.center[2] - maxr;
bmax[2] = orientedBox.center[2] + maxr;

这段代码的意思是，OBB的X,Z的最大值1.41，形成的一个正方形。所以会比相同的AABB的形状大很多。10m1.141见方的一个方块（130.1881平方米），而AABB是 10m*2m（20平方米），大了6.5倍。我这里先使用矩阵把矩形框旋转，投影到X,Z轴上。让bounding更小，只要不突破8个上限，就能正常工作。

Abel'Blog