布爾數據 BOPDS_Iterator

eryar@163.com

1 Introduction

OpenCASCADE中新的布爾工具TKBO相對已經廢棄的TKBool代碼更規范，更易于理解。與ModelingData和ModelingAlgorithms大的模塊組織一樣，主要也是數據結構Data Structure+算法Algorithm的組織形式。

其中BOPDS為布爾中的數據結構部分，BOPAlgo為布爾中的算法部分。理解算法的前提是先理解數據結構DS(Data Structure)，所以先從數據結構入手，來深入理解布爾操作。本文先從簡單的數據結構BOPDS_Iterator開始對源碼進行分析。

2 BOPDS_Iterator

從類的注釋可以看出，迭代器BOPDS_Iterator有以下兩個功能：

- 找出包圍盒相交的Shape；

- 遍歷相交的一對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:

其中核心的算法在函數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)));
    }
  }
}

在求交函數Intersect中使用BVH快速找出包圍盒有相交的每對Shape，并以索引的形式記錄下來。從這個函數中可以看出布爾操作是否使用OBB的選項的作用：當不使用OBB時，只以AABB包圍盒來檢測相交的Shape；當使用OBB時，在AABB的基礎上進一步使用包圍更緊密的OBB來檢測相交，可以排除部分。當相交的模型中以AABB檢測就能檢測出來的，再打開OBB選項，不會提高性能，反而會有所降低。為了減少這個影響，在IntTools_Context中緩存Caching這些OBB，避免構造OBB帶來的性能損失。

3 Conclusion

布爾迭代器BOPDS_Iterator通過BVH找出求交的模型中每對包圍盒有相交的模型并提供遍歷每對包圍盒相交的模型的功能，為后面求交作準備。從其代碼實現可以看出布爾選項使用OBB對性能提高是有限的，當使用AABB能檢測出來的，再使用OBB會降低性能。當使用AABB檢測出來相交，但OBB不相交的場景對性能提升明顯。

今日是“九一八事變”92周年，落后就要挨打，吾輩仍需努力。