布尔数据 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周年，落后就要挨打，吾辈仍需努力。