简介

recast navigation是基于三角形网格的寻路系统，他相比四边形网格可以减少网格数量从而提高网格速度。它具体可以分为两部分，recast和detour。recast是构建寻路网格的过程，detour是利用网格寻路的过程

recast

过程划分参考

具体构建过程是根据Sample_SoloMesh.cpp中的handleBuild

体素化

在体素化阶段，mesh将被转化成体素（一个个小的长方体）。

体素化的目的是填充heightfield的span区域，span是一个二维数组，长和宽是包围盒内体素的长和宽。而每一个span是rcSpan*类型，他是一个链表，链接竖直方向的体素

构建过程：

  1. rcAllocHeightfield：new一个rcHeightfield实例

  2. rcCreateHeightfield： 初始化rcHeightfield

  3. rcMarkWalkableTriangles： 根据传进来的mesh（顶点和三角形）计算出哪个三角形可以通过。具体方法为计算每个三角形的法线，如果法线角超过设定值则认为不可通过

  4. rcRasterizeTriangles(rcContext ctx, const float verts, const int nv, const unsigned short tris, const unsigned char areas, const int nt, rcHeightfield& solid, const int flagMergeThr): 体素化三角形。其中areas就是上一步计算出来的可通过区域。

    // 其中最重要的一个函数为rasterizeTri，用来体素化每一个三角形
    // v0 v1 v2是三角形三个顶点
    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];
    	
    	// Calculate the bounding box of the triangle.
    	rcVcopy(tmin, v0);
    	rcVcopy(tmax, v0);
    	rcVmin(tmin, v1);
    	rcVmin(tmin, v2);
    	rcVmax(tmax, v1);
    	rcVmax(tmax, v2);
    	
    	// If the triangle does not touch the bbox of the heightfield, skip the triagle.
    	if (!overlapBounds(bmin, bmax, tmin, tmax))
    		return true;
    	
    	// Calculate the footprint of the triangle on the grid's y-axis
    	int y0 = (int)((tmin[2] - bmin[2])*ics); // y1-y0表示y坐标上占据了多少个体素
    	int y1 = (int)((tmax[2] - bmin[2])*ics);
    	// use -1 rather than 0 to cut the polygon properly at the start of the tile
    	y0 = rcClamp(y0, -1, h-1);
    	y1 = rcClamp(y1, 0, h-1);
    	
    	// Clip the triangle into all grid cells it touches.
    	float buf[7*3*4];
    	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)
    	{
    		// Clip polygon to row. Store the remaining polygon as well
    		const float cz = bmin[2] + y*cs;
            // 将三角形裁减到z=[cz, cz+cs]平面之间。
    		dividePoly(in, nvIn, inrow, &nvrow, p1, &nvIn, cz+cs, 2);
    		...

    		for (int x = x0; x <= x1; ++x)
    		{
    			// Clip polygon to column. store the remaining polygon as well
    			const float cx = bmin[0] + x*cs;
                // 将三角形裁减到x=[cx, cx+cs]平面之间。
    			dividePoly(inrow, nv2, p1, &nv, p2, &nv2, cx+cs, 0);
    			...
                    
    			// 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;
                
    			//此时，in中存贮的为裁减后的多边形。
                //计算新多边形y轴的最大和最小值
    			// 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);
    			
             // addSpan中还有合并操作，是因为之前的三角形可能已经占据了这个span，但是由于它包括的[ismin, ismax]和当前加入的[ismin, ismax]有重合，则两个区间相与
    			if (!addSpan(hf, x, y, ismin, ismax, area, flagMergeThr))
    				return false;
    		}
    	}

    	return true;
    }

生成区域

生成区域是将一个个的体素划分成若干区域，这些区域最终可以化为简单的多边形。

步骤：

  1. rcFilterLowHangingWalkableObstacles：处理之前不可行走的区域，因为有些区域是可以翻越过去的，因此当两个体素的高度差小于climbHeight并且前面一个区域可以行走时认为后面一个区域也可以行走
  2. rcFilterLedgeSpans：这个是将高度差过大的两个区域认定为不可行走（如悬崖）
  3. rcFilterWalkableLowHeightSpans：将高于某个高度的span认定为不可行走
  4. rcBuildCompactHeightfield： 构建开放高度场, 其中heightfield中的span转变成了compatHeightField中的cell和span。cell是一个二维数组，每一项有index和count两个变量，index表示该位置的体素在span中的起始位置，count表示该位置的体素数量(y坐标体素数量)
  5. rcErodeWalkableArea：过于接近障碍物的span被认定为不可行走
  6. 进行划分，划分有三种方法：
    1. 分水岭算法(Watershed partitioning)： 传统的划分方法，通常最慢但是划分出来的区域最好
    2. Monotone partioning: 划分速度最快，但是效果可能不好
    3. Layer partitoining：速度居于两者中间，并且比较依赖初始数据

生成轮廓

上面的区域是体素的集合，这一步就是将体素转化成多边形。

步骤:

  1. rcBuildContours: 构建轮廓类
  2. rcBuildPolyMesh：构建多边形类