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