5def2f1be79ff1d0517ce2574f7903f94d4af47d
[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 <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 }