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_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>
37 //=======================================================================
38 //function : Selector::Constructor
40 //=======================================================================
41 BRepMesh_WireChecker::BndBox2dTreeSelector::BndBox2dTreeSelector(
42 const Standard_Integer theReservedSize)
44 myIndices(0, theReservedSize - 1),
49 //=======================================================================
52 //=======================================================================
53 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Reject(
54 const Bnd_Box2d& theBox2D) const
56 return myBox2D.IsOut(theBox2D);
59 //=======================================================================
62 //=======================================================================
63 Standard_Boolean BRepMesh_WireChecker::BndBox2dTreeSelector::Accept(
64 const Standard_Integer& theIndex)
66 if (theIndex <= mySkippedIndex)
67 return Standard_False;
69 myIndices(myIndicesNb++) = theIndex;
73 //=======================================================================
76 //=======================================================================
77 void BRepMesh_WireChecker::BndBox2dTreeSelector::Clear()
83 //=======================================================================
86 //=======================================================================
87 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetBox(
88 const Bnd_Box2d& theBox2D)
93 //=======================================================================
96 //=======================================================================
97 void BRepMesh_WireChecker::BndBox2dTreeSelector::SetSkippedIndex(
98 const Standard_Integer theIndex)
100 mySkippedIndex = theIndex;
103 //=======================================================================
106 //=======================================================================
107 const BRepMesh::Array1OfInteger&
108 BRepMesh_WireChecker::BndBox2dTreeSelector::Indices() const
113 //=======================================================================
114 //function : IndicesNb
116 //=======================================================================
117 Standard_Integer BRepMesh_WireChecker::BndBox2dTreeSelector::IndicesNb() const
122 //=======================================================================
123 //function : Constructor
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)
139 myVertexMap(theVertexMap),
140 myStructure(theStructure),
145 myStatus(BRepMesh_NoError),
146 myIsInParallel(isInParallel)
148 TopoDS_Face aFace = theFace;
149 aFace.Orientation(TopAbs_FORWARD);
151 for (TopoDS_Iterator aFaceIt(aFace); aFaceIt.More(); aFaceIt.Next())
153 if (aFaceIt.Value().IsNull() || aFaceIt.Value().ShapeType() != TopAbs_WIRE) // may be inner vertex
155 const TopoDS_Wire& aWire = TopoDS::Wire(aFaceIt.Value());
157 myWiresEdges.Append(ListOfEdges());
158 ListOfEdges& aEdges = myWiresEdges.ChangeLast();
160 // Start traversing the wires
161 BRepTools_WireExplorer aWireExplorer(aWire, aFace);
162 for (; aWireExplorer.More(); aWireExplorer.Next())
164 const TopoDS_Edge& aEdge = aWireExplorer.Current();
165 TopAbs_Orientation aOrient = aEdge.Orientation();
166 if (aOrient != TopAbs_FORWARD && aOrient != TopAbs_REVERSED)
169 aEdges.Append(aEdge);
172 if (aEdges.IsEmpty())
173 myWiresEdges.Remove(myWiresEdges.Size());
177 //=======================================================================
178 //function : ReCompute
180 //=======================================================================
181 void BRepMesh_WireChecker::ReCompute(BRepMesh::HClassifier& theClassifier)
183 if (theClassifier.IsNull())
186 theClassifier->Destroy();
187 myStatus = BRepMesh_NoError;
190 if (!collectDiscretizedWires(aDWires))
193 const Standard_Integer aNbWires = aDWires.Size();
194 BRepMesh::Array1OfSegmentsTree aWiresBiPoints(1, aNbWires);
195 fillSegmentsTree(aDWires, aWiresBiPoints);
197 if (myIsInParallel && aNbWires > 1)
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);
206 BRepMesh_WireInterferenceChecker aIntChecker(aWiresBiPoints, &myStatus);
207 OSD_Parallel::For(1, aNbWires + 1, aIntChecker, Standard_True);
210 if (myStatus == BRepMesh_SelfIntersectingWire)
214 SeqOfDWires::Iterator aDWiresIt(aDWires);
215 for (; aDWiresIt.More(); aDWiresIt.Next())
217 const SeqOfPnt2d& aDWire = aDWiresIt.Value();
218 theClassifier->RegisterWire(aDWire, myTolUV, myUmin, myUmax, myVmin, myVmax);
222 //=======================================================================
223 //function : collectDiscretizedWires
225 //=======================================================================
226 Standard_Boolean BRepMesh_WireChecker::collectDiscretizedWires(
227 SeqOfDWires& theDWires)
229 SeqOfWireEdges::Iterator aWireIt(myWiresEdges);
230 for(; aWireIt.More(); aWireIt.Next())
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.
242 SeqOfPnt2d aSeqPnt2d;
243 BRepMesh::MapOfIntegerInteger aNodeInSeq;
244 Standard_Integer aFirstIndex = 0, aLastIndex = 0;
246 // Start traversing the wire
247 ListOfEdges::Iterator aEdgeIt(aEdges);
248 for (; aEdgeIt.More(); aEdgeIt.Next())
250 const TopoDS_Edge& aEdge = aEdgeIt.Value();
251 TopAbs_Orientation aOrient = aEdge.Orientation();
252 if (!myEdges->IsBound(aEdge))
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)
262 aNOD = aPair.First();
264 aEndId = aNOD->NbNodes();
270 aStartId = aNOD->NbNodes();
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) );
279 if (aFirstVertexId == aLastVertexId && (aEndId - aStartId) == aIncrement)
281 // case of continuous set of degenerated edges
282 aLastIndex = aLastVertexId;
286 if (aFirstIndex != 0)
288 if (aFirstVertexId != aLastIndex)
290 // there's a gap between edges
291 myStatus = BRepMesh_OpenWire;
292 return Standard_False;
296 aFirstIndex = aFirstVertexId;
298 aLastIndex = aLastVertexId;
300 // Record first vertex (to detect loops)
301 aNodeInSeq.Bind(aFirstVertexId, (aSeqPnt2d.Length() + 1));
303 // Add vertices in sequence
304 for (Standard_Integer i = aStartId; i != aEndId; i += aIncrement)
306 Standard_Integer aIndex = ((i == aStartId) ?
308 myVertexMap->FindKey(aIndices(i)));
310 aSeqPnt2d.Append(gp_Pnt2d(myStructure->GetNode(aIndex).Coord()));
313 // Now, is there a loop?
314 if (aNodeInSeq.IsBound(aLastVertexId))
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())
321 theDWires.Append(SeqOfPnt2d());
322 SeqOfPnt2d& aWire = theDWires.ChangeLast();
323 aSeqPnt2d.Split(aIdxWireStart, aWire);
328 if (aFirstIndex == 0)
332 if (aFirstIndex != aLastIndex || aSeqPnt2d.Length() > 1)
334 myStatus = BRepMesh_OpenWire;
335 return Standard_False;
339 return Standard_True;
342 //=======================================================================
343 //function : fillSegmentsTree
345 //=======================================================================
346 void BRepMesh_WireChecker::fillSegmentsTree(
347 const SeqOfDWires& theDWires,
348 BRepMesh::Array1OfSegmentsTree& theWiresSegmentsTree)
350 const Standard_Integer aNbWires = theDWires.Size();
351 for (Standard_Integer aWireIt = 1; aWireIt <= aNbWires; ++aWireIt)
353 const SeqOfPnt2d& aWire = theDWires(aWireIt);
354 const Standard_Integer aWireLen = aWire.Size();
356 BRepMesh::HArray1OfSegments aWireSegments =
357 new BRepMesh::Array1OfSegments(1, aWireLen);
359 BRepMesh::HBndBox2dTree aBndBoxTree =
360 new BRepMesh::BndBox2dTree;
362 BRepMesh::BndBox2dTreeFiller aBndBoxTreeFiller(*aBndBoxTree);
364 Standard_Real x1 = 0., y1 = 0., aXstart = 0., aYstart = 0.;
365 for (Standard_Integer aPntIt = 0; aPntIt <= aWireLen; ++aPntIt)
367 Standard_Real x2, y2;
368 // Obtain last point of the segment
369 if (aPntIt == aWireLen)
376 const gp_Pnt2d& aPnt = aWire(aPntIt + 1);
381 // Build segment (bi-point)
389 gp_Pnt2d aStartPnt(x1, y1);
390 gp_Pnt2d aEndPnt(x2, y2);
392 BRepMesh::Segment& aSegment = aWireSegments->ChangeValue(aPntIt);
393 aSegment.StartPnt = aStartPnt.XY();
394 aSegment.EndPnt = aEndPnt.XY();
399 aBndBoxTreeFiller.Add(aPntIt, aBox);
404 aBndBoxTreeFiller.Fill();
406 BRepMesh::SegmentsTree& aSegmentsTree = theWiresSegmentsTree(aWireIt);
407 aSegmentsTree.first = aWireSegments;
408 aSegmentsTree.second = aBndBoxTree;