布爾數(shù)據(jù) BOPDS_Iterator
eryar@163.com
1 Introduction
OpenCASCADE中新的布爾工具TKBO相對(duì)已經(jīng)廢棄的TKBool代碼更規(guī)范，更易于理解。與ModelingData和ModelingAlgorithms大的模塊組織一樣，主要也是數(shù)據(jù)結(jié)構(gòu)Data Structure+算法Algorithm的組織形式。
其中BOPDS為布爾中的數(shù)據(jù)結(jié)構(gòu)部分，BOPAlgo為布爾中的算法部分。理解算法的前提是先理解數(shù)據(jù)結(jié)構(gòu)DS(Data Structure)，所以先從數(shù)據(jù)結(jié)構(gòu)入手，來(lái)深入理解布爾操作。本文先從簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)BOPDS_Iterator開始對(duì)源碼進(jìn)行分析。
2 BOPDS_Iterator
從類的注釋可以看出，迭代器BOPDS_Iterator有以下兩個(gè)功能：
- 找出包圍盒相交的Shape；
- 遍歷相交的一對(duì)Shape；
//! The class BOPDS_Iterator is
//! 1.to compute intersections between BRep sub-shapes
//! of arguments of an operation (see the class BOPDS_DS)
//! in terms of theirs bounding boxes
//! 2.provides interface to iterate the pairs of
//! intersected sub-shapes of given type
class BOPDS_Iterator
{
public:
其中核心的算法在函數(shù)Intersect()中，代碼如下所示：
//=======================================================================
// function: Intersect
// purpose:
//=======================================================================
void BOPDS_Iterator::Intersect(const Handle(IntTools_Context)& theCtx,
const Standard_Boolean theCheckOBB,
const Standard_Real theFuzzyValue)
{
const Standard_Integer aNb = myDS->NbSourceShapes();
// Prepare BVH
BOPTools_BoxTree aBoxTree;
aBoxTree.SetSize (aNb);
for (Standard_Integer i = 0; i < aNb; ++i)
{
const BOPDS_ShapeInfo& aSI = myDS->ShapeInfo(i);
if (!aSI.HasBRep())
continue;
const Bnd_Box& aBox = aSI.Box();
aBoxTree.Add (i, Bnd_Tools::Bnd2BVH (aBox));
}
// Build BVH
aBoxTree.Build();
// Select pairs of shapes with interfering bounding boxes
BOPTools_BoxPairSelector aPairSelector;
aPairSelector.SetBVHSets (&aBoxTree, &aBoxTree);
aPairSelector.SetSame (Standard_True);
aPairSelector.Select();
aPairSelector.Sort();
// Treat the selected pairs
const std::vector<BOPTools_BoxPairSelector::PairIDs>& aPairs = aPairSelector.Pairs();
const Standard_Integer aNbPairs = static_cast<Standard_Integer> (aPairs.size());
Standard_Integer iPair = 0;
const Standard_Integer aNbR = myDS->NbRanges();
for (Standard_Integer iR = 0; iR < aNbR; ++iR)
{
const BOPDS_IndexRange& aRange = myDS->Range(iR);
for (; iPair < aNbPairs; ++iPair)
{
const BOPTools_BoxPairSelector::PairIDs& aPair = aPairs[iPair];
if (!aRange.Contains (aPair.ID1))
// Go to the next range
break;
if (aRange.Contains (aPair.ID2))
// Go to the next pair
continue;
const BOPDS_ShapeInfo& aSI1 = myDS->ShapeInfo (aPair.ID1);
const BOPDS_ShapeInfo& aSI2 = myDS->ShapeInfo (aPair.ID2);
const TopAbs_ShapeEnum aType1 = aSI1.ShapeType();
const TopAbs_ShapeEnum aType2 = aSI2.ShapeType();
Standard_Integer iType1 = BOPDS_Tools::TypeToInteger (aType1);
Standard_Integer iType2 = BOPDS_Tools::TypeToInteger (aType2);
// avoid interfering of the shape with its sub-shapes
if (((iType1 < iType2) && aSI1.HasSubShape (aPair.ID2)) ||
((iType1 > iType2) && aSI2.HasSubShape (aPair.ID1)))
continue;
if (theCheckOBB)
{
// Check intersection of Oriented bounding boxes of the shapes
const Bnd_OBB& anOBB1 = theCtx->OBB (aSI1.Shape(), theFuzzyValue);
const Bnd_OBB& anOBB2 = theCtx->OBB (aSI2.Shape(), theFuzzyValue);
if (anOBB1.IsOut (anOBB2))
continue;
}
Standard_Integer iX = BOPDS_Tools::TypeToInteger (aType1, aType2);
myLists(iX).Append (BOPDS_Pair (Min (aPair.ID1, aPair.ID2),
Max (aPair.ID1, aPair.ID2)));
}
}
}
在求交函數(shù)Intersect中使用BVH快速找出包圍盒有相交的每對(duì)Shape，并以索引的形式記錄下來(lái)。從這個(gè)函數(shù)中可以看出布爾操作是否使用OBB的選項(xiàng)的作用：當(dāng)不使用OBB時(shí)，只以AABB包圍盒來(lái)檢測(cè)相交的Shape；當(dāng)使用OBB時(shí)，在AABB的基礎(chǔ)上進(jìn)一步使用包圍更緊密的OBB來(lái)檢測(cè)相交，可以排除部分。當(dāng)相交的模型中以AABB檢測(cè)就能檢測(cè)出來(lái)的，再打開OBB選項(xiàng)，不會(huì)提高性能，反而會(huì)有所降低。為了減少這個(gè)影響，在IntTools_Context中緩存Caching這些OBB，避免構(gòu)造OBB帶來(lái)的性能損失。
3 Conclusion
布爾迭代器BOPDS_Iterator通過BVH找出求交的模型中每對(duì)包圍盒有相交的模型并提供遍歷每對(duì)包圍盒相交的模型的功能，為后面求交作準(zhǔn)備。從其代碼實(shí)現(xiàn)可以看出布爾選項(xiàng)使用OBB對(duì)性能提高是有限的，當(dāng)使用AABB能檢測(cè)出來(lái)的，再使用OBB會(huì)降低性能。當(dāng)使用AABB檢測(cè)出來(lái)相交，但OBB不相交的場(chǎng)景對(duì)性能提升明顯。
今日是“九一八事變”92周年，落后就要挨打，吾輩仍需努力。