src/BRepExtrema/BRepExtrema_SelfIntersection.cxx

   1 // Created on: 2015-04-26
   2 // Created by: Denis BOGOLEPOV
   3 // Copyright (c) 2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <BRepExtrema_SelfIntersection.hxx>
  17
  18 #include <Precision.hxx>
  19 #include <TopExp_Explorer.hxx>
  20
  21 //=======================================================================
  22 //function : BRepExtrema_SelfIntersection
  23 //purpose  :
  24 //=======================================================================
  25 BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const Standard_Real theTolerance)
  26 : myTolerance (theTolerance)
  27 {
  28   myIsInit = Standard_False;
  29 }
  30
  31 //=======================================================================
  32 //function : BRepExtrema_SelfIntersection
  33 //purpose  :
  34 //=======================================================================
  35 BRepExtrema_SelfIntersection::BRepExtrema_SelfIntersection (const TopoDS_Shape& theShape, const Standard_Real theTolerance)
  36 : myTolerance (theTolerance)
  37 {
  38   LoadShape (theShape);
  39 }
  40
  41 //=======================================================================
  42 //function : LoadShape
  43 //purpose  :
  44 //=======================================================================
  45 Standard_Boolean BRepExtrema_SelfIntersection::LoadShape (const TopoDS_Shape& theShape)
  46 {
  47   myFaceList.Clear();
  48
  49   for (TopExp_Explorer anIter (theShape, TopAbs_FACE); anIter.More(); anIter.Next())
  50   {
  51     myFaceList.Append (static_cast<const TopoDS_Face&> (anIter.Current()));
  52   }
  53
  54   if (myElementSet.IsNull())
  55   {
  56     myElementSet = new BRepExtrema_TriangleSet;
  57   }
  58
  59   myIsInit = myElementSet->Init (myFaceList);
  60
  61   if (myIsInit)
  62   {
  63     myOverlapTool.LoadTriangleSets (myElementSet,
  64                                     myElementSet);
  65   }
  66
  67   return myIsInit;
  68 }
  69
  70 #define ZERO_VEC BVH_Vec3d (0.0, 0.0, 0.0)
  71
  72 namespace
  73 {
  74   // =======================================================================
  75   // function : ccw
  76   // purpose  : Check if triple is in counterclockwise order
  77   // =======================================================================
  78   Standard_Boolean ccw (const BVH_Vec3d& theVertex0,
  79                         const BVH_Vec3d& theVertex1,
  80                         const BVH_Vec3d& theVertex2,
  81                         const Standard_Integer theX,
  82                         const Standard_Integer theY)
  83 {
  84   const Standard_Real aSum =
  85     (theVertex1[theX] - theVertex0[theX]) * (theVertex1[theY] + theVertex0[theY]) +
  86     (theVertex2[theX] - theVertex1[theX]) * (theVertex2[theY] + theVertex1[theY]) +
  87     (theVertex0[theX] - theVertex2[theX]) * (theVertex0[theY] + theVertex2[theY]);
  88
  89   return aSum < 0.0;
  90 }
  91
  92   // =======================================================================
  93   // function : rayInsideAngle
  94   // purpose  : Check the given ray is inside the angle
  95   // =======================================================================
  96   Standard_Boolean rayInsideAngle (const BVH_Vec3d&   theDirec,
  97                                    const BVH_Vec3d&   theEdge0,
  98                                    const BVH_Vec3d&   theEdge1,
  99                                    const Standard_Integer theX,
 100                                    const Standard_Integer theY)
 101 {
 102   const Standard_Boolean aCCW = ccw (ZERO_VEC, theEdge0, theEdge1, theX, theY);
 103
 104   return ccw (ZERO_VEC, theEdge0, theDirec, theX, theY) == aCCW
 105       && ccw (ZERO_VEC, theDirec, theEdge1, theX, theY) == aCCW;
 106 }
 107
 108   // =======================================================================
 109   // function : getProjectionAxes
 110   // purpose  :
 111   // =======================================================================
 112   void getProjectionAxes (const BVH_Vec3d&  theNorm,
 113                           Standard_Integer& theAxisX,
 114                           Standard_Integer& theAxisY)
 115 {
 116   if (fabs (theNorm[0]) > fabs (theNorm[1]))
 117   {
 118     theAxisX = fabs (theNorm[0]) > fabs (theNorm[2]) ? 1 : 0;
 119     theAxisY = fabs (theNorm[0]) > fabs (theNorm[2]) ? 2 : 1;
 120   }
 121   else
 122   {
 123     theAxisX = fabs (theNorm[1]) > fabs (theNorm[2]) ? 0 : 0;
 124     theAxisY = fabs (theNorm[1]) > fabs (theNorm[2]) ? 2 : 1;
 125   }
 126 }
 127 }
 128
 129 //=======================================================================
 130 //function : isRegularSharedVertex
 131 //purpose  :
 132 //=======================================================================
 133 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::isRegularSharedVertex (const BVH_Vec3d& theSharedVert,
 134                                                                                              const BVH_Vec3d& theTrng0Vtxs1,
 135                                                                                              const BVH_Vec3d& theTrng0Vtxs2,
 136                                                                                              const BVH_Vec3d& theTrng1Vtxs1,
 137                                                                                              const BVH_Vec3d& theTrng1Vtxs2)
 138 {
 139   const BVH_Vec3d aTrng0Edges[] = { (theTrng0Vtxs1 - theSharedVert).Normalized(),
 140                                     (theTrng0Vtxs2 - theSharedVert).Normalized() };
 141
 142   const BVH_Vec3d aTrng1Edges[] = { (theTrng1Vtxs1 - theSharedVert).Normalized(),
 143                                     (theTrng1Vtxs2 - theSharedVert).Normalized() };
 144
 145   const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aTrng0Edges[0], aTrng0Edges[1]);
 146   const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aTrng1Edges[0], aTrng1Edges[1]);
 147
 148   BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal,
 149                                            aTrng1Normal);
 150
 151   Standard_Integer anX;
 152   Standard_Integer anY;
 153
 154   if (aCrossLine.SquareModulus() < Precision::SquareConfusion()) // coplanar case
 155   {
 156     getProjectionAxes (aTrng0Normal, anX, anY);
 157
 158     if (rayInsideAngle (aTrng1Edges[0], aTrng0Edges[0], aTrng0Edges[1], anX, anY)
 159      || rayInsideAngle (aTrng1Edges[1], aTrng0Edges[0], aTrng0Edges[1], anX, anY)
 160      || rayInsideAngle (aTrng0Edges[0], aTrng1Edges[0], aTrng1Edges[1], anX, anY)
 161      || rayInsideAngle (aTrng0Edges[1], aTrng1Edges[0], aTrng1Edges[1], anX, anY))
 162     {
 163       return BRepExtrema_ElementFilter::Overlap;
 164     }
 165
 166     return BRepExtrema_ElementFilter::NoCheck;
 167   }
 168   else // shared line should lie outside at least one triangle
 169   {
 170     getProjectionAxes (aTrng0Normal, anX, anY);
 171
 172     const Standard_Boolean aPosOutTrgn0 = !rayInsideAngle ( aCrossLine, aTrng0Edges[0], aTrng0Edges[1], anX, anY);
 173     const Standard_Boolean aNegOutTrgn0 = !rayInsideAngle (-aCrossLine, aTrng0Edges[0], aTrng0Edges[1], anX, anY);
 174
 175     Standard_ASSERT_RAISE (aPosOutTrgn0 || aNegOutTrgn0,
 176       "Failed to detect if shared vertex is regular or not");
 177
 178     if (aPosOutTrgn0 && aNegOutTrgn0)
 179     {
 180       return BRepExtrema_ElementFilter::NoCheck;
 181     }
 182
 183     getProjectionAxes (aTrng1Normal, anX, anY);
 184
 185     const Standard_Boolean aPosOutTrgn1 = !rayInsideAngle ( aCrossLine, aTrng1Edges[0], aTrng1Edges[1], anX, anY);
 186     const Standard_Boolean aNegOutTrgn1 = !rayInsideAngle (-aCrossLine, aTrng1Edges[0], aTrng1Edges[1], anX, anY);
 187
 188     Standard_ASSERT_RAISE (aPosOutTrgn1 || aNegOutTrgn1,
 189       "Failed to detect if shared vertex is regular or not");
 190
 191     if (aPosOutTrgn1 && aNegOutTrgn1)
 192     {
 193       return BRepExtrema_ElementFilter::NoCheck;
 194     }
 195
 196     return (aPosOutTrgn0 || aPosOutTrgn1) && (aNegOutTrgn0 || aNegOutTrgn1) ?
 197      BRepExtrema_ElementFilter::NoCheck : BRepExtrema_ElementFilter::Overlap;
 198   }
 199 }
 200
 201 //=======================================================================
 202 //function : isRegularSharedEdge
 203 //purpose  :
 204 //=======================================================================
 205 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::isRegularSharedEdge (const BVH_Vec3d& theTrng0Vtxs0,
 206                                                                                            const BVH_Vec3d& theTrng0Vtxs1,
 207                                                                                            const BVH_Vec3d& theTrng0Vtxs2,
 208                                                                                            const BVH_Vec3d& theTrng1Vtxs2)
 209 {
 210   const BVH_Vec3d aSharedEdge = (theTrng0Vtxs1 - theTrng0Vtxs0).Normalized();
 211
 212   const BVH_Vec3d aUniqueEdges[] = { (theTrng0Vtxs2 - theTrng0Vtxs0).Normalized(),
 213                                      (theTrng1Vtxs2 - theTrng0Vtxs0).Normalized() };
 214
 215   const BVH_Vec3d aTrng0Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[0]);
 216   const BVH_Vec3d aTrng1Normal = BVH_Vec3d::Cross (aSharedEdge, aUniqueEdges[1]);
 217
 218   BVH_Vec3d aCrossLine = BVH_Vec3d::Cross (aTrng0Normal,
 219                                            aTrng1Normal);
 220
 221   if (aCrossLine.SquareModulus() > Precision::SquareConfusion()) // non-coplanar case
 222   {
 223     return BRepExtrema_ElementFilter::NoCheck;
 224   }
 225
 226   Standard_Integer anX;
 227   Standard_Integer anY;
 228
 229   getProjectionAxes (aTrng0Normal, anX, anY);
 230
 231   return ccw (ZERO_VEC, aSharedEdge, aUniqueEdges[0], anX, anY) !=
 232          ccw (ZERO_VEC, aSharedEdge, aUniqueEdges[1], anX, anY) ? BRepExtrema_ElementFilter::NoCheck
 233                                                             : BRepExtrema_ElementFilter::Overlap;
 234 }
 235
 236 //=======================================================================
 237 //function : PreCheckElements
 238 //purpose  :
 239 //=======================================================================
 240 BRepExtrema_ElementFilter::FilterResult BRepExtrema_SelfIntersection::PreCheckElements (const Standard_Integer theIndex1,
 241                                                                                         const Standard_Integer theIndex2)
 242 {
 243   if (myElementSet->GetFaceID (theIndex1) == myElementSet->GetFaceID (theIndex2))
 244   {
 245     return BRepExtrema_ElementFilter::NoCheck; // triangles are from the same face
 246   }
 247
 248   BVH_Vec3d aTrng0Vtxs[3];
 249   BVH_Vec3d aTrng1Vtxs[3];
 250
 251   myElementSet->GetVertices (theIndex1,
 252                              aTrng0Vtxs[0],
 253                              aTrng0Vtxs[1],
 254                              aTrng0Vtxs[2]);
 255
 256   myElementSet->GetVertices (theIndex2,
 257                              aTrng1Vtxs[0],
 258                              aTrng1Vtxs[1],
 259                              aTrng1Vtxs[2]);
 260
 261   std::vector<std::pair<Standard_Integer, Standard_Integer> > aSharedVtxs;
 262
 263   for (Standard_Integer aVertIdx1 = 0; aVertIdx1 < 3; ++aVertIdx1)
 264   {
 265     for (Standard_Integer aVertIdx2 = 0; aVertIdx2 < 3; ++aVertIdx2)
 266     {
 267       if ((aTrng0Vtxs[aVertIdx1] - aTrng1Vtxs[aVertIdx2]).SquareModulus() < Precision::SquareConfusion())
 268       {
 269         aSharedVtxs.push_back (std::pair<Standard_Integer, Standard_Integer> (aVertIdx1, aVertIdx2));
 270
 271         break; // go to next vertex of the 1st triangle
 272       }
 273     }
 274   }
 275
 276   if (aSharedVtxs.size() == 2) // check shared edge
 277   {
 278     return isRegularSharedEdge (aTrng0Vtxs[aSharedVtxs[0].first],
 279                                 aTrng0Vtxs[aSharedVtxs[1].first],
 280                                 aTrng0Vtxs[3 - aSharedVtxs[0]. first - aSharedVtxs[1]. first],
 281                                 aTrng1Vtxs[3 - aSharedVtxs[0].second - aSharedVtxs[1].second]);
 282   }
 283   else if (aSharedVtxs.size() == 1) // check shared vertex
 284   {
 285     std::swap (*aTrng0Vtxs, aTrng0Vtxs[aSharedVtxs.front(). first]);
 286     std::swap (*aTrng1Vtxs, aTrng1Vtxs[aSharedVtxs.front().second]);
 287
 288     return isRegularSharedVertex (aTrng0Vtxs[0],
 289                                   aTrng0Vtxs[1],
 290                                   aTrng0Vtxs[2],
 291                                   aTrng1Vtxs[1],
 292                                   aTrng1Vtxs[2]);
 293   }
 294
 295   return BRepExtrema_ElementFilter::DoCheck;
 296 }
 297
 298 //=======================================================================
 299 //function : Perform
 300 //purpose  :
 301 //=======================================================================
 302 void BRepExtrema_SelfIntersection::Perform()
 303 {
 304   if (!myIsInit || myOverlapTool.IsDone())
 305   {
 306     return;
 307   }
 308
 309   myOverlapTool.SetElementFilter (this);
 310
 311   myOverlapTool.Perform (myTolerance);
 312 }