是一棵二叉树,
包围层次盒BVH是一种场景管理技术，广泛应用于碰撞检测、射线相交测试之类的应用场合中。
bvTree有两种节点（Node）类型：Interior Node 和 Leaf Node。
LeafNode 是最终存放tile的地方
划分策略可以选择比较高端的表面积启发式算法（SurfaceArea Heuristic）
SAH基于的思想：如果某物的表面积越大，那么它被射线击中的可能性也就越大。
每次划分，都会得到两个子区域A和B。那么相应也会算出一个cost(A,B)来。比较所有划分方案下所得的cost(A,B)，取值最小的方案就是成本最低的划分方案，也作为划分该节点的最终/优方案。
我们不用链表来存储树，而是用数组：
offset用来指示第二棵子树的位置
eg:在bvTree上遍历找到距离给定方框相接触的polygon
void dtNavMeshQuery::queryPolygonsInTile(const dtMeshTile* tile, const float* qmin, const float* qmax,
const dtQueryFilter* filter, dtPolyQuery* query) const
{
dtAssert(m_nav);
static const int batchSize = 32;//最多找到多少个poly
dtPolyRef polyRefs[batchSize];
dtPoly* polys[batchSize];
int n = 0;
if (tile->bvTree)//用数组存的BVH
{
const dtBVNode* node = &tile->bvTree[0];
const dtBVNode* end = &tile->bvTree[tile->header->bvNodeCount];
const float* tbmin = tile->header->bmin;
const float* tbmax = tile->header->bmax;
const float qfac = tile->header->bvQuantFactor; //1.0f / params->cs
// Calculate quantized box
unsigned short bmin[3], bmax[3];
// dtClamp query box to world box.
float minx = dtClamp(qmin[0], tbmin[0], tbmax[0]) - tbmin[0];
float miny = dtClamp(qmin[1], tbmin[1], tbmax[1]) - tbmin[1];
float minz = dtClamp(qmin[2], tbmin[2], tbmax[2]) - tbmin[2];
float maxx = dtClamp(qmax[0], tbmin[0], tbmax[0]) - tbmin[0];
float maxy = dtClamp(qmax[1], tbmin[1], tbmax[1]) - tbmin[1];
float maxz = dtClamp(qmax[2], tbmin[2], tbmax[2]) - tbmin[2];
// Quantize 可以理解成：bmin和bmax表示各个方向上的第几个cell到第几个cell
bmin[0] = (unsigned short)(qfac * minx) & 0xfffe;
bmin[1] = (unsigned short)(qfac * miny) & 0xfffe;
bmin[2] = (unsigned short)(qfac * minz) & 0xfffe;
bmax[0] = (unsigned short)(qfac * maxx + 1) | 1;
bmax[1] = (unsigned short)(qfac * maxy + 1) | 1;
bmax[2] = (unsigned short)(qfac * maxz + 1) | 1;
// Traverse tree
const dtPolyRef base = m_nav->getPolyRefBase(tile);
while (node < end)
{
const bool overlap = dtOverlapQuantBounds(bmin, bmax, node->bmin, node->bmax);//两个包围盒是否overlap
const bool isLeafNode = node->i >= 0;//i是bvNode的序号，如果是负的说明是escape sequence，那肯定不是叶子，所以也就不会是正的
if (isLeafNode && overlap)
{
dtPolyRef ref = base | (dtPolyRef)node->i;
if (node->i >= batchSize)
{
return;
}
if (filter->passFilter(ref, tile, &tile->polys[node->i]))//测试可通过性
{
polyRefs[n] = ref;
polys[n] = &tile->polys[node->i];//如果可通过就记录下来这个叶子
if (n == batchSize - 1)
{
query->process(tile, polys, polyRefs, batchSize);//算出距离点最近的距离和最近的那个ref
n = 0;
}
else
{
n++;
}
}
}
if (overlap || isLeafNode)//重叠了但是不是叶子，当然往下走去判断左子树，是叶子但是不重叠也往下走相当于判断
//根的右子树
node++;
else
{ //既不是叶子也不重叠，说明作为左子树不重叠应该去找跟的右子树，用的就是escape值
const int escapeIndex = -node->i;
node += escapeIndex;
}
}
}
else
{
float bmin[3], bmax[3];
const dtPolyRef base = m_nav->getPolyRefBase(tile);
for (int i = 0; i < tile->header->polyCount; ++i)
{
dtPoly* p = &tile->polys[i];
// Do not return off-mesh connection polygons.
if (p->getType() == DT_POLYTYPE_OFFMESH_CONNECTION)
continue;
// Must pass filter
const dtPolyRef ref = base | (dtPolyRef)i;
if (!filter->passFilter(ref, tile, p))
continue;
// Calc polygon bounds.
const float* v = &tile->verts[p->verts[0]*3];
dtVcopy(bmin, v);
dtVcopy(bmax, v);
for (int j = 1; j < p->vertCount; ++j)
{
v = &tile->verts[p->verts[j]*3];
dtVmin(bmin, v);
dtVmax(bmax, v);
}
if (dtOverlapBounds(qmin, qmax, bmin, bmax))
{
polyRefs[n] = ref;
polys[n] = p;
if (n == batchSize - 1)
{
query->process(tile, polys, polyRefs, batchSize);
n = 0;
}
else
{
n++;
}
}
}
}
// Process the last polygons that didn't make a full batch.
if (n > 0)
query->process(tile, polys, polyRefs, n);
}