0023106: BRepMesh_IncrementalMesh returns wrong status
[occt.git] / 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 <TopExp_Explorer.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::HDMapOfShapePairOfPolygon& theEdges,
133   const BRepMeshCol::HIMapOfInteger&            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   TopExp_Explorer aFaceExplorer(aFace, TopAbs_WIRE);
155   for (; aFaceExplorer.More(); aFaceExplorer.Next())
156   {
157     const TopoDS_Wire& aWire = TopoDS::Wire(aFaceExplorer.Current());
158
159     myWiresEdges.push_back(ListOfEdges());
160     ListOfEdges& aEdges = myWiresEdges.back();
161
162     // Start traversing the wires
163     BRepTools_WireExplorer aWireExplorer(aWire, aFace);
164     for (; aWireExplorer.More(); aWireExplorer.Next())
165     {
166       const TopoDS_Edge& aEdge   = aWireExplorer.Current();
167       TopAbs_Orientation aOrient = aEdge.Orientation();
168       if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
169         continue;
170
171       aEdges.Append(aEdge);
172     }
173
174     if (aEdges.IsEmpty())
175       myWiresEdges.pop_back();
176   }
177 }
178
179 //=======================================================================
180 //function : ReCompute
181 //purpose  : 
182 //=======================================================================
183 void BRepMesh_WireChecker::ReCompute(BRepMeshCol::HClassifier& theClassifier)
184 {
185   if (theClassifier.IsNull())
186     return;
187
188   theClassifier->Destroy();
189   myStatus = BRepMesh_NoError;
190   
191   SeqOfDWires aDWires;
192   if (!collectDiscretizedWires(aDWires))
193     return;
194
195   const Standard_Integer aNbWires = (Standard_Integer)aDWires.size();
196
197   BRepMeshCol::Array1OfSegmentsTree aWiresBiPoints(aNbWires);
198   fillSegmentsTree(aDWires, aWiresBiPoints);
199
200 #ifdef HAVE_TBB
201   Standard_Mutex aWireMutex;
202   BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints, 
203     &myStatus, &aWireMutex);
204
205   if (myIsInParallel && aNbWires > 1)
206   {
207     // check wires in parallel threads using TBB
208     tbb::parallel_for(tbb::blocked_range<Standard_Integer>(0, aNbWires), 
209       aIntChecker);
210   }
211   else
212   {
213 #else
214     BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints, &myStatus);
215 #endif
216     for (Standard_Integer i = 0; i < aNbWires; ++i)
217       aIntChecker(i);
218 #ifdef HAVE_TBB
219   }
220 #endif
221
222   if (myStatus == BRepMesh_SelfIntersectingWire)
223     return;
224
225   // Find holes
226   SeqOfDWires::iterator aDWiresIt = aDWires.begin();
227   for (; aDWiresIt != aDWires.end(); ++aDWiresIt)
228   {
229     const SeqOfPnt2d& aDWire = *aDWiresIt;
230     theClassifier->RegisterWire(aDWire, myTolUV, myUmin, myUmax, myVmin, myVmax);
231   }
232 }
233
234 //=======================================================================
235 //function : collectDiscretizedWires
236 //purpose  : 
237 //=======================================================================
238 Standard_Boolean BRepMesh_WireChecker::collectDiscretizedWires(
239   SeqOfDWires& theDWires)
240 {
241   // TODO: Collect disretized wires in parallel
242   SeqOfWireEdges::iterator aWireIt = myWiresEdges.begin();
243   for(; aWireIt != myWiresEdges.end(); ++aWireIt)
244   {
245     const ListOfEdges& aEdges = *aWireIt;
246     // For each wire we create a data map, linking vertices (only
247     // the ends of edges) with their positions in the sequence of
248     // all 2d points from this wire.
249     // When we meet some vertex for the second time - the piece
250     // of sequence is treated for a HOLE and quits the sequence.
251     // Actually, we must unbind the vertices belonging to the
252     // loop from the map, but since they can't appear twice on the
253     // valid wire, leave them for a little speed up.
254
255     SeqOfPnt2d    aSeqPnt2d;
256     DataMapIntInt aNodeInSeq;
257     Standard_Integer aFirstIndex = 0, aLastIndex = 0;
258
259     // Start traversing the wire
260     ListOfEdges::Iterator aEdgeIt(aEdges);
261     for (; aEdgeIt.More(); aEdgeIt.Next())
262     {
263       const TopoDS_Edge& aEdge   = aEdgeIt.Value();
264       TopAbs_Orientation aOrient = aEdge.Orientation();
265       if (!myEdges->IsBound(aEdge))
266         continue;
267
268       // Retrieve polygon
269       // Define the direction for adding points to aSeqPnt2d
270       Standard_Integer aStartId, aEndId, aIncrement;
271       const BRepMesh_PairOfPolygon& aPair = myEdges->Find(aEdge);
272       Handle(Poly_PolygonOnTriangulation) aNOD;
273       if (aOrient == TopAbs_FORWARD)
274       {
275         aNOD       = aPair.First();
276         aStartId   = 1;
277         aEndId     = aNOD->NbNodes();
278         aIncrement = 1;
279       }
280       else
281       {
282         aNOD       = aPair.Last();
283         aStartId   = aNOD->NbNodes();
284         aEndId     = 1;
285         aIncrement = -1;
286       }
287
288       const TColStd_Array1OfInteger& aIndices = aNOD->Nodes();
289       const Standard_Integer aFirstVertexId = myVertexMap->FindKey(aIndices(aStartId));
290       const Standard_Integer aLastVertexId  = myVertexMap->FindKey(aIndices(aEndId)  );
291
292       if (aFirstVertexId == aLastVertexId && (aEndId - aStartId) == aIncrement)
293       {
294         // case of continuous set of degenerated edges
295         aLastIndex = aLastVertexId;
296         continue;
297       }
298
299       if (aFirstIndex != 0)
300       {
301         if (aFirstVertexId != aLastIndex)
302         {
303           // there's a gap between edges
304           myStatus = BRepMesh_OpenWire;
305           return Standard_False;
306         }
307       }
308       else
309         aFirstIndex = aFirstVertexId;
310
311       aLastIndex = aLastVertexId;
312
313       // Record first vertex (to detect loops)
314       aNodeInSeq.Bind(aFirstVertexId, (aSeqPnt2d.Length() + 1));
315
316       // Add vertices in sequence
317       for (Standard_Integer i = aStartId; i != aEndId; i += aIncrement)
318       {
319         Standard_Integer aIndex = ((i == aStartId) ? 
320           aFirstVertexId : 
321           myVertexMap->FindKey(aIndices(i)));
322
323         aSeqPnt2d.Append(gp_Pnt2d(myStructure->GetNode(aIndex).Coord()));
324       }
325
326       // Now, is there a loop?
327       if (aNodeInSeq.IsBound(aLastVertexId))
328       {
329         // Yes, treat it separately as a hole
330         // Divide points into main wire and a loop
331         const Standard_Integer aIdxWireStart = aNodeInSeq(aLastVertexId);
332         if(aIdxWireStart < aSeqPnt2d.Length())
333         {
334           theDWires.push_back(SeqOfPnt2d());
335           SeqOfPnt2d& aWire = theDWires.back();
336           aSeqPnt2d.Split(aIdxWireStart, aWire);
337         }
338       }
339     }
340
341     if (aFirstIndex == 0)
342       continue;
343
344     // Isn't wire open?
345     if (aFirstIndex != aLastIndex || aSeqPnt2d.Length() > 1)
346     {
347       myStatus = BRepMesh_OpenWire;
348       return Standard_False;
349     }
350   }
351
352   return Standard_True;
353 }
354
355 //=======================================================================
356 //function : fillSegmentsTree
357 //purpose  :
358 //=======================================================================
359 void BRepMesh_WireChecker::fillSegmentsTree(
360   const SeqOfDWires&                 theDWires,
361   BRepMeshCol::Array1OfSegmentsTree& theWiresSegmentsTree)
362 {
363   const size_t aNbWires = theDWires.size();
364   for (size_t aWireIt = 0; aWireIt < aNbWires; ++aWireIt)
365   {
366     const SeqOfPnt2d&      aWire    = theDWires[aWireIt];
367     const Standard_Integer aWireLen = aWire.Size();
368
369     BRepMeshCol::HArray1OfSegments  aWireSegments = 
370       new BRepMeshCol::Array1OfSegments(aWireLen);
371
372     BRepMeshCol::HBndBox2dTree      aBndBoxTree   = 
373       new BRepMeshCol::BndBox2dTree;
374
375     BRepMeshCol::BndBox2dTreeFiller aBndBoxTreeFiller(*aBndBoxTree);
376
377     Standard_Real x1 = 0., y1 = 0., aXstart = 0., aYstart = 0.;
378     for (Standard_Integer aPntIt = 0; aPntIt <= aWireLen; ++aPntIt)
379     {
380       Standard_Real x2, y2;
381       // Obtain last point of the segment
382       if (aPntIt == aWireLen)
383       {
384         x2 = aXstart;
385         y2 = aYstart;
386       }
387       else
388       {
389         const gp_Pnt2d& aPnt = aWire(aPntIt + 1);
390         x2 = aPnt.X();
391         y2 = aPnt.Y();
392       }
393
394       // Build segment (bi-point)
395       if (aPntIt == 0)
396       {
397         aXstart = x2;
398         aYstart = y2;
399       }
400       else
401       {
402         gp_Pnt2d aStartPnt(x1, y1);
403         gp_Pnt2d   aEndPnt(x2, y2);
404        
405         const Standard_Integer aPointId = aPntIt - 1;
406         BRepMeshCol::Segment& aSegment = aWireSegments->at(aPointId);
407         aSegment.StartPnt = aStartPnt.XY();
408         aSegment.EndPnt   = aEndPnt.XY();
409
410         Bnd_Box2d aBox;
411         aBox.Add(aStartPnt);
412         aBox.Add(  aEndPnt);
413         aBndBoxTreeFiller.Add(aPointId, aBox);
414       }
415       x1 = x2;
416       y1 = y2;
417     }
418     aBndBoxTreeFiller.Fill();
419
420     BRepMeshCol::SegmentsTree& aSegmentsTree = theWiresSegmentsTree[aWireIt];
421     aSegmentsTree.first  = aWireSegments;
422     aSegmentsTree.second = aBndBoxTree;
423   }
424 }