布尔数据 边的相交

eryar@163.com

1 Introduction

在OpenCASCADE中对于边的相交分为三类：边与点，边与边，边与面，边与点的相交已经归结为点与边的相交处理了，边的相交主要处理边与边，边与面的相交。边与边、边与面的相交会引入一个新的数据结构-公共部分Common Part，用于保存重叠的公共部分数据。

2 Edge/Edge Interferences

对于两条边的相交是指在两条边的某些地方的距离小于边的容差之和，主要分为两种情况，一种是两条边只有一个交点的情况；一种是有重叠部分的情况；先看只有一个交点情况：

我们在DRAW中通过脚本构造最简单的情况来测试。

在处理边与边相交的函数BOPAlgo_PaveFiller::PerformEE()中，对每两条边调用BOPAlgo_EdgeEdge进行求交。从这里可以看到Pave Block的使用，相当于对每两条边上的每对Pave Block部分进行求交。这里有一些优化空间，目前是使用的两个循环处理，可以尝试使用BVH来提升一些性能。当每对Pave Block对应的点的索引号一致时，即每对Pave Block的端点重叠时，使用快速计算的算法来判断是否有重叠。

对于边的求交结果保存到BOPDS_InterfEE中，都会保存是哪两条边相交及相交的公共部分。对于相交于一点的公共部分的类型为TopAbs_VERTEX，对于有重叠部分的公共部分类型为TopAbs_EDGE：

当两边条有重叠部分时，如下图所示：

如何检测两条边的公共部分呢？在函数IntTools_EdgeEdge::IsCoincident()中实现：

//=======================================================================
//function :  IsCoincident
//purpose  : 
//=======================================================================
Standard_Boolean IntTools_EdgeEdge::IsCoincident() 
{
  Standard_Integer i, iCnt, aNbSeg, aNbP2;
  Standard_Real dT, aT1, aCoeff, aTresh, aD;
  Standard_Real aT11, aT12, aT21, aT22;
  GeomAPI_ProjectPointOnCurve aProjPC;
  gp_Pnt aP1;
  //
  aTresh=0.5;
  aNbSeg=23;
  myRange1.Range(aT11, aT12);
  myRange2.Range(aT21, aT22);
  //
  aProjPC.Init(myGeom2, aT21, aT22);
  //
  dT=(aT12-aT11)/aNbSeg;
  //
  iCnt=0;
  for(i=0; i <= aNbSeg; ++i) {
    aT1 = aT11+i*dT;
    myGeom1->D0(aT1, aP1);
    //
    aProjPC.Perform(aP1);
    aNbP2=aProjPC.NbPoints();
    if (!aNbP2) {
      continue;
    }
    //
    aD=aProjPC.LowerDistance();
    if(aD < myTol) {
      ++iCnt; 
    }
  }
  //
  aCoeff=(Standard_Real)iCnt/((Standard_Real)aNbSeg+1);
  return aCoeff > aTresh;
}

从上述代码可以看出，对于重叠部分的检测是将一条边根据检测范围分成23段采样点，计算每个点到另一条边的距离，满足条件的采样点的数量超过12个，基本认为是重叠的。从这里可以看出这样检测重叠稍微有点不严谨。固定采样点数量对于小段曲线来说数量过大，对于很长的曲线来说数量又偏小，这里有待提高。如果重叠，则将公共部分的数据保存起来：

对于测试的TCL脚本不会走这个通用的判断流程，会直接有IntTools_EdgeEdge::ComputeLineLine()函数来处理这种特殊情况：

从保存的数据可以看出，公共部分的相交类型为TopAbs_VERTEX，及交点分别在两条边上的参数。关于有重叠部分的两条边相交，同学们可以自行使用DRAW脚本来测试一下。

3 Edge/Face Interferences

边与面的相交会遇到和边与边相交类似的情况，即会有重叠部分Common Part。也分为两种情况，一种情况是边与面只有一个交点的情况，交点可能会有多个；一种情况是有重叠部分的情况。

我们可以在使用脚本来测试一下重叠的情况：

从代码中可以看出当边的端点在面上时，则会判断边与面会不会重叠Coincidence。判断逻辑与判断边是否重叠类似，都是使用固定23个采样点的方式处理，并加上定位器来判断点是否在面上，因为面上可能会有孔洞：

//=======================================================================
//function :  IsCoincident
//purpose  : 
//=======================================================================
Standard_Boolean IntTools_EdgeFace::IsCoincident() 
{
  Standard_Integer i, iCnt;
  Standard_Real dT, aT, aD, aT1, aT2, aU, aV;
  gp_Pnt aP;
  TopAbs_State aState;
  gp_Pnt2d aP2d;
  //
  GeomAPI_ProjectPointOnSurf& aProjector=myContext->ProjPS(myFace);
  Standard_Integer aNbSeg=23;
  if (myC.GetType() == GeomAbs_Line &&
      myS.GetType() == GeomAbs_Plane)
    aNbSeg = 2; // Check only three points for Line/Plane intersection
  const Standard_Real aTresh = 0.5;
  const Standard_Integer aTreshIdxF = RealToInt((aNbSeg+1)*0.25),
                         aTreshIdxL = RealToInt((aNbSeg+1)*0.75);
  const Handle(Geom_Surface) aSurf = BRep_Tool::Surface(myFace);
  aT1=myRange.First();
  aT2=myRange.Last();
  Standard_Real aBndShift = 0.01 * (aT2 - aT1);
  //Shifting first and last curve points in order to avoid projection
  //on surface boundary and rejection projection point with minimal distance
  aT1 += aBndShift;
  aT2 -= aBndShift;
  dT=(aT2-aT1)/aNbSeg;
  //
  Standard_Boolean isClassified = Standard_False;
  iCnt=0;
  for(i=0; i <= aNbSeg; ++i) {
    aT = aT1+i*dT;
    aP=myC.Value(aT);
    //
    aProjector.Perform(aP);
    if (!aProjector.IsDone()) {
      continue;
    }
    //
    aD=aProjector.LowerDistance();
    if (aD > myCriteria) {
      if (aD > 100. * myCriteria)
        return Standard_False;
      else
        continue;
    }
    //
    ++iCnt; 
    //We classify only three points: in the begin, in the 
    //end and in the middle of the edge.
    //However, exact middle point (when i == (aNbSeg + 1)/2)
    //can be unprojectable. Therefore, it will not be able to
    //be classified. Therefore, points with indexes in 
    //[aTreshIdxF, aTreshIdxL] range are made available 
    //for classification.
    //isClassified == TRUE if MIDDLE point has been chosen and
    //classified correctly.
    if(((0 < i) && (i < aTreshIdxF)) || ((aTreshIdxL < i ) && (i < aNbSeg)))
      continue;
    if(isClassified && (i != aNbSeg))
      continue;
    aProjector.LowerDistanceParameters(aU, aV);
    aP2d.SetX(aU);
    aP2d.SetY(aV);
    IntTools_FClass2d& aClass2d=myContext->FClass2d(myFace);
    aState = aClass2d.Perform(aP2d);
    if(aState == TopAbs_OUT)
      return Standard_False;
    if(i != 0)
      isClassified = Standard_True;
  }
  //
  const Standard_Real aCoeff=(Standard_Real)iCnt/((Standard_Real)aNbSeg+1);
  return (aCoeff > aTresh);
}

求交结果与边与边相交类型，会保存边与面的索引，及公共部分的数据。除了保存这些数据以外，还和点与面相交一样，更新面上的信息FaceInfo，即有哪些边在面上。

4 Conclusion

综上所述，边与边、边与面相交会得到公共部分Common Part，公共部分可能是点，也可能是重叠的边。在过滤相交的边与边、边与面时都有一定的优化空间，即使用BVH来加速检测相交部分。在快速判断边与边是否重叠、边与面是否重叠部分的代码采用固定数量的采样点的处理方式不太严谨。将相交的结果及过程数据都保存到BOPDS_DS中作为后面算法使用。