Bounding Volume Hierarchy BVH in OpenCASCADE
eryar@163.com
Abstract. Bounding Volume Hierarchy(BVH) organizes geometric objects in the tree based on spatial relationships. Each node in the tree contains an axis-aligned bounding box of all the objects below it. Bounding volume hierarchies are used in many algorithms to support efficient operations on the sets of geometric objects, such as collision detection, ray-tracing, searching of nearest objects, and view frustum culling. The paper focus on the usage of BVH on TopoDS_Shape, and its application.
Key Words. BVH, Bounding Volume Hierarchy, Collision Detection
1.Introduction
層次包圍盒(Bounding Volume Hierarchy, BVH)是一種基于物體的場(chǎng)景管理技術(shù)，廣泛用于碰撞檢測(cè)，光線(xiàn)追蹤，視錐體物體剔除等場(chǎng)合。對(duì)于三維場(chǎng)景的實(shí)時(shí)渲染來(lái)說(shuō)，BVH是最常用的數(shù)據(jù)結(jié)構(gòu)。場(chǎng)景以層次樹(shù)形結(jié)構(gòu)進(jìn)行組織，包含一個(gè)根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、葉子節(jié)點(diǎn)。樹(shù)中的每個(gè)節(jié)點(diǎn)，包括葉子節(jié)點(diǎn)都有一個(gè)包圍體，可以將其子樹(shù)的所有幾何體包圍起來(lái)，這就是BVH名字的由來(lái)。如下圖所示：
Figure 1. Simple Scene(left), BVH Scene Graph(right)
本文主要介紹OpenCASCADE中的BVH包及其應(yīng)用，如碰撞檢測(cè)。
2.Build BVH
在BVH包中的頭文件里面找到BVH的作者：Denis BOGOLEPOV, Danila ULYANOV，在網(wǎng)上搜到他們的一篇論文：Real-Time SAH BVH Construction for Ray Tracing Dynamic Scenes. 因此，可知BVH中是應(yīng)用SAH（Surface Area Heuristic）策略來(lái)構(gòu)造BVH樹(shù)的。根據(jù)BVH_BinnedBuilder頭文件中的注釋可知：
//! Performs construction of BVH tree using binned SAH algorithm. Number
//! of bins controls BVH quality in cost of construction time (greater
//! better). For optimal results, use 32 - 48 bins. However, reasonable
//! performance is provided even for 4 - 8 bins (it is only 10-20% lower
//! in comparison with optimal settings). Note that multiple threads can
//! be used only with thread safe BVH primitive sets.
OpenCASCADE中也提供了其他的構(gòu)造方法，如類(lèi)BVH_LinearBuilder中使用了Spatial Morton codes方法：
//! Performs fast BVH construction using LBVH building approach.
//! Algorithm uses spatial Morton codes to reduce the BVH construction
//! problem to a sorting problem (radix sort -- O(N) complexity). This
//! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
//! of lower quality compared to SAH-based BVH builders but it is over
//! an order of magnitude faster (up to 3M triangles per second).
//!
//! For more details see:
//! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
//! Fast BVH construction on GPUs. Eurographics, 2009.
3.Traversal BVH
由類(lèi)BVH_TreeBase可知，當(dāng)?shù)玫紹VH樹(shù)后，可以取出節(jié)點(diǎn)索引的數(shù)組。下面給出將TopoDS_Shape的BVH樹(shù)顯示出來(lái)的示例代碼：
/*
Copyright(C) 2017 Shing Liu(eryar@163.com)
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
// Visual Studio 2013 & OpenCASCADE7.1.0
// 2017-04-18 20:52
#include <BRepExtrema_TriangleSet.hxx>
#include <BRepTools.hxx>
#include <BRep_Builder.hxx>
#include <TopoDS.hxx>
#include <TopExp_Explorer.hxx>
#include <BRepPrimAPI_MakeBox.hxx>
#include <BRepMesh_IncrementalMesh.hxx>
#pragma comment(lib, "TKernel.lib")
#pragma comment(lib, "TKMath.lib")
#pragma comment(lib, "TKG2d.lib")
#pragma comment(lib, "TKG3d.lib")
#pragma comment(lib, "TKGeomBase.lib")
#pragma comment(lib, "TKGeomAlgo.lib")
#pragma comment(lib, "TKBRep.lib")
#pragma comment(lib, "TKPrim.lib")
#pragma comment(lib, "TKMesh.lib")
#pragma comment(lib, "TKTopAlgo.lib")
void testBvh(const std::string& theFileName)
{
BRep_Builder aBuilder;
TopoDS_Compound aCompound;
TopoDS_Shape aShape;
BRepTools::Read(aShape, theFileName.c_str(), aBuilder);
BRepExtrema_ShapeList aFaceList;
for (TopExp_Explorer i(aShape, TopAbs_FACE); i.More(); i.Next())
{
aFaceList.Append(TopoDS::Face(i.Current()));
}
aBuilder.MakeCompound(aCompound);
BRepMesh_IncrementalMesh aMesher(aShape, 1.0);
BRepExtrema_TriangleSet aTriangleSet(aFaceList);
const NCollection_Handle<BVH_Tree<Standard_Real, 3> >& aBvh = aTriangleSet.BVH();
for (int i = 0; i < aBvh->Length(); i++)
{
const BVH_Vec4i& aNodeData = aBvh->NodeInfoBuffer()[i];
if (aNodeData.x() == 0)
{
// inner node.
const BVH_Vec3d& aP1 = aBvh->MinPoint(aNodeData.y());
const BVH_Vec3d& aP2 = aBvh->MaxPoint(aNodeData.y());
const BVH_Vec3d& aQ1 = aBvh->MinPoint(aNodeData.z());
const BVH_Vec3d& aQ2 = aBvh->MaxPoint(aNodeData.z());
try
{
BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aP1.x(), aP1.y(), aP1.z()),
gp_Pnt(aP2.x(), aP2.y(), aP2.z()));
for (TopExp_Explorer i(aBoxMaker.Shape(), TopAbs_EDGE); i.More(); i.Next())
{
aBuilder.Add(aCompound, i.Current());
}
}
catch (Standard_Failure f)
{
}
try
{
BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aQ1.x(), aQ1.y(), aQ1.z()),
gp_Pnt(aQ2.x(), aQ2.y(), aQ2.z()));
for (TopExp_Explorer i(aBoxMaker.Shape(), TopAbs_EDGE); i.More(); i.Next())
{
aBuilder.Add(aCompound, i.Current());
}
}
catch (Standard_Failure f)
{
}
}
else
{
// leaves node.
const BVH_Vec3d& aP1 = aBvh->MinPoint(i);
const BVH_Vec3d& aP2 = aBvh->MaxPoint(i);
try
{
BRepPrimAPI_MakeBox aBoxMaker(gp_Pnt(aP1.x(), aP1.y(), aP1.z()),
gp_Pnt(aP2.x(), aP2.y(), aP2.z()));
aBuilder.Add(aCompound, aBoxMaker.Shape());
}
catch (Standard_Failure f)
{
}
}
}
BRepTools::Write(aCompound, "d:/bvh.brep");
}
int main(int argc, char* argv[])
{
if (argc > 1)
{
testBvh(argv[1]);
}
return 0;
}
由上述代碼可知，當(dāng)?shù)玫焦?jié)點(diǎn)信息
const BVH_Vec4i& aNodeData = aBvh->NodeInfoBuffer()[i];
后，通過(guò)判斷aNodeData.x()分量來(lái)確定此節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn)還是葉子節(jié)點(diǎn)。顯示OCC自帶的螺旋槳模型的BVH如下圖所示：
其中紅色線(xiàn)框?yàn)閮?nèi)部節(jié)點(diǎn)，黃色實(shí)體模型是葉子節(jié)點(diǎn)。
4.BVH Application
BVH在OpenCASCADE中也有廣泛地應(yīng)用，如開(kāi)源版本中的模型快速碰撞檢測(cè)，使用類(lèi)BRepExtrema_ShapeProximity. 模型選擇操作，光線(xiàn)跟蹤等算法中都有應(yīng)用。
5.Conclusion
因?yàn)镺penCASCADE中構(gòu)造BVH時(shí)依賴(lài)模型的網(wǎng)格三角形，所以BVH算法的應(yīng)用的結(jié)果就依賴(lài)于網(wǎng)格化算法的質(zhì)量了。如兩個(gè)Topo形狀碰撞檢測(cè)時(shí)，網(wǎng)格化的質(zhì)量越高，結(jié)果精度越高。如果用解析算法去對(duì)兩個(gè)Topo形狀做碰撞檢測(cè)，也會(huì)涉及到解析算法的精度問(wèn)題。
BVH結(jié)構(gòu)廣泛應(yīng)用于碰撞檢測(cè)、光線(xiàn)跟蹤等算法中，大大提高程序性能。本文只是拋磚引玉，對(duì)BVH感興趣的童鞋可以參考相關(guān)資料及OpenCASCADE中的代碼實(shí)現(xiàn)，去深入學(xué)習(xí)應(yīng)用。
6.References
1. Dmitry Sopin, Denis Bogolepov, Danila Ulyanov. Real-Time SAH BVH Construction for Ray Tracing Dynamic Scenes. http://graphicon.ru/html/2011/conference/gc2011Sopin.pdf
2. BVH with SAH. http://www.cnblogs.com/lookof/p/3546320.html
3. 3D游戲引擎中常見(jiàn)的三維場(chǎng)景管理方法. http://www.cnblogs.com/wangchengfeng/p/3495954.html