src/BRepMesh/BRepMesh_WireChecker.cxx

   1 // Created on: 2014-06-03
   2 // Created by: Oleg AGASHIN
   3 // Copyright (c) 1997-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <BRepMesh_WireChecker.hxx>
  18
  19 #include <Precision.hxx>
  20 #include <TColStd_Array1OfInteger.hxx>
  21 #include <gp_Pnt2d.hxx>
  22 #include <BRepTools_WireExplorer.hxx>
  23 #include <TopAbs_Orientation.hxx>
  24 #include <TopoDS.hxx>
  25 #include <TopoDS_Iterator.hxx>
  26 #include <Poly_PolygonOnTriangulation.hxx>
  27 #include <BRepMesh_PairOfPolygon.hxx>
  28 #include <TColStd_SequenceOfInteger.hxx>
  29 #include <TColStd_IndexedMapOfInteger.hxx>
  30 #include <BRepMesh_DataStructureOfDelaun.hxx>
  31 #include <BRepMesh_Classifier.hxx>
  32 #include <BRepMesh_WireInterferenceChecker.hxx>
  33
  34 #ifdef HAVE_TBB
  35   // paralleling using Intel TBB
  36   #include <tbb/parallel_for.h>
  37   #include <tbb/blocked_range.h>
  38 #endif
  39
  40 //=======================================================================
  41 //function : Selector::Constructor
  42 //purpose  :
  43 //=======================================================================
  44 BRepMesh_WireChecker::BndBox2dTreeSelector::BndBox2dTreeSelector(
  45   const Standard_Integer theReservedSize)
  46   : mySkippedIndex(-1),
  47     myIndices(0, theReservedSize - 1),
  48     myIndicesNb(0)
  49 {
  50 }
  51
  52 //=======================================================================
  53 //function : Reject
  54 //purpose  :
  55 //=======================================================================
  56 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Reject(
  57   const Bnd_Box2d& theBox2D) const
  58 {
  59   return myBox2D.IsOut(theBox2D);
  60 }
  61
  62 //=======================================================================
  63 //function : Accept
  64 //purpose  :
  65 //=======================================================================
  66 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Accept(
  67   const Standard_Integer& theIndex)
  68 {
  69   if (theIndex <= mySkippedIndex)
  70     return Standard_False;
  71
  72   myIndices(myIndicesNb++) = theIndex;
  73   return Standard_True;
  74 }
  75
  76 //=======================================================================
  77 //function : Clear
  78 //purpose  :
  79 //=======================================================================
  80 void BRepMesh_WireChecker::BndBox2dTreeSelector::Clear()
  81 {
  82   mySkippedIndex = -1;
  83   myIndicesNb    = 0;
  84 }
  85
  86 //=======================================================================
  87 //function : SetBox
  88 //purpose  :
  89 //=======================================================================
  90 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetBox(
  91   const Bnd_Box2d& theBox2D)
  92 {
  93   myBox2D = theBox2D;
  94 }
  95
  96 //=======================================================================
  97 //function : Clear
  98 //purpose  :
  99 //=======================================================================
 100 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetSkippedIndex(
 101   const Standard_Integer theIndex)
 102 {
 103   mySkippedIndex = theIndex;
 104 }
 105
 106 //=======================================================================
 107 //function : Indices
 108 //purpose  :
 109 //=======================================================================
 110 const BRepMeshCol::Array1OfInteger&
 111   BRepMesh_WireChecker::BndBox2dTreeSelector::Indices() const
 112 {
 113   return myIndices;
 114 }
 115
 116 //=======================================================================
 117 //function : IndicesNb
 118 //purpose  :
 119 //=======================================================================
 120 Standard_Integer BRepMesh_WireChecker::BndBox2dTreeSelector::IndicesNb() const
 121 {
 122   return myIndicesNb;
 123 }
 124
 125 //=======================================================================
 126 //function : Constructor
 127 //purpose  :
 128 //=======================================================================
 129 BRepMesh_WireChecker::BRepMesh_WireChecker(
 130   const TopoDS_Face&                            theFace,
 131   const Standard_Real                           theTolUV,
 132   const BRepMeshCol::DMapOfShapePairOfPolygon&  theEdges,
 133   const TColStd_IndexedMapOfInteger&            theVertexMap,
 134   const Handle(BRepMesh_DataStructureOfDelaun)& theStructure,
 135   const Standard_Real                           theUmin,
 136   const Standard_Real                           theUmax,
 137   const Standard_Real                           theVmin,
 138   const Standard_Real                           theVmax,
 139   const Standard_Boolean                        isInParallel)
 140   : myTolUV(theTolUV),
 141     myEdges(theEdges),
 142     myVertexMap(theVertexMap),
 143     myStructure(theStructure),
 144     myUmin(theUmin),
 145     myUmax(theUmax),
 146     myVmin(theVmin),
 147     myVmax(theVmax),
 148     myStatus(BRepMesh_NoError),
 149     myIsInParallel(isInParallel)
 150 {
 151   TopoDS_Face aFace = theFace;
 152   aFace.Orientation(TopAbs_FORWARD);
 153
 154   TopoDS_Iterator aFaceExplorer(aFace);
 155   for (; aFaceExplorer.More(); aFaceExplorer.Next())
 156   {
 157     const TopoDS_Shape& aWire = aFaceExplorer.Value();
 158     if (aWire.ShapeType() != TopAbs_WIRE)
 159       continue;
 160
 161     myWiresEdges.push_back(ListOfEdges());
 162     ListOfEdges& aEdges = myWiresEdges.back();
 163
 164     // Start traversing the wires
 165     BRepTools_WireExplorer aWireExplorer(TopoDS::Wire(aWire), aFace);
 166     for (; aWireExplorer.More(); aWireExplorer.Next())
 167     {
 168       const TopoDS_Edge& aEdge   = aWireExplorer.Current();
 169       TopAbs_Orientation aOrient = aEdge.Orientation();
 170       if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
 171         continue;
 172
 173       aEdges.Append(aEdge);
 174     }
 175
 176     if (aEdges.IsEmpty())
 177       myWiresEdges.pop_back();
 178   }
 179 }
 180
 181 //=======================================================================
 182 //function : ReCompute
 183 //purpose  :
 184 //=======================================================================
 185 void BRepMesh_WireChecker::ReCompute(BRepMeshCol::HClassifier& theClassifier)
 186 {
 187   if (theClassifier.IsNull())
 188     return;
 189
 190   theClassifier->Destroy();
 191   myStatus = BRepMesh_NoError;
 192
 193   SeqOfDWires aDWires;
 194   if (!collectDiscretizedWires(aDWires))
 195     return;
 196
 197   const Standard_Integer aNbWires = (Standard_Integer)aDWires.size();
 198
 199   BRepMeshCol::Array1OfSegmentsTree aWiresBiPoints(aNbWires);
 200   fillSegmentsTree(aDWires, aWiresBiPoints);
 201
 202 #ifdef HAVE_TBB
 203   Standard_Mutex aWireMutex;
 204   BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints,
 205     &myStatus, &aWireMutex);
 206
 207   if (myIsInParallel && aNbWires > 1)
 208   {
 209     // check wires in parallel threads using TBB
 210     tbb::parallel_for(tbb::blocked_range<Standard_Integer>(0, aNbWires),
 211       aIntChecker);
 212   }
 213   else
 214   {
 215 #else
 216     BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints, &myStatus);
 217 #endif
 218     for (Standard_Integer i = 0; i < aNbWires; ++i)
 219       aIntChecker(i);
 220 #ifdef HAVE_TBB
 221   }
 222 #endif
 223
 224   if (myStatus == BRepMesh_SelfIntersectingWire)
 225     return;
 226
 227   // Find holes
 228   SeqOfDWires::iterator aDWiresIt = aDWires.begin();
 229   for (; aDWiresIt != aDWires.end(); ++aDWiresIt)
 230   {
 231     const SeqOfPnt2d& aDWire = *aDWiresIt;
 232     theClassifier->RegisterWire(aDWire, myTolUV, myUmin, myUmax, myVmin, myVmax);
 233   }
 234 }
 235
 236 //=======================================================================
 237 //function : collectDiscretizedWires
 238 //purpose  :
 239 //=======================================================================
 240 Standard_Boolean BRepMesh_WireChecker::collectDiscretizedWires(
 241   SeqOfDWires& theDWires)
 242 {
 243   // TODO: Collect disretized wires in parallel
 244   SeqOfWireEdges::iterator aWireIt = myWiresEdges.begin();
 245   for(; aWireIt != myWiresEdges.end(); ++aWireIt)
 246   {
 247     const ListOfEdges& aEdges = *aWireIt;
 248     // For each wire we create a data map, linking vertices (only
 249     // the ends of edges) with their positions in the sequence of
 250     // all 2d points from this wire.
 251     // When we meet some vertex for the second time - the piece
 252     // of sequence is treated for a HOLE and quits the sequence.
 253     // Actually, we must unbind the vertices belonging to the
 254     // loop from the map, but since they can't appear twice on the
 255     // valid wire, leave them for a little speed up.
 256
 257     SeqOfPnt2d    aSeqPnt2d;
 258     DataMapIntInt aNodeInSeq;
 259     Standard_Integer aFirstIndex = 0, aLastIndex = 0;
 260
 261     // Start traversing the wire
 262     ListOfEdges::Iterator aEdgeIt(aEdges);
 263     for (; aEdgeIt.More(); aEdgeIt.Next())
 264     {
 265       const TopoDS_Edge& aEdge   = aEdgeIt.Value();
 266       TopAbs_Orientation aOrient = aEdge.Orientation();
 267       if (!myEdges.IsBound(aEdge))
 268         continue;
 269
 270       // Retrieve polygon
 271       // Define the direction for adding points to aSeqPnt2d
 272       Standard_Integer aStartId, aEndId, aIncrement;
 273       const BRepMesh_PairOfPolygon& aPair = myEdges.Find(aEdge);
 274       Handle(Poly_PolygonOnTriangulation) aNOD;
 275       if (aOrient == TopAbs_FORWARD)
 276       {
 277         aNOD       = aPair.First();
 278         aStartId   = 1;
 279         aEndId     = aNOD->NbNodes();
 280         aIncrement = 1;
 281       }
 282       else
 283       {
 284         aNOD       = aPair.Last();
 285         aStartId   = aNOD->NbNodes();
 286         aEndId     = 1;
 287         aIncrement = -1;
 288       }
 289
 290       const TColStd_Array1OfInteger& aIndices = aNOD->Nodes();
 291       const Standard_Integer aFirstVertexId = myVertexMap.FindKey(aIndices(aStartId));
 292       const Standard_Integer aLastVertexId  = myVertexMap.FindKey(aIndices(aEndId)  );
 293
 294       if (aFirstVertexId == aLastVertexId && (aEndId - aStartId) == aIncrement)
 295       {
 296         // case of continuous set of degenerated edges
 297         aLastIndex = aLastVertexId;
 298         continue;
 299       }
 300
 301       if (aFirstIndex != 0)
 302       {
 303         if (aFirstVertexId != aLastIndex)
 304         {
 305           // there's a gap between edges
 306           myStatus = BRepMesh_OpenWire;
 307           return Standard_False;
 308         }
 309       }
 310       else
 311         aFirstIndex = aFirstVertexId;
 312
 313       aLastIndex = aLastVertexId;
 314
 315       // Record first vertex (to detect loops)
 316       aNodeInSeq.Bind(aFirstVertexId, (aSeqPnt2d.Length() + 1));
 317
 318       // Add vertices in sequence
 319       for (Standard_Integer i = aStartId; i != aEndId; i += aIncrement)
 320       {
 321         Standard_Integer aIndex = ((i == aStartId) ?
 322           aFirstVertexId :
 323           myVertexMap.FindKey(aIndices(i)));
 324
 325         aSeqPnt2d.Append(gp_Pnt2d(myStructure->GetNode(aIndex).Coord()));
 326       }
 327
 328       // Now, is there a loop?
 329       if (aNodeInSeq.IsBound(aLastVertexId))
 330       {
 331         // Yes, treat it separately as a hole
 332         // Divide points into main wire and a loop
 333         const Standard_Integer aIdxWireStart = aNodeInSeq(aLastVertexId);
 334         if(aIdxWireStart < aSeqPnt2d.Length())
 335         {
 336           theDWires.push_back(SeqOfPnt2d());
 337           SeqOfPnt2d& aWire = theDWires.back();
 338           aSeqPnt2d.Split(aIdxWireStart, aWire);
 339         }
 340       }
 341     }
 342
 343     if (aFirstIndex == 0)
 344       continue;
 345
 346     // Isn't wire open?
 347     if (aFirstIndex != aLastIndex || aSeqPnt2d.Length() > 1)
 348     {
 349       myStatus = BRepMesh_OpenWire;
 350       return Standard_False;
 351     }
 352   }
 353
 354   return Standard_True;
 355 }
 356
 357 //=======================================================================
 358 //function : fillSegmentsTree
 359 //purpose  :
 360 //=======================================================================
 361 void BRepMesh_WireChecker::fillSegmentsTree(
 362   const SeqOfDWires&                 theDWires,
 363   BRepMeshCol::Array1OfSegmentsTree& theWiresSegmentsTree)
 364 {
 365   const size_t aNbWires = theDWires.size();
 366   for (size_t aWireIt = 0; aWireIt < aNbWires; ++aWireIt)
 367   {
 368     const SeqOfPnt2d&      aWire    = theDWires[aWireIt];
 369     const Standard_Integer aWireLen = aWire.Size();
 370
 371     BRepMeshCol::HArray1OfSegments  aWireSegments =
 372       new BRepMeshCol::Array1OfSegments(aWireLen);
 373
 374     BRepMeshCol::HBndBox2dTree      aBndBoxTree   =
 375       new BRepMeshCol::BndBox2dTree;
 376
 377     BRepMeshCol::BndBox2dTreeFiller aBndBoxTreeFiller(*aBndBoxTree);
 378
 379     Standard_Real x1 = 0., y1 = 0., aXstart = 0., aYstart = 0.;
 380     for (Standard_Integer aPntIt = 0; aPntIt <= aWireLen; ++aPntIt)
 381     {
 382       Standard_Real x2, y2;
 383       // Obtain last point of the segment
 384       if (aPntIt == aWireLen)
 385       {
 386         x2 = aXstart;
 387         y2 = aYstart;
 388       }
 389       else
 390       {
 391         const gp_Pnt2d& aPnt = aWire(aPntIt + 1);
 392         x2 = aPnt.X();
 393         y2 = aPnt.Y();
 394       }
 395
 396       // Build segment (bi-point)
 397       if (aPntIt == 0)
 398       {
 399         aXstart = x2;
 400         aYstart = y2;
 401       }
 402       else
 403       {
 404         gp_Pnt2d aStartPnt(x1, y1);
 405         gp_Pnt2d   aEndPnt(x2, y2);
 406
 407         const Standard_Integer aPointId = aPntIt - 1;
 408         BRepMeshCol::Segment& aSegment = aWireSegments->at(aPointId);
 409         aSegment.StartPnt = aStartPnt.XY();
 410         aSegment.EndPnt   = aEndPnt.XY();
 411
 412         Bnd_Box2d aBox;
 413         aBox.Add(aStartPnt);
 414         aBox.Add(  aEndPnt);
 415         aBndBoxTreeFiller.Add(aPointId, aBox);
 416       }
 417       x1 = x2;
 418       y1 = y2;
 419     }
 420     aBndBoxTreeFiller.Fill();
 421
 422     BRepMeshCol::SegmentsTree& aSegmentsTree = theWiresSegmentsTree[aWireIt];
 423     aSegmentsTree.first  = aWireSegments;
 424     aSegmentsTree.second = aBndBoxTree;
 425   }
 426 }