projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0029915: Porting to VC 2017 : Regressions in Modeling Algorithms on VC 2017
[occt.git] / src / BOPAlgo / BOPAlgo_Tools.cxx
CommitLineData
4e57c75e 1// Created by: Peter KURNEV
973c2be1 2// Copyright (c) 1999-2014 OPEN CASCADE SAS
4e57c75e 3//
973c2be1 4// This file is part of Open CASCADE Technology software library.
4e57c75e 5//
d5f74e42 6// This library is free software; you can redistribute it and/or modify it under
7// the terms of the GNU Lesser General Public License version 2.1 as published
973c2be1 8// by the Free Software Foundation, with special exception defined in the file
9// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10// distribution for complete text of the license and disclaimer of any warranty.
4e57c75e 11//
973c2be1 12// Alternatively, this file may be used under the terms of Open CASCADE
13// commercial license or contractual agreement.
4e57c75e 14
42cf5bc1 15
16#include <BOPAlgo_Tools.hxx>
e6ae74fd 17
e6ae74fd 18#include <BOPAlgo_Builder.hxx>
19#include <BOPAlgo_BuilderFace.hxx>
4e57c75e 20#include <BOPDS_CommonBlock.hxx>
21#include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
42cf5bc1 22#include <BOPDS_DS.hxx>
23#include <BOPDS_IndexedMapOfPaveBlock.hxx>
24#include <BOPDS_MapOfPaveBlock.hxx>
25#include <BOPDS_PaveBlock.hxx>
e6ae74fd 26#include <BOPTools_AlgoTools.hxx>
27#include <BOPTools_AlgoTools2D.hxx>
1155d05a 28#include <BOPTools_BoxBndTree.hxx>
29#include <BOPTools_Parallel.hxx>
30#include <BRep_Builder.hxx>
31#include <BRep_Tool.hxx>
32#include <BRepAdaptor_Curve.hxx>
33#include <BRepBndLib.hxx>
34#include <BRepBuilderAPI_MakeFace.hxx>
35#include <BRepLib.hxx>
36#include <GeomAPI_ProjectPointOnCurve.hxx>
37#include <GeomAPI_ProjectPointOnSurf.hxx>
38#include <gp_Circ.hxx>
39#include <gp_Dir.hxx>
40#include <gp_Elips.hxx>
41#include <gp_Hypr.hxx>
42#include <gp_Parab.hxx>
43#include <gp_Pln.hxx>
44#include <gp_Pnt.hxx>
45#include <gp_Vec.hxx>
3510db62 46#include <IntTools_Context.hxx>
1155d05a 47#include <NCollection_IncAllocator.hxx>
48#include <NCollection_UBTreeFiller.hxx>
49#include <NCollection_Vector.hxx>
50#include <Standard_ErrorHandler.hxx>
51#include <Standard_Failure.hxx>
52#include <TColStd_IndexedMapOfInteger.hxx>
53#include <TopExp.hxx>
54#include <TopExp_Explorer.hxx>
55#include <TopoDS.hxx>
56#include <TopoDS_Edge.hxx>
57#include <TopTools_IndexedDataMapOfShapeListOfShape.hxx>
58#include <TopTools_IndexedMapOfShape.hxx>
59#include <TopTools_MapOfShape.hxx>
e6ae74fd 60
b7cd7c2b 61#include <algorithm>
62
e6ae74fd 63typedef NCollection_IndexedDataMap
64 <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
65typedef NCollection_IndexedDataMap
66 <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
67
68static
1155d05a 69 void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
e6ae74fd 70 TopoDS_Compound& theWires,
71 const Standard_Boolean theCheckUniquePlane,
72 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 73 TopTools_MapOfShape& theMEdgesNoUniquePlane);
e6ae74fd 74
75static
76 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
77 gp_Pln& thePlane);
78
79static
80 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
81 gp_Pln& thePlane,
82 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 83 TopTools_MapOfShape& theMEdgesNoUniquePlane);
e6ae74fd 84
85static
86 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
87 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
88 gp_Dir& theTgt);
89
90static
91 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
92 gp_Vec& theTangent);
4e57c75e 93
4e57c75e 94//=======================================================================
95//function : FillMap
96//purpose :
97//=======================================================================
3510db62 98void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
99 const Standard_Integer nF,
100 BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
101 const Handle(NCollection_BaseAllocator)& aAllocator)
4e57c75e 102{
1155d05a 103 TColStd_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
edfa30de 104 if (!pLI) {
1155d05a 105 pLI = &aMPBLI(aMPBLI.Add(aPB, TColStd_ListOfInteger(aAllocator)));
4e57c75e 106 }
edfa30de 107 pLI->Append(nF);
4e57c75e 108}
109//=======================================================================
110//function : PerformCommonBlocks
111//purpose :
112//=======================================================================
3510db62 113void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
114 const Handle(NCollection_BaseAllocator)& aAllocator,
d3578357 115 BOPDS_PDS& pDS,
116 const Handle(IntTools_Context)& theContext)
4e57c75e 117{
118 Standard_Integer aNbCB;
119 //
120 aNbCB=aMPBLPB.Extent();
121 if (!aNbCB) {
122 return;
123 }
b7cd7c2b 124 // Make Blocks of the pave blocks
edfa30de 125 NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
edfa30de 126 BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
b7cd7c2b 127
128 // Use temporary allocator for the local fence map
129 Handle(NCollection_IncAllocator) anAllocTmp = new NCollection_IncAllocator;
130
edfa30de 131 NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
132 for (; aItB.More(); aItB.Next()) {
133 const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
134 Standard_Integer aNbPB = aLPB.Extent();
b7cd7c2b 135 if (aNbPB < 2)
136 continue;
137
138 // Reset the allocator
139 anAllocTmp->Reset();
140 // New common block
141 Handle(BOPDS_CommonBlock) aCB;
142 // Faces of the common block
1155d05a 143 TColStd_ListOfInteger aLFaces;
b7cd7c2b 144 // Fence map to avoid duplicates in the list of faces of the common block
1155d05a 145 TColStd_MapOfInteger aMFaces(1, anAllocTmp);
b7cd7c2b 146
147 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
148 for (; aItLPB.More(); aItLPB.Next())
149 {
150 const Handle(BOPDS_PaveBlock)& aPB = aItLPB.Value();
151 if (pDS->IsCommonBlock(aPB))
152 {
153 const Handle(BOPDS_CommonBlock)& aCBx = pDS->CommonBlock(aPB);
154 // Move all faces to the new common block
1155d05a 155 TColStd_ListIteratorOfListOfInteger aItLF(aCBx->Faces());
b7cd7c2b 156 for (; aItLF.More(); aItLF.Next())
157 {
158 const Standard_Integer nF = aItLF.Value();
159 // Append to common list avoiding duplicates
160 if (aMFaces.Add(nF))
161 aLFaces.Append(nF);
162 }
163 if (aCB.IsNull())
164 aCB = aCBx;
4e57c75e 165 }
b7cd7c2b 166 }
167
168 if (aCB.IsNull())
169 aCB = new BOPDS_CommonBlock;
170
171 aCB->SetPaveBlocks(aLPB);
172 aCB->SetFaces(aLFaces);
173 for (aItLPB.Initialize(aLPB); aItLPB.More(); aItLPB.Next())
174 pDS->SetCommonBlock(aItLPB.Value(), aCB);
d3578357 175
176 // Compute tolerance for Common Block
177 Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
178 aCB->SetTolerance(aTolCB);
4e57c75e 179 }
180}
181//=======================================================================
182//function : PerformCommonBlocks
183//purpose :
184//=======================================================================
3510db62 185void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
186 const Handle(NCollection_BaseAllocator)& ,//aAllocator
d3578357 187 BOPDS_PDS& pDS,
188 const Handle(IntTools_Context)& theContext)
4e57c75e 189{
190 Standard_Integer nF, i, aNb;
1155d05a 191 TColStd_ListIteratorOfListOfInteger aItLI;
4e57c75e 192 Handle(BOPDS_PaveBlock) aPB;
193 Handle(BOPDS_CommonBlock) aCB;
194 //
195 aNb=aMPBLI.Extent();
196 for (i=1; i<=aNb; ++i) {
197 aPB=aMPBLI.FindKey(i);
5a77460e 198 if (pDS->IsCommonBlock(aPB)) {
199 aCB=pDS->CommonBlock(aPB);
4e57c75e 200 }
201 else {
202 aCB=new BOPDS_CommonBlock;
203 aCB->AddPaveBlock(aPB);
204 }
205 //
1155d05a 206 const TColStd_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
207 TColStd_ListOfInteger aNewFaces;
208 const TColStd_ListOfInteger& anOldFaces = aCB->Faces();
4e57c75e 209 aItLI.Initialize(aLI);
210 for (; aItLI.More(); aItLI.Next()) {
211 nF=aItLI.Value();
3510db62 212 // the both lists aLI and anOldFaces are expected to be short,
213 // so we can allow to run nested loop here
1155d05a 214 TColStd_ListIteratorOfListOfInteger it(anOldFaces);
3510db62 215 for (; it.More(); it.Next()) {
216 if (it.Value() == nF)
217 break;
218 }
219 if (!it.More()) {
220 aNewFaces.Append(nF);
221 }
4e57c75e 222 }
3510db62 223 aCB->AppendFaces(aNewFaces);
5a77460e 224 pDS->SetCommonBlock(aPB, aCB);
d3578357 225 // Compute tolerance for Common Block
226 Standard_Real aTolCB = BOPAlgo_Tools::ComputeToleranceOfCB(aCB, pDS, theContext);
227 aCB->SetTolerance(aTolCB);
4e57c75e 228 }
229}
3510db62 230//=======================================================================
231//function : ComputeToleranceOfCB
232//purpose :
233//=======================================================================
234Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
235 (const Handle(BOPDS_CommonBlock)& theCB,
236 const BOPDS_PDS theDS,
237 const Handle(IntTools_Context)& theContext)
238{
239 Standard_Real aTolMax = 0.;
240 if (theCB.IsNull()) {
241 return aTolMax;
242 }
243 //
244 const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
245 Standard_Integer nE = aPBR->OriginalEdge();
246 const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
247 aTolMax = BRep_Tool::Tolerance(aEOr);
248 //
249 const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
1155d05a 250 const TColStd_ListOfInteger& aLFI = theCB->Faces();
3510db62 251 //
252 if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
253 return aTolMax;
254 }
255 //
256 const Standard_Integer aNbPnt = 11;
257 Standard_Real aTol, aT, aT1, aT2, aDt;
258 gp_Pnt aP;
259 //
260 const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
261 //
262 aPBR->Range(aT1, aT2);
263 aDt = (aT2 - aT1) / (aNbPnt + 1);
264 //
d3578357 265 Handle(IntTools_Context) aCtx = theContext;
266 if (aCtx.IsNull())
267 aCtx = new IntTools_Context();
268
3510db62 269 // compute max tolerance for common blocks on edges
270 if (aLPB.Extent() > 1) {
271 // compute max distance between edges
272 BOPDS_ListIteratorOfListOfPaveBlock aItPB;
273 GeomAPI_ProjectPointOnCurve aProjPC;
274 //
275 aItPB.Initialize(aLPB);
276 for (; aItPB.More(); aItPB.Next()) {
277 const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
278 if (aPB == aPBR) {
279 continue;
280 }
281 //
282 nE = aPB->OriginalEdge();
283 const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
284 aTol = BRep_Tool::Tolerance(aE);
285 //
d3578357 286 aProjPC = aCtx->ProjPC(aE);
3510db62 287 //
288 aT = aT1;
289 for (Standard_Integer i=1; i <= aNbPnt; i++) {
290 aT += aDt;
291 aC3D->D0(aT, aP);
292 aProjPC.Perform(aP);
293 if (aProjPC.NbPoints()) {
294 Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
295 if (aTolNew > aTolMax) {
296 aTolMax = aTolNew;
297 }
298 }
299 }
300 }
301 }
302 //
303 // compute max tolerance for common blocks on faces
304 if (aLFI.Extent()) {
305 Standard_Integer nF;
306 GeomAPI_ProjectPointOnSurf aProjPS;
1155d05a 307 TColStd_ListIteratorOfListOfInteger aItLI;
3510db62 308 //
309 aItLI.Initialize(aLFI);
310 for (; aItLI.More(); aItLI.Next()) {
311 nF = aItLI.Value();
312 const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
313 aTol = BRep_Tool::Tolerance(aF);
314 //
d3578357 315 aProjPS = aCtx->ProjPS(aF);
3510db62 316 //
317 aT = aT1;
318 for (Standard_Integer i=1; i <= aNbPnt; i++) {
319 aT += aDt;
320 aC3D->D0(aT, aP);
321 aProjPS.Perform(aP);
322 if (aProjPS.NbPoints()) {
323 Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
324 if (aTolNew > aTolMax) {
325 aTolMax = aTolNew;
326 }
327 }
328 }
329 }
330 }
331 //
332 return aTolMax;
333}
e6ae74fd 334
335//=======================================================================
336//function : EdgesToWires
337//purpose :
338//=======================================================================
339Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
340 TopoDS_Shape& theWires,
341 const Standard_Boolean theShared,
342 const Standard_Real theAngTol)
343{
344 Standard_Integer iErr = 0;
345 //
346 // 1. Check the input edges
347 //
348 // List of edges to process
1155d05a 349 TopTools_ListOfShape aLE;
e6ae74fd 350 //
351 TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
352 for (; aExp.More(); aExp.Next()) {
353 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
354 if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
355 aLE.Append(aExp.Current());
356 }
357 }
358 //
359 if (aLE.IsEmpty()) {
360 // no edges to process
361 iErr = 1;
362 return iErr;
363 }
364 //
365 BRep_Builder aBB;
366 TopoDS_Compound aRWires;
367 aBB.MakeCompound(aRWires);
368 //
369 if (aLE.Extent() == 1) {
370 TopoDS_Wire aWire;
371 aBB.MakeWire(aWire);
372 aBB.Add(aWire, aLE.First());
373 aBB.Add(aRWires, aWire);
374 theWires = aRWires;
375 return iErr;
376 }
377 //
378 // 2. Make compound of shared edges
379 TopoDS_Shape aSEdges;
380 //
381 if (!theShared) {
382 // intersect the edges if necessary
383 BOPAlgo_Builder aGF;
384 aGF.SetArguments(aLE);
385 aGF.Perform();
33ba8565 386 if (aGF.HasErrors()) {
e6ae74fd 387 // unable to share the edges
388 iErr = 2;
389 return iErr;
390 }
391 //
392 aSEdges = aGF.Shape();
393 }
394 else {
395 aBB.MakeCompound(TopoDS::Compound(aSEdges));
1155d05a 396 TopTools_ListIteratorOfListOfShape aItLE(aLE);
e6ae74fd 397 for (; aItLE.More(); aItLE.Next()) {
398 aBB.Add(aSEdges, aItLE.Value());
399 }
400 }
401 //
402 // 3. Find edges located in the same planes and make wires from them.
403 // If the plane cannot be found for a single edge, then it is necessary
404 // to find all pairs of connected edges with the same cross product.
405
406 // Try to compute the plane in which the edge is located
407 BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
408 // Compute the tangent direction for the edges for which the plane is not defined
409 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
410 //
411 // edges for which the plane is not found
1155d05a 412 TopTools_MapOfShape aMEdgesNoUniquePlane;
e6ae74fd 413 //
414 // edges for which the plane cannot be found on a single edge
415 TopoDS_Compound aLEdges;
416 aBB.MakeCompound(aLEdges);
417 //
418 aExp.Init(aSEdges, TopAbs_EDGE);
419 for (; aExp.More(); aExp.Next()) {
420 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
421 BRepAdaptor_Curve aBAC(aE);
422 //
423 gp_Pln aPln;
424 if (FindPlane(aBAC, aPln)) {
425 aDMEdgePln.Add(aE, aPln);
426 }
427 else {
428 gp_Vec aVT;
429 if (FindEdgeTangent(aBAC, aVT)) {
430 aDMEdgeTgt.Add(aE, gp_Dir(aVT));
431 aBB.Add(aLEdges, aE);
432 aMEdgesNoUniquePlane.Add(aE);
433 }
434 }
435 }
436 //
437 typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
438 //
439 // to avoid processing of the same edges in the same plane store
440 // the processed planes into a list and use it as a fence map
441 BOPAlgo_ListOfDir aLPFence;
442 //
443 // used edges
1155d05a 444 TopTools_MapOfShape aMEFence;
e6ae74fd 445 //
446 // look for a planes on the single edges
447 Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
448 for (i = 1; i <= aNbPlanes; ++i) {
449 const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
450 if (!aMEFence.Add(aEI)) {
451 continue;
452 }
453 //
454 const gp_Pln& aPlnI = aDMEdgePln(i);
455 const gp_Dir& aDI = aPlnI.Position().Direction();
456 //
457 aLPFence.Append(aDI);
458 //
1155d05a 459 TopTools_IndexedMapOfShape aMEPln;
e6ae74fd 460 aMEPln.Add(aEI);
461 //
1155d05a 462 TopTools_IndexedMapOfShape aMV;
463 TopExp::MapShapes(aEI, TopAbs_VERTEX, aMV);
e6ae74fd 464 //
465 // look for other edges with the plane parallel to current one
466 for (j = i + 1; j <= aNbPlanes; ++j) {
467 const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
468 if (aDI.IsParallel(aDJ, theAngTol)) {
469 const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
470 aMEPln.Add(aEJ);
471 aMEFence.Add(aEJ);
1155d05a 472 TopExp::MapShapes(aEJ, TopAbs_VERTEX, aMV);
e6ae74fd 473 }
474 }
475 //
476 // look for all other edges located in the plane parallel to current one
477 TopoDS_Compound aCEPln;
478 aBB.MakeCompound(aCEPln);
479 //
480 for (j = 1; j <= aNbEdges; ++j) {
481 const gp_Dir& aDJ = aDMEdgeTgt(j);
482 if (aDI.IsNormal(aDJ, theAngTol)) {
483 aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
484 }
485 }
486 //
487 // make blocks of these edges and check blocks to be connected
488 // to any of the already added edges or forming a wire themselves
1155d05a 489 TopTools_ListOfShape aLCBE;
e6ae74fd 490 BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
491 //
492 // make wire from each block
1155d05a 493 TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
e6ae74fd 494 for (; aItLCB.More(); aItLCB.Next()) {
495 const TopoDS_Shape& aCBE = aItLCB.Value();
496 //
497 // check connectivity
498 TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
499 for (; aExpV.More(); aExpV.Next()) {
500 if (aMV.Contains(aExpV.Current())) {
501 break;
502 }
503 }
504 //
505 Standard_Boolean bAddBlock = aExpV.More();
506 if (!bAddBlock) {
507 // check if the edges are forming a wire
508 gp_Pln aPln;
509 bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
510 }
511 //
512 if (bAddBlock) {
513 // add edges
514 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
515 aMEPln.Add(aItE.Value());
516 }
517 }
518 }
519 //
520 MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
521 }
522 //
523 // make connection map from vertices to edges to find the connected pairs
1155d05a 524 TopTools_IndexedDataMapOfShapeListOfShape aDMVE;
525 TopExp::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
e6ae74fd 526 //
527 // find planes for connected edges
528 Standard_Integer aNbV = aDMVE.Extent();
529 for (i = 1; i <= aNbV; ++i) {
1155d05a 530 const TopTools_ListOfShape& aLEI = aDMVE(i);
e6ae74fd 531 if (aLEI.Extent() < 2) {
532 continue;
533 }
534 //
1155d05a 535 TopTools_ListIteratorOfListOfShape aItLEI1(aLEI);
e6ae74fd 536 for (; aItLEI1.More(); aItLEI1.Next()) {
537 const TopoDS_Shape& aEI1 = aItLEI1.Value();
538 const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
539 //
1155d05a 540 TopTools_ListIteratorOfListOfShape aItLEI2(aLEI);
e6ae74fd 541 for (; aItLEI2.More(); aItLEI2.Next()) {
542 const TopoDS_Shape& aEI2 = aItLEI2.Value();
543 if (aEI2.IsSame(aEI1)) {
544 continue;
545 }
546 //
547 const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
548 //
549 if (aDI1.IsParallel(aDI2, theAngTol)) {
550 continue;
551 }
552 //
553 gp_Dir aDNI = aDI1^aDI2;
554 //
555 // check if this normal direction has not been checked yet
556 BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
557 for (; aItLPln.More(); aItLPln.Next()) {
558 if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
559 break;
560 }
561 }
562 if (aItLPln.More()) {
563 continue;
564 }
565 //
566 aLPFence.Append(aDNI);
567 //
568 // find all other edges in the plane parallel to current one
1155d05a 569 TopTools_IndexedMapOfShape aMEPln;
e6ae74fd 570 aMEPln.Add(aEI1);
571 aMEPln.Add(aEI2);
572 //
573 // iterate on all other edges to find all edges lying in the plane parallel to current one
574 for (j = 1; j <= aNbEdges; ++j) {
575 const gp_Dir& aDJ = aDMEdgeTgt(j);
576 if (aDNI.IsNormal(aDJ, theAngTol)) {
577 aMEPln.Add(aDMEdgeTgt.FindKey(j));
578 }
579 }
580 //
581 MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
582 } // for (; aItLEI2.More(); aItLEI2.Next()) {
583 } // for (; aItLEI1.More(); aItLEI1.Next()) {
584 } // for (i = 1; i < aNb; ++i) {
585 //
586 // 4. Find unused edges and make wires from them
1155d05a 587 TopTools_IndexedMapOfShape aMEAlone, aMEUsed;
588 TopExp::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
e6ae74fd 589 //
590 for (i = 1; i <= aNbEdges; ++i) {
591 const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
592 if (!aMEUsed.Contains(aE)) {
593 aMEAlone.Add(aE);
594 }
595 }
596 //
597 MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
598 //
599 theWires = aRWires;
600 //
601 return iErr;
602}
603
604//=======================================================================
605//function : WiresToFaces
606//purpose :
607//=======================================================================
608Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
609 TopoDS_Shape& theFaces,
610 const Standard_Real theAngTol)
611{
612 BRep_Builder aBB;
1155d05a 613 TopTools_MapOfShape aMFence;
e6ae74fd 614 TopoDS_Compound aRFaces;
615 aBB.MakeCompound(aRFaces);
616 //
617 const Standard_Real aMax = 1.e+8;
618 //
619 // map to store the tangent vectors for the edges
620 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
621 // maps to store the planes found for the wires
622 BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
623 // map to store the tolerance for the wire
624 NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
625 // edges for which the plane is not found
1155d05a 626 TopTools_MapOfShape aMEdgesNoUniquePlane;
e6ae74fd 627 //
628 // Find planes for the wires
629 TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
630 for (; aExpW.More(); aExpW.Next()) {
631 const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
632 gp_Pln aPlane;
633 if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
634 aDMWirePln.Add(aWire, aPlane);
635 // find tolerance for the wire - max tolerance of its edges
636 aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
637 }
638 }
639 //
640 Standard_Integer i, j, aNb = aDMWirePln.Extent();
641 for (i = 1; i <= aNb; ++i) {
642 const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
643 if (aMFence.Contains(aWireI)) {
644 continue;
645 }
646 //
647 const gp_Pln& aPlnI = aDMWirePln(i);
648 //
1155d05a 649 TopTools_ListOfShape aLW;
e6ae74fd 650 aLW.Append(aWireI);
651 aMFence.Add(aWireI);
652 //
653 Standard_Real aTolI = aDMWireTol.Find(aWireI);
654 //
655 // Find other wires in the same plane
656 for (j = i + 1; j <= aNb; ++j) {
657 const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
658 if (aMFence.Contains(aWireJ)) {
659 continue;
660 }
661 //
662 // check if the planes are the same
663 const gp_Pln& aPlnJ = aDMWirePln(j);
664 // check direction of the planes
665 if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
666 continue;
667 }
668 // check distance between the planes
669 Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
670 Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
671 if (aDist > (aTolI + aTolJ)) {
672 continue;
673 }
674 //
675 aLW.Append(aWireJ);
676 aMFence.Add(aWireJ);
677 }
678 //
679 // Take the edges to build the face
1155d05a 680 TopTools_ListOfShape aLE;
681 TopTools_ListIteratorOfListOfShape aItLW(aLW);
e6ae74fd 682 for (; aItLW.More(); aItLW.Next()) {
683 TopoDS_Iterator aItE(aItLW.Value());
684 for (; aItE.More(); aItE.Next()) {
685 aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
686 aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
687 }
688 }
689 //
690 // build planar face
691 TopoDS_Face aFF = BRepBuilderAPI_MakeFace
692 (aPlnI, -aMax, aMax, -aMax, aMax).Face();
693 aFF.Orientation(TopAbs_FORWARD);
694 //
695 try {
696 OCC_CATCH_SIGNALS
697 //
698 // build pcurves for edges on this face
f16a6cc5 699 BRepLib::BuildPCurveForEdgesOnPlane(aLE, aFF);
e6ae74fd 700 //
701 // split the face with the edges
702 BOPAlgo_BuilderFace aBF;
703 aBF.SetShapes(aLE);
704 aBF.SetFace(aFF);
705 aBF.Perform();
33ba8565 706 if (aBF.HasErrors()) {
e6ae74fd 707 continue;
708 }
709 //
1155d05a 710 const TopTools_ListOfShape& aLFSp = aBF.Areas();
711 TopTools_ListIteratorOfListOfShape aItLF(aLFSp);
e6ae74fd 712 for (; aItLF.More(); aItLF.Next()) {
713 const TopoDS_Shape& aFSp = aItLF.ChangeValue();
714 aBB.Add(aRFaces, aFSp);
715 }
716 }
717 catch (Standard_Failure) {
718 continue;
719 }
720 }
721 //
722 // fix tolerances of the resulting faces
1155d05a 723 TopTools_IndexedMapOfShape aMEmpty;
e6ae74fd 724 BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
725 BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
726 //
727 theFaces = aRFaces;
b2d1851c 728 return theFaces.NbChildren() > 0;
e6ae74fd 729}
730
731//=======================================================================
732//function : MakeWires
733//purpose : Makes wires from the separate blocks of the given edges
734//=======================================================================
1155d05a 735void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
e6ae74fd 736 TopoDS_Compound& theWires,
737 const Standard_Boolean theCheckUniquePlane,
738 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 739 TopTools_MapOfShape& theMEdgesNoUniquePlane)
e6ae74fd 740{
741 TopoDS_Compound aCE;
742 BRep_Builder().MakeCompound(aCE);
743 Standard_Integer i, aNbE = theEdges.Extent();
744 for (i = 1; i <= aNbE; ++i) {
745 BRep_Builder().Add(aCE, theEdges(i));
746 }
747 //
1155d05a 748 TopTools_ListOfShape aLCBE;
e6ae74fd 749 BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
750 //
751 // make wire from each block
1155d05a 752 TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
e6ae74fd 753 for (; aItLCB.More(); aItLCB.Next()) {
754 const TopoDS_Shape& aCBE = aItLCB.Value();
755 //
756 if (theCheckUniquePlane) {
757 gp_Pln aPln;
758 if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
759 continue;
760 }
761 }
762 //
763 TopoDS_Wire aWire;
764 BRep_Builder().MakeWire(aWire);
765 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
766 BRep_Builder().Add(aWire, aItE.Value());
767 }
768 //
769 BRep_Builder().Add(theWires, aWire);
770 }
771}
772
773//=======================================================================
774//function : FindEdgeTangent
775//purpose : Finds the tangent for the edge using the map
776//=======================================================================
777Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
778 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
779 gp_Dir& theTgt)
780{
781 gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
782 if (!pDTE) {
783 gp_Vec aVTE;
784 BRepAdaptor_Curve aBAC(theEdge);
785 if (!FindEdgeTangent(aBAC, aVTE)) {
786 return Standard_False;
787 }
788 pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
789 }
790 theTgt = *pDTE;
791 return Standard_True;
792}
793
794//=======================================================================
795//function : FindEdgeTangent
796//purpose : Finds the tangent for the edge
797//=======================================================================
798Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
799 gp_Vec& theTangent)
800{
801 if (!theCurve.Is3DCurve()) {
802 return Standard_False;
803 }
804 // for the line the tangent is defined by the direction
805 if (theCurve.GetType() == GeomAbs_Line) {
806 theTangent = theCurve.Line().Position().Direction();
807 return Standard_True;
808 }
809 //
810 // for other curves take D1 and check for its length
811 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
812 const Standard_Integer aNbP = 11;
813 const Standard_Real aDt = (aT2 - aT1) / aNbP;
814 //
815 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
816 gp_Pnt aP;
817 theCurve.D1(aT, aP, theTangent);
818 if (theTangent.Magnitude() > Precision::Confusion()) {
819 return Standard_True;
820 }
821 }
822 //
823 return Standard_False;
824}
825
826//=======================================================================
827//function : FindPlane
828//purpose : Finds the plane in which the edge is located
829//=======================================================================
830Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
831 gp_Pln& thePlane)
832{
833 if (!theCurve.Is3DCurve()) {
834 return Standard_False;
835 }
836 //
837 Standard_Boolean bFound = Standard_True;
838 gp_Vec aVN;
839 switch (theCurve.GetType()) {
840 case GeomAbs_Line:
841 return Standard_False;
842 case GeomAbs_Circle:
843 aVN = theCurve.Circle().Position().Direction();
844 break;
845 case GeomAbs_Ellipse:
846 aVN = theCurve.Ellipse().Position().Direction();
847 break;
848 case GeomAbs_Hyperbola:
849 aVN = theCurve.Hyperbola().Position().Direction();
850 break;
851 case GeomAbs_Parabola:
852 aVN = theCurve.Parabola().Position().Direction();
853 break;
854 default: {
855 // for all other types of curve compute two tangent vectors
856 // on the curve and cross them
857 bFound = Standard_False;
858 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
859 const Standard_Integer aNbP = 11;
860 const Standard_Real aDt = (aT2 - aT1) / aNbP;
861 //
862 aT = aT1;
863 gp_Pnt aP1;
864 gp_Vec aV1;
865 theCurve.D1(aT, aP1, aV1);
866 //
867 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
868 gp_Pnt aP2;
869 gp_Vec aV2;
870 theCurve.D1(aT, aP2, aV2);
871 //
872 aVN = aV1^aV2;
873 if (aVN.Magnitude() > Precision::Confusion()) {
874 bFound = Standard_True;
875 break;
876 }
877 }
878 break;
879 }
880 }
881 //
882 if (bFound) {
883 thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
884 }
885 return bFound;
886}
887
888//=======================================================================
889//function : FindPlane
890//purpose : Finds the plane in which the wire is located
891//=======================================================================
892Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
893 gp_Pln& thePlane,
894 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 895 TopTools_MapOfShape& theMEdgesNoUniquePlane)
e6ae74fd 896{
897 TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
898 if (!aExpE1.More()) {
899 return Standard_False;
900 }
901 //
902 // try to find two not parallel edges in wire to get normal of the plane
903 for (; aExpE1.More(); aExpE1.Next()) {
904 // get the first edge in the wire
905 const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
906 //
907 // find tangent for the first edge
908 gp_Dir aDTE1;
909 if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
910 continue;
911 }
912 //
913 // find the other edge not parallel to the first one
914 TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
915 for (; aExpE2.More(); aExpE2.Next()) {
916 const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
917 if (aE1.IsSame(aE2)) {
918 continue;
919 }
920 //
921 // find tangent for the second edge
922 gp_Dir aDTE2;
923 if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
924 continue;
925 }
926 //
927 if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
928 continue;
929 }
930 //
931 gp_Dir aDN = aDTE1^aDTE2;
932 //
933 TopoDS_Iterator aItV(aE1);
934 thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
935 return Standard_True;
936 }
937 }
938 //
939 // try to compute normal on the single edge
940 aExpE1.Init(theWire, TopAbs_EDGE);
941 for (; aExpE1.More(); aExpE1.Next()) {
942 const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
943 if (theMEdgesNoUniquePlane.Contains(aE)) {
944 continue;
945 }
946 BRepAdaptor_Curve aBAC(aE);
947 if (FindPlane(aBAC, thePlane)) {
948 return Standard_True;
949 }
950 theMEdgesNoUniquePlane.Add(aE);
951 }
952 return Standard_False;
953}
8ae442a8 954
955/////////////////////////////////////////////////////////////////////////
956//=======================================================================
957//class : BOPAlgo_TNV
958//purpose :
959//=======================================================================
960class BOPAlgo_TNV;
1155d05a 961typedef NCollection_Vector
8ae442a8 962 <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
963//
1155d05a 964typedef BOPTools_Functor
8ae442a8 965 <BOPAlgo_TNV,
966 BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
967//
1155d05a 968typedef BOPTools_Cnt
8ae442a8 969 <BOPAlgo_TNVFunctor,
970 BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
971//=======================================================================
1155d05a 972class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
8ae442a8 973 public:
974 BOPAlgo_TNV()
1155d05a 975 : BOPTools_BoxBndTreeSelector(),
8ae442a8 976 myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
977 };
978 //
979 ~BOPAlgo_TNV(){
980 };
981 //
982 void SetVertex(const TopoDS_Vertex& aV) {
983 myV=aV;
984 myPnt = BRep_Tool::Pnt(myV);
985 }
986 //
987 const TopoDS_Vertex& Vertex()const {
988 return myV;
989 }
990 //
1155d05a 991 void SetTree(BOPTools_BoxBndTree& aTree) {
8ae442a8 992 myTree=&aTree;
993 }
994 //
995 void SetTolerance(const Standard_Real theTol) {
996 myTol = theTol;
997 }
998 //
999 Standard_Real Tolerance() const {
1000 return myTol;
1001 }
1002 //
1003 const gp_Pnt& Pnt() const {
1004 return myPnt;
1005 }
1006 //
1007 void SetFuzzyValue(const Standard_Real theFuzzyValue) {
1008 myFuzzyValue = theFuzzyValue;
1009 }
1010 //
1011 void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
1012 myVecTNV = &theVec;
1013 }
1014 //
1015 virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
1016 {
1017 const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
1018 Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
1019 aTolSum2 *= aTolSum2;
1020 Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
1021 if (aD2 < aTolSum2)
1155d05a 1022 return BOPTools_BoxBndTreeSelector::Accept(theIndex);
8ae442a8 1023 return Standard_False;
1024 }
1025 //
1026 void Perform() {
1027 myTree->Select(*this);
1028 }
1029 //
1030 protected:
1031 Standard_Real myTol;
1032 Standard_Real myFuzzyValue;
1033 gp_Pnt myPnt;
1034 TopoDS_Vertex myV;
1155d05a 1035 BOPTools_BoxBndTree *myTree;
8ae442a8 1036 const BOPAlgo_VectorOfTNV *myVecTNV;
1037};
1038//
1039/////////////////////////////////////////////////////////////////////////
1040
1041//=======================================================================
1042//function : IntersectVertices
1043//purpose : Builds the chains of intersecting vertices
1044//=======================================================================
1155d05a 1045void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
8ae442a8 1046 const Standard_Boolean theRunParallel,
1047 const Standard_Real theFuzzyValue,
1155d05a 1048 TopTools_ListOfListOfShape& theChains)
8ae442a8 1049{
1050 Standard_Integer i, j, aNbV = theVertices.Extent();
1051 if (aNbV <= 1) {
1052 if (aNbV == 1) {
1155d05a 1053 theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
8ae442a8 1054 }
1055 return;
1056 }
1057 //
1058 // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1155d05a 1059 BOPTools_BoxBndTree aBBTree;
8ae442a8 1060 NCollection_UBTreeFiller <Standard_Integer,
1061 Bnd_Box> aTreeFiller(aBBTree);
1062 // Perform intersection of the vertices
1063 BOPAlgo_VectorOfTNV aVTNV;
1064 //
1065 // Use additional tolerance for intersection
1066 Standard_Real aTolAdd = theFuzzyValue / 2.;
1067 // Prepare the tree
1068 for (i = 1; i <= aNbV; ++i) {
1069 const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1070 Standard_Real aTol = BRep_Tool::Tolerance(aV);
1071 if (aTol < theVertices(i)) {
1072 aTol = theVertices(i);
1073 }
1074 // Build bnd box for vertex
1075 Bnd_Box aBox;
1076 aBox.Add(BRep_Tool::Pnt(aV));
1077 aBox.SetGap(aTol + aTolAdd);
1078 //
1079 aTreeFiller.Add(i, aBox);
1080 //
1155d05a 1081 BOPAlgo_TNV& aTNV=aVTNV.Appended();
8ae442a8 1082 aTNV.SetTree(aBBTree);
1083 aTNV.SetBox(aBox);
1084 aTNV.SetVertex(aV);
1085 aTNV.SetTolerance(aTol);
1086 aTNV.SetFuzzyValue(theFuzzyValue);
1087 aTNV.SetVectorOfTNV(aVTNV);
1088 }
1089 // Shake the tree
1090 aTreeFiller.Fill();
1091 //
1092 // Perform intersection
1093 BOPAlgo_TNVCnt::Perform(theRunParallel, aVTNV);
1094 //
1095 // Fence map
1155d05a 1096 TColStd_MapOfInteger aMFence;
8ae442a8 1097 // Build chains of intersecting vertices
1098 for (i = 1; i <= aNbV; ++i) {
1099 if (!aMFence.Add(i)) {
1100 continue;
1101 }
1102 // Start the chain
1155d05a 1103 TColStd_IndexedMapOfInteger aMChain;
8ae442a8 1104 aMChain.Add(i);
1105 //
1106 for (j = 1; j <= aMChain.Extent(); ++j) {
1107 BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1155d05a 1108 const TColStd_ListOfInteger& aLI = aTNV.Indices();
8ae442a8 1109 // Add these vertices into the chain
1155d05a 1110 for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
8ae442a8 1111 if (aMFence.Add(aItLI.Value())) {
1112 aMChain.Add(aItLI.Value());
1113 }
1114 }
1115 }
1116 //
1117 // Put vertices of the chain into the list
1155d05a 1118 TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
8ae442a8 1119 //
1120 Standard_Integer aNbVChain = aMChain.Extent();
1121 for (j = 1; j <= aNbVChain; ++j) {
1122 const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1123 aChain.Append(aVP);
1124 }
1125 }
1126}
977ad983 1127
1128//=======================================================================
1129//function : TreatCompound
1130//purpose :
1131//=======================================================================
1132void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1155d05a 1133 TopTools_MapOfShape& aMFence,
1134 TopTools_ListOfShape& theLS)
977ad983 1135{
1136 TopAbs_ShapeEnum aType = theS.ShapeType();
1137 if (aType != TopAbs_COMPOUND)
1138 {
1139 if (aMFence.Add(theS))
1140 theLS.Append(theS);
1141 return;
1142 }
1143 TopoDS_Iterator aIt(theS);
1144 for (; aIt.More(); aIt.Next())
1145 {
1146 const TopoDS_Shape& aS = aIt.Value();
1147 TreatCompound(aS, aMFence, theLS);
1148 }
1149}
b7cd7c2b 1150
1151//=======================================================================
1152// Classification of the faces relatively solids
1153//=======================================================================
1154
1155//=======================================================================
1156//class : BOPAlgo_ShapeBox
1157//purpose : Auxiliary class defining ShapeBox structure
1158//=======================================================================
1159class BOPAlgo_ShapeBox
1160{
1161public:
1162 //! Empty constructor
1163 BOPAlgo_ShapeBox() {};
1164 //! Sets the shape
1165 void SetShape(const TopoDS_Shape& theS)
1166 {
1167 myShape = theS;
1168 };
1169 //! Returns the shape
1170 const TopoDS_Shape& Shape() const
1171 {
1172 return myShape;
1173 };
1174 //! Sets the bounding box
1175 void SetBox(const Bnd_Box& theBox)
1176 {
1177 myBox = theBox;
1178 };
1179 //! Returns the bounding box
1180 const Bnd_Box& Box() const
1181 {
1182 return myBox;
1183 };
1184private:
1185 TopoDS_Shape myShape;
1186 Bnd_Box myBox;
1187};
1188// Vector of ShapeBox
1155d05a 1189typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
b7cd7c2b 1190
1191//=======================================================================
1192//class : BOPAlgo_FillIn3DParts
1193//purpose : Auxiliary class for faces classification in parallel mode
1194//=======================================================================
1195class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1196{
1197public:
1198 DEFINE_STANDARD_ALLOC
1199
1200 //! Constructor
1201 BOPAlgo_FillIn3DParts()
1202 {
1203 myBBTree = NULL;
1204 myVShapeBox = NULL;
1205 };
1206
1207 //! Destructor
1208 virtual ~BOPAlgo_FillIn3DParts() {};
1209
1210 //! Sets the solid
1211 void SetSolid(const TopoDS_Solid& theSolid)
1212 {
1213 mySolid = theSolid;
1214 };
1215
1216 //! Returns the solid
1217 const TopoDS_Solid& Solid() const
1218 {
1219 return mySolid;
1220 };
1221
1222 //! Sets the box for the solid
1223 void SetBoxS(const Bnd_Box& theBox)
1224 {
1225 myBoxS = theBox;
1226 };
1227
1228 //! Returns the solid's box
1229 const Bnd_Box& BoxS() const
1230 {
1231 return myBoxS;
1232 };
1233
1234 //! Sets own INTERNAL faces of the solid
1155d05a 1235 void SetOwnIF(const TopTools_ListOfShape& theLIF)
b7cd7c2b 1236 {
1237 myOwnIF = theLIF;
1238 };
1239
1240 //! Returns own INTERNAL faces of the solid
1155d05a 1241 const TopTools_ListOfShape& OwnIF() const
b7cd7c2b 1242 {
1243 return myOwnIF;
1244 };
1245
1246 //! Sets the Bounding Box tree
1155d05a 1247 void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
b7cd7c2b 1248 {
1155d05a 1249 myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
b7cd7c2b 1250 };
1251
1252 //! Sets the ShapeBox structure
1253 void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1254 {
1255 myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1256 };
1257
1258 //! Sets the context
1259 void SetContext(const Handle(IntTools_Context)& theContext)
1260 {
1261 myContext = theContext;
1262 }
1263
1264 //! Returns the context
1265 const Handle(IntTools_Context)& Context() const
1266 {
1267 return myContext;
1268 }
1269
1270 //! Performs the classification
1271 virtual void Perform();
1272
1273 //! Returns the faces classified as IN for solid
1155d05a 1274 const TopTools_ListOfShape& InFaces() const
b7cd7c2b 1275 {
1276 return myInFaces;
1277 };
1278
1279private:
1280
1281 //! Prepares Edge-Face connection map of the given shape
1282 void MapEdgesAndFaces(const TopoDS_Shape& theF,
1155d05a 1283 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
b7cd7c2b 1284 const Handle(NCollection_BaseAllocator)& theAlloc);
1285
1286 //! Makes the connexity block of faces using the connection map
1287 void MakeConnexityBlock(const TopoDS_Face& theF,
1155d05a 1288 const TopTools_IndexedMapOfShape& theMEToAvoid,
1289 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1290 TopTools_MapOfShape& theMFDone,
1291 TopTools_ListOfShape& theLCB,
b7cd7c2b 1292 TopoDS_Face& theFaceToClassify);
1293
1294 TopoDS_Solid mySolid; //! Solid
1295 Bnd_Box myBoxS; // Bounding box of the solid
1155d05a 1296 TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1297 TopTools_ListOfShape myInFaces; //! Faces classified as IN
b7cd7c2b 1298
1155d05a 1299 BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
b7cd7c2b 1300 BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1301
1302 TopoDS_Iterator myItF; //! Iterators
1303 TopoDS_Iterator myItW;
1304
1305 Handle(IntTools_Context) myContext; //! Context
1306};
1307
1308//=======================================================================
1309//function : BOPAlgo_FillIn3DParts::Perform
1310//purpose :
1311//=======================================================================
1312void BOPAlgo_FillIn3DParts::Perform()
1313{
1314 BOPAlgo_Algo::UserBreak();
1315
1316 myInFaces.Clear();
1317
1318 // 1. Select boxes of faces that are not out of aBoxS
1155d05a 1319 BOPTools_BoxBndTreeSelector aSelector;
b7cd7c2b 1320 aSelector.SetBox(myBoxS);
1321 //
1322 if (!myBBTree->Select(aSelector))
1323 return;
1324
1155d05a 1325 const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
b7cd7c2b 1326
1327 // 2. Fill maps of edges and faces of the solid
1328
1329 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1330
1331 BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1332
1155d05a 1333 TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1334 TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1335 TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
b7cd7c2b 1336
1337 // Check if the Solid contains any faces
1338 Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1339
1340 // Add own internal faces of the solid into aMSF
1155d05a 1341 TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
b7cd7c2b 1342 for (; aItLS.More(); aItLS.Next())
1343 aMSF.Add(aItLS.Value());
1344
1345 // 3. aIVec - faces to process.
1346 // Filter the selected faces with faces of the solid.
1155d05a 1347 NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
b7cd7c2b 1348
1155d05a 1349 TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
b7cd7c2b 1350 for (; aItLI.More(); aItLI.Next()) {
1351 Standard_Integer nFP = aItLI.Value();
1352 const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1353 if (!aMSF.Contains(aFP))
1155d05a 1354 aIVec.Appended() = nFP;
b7cd7c2b 1355 }
1356
1357 // 4. Classify faces relatively solid.
1358 // Store faces that are IN mySolid into <myInFaces>
1359
1155d05a 1360 Standard_Integer k, aNbFP = aIVec.Length();
b7cd7c2b 1361 // Sort indices if necessary
1362 if (aNbFP > 1)
1363 std::sort(aIVec.begin(), aIVec.end());
1364
1365 if (bIsEmpty)
1366 {
1367 // The solid is empty as it does not contain any faces.
1368 // It could happen when the input solid consists of INTERNAL faces only.
1369 // Classification of any point relatively empty solid would always give IN status.
1370 // Thus, we consider all selected faces as IN without real classification.
1371 for (k = 0; k < aNbFP; ++k)
1372 myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1373
1374 return;
1375 }
1376
1377 // Prepare EF map of faces to process for building connexity blocks
1155d05a 1378 TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
b7cd7c2b 1379 if (aNbFP > 1)
1380 {
1381 for (k = 0; k < aNbFP; ++k)
1382 MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1383 }
1384
1385 // Map of Edge-Face connection, necessary for solid classification.
1386 // It will be filled when first classification is performed.
1155d05a 1387 TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
b7cd7c2b 1388
1389 // Fence map to avoid processing of the same faces twice
1155d05a 1390 TopTools_MapOfShape aMFDone(1, anAlloc);
b7cd7c2b 1391
1392 for (k = 0; k < aNbFP; ++k)
1393 {
1394 Standard_Integer nFP = aIVec(k);
1395 const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1396 if (!aMFDone.Add(aFP))
1397 continue;
1398
1399 // Make connexity blocks of faces, avoiding passing through the
1400 // borders of the solid. It helps to reduce significantly the
1401 // number of classified faces.
1155d05a 1402 TopTools_ListOfShape aLCBF(anAlloc);
b7cd7c2b 1403 // The most appropriate face for classification
1404 TopoDS_Face aFaceToClassify;
1405 MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1406
1407 if (!myBoxS.IsWhole())
1408 {
1409 // First, try fast classification of the whole block by additional
1410 // check on bounding boxes - check that bounding boxes of all vertices
1411 // of the block interfere with the box of the solid.
1412 // If not, the faces are out.
1413 Standard_Boolean bOut = Standard_False;
1414 aItLS.Initialize(aLCBF);
1415 for (; aItLS.More() && !bOut; aItLS.Next())
1416 {
1417 TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1418 for (; anExpV.More() && !bOut; anExpV.Next())
1419 {
1420 const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1421 Bnd_Box aBBV;
1422 aBBV.Add(BRep_Tool::Pnt(aV));
1423 aBBV.SetGap(BRep_Tool::Tolerance(aV));
1424 bOut = myBoxS.IsOut(aBBV);
1425 }
1426 }
1427 if (bOut)
1428 continue;
1429 }
1430
1431 if (aFaceToClassify.IsNull())
1432 aFaceToClassify = aFP;
1433
1434 if (aMEFDS.IsEmpty())
1435 // Fill EF map for Solid
1155d05a 1436 TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
b7cd7c2b 1437
1438 // All vertices are interfere with the solids box, run classification.
1439 Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1440 (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1441 if (bIsIN)
1442 {
1443 aItLS.Initialize(aLCBF);
1444 for (; aItLS.More(); aItLS.Next())
1445 myInFaces.Append(aItLS.Value());
1446 }
1447 }
1448}
1449//=======================================================================
1450// function: MapEdgesAndFaces
1451// purpose:
1452//=======================================================================
1453void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1155d05a 1454 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
b7cd7c2b 1455 const Handle(NCollection_BaseAllocator)& theAllocator)
1456{
1457 myItF.Initialize(theF);
1458 for (; myItF.More(); myItF.Next())
1459 {
1460 const TopoDS_Shape& aW = myItF.Value();
1461 if (aW.ShapeType() != TopAbs_WIRE)
1462 continue;
1463
1464 myItW.Initialize(aW);
1465 for (; myItW.More(); myItW.Next())
1466 {
1467 const TopoDS_Shape& aE = myItW.Value();
1468
1155d05a 1469 TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
b7cd7c2b 1470 if (!pLF)
1155d05a 1471 pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
b7cd7c2b 1472 pLF->Append(theF);
1473 }
1474 }
1475}
1476//=======================================================================
1477// function: MakeConnexityBlock
1478// purpose:
1479//=======================================================================
1480void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1155d05a 1481 const TopTools_IndexedMapOfShape& theMEAvoid,
1482 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1483 TopTools_MapOfShape& theMFDone,
1484 TopTools_ListOfShape& theLCB,
b7cd7c2b 1485 TopoDS_Face& theFaceToClassify)
1486{
1487 // Add start element
1488 theLCB.Append(theFStart);
1489 if (theEFMap.IsEmpty())
1490 return;
1491
1155d05a 1492 TopTools_ListIteratorOfListOfShape aItCB(theLCB);
b7cd7c2b 1493 for (; aItCB.More(); aItCB.Next())
1494 {
1495 const TopoDS_Shape& aF = aItCB.Value();
1496 myItF.Initialize(aF);
1497 for (; myItF.More(); myItF.Next())
1498 {
1499 const TopoDS_Shape& aW = myItF.Value();
1500 if (aW.ShapeType() != TopAbs_WIRE)
1501 continue;
1502
1503 myItW.Initialize(aW);
1504 for (; myItW.More(); myItW.Next())
1505 {
7f3408c8 1506 const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1507 if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
b7cd7c2b 1508 {
1509 if (theFaceToClassify.IsNull())
1510 theFaceToClassify = TopoDS::Face(aF);
1511 continue;
1512 }
1513
1155d05a 1514 const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
b7cd7c2b 1515 if (!pLF)
1516 continue;
1155d05a 1517 TopTools_ListIteratorOfListOfShape aItLF(*pLF);
b7cd7c2b 1518 for (; aItLF.More(); aItLF.Next())
1519 {
1520 const TopoDS_Shape& aFToAdd = aItLF.Value();
1521 if (theMFDone.Add(aFToAdd))
1522 theLCB.Append(aFToAdd);
1523 }
1524 }
1525 }
1526 }
1527}
1528
1529// Vector of solid classifiers
1155d05a 1530typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
b7cd7c2b 1531
1532// Functors to perform classification
1155d05a 1533typedef BOPTools_ContextFunctor<BOPAlgo_FillIn3DParts,
1534 BOPAlgo_VectorOfFillIn3DParts,
1535 Handle(IntTools_Context),
1536 IntTools_Context> BOPAlgo_FillIn3DPartsFunctor;
b7cd7c2b 1537
1155d05a 1538typedef BOPTools_ContextCnt<BOPAlgo_FillIn3DPartsFunctor,
1539 BOPAlgo_VectorOfFillIn3DParts,
1540 Handle(IntTools_Context)> BOPAlgo_FillIn3DPartsCnt;
b7cd7c2b 1541
1542//=======================================================================
1543//function : ClassifyFaces
1544//purpose :
1545//=======================================================================
1155d05a 1546void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1547 const TopTools_ListOfShape& theSolids,
b7cd7c2b 1548 const Standard_Boolean theRunParallel,
1549 Handle(IntTools_Context)& theContext,
1155d05a 1550 TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1551 const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1552 const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
b7cd7c2b 1553{
1554 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1555
1556 // Fill the vector of shape box with faces and its bounding boxes
1557 BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1558
1155d05a 1559 TopTools_ListIteratorOfListOfShape aItLF(theFaces);
b7cd7c2b 1560 for (; aItLF.More(); aItLF.Next())
1561 {
1562 const TopoDS_Shape& aF = aItLF.Value();
1563 // Append face to the vector of shape box
1155d05a 1564 BOPAlgo_ShapeBox& aSB = aVSB.Appended();
b7cd7c2b 1565 aSB.SetShape(aF);
1566
1567 // Get bounding box for the face
1568 const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1569 if (pBox)
1570 aSB.SetBox(*pBox);
1571 else
1572 {
1573 // Build the bounding box
1574 Bnd_Box aBox;
1575 BRepBndLib::Add(aF, aBox);
1576 aSB.SetBox(aBox);
1577 }
1578 }
1579
1580 // Prepare UB tree of bounding boxes of the faces to classify
1581 // taking the bounding boxes from the just prepared vector
1155d05a 1582 BOPTools_BoxBndTree aBBTree;
b7cd7c2b 1583 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
1584
1155d05a 1585 Standard_Integer aNbF = aVSB.Length();
b7cd7c2b 1586 for (Standard_Integer i = 0; i < aNbF; ++i)
1587 {
1588 aTreeFiller.Add(i, aVSB(i).Box());
1589 }
1590
1591 // Shake tree filler
1592 aTreeFiller.Fill();
1593
1594 // Prepare vector of solids to classify
1595 BOPAlgo_VectorOfFillIn3DParts aVFIP;
1596
1155d05a 1597 TopTools_ListIteratorOfListOfShape aItLS(theSolids);
b7cd7c2b 1598 for (; aItLS.More(); aItLS.Next())
1599 {
1600 const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1601 // Append solid to the vector
1155d05a 1602 BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
b7cd7c2b 1603 aFIP.SetSolid(aSolid);
1604
1605 // Get bounding box for the solid
1606 const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1607 if (pBox)
1608 aFIP.SetBoxS(*pBox);
1609 else
1610 {
1611 // Build the bounding box
1612 Bnd_Box aBox;
1613 BRepBndLib::Add(aSolid, aBox);
1614 if (!aBox.IsWhole())
1615 {
1616 if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1617 aBox.SetWhole();
1618 }
1619 aFIP.SetBoxS(aBox);
1620 }
1621
1155d05a 1622 const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
b7cd7c2b 1623 if (pLIF)
1624 aFIP.SetOwnIF(*pLIF);
1625
1626 aFIP.SetBBTree(aBBTree);
1627 aFIP.SetShapeBoxVector(aVSB);
1628 }
1629
1630 // Perform classification
1631 //================================================================
1632 BOPAlgo_FillIn3DPartsCnt::Perform(theRunParallel, aVFIP, theContext);
1633 //================================================================
1634
1635 // Analyze the results and fill the resulting map
1636
1155d05a 1637 Standard_Integer aNbS = aVFIP.Length();
b7cd7c2b 1638 for (Standard_Integer i = 0; i < aNbS; ++i)
1639 {
1640 BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1641 const TopoDS_Shape& aS = aFIP.Solid();
1155d05a 1642 const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
b7cd7c2b 1643 theInParts.Add(aS, aLFIn);
1644 }
1645}
Open CASCADE Technology repository