Function createBVTree

3rdparty/recast/DetourNavMeshBuilder.cpp:171–241

}

static int createBVTree(dtNavMeshCreateParams* params, dtBVNode* nodes, int /*nnodes*/)
{
	// Build tree
	float quantFactor = 1 / params->cs;
	BVItem* items = (BVItem*)dtAlloc(sizeof(BVItem)*params->polyCount, DT_ALLOC_TEMP);
	for (int i = 0; i < params->polyCount; i++)
	{
		BVItem& it = items[i];
		it.i = i;
		// Calc polygon bounds. Use detail meshes if available.
		if (params->detailMeshes)
		{
			int vb = (int)params->detailMeshes[i*4+0];
			int ndv = (int)params->detailMeshes[i*4+1];
			float bmin[3];
			float bmax[3];

			const float* dv = &params->detailVerts[vb*3];
			dtVcopy(bmin, dv);
			dtVcopy(bmax, dv);

			for (int j = 1; j < ndv; j++)
			{
				dtVmin(bmin, &dv[j * 3]);
				dtVmax(bmax, &dv[j * 3]);
			}

			// BV-tree uses cs for all dimensions
			it.bmin[0] = (unsigned short)dtClamp((int)((bmin[0] - params->bmin[0])*quantFactor), 0, 0xffff);
			it.bmin[1] = (unsigned short)dtClamp((int)((bmin[1] - params->bmin[1])*quantFactor), 0, 0xffff);
			it.bmin[2] = (unsigned short)dtClamp((int)((bmin[2] - params->bmin[2])*quantFactor), 0, 0xffff);

			it.bmax[0] = (unsigned short)dtClamp((int)((bmax[0] - params->bmin[0])*quantFactor), 0, 0xffff);
			it.bmax[1] = (unsigned short)dtClamp((int)((bmax[1] - params->bmin[1])*quantFactor), 0, 0xffff);
			it.bmax[2] = (unsigned short)dtClamp((int)((bmax[2] - params->bmin[2])*quantFactor), 0, 0xffff);
		}
		else
		{
			const unsigned short* p = &params->polys[i*params->nvp * 2];
			it.bmin[0] = it.bmax[0] = params->verts[p[0] * 3 + 0];
			it.bmin[1] = it.bmax[1] = params->verts[p[0] * 3 + 1];
			it.bmin[2] = it.bmax[2] = params->verts[p[0] * 3 + 2];

			for (int j = 1; j < params->nvp; ++j)
			{
				if (p[j] == MESH_NULL_IDX) break;
				unsigned short x = params->verts[p[j] * 3 + 0];
				unsigned short y = params->verts[p[j] * 3 + 1];
				unsigned short z = params->verts[p[j] * 3 + 2];

				if (x < it.bmin[0]) it.bmin[0] = x;
				if (y < it.bmin[1]) it.bmin[1] = y;
				if (z < it.bmin[2]) it.bmin[2] = z;

				if (x > it.bmax[0]) it.bmax[0] = x;
				if (y > it.bmax[1]) it.bmax[1] = y;
				if (z > it.bmax[2]) it.bmax[2] = z;
			}