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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <BRepMesh_WireChecker.hxx>
19 #include <Precision.hxx>
20 #include <TColStd_Array1OfInteger.hxx>
21 #include <gp_Pnt2d.hxx>
22 #include <BRepTools_WireExplorer.hxx>
23 #include <TopAbs_Orientation.hxx>
25 #include <TopoDS_Iterator.hxx>
26 #include <Poly_PolygonOnTriangulation.hxx>
27 #include <BRepMesh_PairOfPolygon.hxx>
28 #include <BRepMesh_DataMapOfShapePairOfPolygon.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>
36 // paralleling using Intel TBB
37 #include <tbb/parallel_for.h>
38 #include <tbb/blocked_range.h>
41 //=======================================================================
42 //function : Selector::Constructor
44 //=======================================================================
45 BRepMesh_WireChecker::BndBox2dTreeSelector::BndBox2dTreeSelector(
46 const Standard_Integer theReservedSize)
48 myIndices(0, theReservedSize - 1),
53 //=======================================================================
56 //=======================================================================
57 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Reject(
58 const Bnd_Box2d& theBox2D) const
60 return myBox2D.IsOut(theBox2D);
63 //=======================================================================
66 //=======================================================================
67 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Accept(
68 const Standard_Integer& theIndex)
70 if (theIndex <= mySkippedIndex)
71 return Standard_False;
73 myIndices(myIndicesNb++) = theIndex;
77 //=======================================================================
80 //=======================================================================
81 void BRepMesh_WireChecker::BndBox2dTreeSelector::Clear()
87 //=======================================================================
90 //=======================================================================
91 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetBox(
92 const Bnd_Box2d& theBox2D)
97 //=======================================================================
100 //=======================================================================
101 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetSkippedIndex(
102 const Standard_Integer theIndex)
104 mySkippedIndex = theIndex;
107 //=======================================================================
110 //=======================================================================
111 const BRepMesh_WireChecker::ArrayOfInteger&
112 BRepMesh_WireChecker::BndBox2dTreeSelector::Indices() const
117 //=======================================================================
118 //function : IndicesNb
120 //=======================================================================
121 Standard_Integer BRepMesh_WireChecker::BndBox2dTreeSelector::IndicesNb() const
126 //=======================================================================
127 //function : Constructor
129 //=======================================================================
130 BRepMesh_WireChecker::BRepMesh_WireChecker(
131 const TopoDS_Face& theFace,
132 const Standard_Real theTolUV,
133 const BRepMesh_DataMapOfShapePairOfPolygon& theEdges,
134 const TColStd_IndexedMapOfInteger& theVertexMap,
135 const Handle(BRepMesh_DataStructureOfDelaun)& theStructure,
136 const Standard_Real theUmin,
137 const Standard_Real theUmax,
138 const Standard_Real theVmin,
139 const Standard_Real theVmax,
140 const Standard_Boolean isInParallel)
143 myVertexMap(theVertexMap),
144 myStructure(theStructure),
149 myStatus(BRepMesh_NoError),
150 myIsInParallel(isInParallel)
152 TopoDS_Face aFace = theFace;
153 aFace.Orientation(TopAbs_FORWARD);
155 TopoDS_Iterator aFaceExplorer(aFace);
156 for (; aFaceExplorer.More(); aFaceExplorer.Next())
158 const TopoDS_Shape& aWire = aFaceExplorer.Value();
159 if (aWire.ShapeType() != TopAbs_WIRE)
162 myWiresEdges.push_back(ListOfEdges());
163 ListOfEdges& aEdges = myWiresEdges.back();
165 // Start traversing the wires
166 BRepTools_WireExplorer aWireExplorer(TopoDS::Wire(aWire), aFace);
167 for (; aWireExplorer.More(); aWireExplorer.Next())
169 const TopoDS_Edge& aEdge = aWireExplorer.Current();
170 TopAbs_Orientation aOrient = aEdge.Orientation();
171 if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
174 aEdges.Append(aEdge);
177 if (aEdges.IsEmpty())
178 myWiresEdges.pop_back();
182 //=======================================================================
183 //function : ReCompute
185 //=======================================================================
186 void BRepMesh_WireChecker::ReCompute(BRepMesh_ClassifierPtr& theClassifier)
188 if (theClassifier.IsNull())
191 theClassifier->Destroy();
192 myStatus = BRepMesh_NoError;
195 if (!collectDiscretizedWires(aDWires))
198 const Standard_Integer aNbWires = aDWires.size();
200 std::vector<SegmentsTree> aWiresBiPoints(aNbWires);
201 fillSegmentsTree(aDWires, aWiresBiPoints);
204 Standard_Mutex aWireMutex;
205 BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints,
206 &myStatus, &aWireMutex);
208 if (myIsInParallel && aNbWires > 1)
210 // check wires in parallel threads using TBB
211 tbb::parallel_for(tbb::blocked_range<Standard_Integer>(0, aNbWires),
217 BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints, &myStatus);
219 for (Standard_Integer i = 0; i < aNbWires; ++i)
225 if (myStatus == BRepMesh_SelfIntersectingWire)
229 SeqOfDWires::iterator aDWiresIt = aDWires.begin();
230 for (; aDWiresIt != aDWires.end(); ++aDWiresIt)
232 const SeqOfPnt2d& aDWire = *aDWiresIt;
233 theClassifier->RegisterWire(aDWire, myTolUV, myUmin, myUmax, myVmin, myVmax);
237 //=======================================================================
238 //function : collectDiscretizedWires
240 //=======================================================================
241 Standard_Boolean BRepMesh_WireChecker::collectDiscretizedWires(
242 SeqOfDWires& theDWires)
244 // TODO: Collect disretized wires in parallel
245 SeqOfWireEdges::iterator aWireIt = myWiresEdges.begin();
246 for(; aWireIt != myWiresEdges.end(); ++aWireIt)
248 const ListOfEdges& aEdges = *aWireIt;
249 // For each wire we create a data map, linking vertices (only
250 // the ends of edges) with their positions in the sequence of
251 // all 2d points from this wire.
252 // When we meet some vertex for the second time - the piece
253 // of sequence is treated for a HOLE and quits the sequence.
254 // Actually, we must unbind the vertices belonging to the
255 // loop from the map, but since they can't appear twice on the
256 // valid wire, leave them for a little speed up.
258 SeqOfPnt2d aSeqPnt2d;
259 DataMapIntInt aNodeInSeq;
260 Standard_Integer aFirstIndex = 0, aLastIndex = 0;
262 // Start traversing the wire
263 ListOfEdges::Iterator aEdgeIt(aEdges);
264 for (; aEdgeIt.More(); aEdgeIt.Next())
266 const TopoDS_Edge& aEdge = aEdgeIt.Value();
267 TopAbs_Orientation aOrient = aEdge.Orientation();
268 if (!myEdges.IsBound(aEdge))
272 // Define the direction for adding points to aSeqPnt2d
273 Standard_Integer aStartId, aEndId, aIncrement;
274 const BRepMesh_PairOfPolygon& aPair = myEdges.Find(aEdge);
275 Handle(Poly_PolygonOnTriangulation) aNOD;
276 if (aOrient == TopAbs_FORWARD)
278 aNOD = aPair.First();
280 aEndId = aNOD->NbNodes();
286 aStartId = aNOD->NbNodes();
291 const TColStd_Array1OfInteger& aIndices = aNOD->Nodes();
292 const Standard_Integer aFirstVertexId = myVertexMap.FindKey(aIndices(aStartId));
293 const Standard_Integer aLastVertexId = myVertexMap.FindKey(aIndices(aEndId) );
295 if (aFirstVertexId == aLastVertexId && (aEndId - aStartId) == aIncrement)
297 // case of continuous set of degenerated edges
298 aLastIndex = aLastVertexId;
302 if (aFirstIndex != 0)
304 if (aFirstVertexId != aLastIndex)
306 // there's a gap between edges
307 myStatus = BRepMesh_OpenWire;
308 return Standard_False;
312 aFirstIndex = aFirstVertexId;
314 aLastIndex = aLastVertexId;
316 // Record first vertex (to detect loops)
317 aNodeInSeq.Bind(aFirstVertexId, (aSeqPnt2d.Length() + 1));
319 // Add vertices in sequence
320 for (Standard_Integer i = aStartId; i != aEndId; i += aIncrement)
322 Standard_Integer aIndex = ((i == aStartId) ?
324 myVertexMap.FindKey(aIndices(i)));
326 aSeqPnt2d.Append(gp_Pnt2d(myStructure->GetNode(aIndex).Coord()));
329 // Now, is there a loop?
330 if (aNodeInSeq.IsBound(aLastVertexId))
332 // Yes, treat it separately as a hole
333 // Divide points into main wire and a loop
334 const Standard_Integer aIdxWireStart = aNodeInSeq(aLastVertexId);
335 if(aIdxWireStart < aSeqPnt2d.Length())
337 theDWires.push_back(SeqOfPnt2d());
338 SeqOfPnt2d& aWire = theDWires.back();
339 aSeqPnt2d.Split(aIdxWireStart, aWire);
344 if (aFirstIndex == 0)
348 if (aFirstIndex != aLastIndex || aSeqPnt2d.Length() > 1)
350 myStatus = BRepMesh_OpenWire;
351 return Standard_False;
355 return Standard_True;
358 //=======================================================================
359 //function : fillSegmentsTree
361 //=======================================================================
362 void BRepMesh_WireChecker::fillSegmentsTree(
363 const SeqOfDWires& theDWires,
364 std::vector<SegmentsTree>& theWiresSegmentsTree)
366 const Standard_Integer aNbWires = theDWires.size();
367 for (Standard_Integer aWireIt = 0; aWireIt < aNbWires; ++aWireIt)
369 const SeqOfPnt2d& aWire = theDWires[aWireIt];
370 const Standard_Integer aWireLen = aWire.Size();
372 HArrayOfSegments aWireSegments = new ArrayOfSegments(aWireLen);
373 HBndBox2dTree aBndBoxTree = new BndBox2dTree;
374 BndBox2dTreeFiller aBndBoxTreeFiller(*aBndBoxTree);
376 Standard_Real x1 = 0., y1 = 0., aXstart = 0., aYstart = 0.;
377 for (Standard_Integer aPntIt = 0; aPntIt <= aWireLen; ++aPntIt)
379 Standard_Real x2, y2;
380 // Obtain last point of the segment
381 if (aPntIt == aWireLen)
388 const gp_Pnt2d& aPnt = aWire(aPntIt + 1);
393 // Build segment (bi-point)
401 gp_Pnt2d aStartPnt(x1, y1);
402 gp_Pnt2d aEndPnt(x2, y2);
404 const Standard_Integer aPointId = aPntIt - 1;
405 Segment& aSegment = aWireSegments->at(aPointId);
406 aSegment.StartPnt = aStartPnt.XY();
407 aSegment.EndPnt = aEndPnt.XY();
412 aBndBoxTreeFiller.Add(aPointId, aBox);
417 aBndBoxTreeFiller.Fill();
419 SegmentsTree& aSegmentsTree = theWiresSegmentsTree[aWireIt];
420 aSegmentsTree.first = aWireSegments;
421 aSegmentsTree.second = aBndBoxTree;