性能提升-BVH层次包围体
eryar@163.com
Abstract. OpenCASCADE provides BVH to achieve high performance in AIS of visualization module. To understand BVH usage will help us to understand many code of opencascade.
Key Words. BVH, Bounding Volume Hierarchy, LBVH, SAH Algorithm
1 Introduction
层次包围体技术 (BVH) 指的是将所有包围体分层逐次地再次包围，获得一个更大的包围体，直到包围住所有物体。实际上，它是一个树形结构，因此可以仿照树的结构，将两个或三个小的包围体包围成一个更大的包围体，以此类推。
BVH是一种以物体BV为基础进行划分的结构。它由根节点、内部节点和叶子节点组成。其中叶子节点存放物体，每个非叶子节点都有包围体，父节点可以把子节点包围起来。每个非叶子节点的包围体大小，是它所包含的所有物体的包围体的总和，所以它在空间上比较紧凑，非常适用于需要大量求相交测试的应用场景，如光线追踪、碰撞检测、射线相交测试之类的应用场合中。
BVH在OpenCASCADE中也有广泛地应用，如开源版本中的模型快速碰撞检测，使用类BRepExtrema_ShapeProximity. 模型选择操作，光线跟踪等算法中都有应用。在
https://www.cnblogs.com/opencascade/p/6804446.html
中介绍如何遍历BVH树，本文主要介绍BVH使用方法。
2 BVH
OpenCASCADE中的BVH是相对独立的一个包，是作者根据论文实现的纯C++版本移植过来的。在DRAW中的QA品质保证Bugs中提供了BVH的使用示例。
2.1 BVH_Set
首先要定义层次包围盒的集合Set来构造BVH树，从BVH_Set基类派生的集合是可以直接使用的：
如可以直接使用BVH_Triangulation，也可以直接使用BVH_BoxSet：
从这些类名中，我们可以看出在求模型间极值距离Extrema，三维可视化Graphic3d及Select3D拾取及布尔操作BOPTools中都有BVH的应用。
将元素通过Add函数添加到BVH集合后，调用BVH()函数就可以构造BVH树。
2.2 BVH_Traverse
对于单个BVH的遍历提供类BVH_Traverse，一般的应用场景如求距离一点P最近的模型，或者位于某个空间范围内的所有模型。代码如下所示：
//=======================================================================
//function : ShapeSelector
//purpose : Implement the simplest shape's selector
//=======================================================================
class ShapeSelector :
public BVH_Traverse <Standard_Real, 3, BVH_BoxSet <Standard_Real, 3, TopoDS_Shape>, Standard_Boolean>
{
public:
//! Constructor
ShapeSelector() {}
//! Sets the Box for selection
void SetBox (const Bnd_Box& theBox)
{
myBox = Bnd_Tools::Bnd2BVH (theBox);
}
//! Returns the selected shapes
const NCollection_List<TopoDS_Shape>& Shapes () const { return myShapes; }
public:
//! Defines the rules for node rejection by bounding box
virtual Standard_Boolean RejectNode (const BVH_Vec3d& theCornerMin,
const BVH_Vec3d& theCornerMax,
Standard_Boolean& theIsInside) const Standard_OVERRIDE
{
Standard_Boolean hasOverlap;
theIsInside = myBox.Contains (theCornerMin, theCornerMax, hasOverlap);
return !hasOverlap;
}
//! Defines the rules for leaf acceptance
virtual Standard_Boolean AcceptMetric (const Standard_Boolean& theIsInside) const Standard_OVERRIDE
{
return theIsInside;
}
//! Defines the rules for leaf acceptance
virtual Standard_Boolean Accept (const Standard_Integer theIndex,
const Standard_Boolean& theIsInside) Standard_OVERRIDE
{
if (theIsInside || !myBox.IsOut (myBVHSet->Box (theIndex)))
{
myShapes.Append (myBVHSet->Element (theIndex));
return Standard_True;
}
return Standard_False;
}
protected:
BVH_Box <Standard_Real, 3> myBox; //!< Selection box
NCollection_List <TopoDS_Shape> myShapes; //!< Selected shapes
};
主要是从类BVH_Traverse派生并重写两个虚函数RejectNode()和Accept()，即在RejectNode()中定义排除结点的规则，在Accept()中处理满足条件的情况。
2.3 BVH_PairTraverse
对于两个BVH的遍历提供类BVH_PairTraverse，一般的应用场景有求两个Mesh之间的最近距离，判断两个Mesh之间是否有碰撞等。
//=======================================================================
//function : MeshMeshDistance
//purpose : Class to compute the distance between two meshes
//=======================================================================
class MeshMeshDistance : public BVH_PairDistance<Standard_Real, 3, BVH_BoxSet<Standard_Real, 3, Triangle>>
{
public:
//! Constructor
MeshMeshDistance() {}
public:
//! Defines the rules for leaf acceptance
virtual Standard_Boolean Accept (const Standard_Integer theIndex1,
const Standard_Integer theIndex2) Standard_OVERRIDE
{
const Triangle& aTri1 = myBVHSet1->Element (theIndex1);
const Triangle& aTri2 = myBVHSet2->Element (theIndex2);
Standard_Real aDistance = TriangleTriangleSqDistance (aTri1._Node1, aTri1._Node2, aTri1._Node3,
aTri2._Node1, aTri2._Node2, aTri2._Node3);
if (aDistance < myDistance)
{
myDistance = aDistance;
return Standard_True;
}
return Standard_False;
}
};
主要也是从BVH_PairTraverse派生并重写两个虚函数RejectNode()和Accept()。
2.4 BVH_Builder
关于BVH的构造提供多种Builder，默认是使用基于SAH算法的BVH_BinnedBuilder来构造BVH树，如果要切换不同的构造器，可以在BVH集合的构造函数中传入一个。
下面给出求两个Mesh之间最近距离的示例代码：
// Define BVH Builder
opencascade::handle <BVH_LinearBuilder <Standard_Real, 3> > aLBuilder =
new BVH_LinearBuilder <Standard_Real, 3>();
// Create the ShapeSet
opencascade::handle <BVH_BoxSet <Standard_Real, 3, Triangle> > aTriangleBoxSet[2];
for (Standard_Integer i = 0; i < 2; ++i)
{
aTriangleBoxSet[i] = new BVH_BoxSet <Standard_Real, 3, Triangle> (aLBuilder);
TopTools_IndexedMapOfShape aMapShapes;
TopExp::MapShapes (aShape[i], TopAbs_FACE, aMapShapes);
for (Standard_Integer iS = 1; iS <= aMapShapes.Extent(); ++iS)
{
const TopoDS_Face& aF = TopoDS::Face (aMapShapes(iS));
TopLoc_Location aLoc;
const Handle(Poly_Triangulation)& aTriangulation = BRep_Tool::Triangulation(aF, aLoc);
const int aNbTriangles = aTriangulation->NbTriangles();
for (int iT = 1; iT <= aNbTriangles; ++iT)
{
const Poly_Triangle aTriangle = aTriangulation->Triangle (iT);
// Nodes indices
Standard_Integer id1, id2, id3;
aTriangle.Get (id1, id2, id3);
const gp_Pnt aP1 = aTriangulation->Node (id1).Transformed (aLoc.Transformation());
const gp_Pnt aP2 = aTriangulation->Node (id2).Transformed (aLoc.Transformation());
const gp_Pnt aP3 = aTriangulation->Node (id3).Transformed (aLoc.Transformation());
BVH_Vec3d aBVHP1 (aP1.X(), aP1.Y(), aP1.Z());
BVH_Vec3d aBVHP2 (aP2.X(), aP2.Y(), aP2.Z());
BVH_Vec3d aBVHP3 (aP3.X(), aP3.Y(), aP3.Z());
BVH_Box<Standard_Real, 3> aBox;
aBox.Add (aBVHP1);
aBox.Add (aBVHP2);
aBox.Add (aBVHP3);
aTriangleBoxSet[i]->Add (Triangle (aBVHP1, aBVHP2, aBVHP3), aBox);
}
}
// Build BVH
aTriangleBoxSet[i]->Build();
}
// Initialize selector
MeshMeshDistance aDistTool;
// Select the elements
aDistTool.SetBVHSets (aTriangleBoxSet[0].get(), aTriangleBoxSet[1].get());
Standard_Real aSqDist = aDistTool.ComputeDistance();
if (!aDistTool.IsDone())
std::cout << "Not Done" << std::endl;
else
theDI << "Distance " << sqrt (aSqDist) << "\n";
3 Conclusion
准确、稳定、高效是高品质几何内核的目标，我们在开发软件时，也要时刻追求这个目标。而BVH层次包围盒技术是提升性能的一种方式，理解BVH的使用，我们可以理解opencascade中快速求极值Extrema，交互选择SelectMgr等很多代码。甚至我们也可以参与贡献，如将
Standard_Boolean BRepExtrema_Poly::Distance (const TopoDS_Shape& S1, const TopoDS_Shape& S2,
gp_Pnt& P1, gp_Pnt& P2, Standard_Real& dist)
这个O(N^2)的改造成BVH的来对比一下性能。