Recast-SoloMesh

简介

Recast中有一个静态方式的导航文件格式。这种模式是使用在地图导航不变化的情况。也是最简单的方式。这篇文章将详细的分析其中的细节。

基础知识

在recast中存在cell概念，在水平地面上是使用的size作为边长的正方形来打格子，垂直方式是使用的cell height来打格子

水平方向上的格子计算邻居有两种方式：

按照垂直轴线的方式：

按对角线：

数据导出

右手坐标系

函数入口Sample_SoloMesh::handleBuild()。

// 检查输入的模型是否输入了
if (!m_geom || !m_geom->getMesh())

// 清理上一轮的数据结构。
cleanup();
  void Sample_SoloMesh::cleanup()
  {
    delete [] m_triareas;
    m_triareas = 0;
    rcFreeHeightField(m_solid);
    m_solid = 0;
    rcFreeCompactHeightfield(m_chf);
    m_chf = 0;
    rcFreeContourSet(m_cset);
    m_cset = 0;
    rcFreePolyMesh(m_pmesh);
    m_pmesh = 0;
    rcFreePolyMeshDetail(m_dmesh);
    m_dmesh = 0;
    dtFreeNavMesh(m_navMesh);
    m_navMesh = 0;
  }

// 读取几何体的信息
const float* bmin = m_geom->getNavMeshBoundsMin(); // 集合体最小坐标最大坐标
const float* bmax = m_geom->getNavMeshBoundsMax();
const float* verts = m_geom->getMesh()->getVerts(); // 读取几何体的顶点信息
const int nverts = m_geom->getMesh()->getVertCount();
const int* tris = m_geom->getMesh()->getTris(); // 读取三角形面片信息
const int ntris = m_geom->getMesh()->getTriCount();

// 第一步骤： 从GUI界面中读取全部配置信息
// Init build configuration from GUI
memset(&m_cfg, 0, sizeof(m_cfg));
m_cfg.cs = m_cellSize;// cell的方格size
m_cfg.ch = m_cellHeight;// cell的高
m_cfg.walkableSlopeAngle = m_agentMaxSlope; // 45°斜坡
m_cfg.walkableHeight = (int)ceilf(m_agentHeight / m_cfg.ch);
m_cfg.walkableClimb = (int)floorf(m_agentMaxClimb / m_cfg.ch);
m_cfg.walkableRadius = (int)ceilf(m_agentRadius / m_cfg.cs);
m_cfg.maxEdgeLen = (int)(m_edgeMaxLen / m_cellSize);
m_cfg.maxSimplificationError = m_edgeMaxError;
m_cfg.minRegionArea = (int)rcSqr(m_regionMinSize);	// Note: area = size*size
m_cfg.mergeRegionArea = (int)rcSqr(m_regionMergeSize);	// Note: area = size*size
m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
m_cfg.detailSampleDist = m_detailSampleDist < 0.9f ? 0 : m_cellSize * m_detailSampleDist;
m_cfg.detailSampleMaxError = m_cellHeight * m_detailSampleMaxError;

// 设置区域的大小。按照cell的大小，将格子数目计算出来。
rcVcopy(m_cfg.bmin, bmin);
rcVcopy(m_cfg.bmax, bmax);
rcCalcGridSize(m_cfg.bmin, m_cfg.bmax, m_cfg.cs, &m_cfg.width, &m_cfg.height);
  void rcCalcGridSize(const float* bmin, const float* bmax, float cs, int* w, int* h)
  {
    *w = (int)((bmax[0] - bmin[0])/cs+0.5f);
    *h = (int)((bmax[2] - bmin[2])/cs+0.5f); // 高程使用[2]的槽位
  }

// 第二阶段： 光栅化
// 分配素体
m_solid = rcAllocHeightfield();
  // 高域对象
  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.
  };
// 体素对象的初始化
if (!rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch))
  bool rcCreateHeightfield(rcContext* ctx, rcHeightfield& hf, int width, int height,
              const float* bmin, const float* bmax,
              float cs, float ch)
  {
    rcIgnoreUnused(ctx);

    hf.width = width;
    hf.height = height;
    rcVcopy(hf.bmin, bmin);
    rcVcopy(hf.bmax, bmax);
    hf.cs = cs;
    hf.ch = ch;
    hf.spans = (rcSpan**)rcAlloc(sizeof(rcSpan*)*hf.width*hf.height, RC_ALLOC_PERM); // 按照cell的格子数，按照宽高创建spans，每个span就是一个平面
    if (!hf.spans)
      return false;
    memset(hf.spans, 0, sizeof(rcSpan*)*hf.width*hf.height);
    return true;
  }
    // 表示一个高域数据结构
    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.
    };

// 对于全部三角形标记是否翘起的太高
m_triareas = new unsigned char[ntris];
memset(m_triareas, 0, ntris*sizeof(unsigned char));
rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, verts, nverts, tris, ntris, m_triareas);
  // 标记可行走的三角形
  void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle,
                const float* verts, int nv,
                const int* tris, int nt,
                unsigned char* areas)
  {
    rcIgnoreUnused(ctx);
    rcIgnoreUnused(nv);

    const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);// 最大能行走的角度，算出cos值，和三角形面片比较，翘的太高就不允许走

    float norm[3]; // 算出三角形的法线向量，归一化，cos用于控制夹角，这个角度其实就是法线向量和y轴向量的夹角的cos值，如果归于±Θ就说明能爬上去。

    for (int i = 0; i < nt; ++i)
    {
      const int* tri = &tris[i*3];
      calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);// 从顶点中读取三角形的三个点，传入，计算出归一化的向量
        static void calcTriNormal(const float* v0, const float* v1, const float* v2, float* norm)
        {
          float e0[3], e1[3];
          rcVsub(e0, v1, v0); // v1->v0
          rcVsub(e1, v2, v0); // v2->v0
          rcVcross(norm, e0, e1); // 叉乘，获取三角形法线指向上
          rcVnormalize(norm);// 归一化
        }
      // 归一化的向量的y就是cosf，cos:夹角在-90°~＋90°之间，角度绝对值越小，数值越大。
      if (norm[1] > walkableThr)
        areas[i] = RC_WALKABLE_AREA;
    }
  }
// 将每个三角形是否可以翘的太高以至于不能行走的队列（m_triareas）传入，开始光栅化三角形。
if (!rcRasterizeTriangles(m_ctx, verts, nverts, tris, m_triareas, ntris, *m_solid, m_cfg.walkableClimb))
  bool rcRasterizeTriangles(rcContext* ctx, const float* verts, const int /*nv*/,
                const int* tris, const unsigned char* areas, const int nt,
                rcHeightfield& solid, const int flagMergeThr)
  {
    rcAssert(ctx);

    rcScopedTimer timer(ctx, RC_TIMER_RASTERIZE_TRIANGLES);

    const float ics = 1.0f/solid.cs; // 用于做将坐标转化到格子中 x,z方向，地面水平方块缩放比例，用于将x,z方向的格子换算成真实坐标
    const float ich = 1.0f/solid.ch; // y方向 垂直方向
    // 光栅化三角形，将会遍历全部的三角形
    for (int i = 0; i < nt; ++i)
    {
      const float* v0 = &verts[tris[i*3+0]*3]; // 读取obj中三角形的顶点信息
      const float* v1 = &verts[tris[i*3+1]*3];
      const float* v2 = &verts[tris[i*3+2]*3];
      // 栅格化一个三角形
      if (!rasterizeTri(v0, v1, v2, areas[i], solid, solid.bmin, solid.bmax, solid.cs, ics, ich, flagMergeThr))
      {
        ctx->log(RC_LOG_ERROR, "rcRasterizeTriangles: Out of memory.");
        return false;
      }
        // 输入三角形三个点 
        // v0,v1,v2 三角形3个点
        // area 标记是否可行走， RC_WALKABLE_AREA
        // hf 输出高域
        // bmin 形状的最小位置
        // bmax 形状的最大位置
        // cs 水平方向上尺寸
        // ics 水平方向上缩放
        // ich 垂直方向上缩放
        // flagMergeThr ?
        static bool rasterizeTri(const float* v0, const float* v1, const float* v2,
                    const unsigned char area, rcHeightfield& hf,
                    const float* bmin, const float* bmax,
                    const float cs, const float ics, const float ich,
                    const int flagMergeThr)
        {
          const int w = hf.width; // 高域-宽、高 按照格子为单位
          const int h = hf.height;
          float tmin[3], tmax[3];
          const float by = bmax[1] - bmin[1]; // y轴的区域

          // 计算三角形的包围盒的最小点，最大点
          rcVcopy(tmin, v0);
          rcVcopy(tmax, v0);
          rcVmin(tmin, v1);
          rcVmin(tmin, v2);
          rcVmax(tmax, v1);
          rcVmax(tmax, v2);

          // 如果三角形超出了区域将直接返回
          if (!overlapBounds(bmin, bmax, tmin, tmax))
            return true;

          // 计算三角形在y轴上的触碰到的区间。
          int y0 = (int)((tmin[2] - bmin[2])*ics);// 虽然计算的是y轴，但是使用了cs，这也就意味着里面全部都是使用的正方体来计算
          int y1 = (int)((tmax[2] - bmin[2])*ics);
          y0 = rcClamp(y0, 0, h-1); // 让三角形不会冲破范围
          y1 = rcClamp(y1, 0, h-1);
            // 参数v将会强行矫正在mn-mx之间。
            template<class T> inline T rcClamp(T v, T mn, T mx) { return v < mn ? mn : (v > mx ? mx : v); }

          // 将三角形剪切到它接触到的单元格中
          float buf[7*3*4]; // 7*3*4 为单位， 分配4份
          // in 三角形的点 inrow 在行里面 p1 参数1 p2 参数2，参数后续在多边形切割的时候使用。
          // 每组7份内存保存
          float *in = buf, *inrow = buf+7*3, *p1 = inrow+7*3, *p2 = p1+7*3;

          rcVcopy(&in[0], v0); // 原始三角形的三个点填充进去。
          rcVcopy(&in[1*3], v1);
          rcVcopy(&in[2*3], v2);
          int nvrow, nvIn = 3;

          for (int y = y0; y <= y1; ++y) // 遍历三角型的垂直方向，从下往上开始检查
          {
            // 剪切多边形到列里面。剩余剩余的多边形。
            const float cz = bmin[2] + y*cs; // 全部使用cs，这里说明使用的都是cs*cs*cs见方的立方体当成盒子拼凑。
            dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2);
              // 通过一根线将一个凸多边形分割成两个凸多边形
              static void dividePoly(const float* in, int nin,
                          float* out1, int* nout1,
                          float* out2, int* nout2,
                          float x, int axis)
              {
                float d[12];
                for (int i = 0; i < nin; ++i) // nin 3 axis: 2，表示y轴。 x：表示当前y轴立方体的上限
                  d[i] = x - in[i*3+axis]; // 计算三角形三个点和当前立方体y轴方向上的差值。

                int m = 0, n = 0;// out1用m控制偏移 out2用n控制偏移
                for (int i = 0, j = nin-1; i < nin; j=i, ++i) // 遍历三角形三个点的垂直方向离顶的大小， i=0,1,2 j =2,0,1。其实就是彼此比较3个点
                {
                  bool ina = d[j] >= 0; // ｊ/i点如果>=0说明点在正方块的下方
                  bool inb = d[i] >= 0;
                  if (ina != inb) // 说明三角形两个点在正方体上限的两侧
                  {
                    float s = d[j] / (d[j] - d[i]); // d[j] d[i] 符号相反，所以做减法之后绝对值是做了加法，分子分母符号相同，所以计算出来的数值一定是 >0 <1。
                    out1[m*3+0] = in[j*3+0] + (in[i*3+0] - in[j*3+0])*s; // j指向i的差值＊缩放+j本身的位置
                    out1[m*3+1] = in[j*3+1] + (in[i*3+1] - in[j*3+1])*s;
                    out1[m*3+2] = in[j*3+2] + (in[i*3+2] - in[j*3+2])*s;
                    rcVcopy(out2 + n*3, out1 + m*3); // 复制到out2中
                    m++;
                    n++;
                    // add the i'th point to the right polygon. Do NOT add points that are on the dividing line
                    // since these were already added above
                    // 将i点加入右侧的多边形。不要将点增加到分割线切割的点因为上层多边形会包含它。
                    if (d[i] > 0)
                    {
                      rcVcopy(out1 + m*3, in + i*3); // 将i点复制到 out1 中；
                      m++;
                    }
                    else if (d[i] < 0)
                    {
                      rcVcopy(out2 + n*3, in + i*3); // 将i点复制到 out2 中；
                      n++;
                    }
                  }
                  else // 三角形取的i,j两点在同一侧
                  {
                    // add the i'th point to the right polygon. Addition is done even for points on the dividing line
                    if (d[i] >= 0) // 表示i,j都在正方形的右侧，
                    {
                      rcVcopy(out1 + m*3, in + i*3);
                      m++;
                      if (d[i] != 0)　// 触到了边沿
                        continue;
                    }
                    rcVcopy(out2 + n*3, in + i*3); // 存储第二个存储列表中
                    n++;
                  }
                }

                *nout1 = m;
                *nout2 = n;
              } // dividePoly 分割凸多边形
            rcSwap(in, p1); // 交换两个向量
            if (nvrow < 3) continue; // 如果拆分不打到3个，将不处理

            // find the horizontal bounds in the row
            // 获取水平方向上的边界
            float minX = inrow[0], maxX = inrow[0];
            for (int i=1; i<nvrow; ++i)
            {
              if (minX > inrow[i*3])	minX = inrow[i*3];
              if (maxX < inrow[i*3])	maxX = inrow[i*3];
            }
            int x0 = (int)((minX - bmin[0])*ics); // 将坐标从格子转换到坐标系位置
            int x1 = (int)((maxX - bmin[0])*ics);
            x0 = rcClamp(x0, 0, w-1);
            x1 = rcClamp(x1, 0, w-1);

            int nv, nv2 = nvrow;

            for (int x = x0; x <= x1; ++x)
            {
              // Clip polygon to column. store the remaining polygon as well
              const float cx = bmin[0] + x*cs; // 从格子转换到坐标系中位置
              dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0);
              rcSwap(inrow, p2);
              if (nv < 3) continue;

              // Calculate min and max of the span.
              float smin = p1[1], smax = p1[1];
              for (int i = 1; i < nv; ++i)
              {
                smin = rcMin(smin, p1[i*3+1]);
                smax = rcMax(smax, p1[i*3+1]);
              }
              smin -= bmin[1];
              smax -= bmin[1];
              // Skip the span if it is outside the heightfield bbox
              if (smax < 0.0f) continue;
              if (smin > by) continue;
              // Clamp the span to the heightfield bbox.
              if (smin < 0.0f) smin = 0;
              if (smax > by) smax = by;

              // Snap the span to the heightfield height grid.
              unsigned short ismin = (unsigned short)rcClamp((int)floorf(smin * ich), 0, RC_SPAN_MAX_HEIGHT);
              unsigned short ismax = (unsigned short)rcClamp((int)ceilf(smax * ich), (int)ismin+1, RC_SPAN_MAX_HEIGHT);

              if (!addSpan(hf, x, y, ismin, ismax, area, flagMergeThr))
                return false;
            }
          }

          return true;
        }
    }

    return true;
  }

寻路逻辑

附录

几何体数据结构

几何体加载分为两种： .gset、.obj

obj表示方式

顶点信息：3个float类型的点；

三角形：三个int类型，读取三角形三个点在数组中下标；

bool InputGeom::loadMesh(rcContext* ctx, const std::string& filepath)
rcMeshLoaderObj();

// 加载顶点信息
if (row[0] == 'v' && row[1] != 'n' && row[1] != 't') // 顶点数据：v 16.000000 3.000000 18.287647
{
  // Vertex pos
  sscanf(row+1, "%f %f %f", &x, &y, &z);
  addVertex(x, y, z, vcap);
}
// 加载面信息
if (row[0] == 'f') // 面数据结构： f 102 101 100
{
  // Faces
  nv = parseFace(row+1, face, 32, m_vertCount);
  for (int i = 2; i < nv; ++i)
  {
    const int a = face[0];
    const int b = face[i-1];
    const int c = face[i];
    if (a < 0 || a >= m_vertCount || b < 0 || b >= m_vertCount || c < 0 || c >= m_vertCount)
      continue;
    addTriangle(a, b, c, tcap);// 标记了顶点的下标，通过下标就能读取vertex坐标，3个点的坐标都能被确定下来。
  }
}