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