Quick'n'Dirty Recast/Detour Pathfinding.

[mkultra333]

Just got basic Recast/Detour pathfinding working in my project. Someone else asked about pathfinding and the perception is that Recast/Detour is too difficult. Fair comment, since the demo is fairly complex and there's almost no documentation.

So I thought I'd post my code. It's simple, and a lot of it is just taken from the demo. I can't say it's bug free or the best usage of Recast/Detour, but it should be handy as a starting point.

First up, some helper stuff. Here's a shader for debugging, used to draw the navigation mesh and lines.

0_recastdebug.material

Code: Select all

//////////////////////////////////////////////////////////////////////////////

vertex_program recastwalk_vs cg         
{
   source 0_recastdebug.cg
   entry_point recastwalk_vs
   profiles arbvp1 vs_2_x

		default_params
    {
        param_named_auto wvp worldviewproj_matrix
		}
}

fragment_program recastwalk_ps cg         
{
   source 0_recastdebug.cg
   entry_point recastwalk_ps
   profiles ps_2_x fp40 arbfp1 fp30
}


material recastwalk
{
	technique
	{

	    pass
	    {
            	ambient  0 0 0
            	diffuse  0 0 0
            	specular 0 0 0 0
            	emissive 0 0 0

            	vertex_program_ref recastwalk_vs
            	{
            	}

            	fragment_program_ref recastwalk_ps
            	{
            	}
	    }

	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

vertex_program recastline_vs cg         
{
   source 0_recastdebug.cg
   entry_point recastline_vs
   profiles arbvp1 vs_2_x

		default_params
    {
        param_named_auto wvp worldviewproj_matrix
		}
}

fragment_program recastline_ps cg         
{
   source 0_recastdebug.cg
   entry_point recastline_ps
   profiles ps_2_x fp40 arbfp1 fp30
}


material recastline
{
	technique
	{

	    pass
	    {
            	ambient  0 0 0
            	diffuse  0 0 0
            	specular 0 0 0 0
            	emissive 0 0 0

							depth_bias 16

            	vertex_program_ref recastline_vs
            	{
            	}

            	fragment_program_ref recastline_ps
            	{
            	}
	    }
	}
}

0_recastdebug.cg

Code: Select all

//////////////////////////////////////////////////////////////////////////////

void recastwalk_vs(
    float4 InPos : POSITION,
		float3 InCol : COLOR,

		out float4 OutPos : POSITION,
		out float3 OutCol : COLOR, 

    uniform float4x4 wvp
    ) 
{
		OutCol = InCol ;
    OutPos = mul(wvp, InPos);
}


void recastwalk_ps(
	float4 InPos : POSITION,
	float3 InCol : COLOR,
	out float4 Colour : COLOR
) 
{
    Colour = float4(InCol*0.9, 1);
}


//////////////////////////////////////////////////////////////////////////////

void recastline_vs(
    float4 InPos : POSITION,
		float3 InCol : COLOR,

		out float4 OutPos : POSITION,
		out float3 OutCol : COLOR, 

    uniform float4x4 wvp
    ) 
{
		OutCol = InCol ;
    OutPos = mul(wvp, InPos);
}


void recastline_ps(
	float4 InPos : POSITION,
	float3 InCol : COLOR,
	out float4 Colour : COLOR
) 
{
    Colour = float4(InCol*0.9, 1);
}

Add the following files to the project from Detour/Recast.

DetourAlloc.h
DetourAssert.h
DetourCommon.h
DetourNavMesh.h
DetourNavMeshBuilder.h
DetourNavMeshQuery.h
DetourNode.h
DetourObstacleAvoidance.h
Recast.h
RecastAlloc.h
RecastAssert.h

DetourAlloc.cpp
DetourCommon.cpp
DetourNavMesh.cpp
DetourNavMeshBuilder.cpp
DetourNavMeshQuery.cpp
DetourNode.cpp
DetourObstacleAvoidance.cpp
Recast.cpp
RecastAlloc.cpp
RecastArea.cpp
RecastContour.cpp
RecastFilter.cpp
RecastMesh.cpp
RecastMeshDetail.cpp
RecastRasterization.cpp
RecastRegion.cpp

Add the following to your project's main header file.

Code: Select all

// recast/detour stuff
#include "RecastDetour/Recast.h"
#include "RecastDetour/DetourNavMesh.h"
#include "RecastDetour/DetourNavMeshBuilder.h"
#include "RecastDetour/DetourNavMeshQuery.h"

#define MAX_PATHSLOT		128 // how many paths we can store
#define MAX_PATHPOLY		256 // max number of polygons in a path
#define MAX_PATHVERT		512 // most verts in a path 

// structure for storing output straight line paths
typedef struct
{
	float PosX[MAX_PATHVERT] ;
	float PosY[MAX_PATHVERT] ;
	float PosZ[MAX_PATHVERT] ;
	int MaxVertex ;
	int Target ;
}
PATHDATA ;

// These are just sample areas to use consistent values across the samples.
// The use should specify these base on his needs.

// bzn most aren't used yet, just SAMPLE_POLYAREA_GROUND and SAMPLE_POLYFLAGS_WALK
enum SamplePolyAreas
{
	SAMPLE_POLYAREA_GROUND,
	SAMPLE_POLYAREA_WATER,
	SAMPLE_POLYAREA_ROAD,
	SAMPLE_POLYAREA_DOOR,
	SAMPLE_POLYAREA_GRASS,
	SAMPLE_POLYAREA_JUMP,
};
enum SamplePolyFlags
{
	SAMPLE_POLYFLAGS_WALK = 0x01,		// Ability to walk (ground, grass, road)
	SAMPLE_POLYFLAGS_SWIM = 0x02,		// Ability to swim (water).
	SAMPLE_POLYFLAGS_DOOR = 0x04,		// Ability to move through doors.
	SAMPLE_POLYFLAGS_JUMP = 0x08,		// Ability to jump.
	SAMPLE_POLYFLAGS_ALL = 0xffff		// All abilities.
};

This demo only uses SAMPLE_POLYAREA_GROUND and SAMPLE_POLYFLAGS_WALK.

Add this inside the header, it sets up some global variables and functions we'll be using.

Code: Select all

// Detour/Recast stuff

	unsigned char* m_triareas;
	rcHeightfield* m_solid;
	rcCompactHeightfield* m_chf;
	rcContourSet* m_cset;
	rcPolyMesh* m_pmesh;
	rcConfig m_cfg;	
	rcPolyMeshDetail* m_dmesh;

	class InputGeom* m_geom;
	class dtNavMesh* m_navMesh;
	class dtNavMeshQuery* m_navQuery;
	unsigned char m_navMeshDrawFlags;

	rcContext* m_ctx;

	float m_cellSize;
	float m_cellHeight;
	float m_agentHeight;
	float m_agentRadius;
	float m_agentMaxClimb;
	float m_agentMaxSlope;
	float m_regionMinSize;
	float m_regionMergeSize;
	float m_edgeMaxLen;
	float m_edgeMaxError;
	float m_vertsPerPoly;
	float m_detailSampleDist;
	float m_detailSampleMaxError;
	bool m_keepInterResults ;

	// Off-Mesh connections.  Not used yet.
	static const int MAX_OFFMESH_CONNECTIONS = 256;
	float m_offMeshConVerts[MAX_OFFMESH_CONNECTIONS*3*2];
	float m_offMeshConRads[MAX_OFFMESH_CONNECTIONS];
	unsigned char m_offMeshConDirs[MAX_OFFMESH_CONNECTIONS];
	unsigned char m_offMeshConAreas[MAX_OFFMESH_CONNECTIONS];
	unsigned short m_offMeshConFlags[MAX_OFFMESH_CONNECTIONS];
	unsigned int m_offMeshConId[MAX_OFFMESH_CONNECTIONS];
	int m_offMeshConCount;

	void RecastCleanup() ;
	bool NavMeshBuild() ;
	int FindPath(float* pStartPos, float* pEndPos, int nPathSlot, int nTarget) ;
	
	// helper debug drawing stuff
	int m_nAreaCount ;
	Ogre::ManualObject* m_pRecastMOWalk ;
	Ogre::ManualObject* m_pRecastMONeighbour ;
	Ogre::ManualObject* m_pRecastMOBoundary ;
	Ogre::ManualObject* m_pRecastMOPath ;
	Ogre::SceneNode*		m_pRecastSN ;
	void CreateRecastPolyMesh(const struct rcPolyMesh& mesh) ;
	void CreateRecastPathLine(int nPathSlot) ;
	
	float m_flTestStart[3] ;
	float m_flTestEnd[3] ;

	PATHDATA m_PathStore[MAX_PATHSLOT] ; 

Created paths will be stored in m_PathStore. I've made it so that up to 128 paths can be stored.

Here's the debug drawing functions, they convert the navmesh and paths to manual objects. To see them, add the m_pRecastSN scenenode to the root node.

Code: Select all

void OgreFramework::CreateRecastPolyMesh(const struct rcPolyMesh& mesh)
{

	const int nvp = mesh.nvp; 
	const float cs = mesh.cs;
	const float ch = mesh.ch;
	const float* orig = mesh.bmin;

	m_flDataX=mesh.npolys ;
	m_flDataY=mesh.nverts ;
	
	// create scenenodes
	m_pRecastSN=m_pSceneMgr->getRootSceneNode()->createChildSceneNode("RecastSN") ;

	int nIndex=0 ;
	m_nAreaCount=mesh.npolys ;



	if(m_nAreaCount)
	{

		// start defining the manualObject
		m_pRecastMOWalk = m_pSceneMgr->createManualObject("RecastMOWalk");
		m_pRecastMOWalk->begin("recastwalk", RenderOperation::OT_TRIANGLE_LIST) ;
		for (int i = 0; i < mesh.npolys; ++i) // go through all polygons
			if (mesh.areas[i] == SAMPLE_POLYAREA_GROUND)
			{
				const unsigned short* p = &mesh.polys[i*nvp*2];

				unsigned short vi[3];
				for (int j = 2; j < nvp; ++j) // go through all verts in the polygon
				{
					if (p[j] == RC_MESH_NULL_IDX) break;
					vi[0] = p[0];
					vi[1] = p[j-1];
					vi[2] = p[j];
					for (int k = 0; k < 3; ++k) // create a 3-vert triangle for each 3 verts in the polygon.
					{
						const unsigned short* v = &mesh.verts[vi[k]*3];
						const float x = orig[0] + v[0]*cs;
						const float y = orig[1] + (v[1]+1)*ch;
						const float z = orig[2] + v[2]*cs;

						m_pRecastMOWalk->position(x, y, z) ;
						if (mesh.areas[i] == SAMPLE_POLYAREA_GROUND)
							m_pRecastMOWalk->colour(0,0.7,0) ;
						else
							m_pRecastMOWalk->colour(0,0.175,0) ;

					}
					m_pRecastMOWalk->triangle(nIndex, nIndex+1, nIndex+2) ;
					nIndex+=3 ;
				}
			}
		m_pRecastMOWalk->end() ;
		m_pRecastSN->attachObject(m_pRecastMOWalk) ;



		
		m_pRecastMONeighbour = m_pSceneMgr->createManualObject("RecastMONeighbour");
		m_pRecastMONeighbour->begin("recastline", RenderOperation::OT_LINE_LIST) ;

		for (int i = 0; i < mesh.npolys; ++i)
		{
			const unsigned short* p = &mesh.polys[i*nvp*2];
			for (int j = 0; j < nvp; ++j)
			{
				if (p[j] == RC_MESH_NULL_IDX) break;
				if (p[nvp+j] == RC_MESH_NULL_IDX) continue;
				int vi[2];
				vi[0] = p[j];
				if (j+1 >= nvp || p[j+1] == RC_MESH_NULL_IDX)
					vi[1] = p[0];
				else
					vi[1] = p[j+1];
				for (int k = 0; k < 2; ++k)
				{
					const unsigned short* v = &mesh.verts[vi[k]*3];
					const float x = orig[0] + v[0]*cs;
					const float y = orig[1] + (v[1]+1)*ch + 0.1f;
					const float z = orig[2] + v[2]*cs;
					//dd->vertex(x, y, z, coln);
					m_pRecastMONeighbour->position(x, y+0.25, z) ;
					m_pRecastMONeighbour->colour(0,1,1) ;

				}
			}
		}

		m_pRecastMONeighbour->end() ;
		m_pRecastSN->attachObject(m_pRecastMONeighbour) ;
		

		m_pRecastMOBoundary = m_pSceneMgr->createManualObject("RecastMOBoundary");
		m_pRecastMOBoundary->begin("recastline", RenderOperation::OT_LINE_LIST) ;

		for (int i = 0; i < mesh.npolys; ++i)
		{
			const unsigned short* p = &mesh.polys[i*nvp*2];
			for (int j = 0; j < nvp; ++j)
			{
				if (p[j] == RC_MESH_NULL_IDX) break;
				if (p[nvp+j] != RC_MESH_NULL_IDX) continue;
				int vi[2];
				vi[0] = p[j];
				if (j+1 >= nvp || p[j+1] == RC_MESH_NULL_IDX)
					vi[1] = p[0];
				else
					vi[1] = p[j+1];
				for (int k = 0; k < 2; ++k)
				{
					const unsigned short* v = &mesh.verts[vi[k]*3];
					const float x = orig[0] + v[0]*cs;
					const float y = orig[1] + (v[1]+1)*ch + 0.1f;
					const float z = orig[2] + v[2]*cs;
					//dd->vertex(x, y, z, colb);

					m_pRecastMOBoundary->position(x, y+0.25, z) ;
					m_pRecastMOBoundary->colour(0,1,0) ;
				}
			}
		}

		m_pRecastMOBoundary->end() ;
		m_pRecastSN->attachObject(m_pRecastMOBoundary) ;




	}// end areacount


}

void OgreFramework::CreateRecastPathLine(int nPathSlot)
{
	if(m_pRecastMOPath)
	{
		m_pRecastSN->detachObject("RecastMOPath") ;
		m_pSceneMgr->destroyManualObject(m_pRecastMOPath) ;
		m_pRecastMOPath=NULL ;
	}


	m_pRecastMOPath = m_pSceneMgr->createManualObject("RecastMOPath");
	m_pRecastMOPath->begin("recastline", RenderOperation::OT_LINE_STRIP) ;

	
	int nVertCount=m_PathStore[nPathSlot].MaxVertex ;
	for(int nVert=0 ; nVert<nVertCount ; nVert++)
	{
		m_pRecastMOPath->position(m_PathStore[nPathSlot].PosX[nVert], m_PathStore[nPathSlot].PosY[nVert]+8.0f, m_PathStore[nPathSlot].PosZ[nVert]) ;
		m_pRecastMOPath->colour(1,0,0) ;

		//sprintf(m_chBug, "Line Vert %i, %f %f %f", nVert, m_PathStore[nPathSlot].PosX[nVert], m_PathStore[nPathSlot].PosY[nVert], m_PathStore[nPathSlot].PosZ[nVert]) ;
		//m_pLog->logMessage(m_chBug);
	}
					



	m_pRecastMOPath->end() ;
	m_pRecastSN->attachObject(m_pRecastMOPath) ;




}

There's some cleanup code, call this when you want to destroy the recast stuff (not including my debug manual objects, you'll have to destory those yourself). The demo also calls the cleanup code before it first generates a mesh, so I added the following to the project initialization just to make sure it starts clean.

Initial cleanup done during project startup:

Code: Select all

	m_triareas=NULL;
	m_solid=NULL ;
	m_chf=NULL ;
	m_cset=NULL;
	m_pmesh=NULL;
	//m_cfg;	
	m_dmesh=NULL ;
	m_geom=NULL;
	m_navMesh=NULL;
	m_navQuery=NULL;
	//m_navMeshDrawFlags;
	m_ctx=NULL ;

	RecastCleanup() ; //?? don't know if I should do this prior to making any recast stuff, but the demo did.
	m_pRecastMOPath=NULL ;

Cleanup function:

Code: Select all

void OgreFramework::RecastCleanup()
{
	if(m_triareas) 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;

	dtFreeNavMeshQuery(m_navQuery);
	m_navQuery = 0 ;

	if(m_ctx) delete m_ctx ;
}

Now for the navmesh creation function. I've mostly taken this from the demo, apart from the top part where I create the triangles. Recast needs a bunch of input vertices and triangles from your map to build the navigation mesh. Where you get those verts amd triangles is up to you, my map loader was already outputing verts and triangle so it was easy to use those. Make sure the triangles wind the correct way or Recast will try to build the navmesh on the outside of your map.

Code: Select all

bool OgreFramework::NavMeshBuild()
{
	// convert our geometry into the recast format

	m_pLog->logMessage("NavMeshBuild Start");



	int nLoop=0 ;
	
	float*           rc_verts;
	unsigned int     rc_nverts;
	int*             rc_tris;
	float*           rc_trinorms;
	unsigned int     rc_ntris;
	float	           rc_bmin[3];
	float	           rc_bmax[3];

	Ogre::Vector3 VertA ;
	Ogre::Vector3 VertB ;
	Ogre::Vector3 VertC ;
	Ogre::Vector3 TriNorm ;
	int nVert=0 ;
	
	
	rc_bmin[0]=SPLAT_BANKDISTANCE ;
	rc_bmin[1]=SPLAT_BANKDISTANCE ;
	rc_bmin[2]=SPLAT_BANKDISTANCE ;
	rc_bmax[0]=-SPLAT_BANKDISTANCE ;
	rc_bmax[1]=-SPLAT_BANKDISTANCE ;
	rc_bmax[2]=-SPLAT_BANKDISTANCE ;


	// setup recast verts, and min/max
	rc_nverts=m_OgreBZNBSP->m_nVertexMax ;
	rc_verts= new float[rc_nverts*3] ;
	for(nLoop=0 ; nLoop<rc_nverts ; nLoop++)
	{
		rc_verts[nLoop*3+0] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[0] ;
		rc_verts[nLoop*3+1] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[1] ;
		rc_verts[nLoop*3+2] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[2] ;

		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[0]<rc_bmin[0]) rc_bmin[0]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[0] ;
		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[1]<rc_bmin[1]) rc_bmin[1]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[1] ;
		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[2]<rc_bmin[2]) rc_bmin[2]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[2] ;

		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[0]>rc_bmax[0]) rc_bmax[0]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[0] ;
		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[1]>rc_bmax[1]) rc_bmax[1]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[1] ;
		if(m_OgreBZNBSP->m_pVertex[nLoop].xyz[2]>rc_bmax[2]) rc_bmax[2]=m_OgreBZNBSP->m_pVertex[nLoop].xyz[2] ;

	}

	// work out how many triangles we need.  We don't use every triangle, for instance we don't use def light boxes.
	// we only used opaque, gel or alphat triangles.
	int nMaxTri=m_OgreBZNBSP->m_nTriangleMax ;
	int nTextureCategory=0 ;
	rc_ntris=0 ;
	for(nLoop=0 ; nLoop<nMaxTri; nLoop++)
	{
		nTextureCategory=m_OgreBZNBSP->m_pTextureCat[  m_OgreBZNBSP->m_pTriangle[nLoop].Texture  ] ;
		if((nTextureCategory>=TEXCAT_OPAQUE) && (nTextureCategory<=TEXCAT_ALPHAT2))
			rc_ntris++ ;
	}



	// setup recast triangles
	rc_tris= new int[rc_ntris*3] ;
	rc_trinorms = new float[rc_ntris*3] ;

	int nTriCount=0 ;
	for(nLoop=0 ; nLoop<nMaxTri ; nLoop++)
	{
		// not all triangles should be added, for instance we don't want deferred light boxes.
		// So check the texture category.  We only accept opaque, gel or alphat textures.
		nTextureCategory=m_OgreBZNBSP->m_pTextureCat[  m_OgreBZNBSP->m_pTriangle[nLoop].Texture  ] ;
		if((nTextureCategory<TEXCAT_OPAQUE) || (nTextureCategory>TEXCAT_ALPHAT2))
			continue ;


		// vertex indices
		rc_tris[nTriCount*3+0] = m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[0] ;
		rc_tris[nTriCount*3+1] = m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[2] ;
		rc_tris[nTriCount*3+2] = m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[1] ;


		// calculate normal for this triangle.  
		// Why doesn't it exist already?  Because we usually use normals on verts, not triangles.
		nVert=m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[0] ;
		VertA.x=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[0] ;
		VertA.y=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[1] ;
		VertA.z=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[2] ;

		nVert=m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[1] ;
		VertB.x=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[0] ;
		VertB.y=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[1] ;
		VertB.z=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[2] ;

		nVert=m_OgreBZNBSP->m_pTriangle[nLoop].VIndex[2] ;
		VertC.x=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[0] ;
		VertC.y=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[1] ;
		VertC.z=m_OgreBZNBSP->m_pVertex[  nVert  ].xyz[2] ;

		VertA-=VertC ;
		VertB-=VertC ;

		VertA=VertA.crossProduct(VertB) ;
		VertA.normalise() ;

		// recast version of the normal
		rc_trinorms[nTriCount*3+0] = VertA.x ;
		rc_trinorms[nTriCount*3+1] = VertA.y ;
		rc_trinorms[nTriCount*3+2] = VertA.z ;

		nTriCount++ ;

	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////



	//RecastCleanup() ;

	m_ctx=new rcContext(true) ;
	//
	// Step 1. Initialize build config.
	//

	// cellsize (1.5, 1.0) was the most accurate at finding all the places we could go, but was also slow to generate.
	// Might be suitable for pre-generated meshes. Though it also produces a lot more polygons.

	m_cellSize = 9.0 ;//0.3;
	m_cellHeight = 6.0 ;//0.2;
	m_agentMaxSlope = 45;
	m_agentHeight = 64.0;
	m_agentMaxClimb = 16;
	m_agentRadius = 16;
	m_edgeMaxLen = 512;
	m_edgeMaxError = 1.3;
	m_regionMinSize = 50;
	m_regionMergeSize = 20;
	m_vertsPerPoly = 6;
	m_detailSampleDist = 6;
	m_detailSampleMaxError = 1;
	m_keepInterResults = false;
	
	// Init build configuration from GUI
	memset(&m_cfg, 0, sizeof(m_cfg));
	m_cfg.cs = m_cellSize;
	m_cfg.ch = m_cellHeight;
	m_cfg.walkableSlopeAngle = m_agentMaxSlope;
	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;
	

	// Reset build times gathering.
	m_ctx->resetTimers();

	// Start the build process.	
	m_ctx->startTimer(RC_TIMER_TOTAL);

	// Set the area where the navigation will be build.
	// Here the bounds of the input mesh are used, but the
	// area could be specified by an user defined box, etc.
	rcVcopy(m_cfg.bmin, rc_bmin);
	rcVcopy(m_cfg.bmax, rc_bmax);
	rcCalcGridSize(m_cfg.bmin, m_cfg.bmax, m_cfg.cs, &m_cfg.width, &m_cfg.height);


	//
	// Step 2. Rasterize input polygon soup.
	//
	
	// Allocate voxel heightfield where we rasterize our input data to.

	m_solid = rcAllocHeightfield();
	if (!m_solid)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'solid'.");
		return false;
	}
	if (!rcCreateHeightfield(m_ctx, *m_solid, m_cfg.width, m_cfg.height, m_cfg.bmin, m_cfg.bmax, m_cfg.cs, m_cfg.ch))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not create solid heightfield.");
		return false;
	}
	
	// Allocate array that can hold triangle area types.
	// If you have multiple meshes you need to process, allocate
	// and array which can hold the max number of triangles you need to process.
	m_triareas = new unsigned char[rc_ntris];
	if (!m_triareas)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'm_triareas' (%d).", rc_ntris);
		return false;
	}
	
	// Find triangles which are walkable based on their slope and rasterize them.
	// If your input data is multiple meshes, you can transform them here, calculate
	// the are type for each of the meshes and rasterize them.
	memset(m_triareas, 0, rc_ntris*sizeof(unsigned char));
	rcMarkWalkableTriangles(m_ctx, m_cfg.walkableSlopeAngle, rc_verts, rc_nverts, rc_tris, rc_ntris, m_triareas);
	rcRasterizeTriangles(m_ctx, rc_verts, rc_nverts, rc_tris, m_triareas, rc_ntris, *m_solid, m_cfg.walkableClimb);

	if (!m_keepInterResults)
	{
		delete [] m_triareas;
		m_triareas = 0;
	}

	//
	// Step 3. Filter walkables surfaces.
	//
	
	// Once all geoemtry is rasterized, we do initial pass of filtering to
	// remove unwanted overhangs caused by the conservative rasterization
	// as well as filter spans where the character cannot possibly stand.
	rcFilterLowHangingWalkableObstacles(m_ctx, m_cfg.walkableClimb, *m_solid);
	rcFilterLedgeSpans(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid);
	rcFilterWalkableLowHeightSpans(m_ctx, m_cfg.walkableHeight, *m_solid);



	//
	// Step 4. Partition walkable surface to simple regions.
	//

	// Compact the heightfield so that it is faster to handle from now on.
	// This will result more cache coherent data as well as the neighbours
	// between walkable cells will be calculated.
	m_chf = rcAllocCompactHeightfield();
	if (!m_chf)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'chf'.");
		return false;
	}
	if (!rcBuildCompactHeightfield(m_ctx, m_cfg.walkableHeight, m_cfg.walkableClimb, *m_solid, *m_chf))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build compact data.");
		return false;
	}
	
	if (!m_keepInterResults)
	{
		rcFreeHeightField(m_solid);
		m_solid = 0;
	}
		
	// Erode the walkable area by agent radius.
	if (!rcErodeWalkableArea(m_ctx, m_cfg.walkableRadius, *m_chf))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not erode.");
		return false;
	}

	// (Optional) Mark areas.
	//const ConvexVolume* vols = m_geom->getConvexVolumes();
	//for (int i  = 0; i < m_geom->getConvexVolumeCount(); ++i)
	//	rcMarkConvexPolyArea(m_ctx, vols[i].verts, vols[i].nverts, vols[i].hmin, vols[i].hmax, (unsigned char)vols[i].area, *m_chf);
	
	// Prepare for region partitioning, by calculating distance field along the walkable surface.
	if (!rcBuildDistanceField(m_ctx, *m_chf))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build distance field.");
		return false;
	}

	// Partition the walkable surface into simple regions without holes.
	if (!rcBuildRegions(m_ctx, *m_chf, m_cfg.borderSize, m_cfg.minRegionArea, m_cfg.mergeRegionArea))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build regions.");
		return false;
	}

	//
	// Step 5. Trace and simplify region contours.
	//
	
	// Create contours.
	m_cset = rcAllocContourSet();
	if (!m_cset)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'cset'.");
		return false;
	}
	if (!rcBuildContours(m_ctx, *m_chf, m_cfg.maxSimplificationError, m_cfg.maxEdgeLen, *m_cset))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not create contours.");
		return false;
	}

	//
	// Step 6. Build polygons mesh from contours.
	//
	
	// Build polygon navmesh from the contours.
	m_pmesh = rcAllocPolyMesh();
	if (!m_pmesh)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'pmesh'.");
		return false;
	}
	if (!rcBuildPolyMesh(m_ctx, *m_cset, m_cfg.maxVertsPerPoly, *m_pmesh))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not triangulate contours.");
		return false;
	}
	
	//
	// Step 7. Create detail mesh which allows to access approximate height on each polygon.
	//
	
	m_dmesh = rcAllocPolyMeshDetail();
	if (!m_dmesh)
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Out of memory 'pmdtl'.");
		return false;
	}

	if (!rcBuildPolyMeshDetail(m_ctx, *m_pmesh, *m_chf, m_cfg.detailSampleDist, m_cfg.detailSampleMaxError, *m_dmesh))
	{
		m_ctx->log(RC_LOG_ERROR, "buildNavigation: Could not build detail mesh.");
		return false;
	}

	if (!m_keepInterResults)
	{
		rcFreeCompactHeightfield(m_chf);
		m_chf = 0;
		rcFreeContourSet(m_cset);
		m_cset = 0;
	}

	// At this point the navigation mesh data is ready, you can access it from m_pmesh.
	// See duDebugDrawPolyMesh or dtCreateNavMeshData as examples how to access the data.
	
	//
	// (Optional) Step 8. Create Detour data from Recast poly mesh.
	//
	
	// The GUI may allow more max points per polygon than Detour can handle.
	// Only build the detour navmesh if we do not exceed the limit.


	if (m_cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON)
	{
		m_pLog->logMessage("Detour 1000");

		unsigned char* navData = 0;
		int navDataSize = 0;

		
		// Update poly flags from areas.
		for (int i = 0; i < m_pmesh->npolys; ++i)
		{
			if (m_pmesh->areas[i] == RC_WALKABLE_AREA)
			{
				m_pmesh->areas[i] = SAMPLE_POLYAREA_GROUND;
				m_pmesh->flags[i] = SAMPLE_POLYFLAGS_WALK;
			}
		}
		

		dtNavMeshCreateParams params;
		memset(&params, 0, sizeof(params));
		params.verts = m_pmesh->verts;
		params.vertCount = m_pmesh->nverts;
		params.polys = m_pmesh->polys;
		params.polyAreas = m_pmesh->areas;
		params.polyFlags = m_pmesh->flags;
		params.polyCount = m_pmesh->npolys;
		params.nvp = m_pmesh->nvp;
		params.detailMeshes = m_dmesh->meshes;
		params.detailVerts = m_dmesh->verts;
		params.detailVertsCount = m_dmesh->nverts;
		params.detailTris = m_dmesh->tris;
		params.detailTriCount = m_dmesh->ntris;

		// no off mesh connections yet
		m_offMeshConCount=0 ;
		params.offMeshConVerts = m_offMeshConVerts ;
		params.offMeshConRad = m_offMeshConRads ;
		params.offMeshConDir = m_offMeshConDirs ;
		params.offMeshConAreas = m_offMeshConAreas ;
		params.offMeshConFlags = m_offMeshConFlags ;
		params.offMeshConUserID = m_offMeshConId ;
		params.offMeshConCount = m_offMeshConCount ;

		params.walkableHeight = m_agentHeight;
		params.walkableRadius = m_agentRadius;
		params.walkableClimb = m_agentMaxClimb;
		rcVcopy(params.bmin, m_pmesh->bmin);
		rcVcopy(params.bmax, m_pmesh->bmax);
		params.cs = m_cfg.cs;
		params.ch = m_cfg.ch;
		
		m_pLog->logMessage("Detour 2000");

		if (!dtCreateNavMeshData(&params, &navData, &navDataSize))
		{
			m_ctx->log(RC_LOG_ERROR, "Could not build Detour navmesh.");
			return false;
		}

		m_pLog->logMessage("Detour 3000");
		
		m_navMesh = dtAllocNavMesh();
		if (!m_navMesh)
		{
			dtFree(navData);
			m_ctx->log(RC_LOG_ERROR, "Could not create Detour navmesh");
			return false;
		}

		m_pLog->logMessage("Detour 4000");
		
		dtStatus status;
		
		status = m_navMesh->init(navData, navDataSize, DT_TILE_FREE_DATA);
		if (dtStatusFailed(status))
		{
			dtFree(navData);
			m_ctx->log(RC_LOG_ERROR, "Could not init Detour navmesh");
			return false;
		}

		m_pLog->logMessage("Detour 5000");
		
		m_navQuery = dtAllocNavMeshQuery();
		status = m_navQuery->init(m_navMesh, 2048);

		m_pLog->logMessage("Detour 5500");

		if (dtStatusFailed(status))
		{
			m_ctx->log(RC_LOG_ERROR, "Could not init Detour navmesh query");
			return false;
		}

		m_pLog->logMessage("Detour 6000");
	}
	
	m_ctx->stopTimer(RC_TIMER_TOTAL);

	
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	// cleanup stuff we don't need
	delete [] rc_verts ;
	delete [] rc_tris ;
	delete [] rc_trinorms ;

	CreateRecastPolyMesh(*m_pmesh) ;

	m_pLog->logMessage("NavMeshBuild End");
	return true ;
}

There's some potentially groovy stuff in there that I haven't touched, like filtering and different weights for different types of zones. Also I've just gone for the simplest navmesh type, there's also other modes like tiling navmeshes which I've ignored.

Perhaps the most important part of the above is setting the agent size with m_agentHeight and m_agentRadius, and the voxel cell size used, m_cellSize and m_cellHeight. In my project 32.0 units is 1 meter, so I've set the agent to 48 units high, and the cell sizes are quite large. The original cell sizes in the Recast/Detour demo were down around 0.3.

Now for the pathfinding code. This takes a start point and an end point and, if possible, generates a list of lines in a path. It might fail if the start or end points aren't near any navmesh polygons, or if the path is too long, or it can't make a path, or various other reasons. So far I've not had problems though.

Code: Select all

int OgreFramework::FindPath(float* pStartPos, float* pEndPos, int nPathSlot, int nTarget)
{
	dtStatus status ;
	float pExtents[3]={32.0f, 32.0f, 32.0f} ; // size of box around start/end points to look for nav polygons
	dtPolyRef StartPoly ;
	float StartNearest[3] ;
	dtPolyRef EndPoly ;
	float EndNearest[3] ;
	dtPolyRef PolyPath[MAX_PATHPOLY] ;
	int nPathCount=0 ;
	float StraightPath[MAX_PATHVERT*3] ;
	int nVertCount=0 ;


	// setup the filter
	dtQueryFilter Filter;
	Filter.setIncludeFlags(0xFFFF) ;
	Filter.setExcludeFlags(0) ;
	Filter.setAreaCost(SAMPLE_POLYAREA_GROUND, 1.0f) ;

	// find the start polygon
	status=m_navQuery->findNearestPoly(pStartPos, pExtents, &Filter, &StartPoly, StartNearest) ;
	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) return -1 ; // couldn't find a polygon

	// find the end polygon
	status=m_navQuery->findNearestPoly(pEndPos, pExtents, &Filter, &EndPoly, EndNearest) ;
	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) return -2 ; // couldn't find a polygon

	status=m_navQuery->findPath(StartPoly, EndPoly, StartNearest, EndNearest, &Filter, PolyPath, &nPathCount, MAX_PATHPOLY) ;
	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) return -3 ; // couldn't create a path
	if(nPathCount==0) return -4 ; // couldn't find a path

	status=m_navQuery->findStraightPath(StartNearest, EndNearest, PolyPath, nPathCount, StraightPath, NULL, NULL, &nVertCount, MAX_PATHVERT) ;
	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) return -5 ; // couldn't create a path
	if(nVertCount==0) return -6 ; // couldn't find a path

	// At this point we have our path.  Copy it to the path store
	int nIndex=0 ;
	for(int nVert=0 ; nVert<nVertCount ; nVert++)
	{
		m_PathStore[nPathSlot].PosX[nVert]=StraightPath[nIndex++] ;
		m_PathStore[nPathSlot].PosY[nVert]=StraightPath[nIndex++] ;
		m_PathStore[nPathSlot].PosZ[nVert]=StraightPath[nIndex++] ;

		//sprintf(m_chBug, "Path Vert %i, %f %f %f", nVert, m_PathStore[nPathSlot].PosX[nVert], m_PathStore[nPathSlot].PosY[nVert], m_PathStore[nPathSlot].PosZ[nVert]) ;
		//m_pLog->logMessage(m_chBug);
	}
	m_PathStore[nPathSlot].MaxVertex=nVertCount ;
	m_PathStore[nPathSlot].Target=nTarget ;

	return nVertCount ;

}

To use the above code, set the start and end points as two float[3] arrays, and call like so:

Code: Select all

// 0 for the slot to save the path too, and 0 as the "target", to remember what the path was for.
// will return a negative number if the search for a path failed.
FindPath(m_flTestStart, m_flTestEnd, 0, 0) ; 
CreateRecastPathLine(0) ; // create a line that shows path 0, if we want to debug.

Here's some images showing the output. Firstup the navmesh, both with and without the source geometry.




And here's a generated path, the red line, from one side of the map to the other.


I've probably left stuff out or made errors, but anyway, hope this is a useful start for someone.

Edit: Ah, did my pet hate and posted code without license info. The stuff copied from the Recast demo is mit, see the license that comes with the recast download. My own code is now public domain, use it as you see fit either commercially or otherwise, no need to credit or reimburse me, and on your own head be it if it malfunctions. Or consider it MIT if you need something more technical.

[jacmoe]

Great stuff!

If you're not going to wiki this, I will.
Thanks.

[mkultra333]

Thanks Jacmoe. I should add that I also looked at DarkScythe's AI demo to get this set up, http://www.ogre3d.org/forums/viewtopic.php?f=11&t=60487, though I don't think I used any of his (MIT) code and the recast functions have changed a bit since the version he used. But his code was very useful for me to see what parts of the Recast demo I needed.

[End]

Thanks for the code snippets mkultra333.
Theres something I can't quite figure out though, how do you update just part of the generated path after adding new objects to the terrain? Do you have to rebuild the whole path?

[mkultra333]

There is some function for just generating the next straight-line part of a path rather than the whole thing, but I've not explored that yet, sorry. You might be able to get that info looking through the Recast google group, or asking there. http://groups.google.com/group/recastnavigation

[kklouzal]

Hello mkultra, thank you tremendously for this example on how to get recast/detour going, it was a crude but helpful example as there is little to no tutorials out there on the subject which leads me to the reason I've necro'd this from the depths of hell.

When you first initialize the build configuration and set the recast parameters there is one specific option:
m_vertsPerPoly = 6;
A little further down:
m_cfg.maxVertsPerPoly = (int)m_vertsPerPoly;
Finally near the end of this function during step 8 (Create Detour data from Recast poly mesh.) the first if-then statement is as follows:
if (m_cfg.maxVertsPerPoly <= DT_VERTS_PER_POLYGON)
DT_VERTS_PER_POLYGON happens to be 3, so this code never executes, was this an accident or intentional?

Second question,

There is some function for just generating the next straight-line part of a path rather than the whole thing, but I've not explored that yet, sorry.

Have you possibly looked into that at all in the last 2 years?

Third and final question,
Could you explain how to actually use the path information in m_PathStore?


I want to thank you again for taking the time to create and release this to the public, it has helped me and I'm sure countless others, keep up the good work!

[mkultra333]

Hi kklouzal, glad you've found the code helpful.

DT_VERTS_PER_POLYGON happens to be 3, so this code never executes, was this an accident or intentional?

I had a look, and in the recast code I have DT_VERTS_PER_POLYGON is 6. I'm still using the same version of Recast I used when I first made these posts, which means it's about 3 years old now. There may have been a lot of changes in Recast/Detour since then, and perhaps DT_VERTS_PER_POLYGON has changed. At any rate, that section of code after the "if" is definitely supposed to execute, it's what creates the navigation data based on the navigation mesh.
Pretty much all that setup code was copied directly from the demo that came with the recast code at https://github.com/memononen/recastnavigation as it was in 2010.

Have you possibly looked into that at all in the last 2 years?

Regarding getting just the next line segment, no, sorry, it hasn't been something I've needed.

Could you explain how to actually use the path information in m_PathStore?

m_PathStore is just an array of paths, each one independent. I did that at the time so that multiple agents who might need to follow the same paths could see if there was already a path they needed in the array and just use that, otherwise they could generate a new one, and other agents might end up using that path. To keep things simple, lets just say you only want to make one path, stored in m_PathStore[0].
If you use that "FindPath" function I posted above, and the function succeeds and finds a path, then
m_PathStore[0].MaxVertex will tell you how many vertices there are in the path,
and each of those vertices is stored in
m_PathStore[0].PosX[nVertNum]
m_PathStore[0].PosY[nVertNum]
m_PathStore[0].PosZ[nVertNum]

One thing, using that code from 2010, I would run into a bug so you might have to modify the code for finding paths with something like this:

Code: Select all

	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	
	// The version of Recast/Detour I have seems to have a bug, it doesn't report failure to find a nearby navigation polygon
	// even if there is none.  In order to detect failure, I have to check if it failed to update the output Nearest point.

	StartNearest[0]=-1000000.0f ;
	StartNearest[1]=0.0f ;
	StartNearest[2]=0.0f ;

	// find the start polygon
	status=m_navQuery_SMLNAV->findNearestPoly(pStartPos, pExtents, &Filter, &StartPoly, StartNearest) ; m_nRecastFindPolyCount++ ;
	

	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) { return PATHERROR_NOPOLYGONATSTART ; } // couldn't find a polygon
	if(StartNearest[0]==-1000000.0f) { return PATHERROR_NOPOLYGONATSTART ;} // extra test due to bug, couldn't find a polygon

	EndNearest[0]=-1000000.0f ;
	EndNearest[1]=0.0f ;
	EndNearest[2]=0.0f ;

	// find the end polygon
	status=m_navQuery_SMLNAV->findNearestPoly(pEndPos, pExtents, &Filter, &EndPoly, EndNearest) ; m_nRecastFindPolyCount++ ;

	if((status&DT_FAILURE) || (status&DT_STATUS_DETAIL_MASK)) {return PATHERROR_NOPOLYGONATEND ;} // couldn't find a polygon
	if(EndNearest[0]==-1000000.0f) {return PATHERROR_NOPOLYGONATEND ;} // extra test due to bug, couldn't find a polygon

That code above is rough, sort of paraphrased from the code I use, but the idea is to do an extra test after the intial test for finding the start and end polygon to see if it has really updated the start and end point. If it hasn't, then it didn't find a polygon but didn't bother telling us that it failed. Newer versions may not have this problem.

BTW, you might want to also look at http://www.ogre3d.org/forums/viewtopic.php?f=11&t=69781, it's a more complete integration of recast/detour done by duststorm, probably more up to date and also he worked on the crowd control component of Detour as well, for moving around multiple agents without having them run into each other all the time. That's something I never touched on my very basic demo.

[kklouzal]

Thank you I really appreciate the response I understand how to get the coordinates for each vertex out of the pathStore now, thanks a million!
I checked again and DT_VERTS_PER_POLYGON is 6, I don't know how I got that mixed up so sorry for the run around there.
Perhaps you've had the pleasure of working with the tile system?
I will give OgreCast a look, I prefer to keep things simple when I first start out learning them but I will definitely have a look see, being as I'm not using this with the OGRE engine directly the simpler the better

[kklouzal]

I'll redirect the question to maybe has anyone been able to get the tile system working with recast?

[nickG]

subscribed

[Klaim]

subscribed

You can suscribe to posts without posting. See the subscribe link at the bottom of each thread page.

[insider]

Almost got it working until a compiler error.
What exactly is m_OgreBZNBSP ?

Any help would be great.
And apologies to revive an old post

[Zonder]

Almost got it working until a compiler error.
What exactly is m_OgreBZNBSP ?

Any help would be great.
And apologies to revive an old post

You do know about ogre crowd also don't you? http://www.ogre3d.org/forums/viewtopic.php?f=11&t=69781

[insider]

Almost got it working until a compiler error.
What exactly is m_OgreBZNBSP ?

Any help would be great.
And apologies to revive an old post

You do know about ogre crowd also don't you? http://www.ogre3d.org/forums/viewtopic.php?f=11&t=69781

Yep I was just trying out Ogre crowd today, just checking out all the Recast options out there.
Was just curious the post makes no note of what m_OgreBZNBSP is

[Zonder]

Almost got it working until a compiler error.
What exactly is m_OgreBZNBSP ?

Any help would be great.
And apologies to revive an old post

You do know about ogre crowd also don't you? http://www.ogre3d.org/forums/viewtopic.php?f=11&t=69781

Yep I was just trying out Ogre crowd today, just checking out all the Recast options out there.
Was just curious the post makes no note of what m_OgreBZNBSP is

hmm so it doesn't and have no idea lol.

As I recollect ogre crowd was an expansion on what was done in this thread been ages since i read it though.

[mkultra333]

Happened to be passing by and noticed there were some new posts here.

m_OgreBZNBSP is not important, it was a binary space partition class that also held all the polygon data for the map. So in the code where it says things like...

Code: Select all

// setup recast verts, and min/max
   rc_nverts=m_OgreBZNBSP->m_nVertexMax ;
   rc_verts= new float[rc_nverts*3] ;
   for(nLoop=0 ; nLoop<rc_nverts ; nLoop++)
   {
      rc_verts[nLoop*3+0] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[0] ;
      rc_verts[nLoop*3+1] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[1] ;
      rc_verts[nLoop*3+2] = m_OgreBZNBSP->m_pVertex[nLoop].xyz[2] ;

... it's just saying rc_nverts equals the maximum vertices, and that the xyz positions of the actual vertices, stored in m_OgreBZNBSP->m_pVertex[], gets copied to rc_verts[].

I guess I thought that was obvious at the time... come to think of it, it still looks obvious. :p