projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0029511: Section fails for these two faces
[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,
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;
715 TopoDS_Iterator aItF(theFaces);
716 return aItF.More();
717}
718
719//=======================================================================
720//function : MakeWires
721//purpose : Makes wires from the separate blocks of the given edges
722//=======================================================================
1155d05a 723void MakeWires(const TopTools_IndexedMapOfShape& theEdges,
e6ae74fd 724 TopoDS_Compound& theWires,
725 const Standard_Boolean theCheckUniquePlane,
726 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 727 TopTools_MapOfShape& theMEdgesNoUniquePlane)
e6ae74fd 728{
729 TopoDS_Compound aCE;
730 BRep_Builder().MakeCompound(aCE);
731 Standard_Integer i, aNbE = theEdges.Extent();
732 for (i = 1; i <= aNbE; ++i) {
733 BRep_Builder().Add(aCE, theEdges(i));
734 }
735 //
1155d05a 736 TopTools_ListOfShape aLCBE;
e6ae74fd 737 BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
738 //
739 // make wire from each block
1155d05a 740 TopTools_ListIteratorOfListOfShape aItLCB(aLCBE);
e6ae74fd 741 for (; aItLCB.More(); aItLCB.Next()) {
742 const TopoDS_Shape& aCBE = aItLCB.Value();
743 //
744 if (theCheckUniquePlane) {
745 gp_Pln aPln;
746 if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
747 continue;
748 }
749 }
750 //
751 TopoDS_Wire aWire;
752 BRep_Builder().MakeWire(aWire);
753 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
754 BRep_Builder().Add(aWire, aItE.Value());
755 }
756 //
757 BRep_Builder().Add(theWires, aWire);
758 }
759}
760
761//=======================================================================
762//function : FindEdgeTangent
763//purpose : Finds the tangent for the edge using the map
764//=======================================================================
765Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
766 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
767 gp_Dir& theTgt)
768{
769 gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
770 if (!pDTE) {
771 gp_Vec aVTE;
772 BRepAdaptor_Curve aBAC(theEdge);
773 if (!FindEdgeTangent(aBAC, aVTE)) {
774 return Standard_False;
775 }
776 pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
777 }
778 theTgt = *pDTE;
779 return Standard_True;
780}
781
782//=======================================================================
783//function : FindEdgeTangent
784//purpose : Finds the tangent for the edge
785//=======================================================================
786Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
787 gp_Vec& theTangent)
788{
789 if (!theCurve.Is3DCurve()) {
790 return Standard_False;
791 }
792 // for the line the tangent is defined by the direction
793 if (theCurve.GetType() == GeomAbs_Line) {
794 theTangent = theCurve.Line().Position().Direction();
795 return Standard_True;
796 }
797 //
798 // for other curves take D1 and check for its length
799 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
800 const Standard_Integer aNbP = 11;
801 const Standard_Real aDt = (aT2 - aT1) / aNbP;
802 //
803 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
804 gp_Pnt aP;
805 theCurve.D1(aT, aP, theTangent);
806 if (theTangent.Magnitude() > Precision::Confusion()) {
807 return Standard_True;
808 }
809 }
810 //
811 return Standard_False;
812}
813
814//=======================================================================
815//function : FindPlane
816//purpose : Finds the plane in which the edge is located
817//=======================================================================
818Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
819 gp_Pln& thePlane)
820{
821 if (!theCurve.Is3DCurve()) {
822 return Standard_False;
823 }
824 //
825 Standard_Boolean bFound = Standard_True;
826 gp_Vec aVN;
827 switch (theCurve.GetType()) {
828 case GeomAbs_Line:
829 return Standard_False;
830 case GeomAbs_Circle:
831 aVN = theCurve.Circle().Position().Direction();
832 break;
833 case GeomAbs_Ellipse:
834 aVN = theCurve.Ellipse().Position().Direction();
835 break;
836 case GeomAbs_Hyperbola:
837 aVN = theCurve.Hyperbola().Position().Direction();
838 break;
839 case GeomAbs_Parabola:
840 aVN = theCurve.Parabola().Position().Direction();
841 break;
842 default: {
843 // for all other types of curve compute two tangent vectors
844 // on the curve and cross them
845 bFound = Standard_False;
846 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
847 const Standard_Integer aNbP = 11;
848 const Standard_Real aDt = (aT2 - aT1) / aNbP;
849 //
850 aT = aT1;
851 gp_Pnt aP1;
852 gp_Vec aV1;
853 theCurve.D1(aT, aP1, aV1);
854 //
855 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
856 gp_Pnt aP2;
857 gp_Vec aV2;
858 theCurve.D1(aT, aP2, aV2);
859 //
860 aVN = aV1^aV2;
861 if (aVN.Magnitude() > Precision::Confusion()) {
862 bFound = Standard_True;
863 break;
864 }
865 }
866 break;
867 }
868 }
869 //
870 if (bFound) {
871 thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
872 }
873 return bFound;
874}
875
876//=======================================================================
877//function : FindPlane
878//purpose : Finds the plane in which the wire is located
879//=======================================================================
880Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
881 gp_Pln& thePlane,
882 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
1155d05a 883 TopTools_MapOfShape& theMEdgesNoUniquePlane)
e6ae74fd 884{
885 TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
886 if (!aExpE1.More()) {
887 return Standard_False;
888 }
889 //
890 // try to find two not parallel edges in wire to get normal of the plane
891 for (; aExpE1.More(); aExpE1.Next()) {
892 // get the first edge in the wire
893 const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
894 //
895 // find tangent for the first edge
896 gp_Dir aDTE1;
897 if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
898 continue;
899 }
900 //
901 // find the other edge not parallel to the first one
902 TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
903 for (; aExpE2.More(); aExpE2.Next()) {
904 const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
905 if (aE1.IsSame(aE2)) {
906 continue;
907 }
908 //
909 // find tangent for the second edge
910 gp_Dir aDTE2;
911 if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
912 continue;
913 }
914 //
915 if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
916 continue;
917 }
918 //
919 gp_Dir aDN = aDTE1^aDTE2;
920 //
921 TopoDS_Iterator aItV(aE1);
922 thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
923 return Standard_True;
924 }
925 }
926 //
927 // try to compute normal on the single edge
928 aExpE1.Init(theWire, TopAbs_EDGE);
929 for (; aExpE1.More(); aExpE1.Next()) {
930 const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
931 if (theMEdgesNoUniquePlane.Contains(aE)) {
932 continue;
933 }
934 BRepAdaptor_Curve aBAC(aE);
935 if (FindPlane(aBAC, thePlane)) {
936 return Standard_True;
937 }
938 theMEdgesNoUniquePlane.Add(aE);
939 }
940 return Standard_False;
941}
8ae442a8 942
943/////////////////////////////////////////////////////////////////////////
944//=======================================================================
945//class : BOPAlgo_TNV
946//purpose :
947//=======================================================================
948class BOPAlgo_TNV;
1155d05a 949typedef NCollection_Vector
8ae442a8 950 <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
951//
1155d05a 952typedef BOPTools_Functor
8ae442a8 953 <BOPAlgo_TNV,
954 BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
955//
1155d05a 956typedef BOPTools_Cnt
8ae442a8 957 <BOPAlgo_TNVFunctor,
958 BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
959//=======================================================================
1155d05a 960class BOPAlgo_TNV : public BOPTools_BoxBndTreeSelector{
8ae442a8 961 public:
962 BOPAlgo_TNV()
1155d05a 963 : BOPTools_BoxBndTreeSelector(),
8ae442a8 964 myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
965 };
966 //
967 ~BOPAlgo_TNV(){
968 };
969 //
970 void SetVertex(const TopoDS_Vertex& aV) {
971 myV=aV;
972 myPnt = BRep_Tool::Pnt(myV);
973 }
974 //
975 const TopoDS_Vertex& Vertex()const {
976 return myV;
977 }
978 //
1155d05a 979 void SetTree(BOPTools_BoxBndTree& aTree) {
8ae442a8 980 myTree=&aTree;
981 }
982 //
983 void SetTolerance(const Standard_Real theTol) {
984 myTol = theTol;
985 }
986 //
987 Standard_Real Tolerance() const {
988 return myTol;
989 }
990 //
991 const gp_Pnt& Pnt() const {
992 return myPnt;
993 }
994 //
995 void SetFuzzyValue(const Standard_Real theFuzzyValue) {
996 myFuzzyValue = theFuzzyValue;
997 }
998 //
999 void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
1000 myVecTNV = &theVec;
1001 }
1002 //
1003 virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
1004 {
1005 const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
1006 Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
1007 aTolSum2 *= aTolSum2;
1008 Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
1009 if (aD2 < aTolSum2)
1155d05a 1010 return BOPTools_BoxBndTreeSelector::Accept(theIndex);
8ae442a8 1011 return Standard_False;
1012 }
1013 //
1014 void Perform() {
1015 myTree->Select(*this);
1016 }
1017 //
1018 protected:
1019 Standard_Real myTol;
1020 Standard_Real myFuzzyValue;
1021 gp_Pnt myPnt;
1022 TopoDS_Vertex myV;
1155d05a 1023 BOPTools_BoxBndTree *myTree;
8ae442a8 1024 const BOPAlgo_VectorOfTNV *myVecTNV;
1025};
1026//
1027/////////////////////////////////////////////////////////////////////////
1028
1029//=======================================================================
1030//function : IntersectVertices
1031//purpose : Builds the chains of intersecting vertices
1032//=======================================================================
1155d05a 1033void BOPAlgo_Tools::IntersectVertices(const TopTools_IndexedDataMapOfShapeReal& theVertices,
8ae442a8 1034 const Standard_Boolean theRunParallel,
1035 const Standard_Real theFuzzyValue,
1155d05a 1036 TopTools_ListOfListOfShape& theChains)
8ae442a8 1037{
1038 Standard_Integer i, j, aNbV = theVertices.Extent();
1039 if (aNbV <= 1) {
1040 if (aNbV == 1) {
1155d05a 1041 theChains.Append(TopTools_ListOfShape()).Append(theVertices.FindKey(1));
8ae442a8 1042 }
1043 return;
1044 }
1045 //
1046 // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1155d05a 1047 BOPTools_BoxBndTree aBBTree;
8ae442a8 1048 NCollection_UBTreeFiller <Standard_Integer,
1049 Bnd_Box> aTreeFiller(aBBTree);
1050 // Perform intersection of the vertices
1051 BOPAlgo_VectorOfTNV aVTNV;
1052 //
1053 // Use additional tolerance for intersection
1054 Standard_Real aTolAdd = theFuzzyValue / 2.;
1055 // Prepare the tree
1056 for (i = 1; i <= aNbV; ++i) {
1057 const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1058 Standard_Real aTol = BRep_Tool::Tolerance(aV);
1059 if (aTol < theVertices(i)) {
1060 aTol = theVertices(i);
1061 }
1062 // Build bnd box for vertex
1063 Bnd_Box aBox;
1064 aBox.Add(BRep_Tool::Pnt(aV));
1065 aBox.SetGap(aTol + aTolAdd);
1066 //
1067 aTreeFiller.Add(i, aBox);
1068 //
1155d05a 1069 BOPAlgo_TNV& aTNV=aVTNV.Appended();
8ae442a8 1070 aTNV.SetTree(aBBTree);
1071 aTNV.SetBox(aBox);
1072 aTNV.SetVertex(aV);
1073 aTNV.SetTolerance(aTol);
1074 aTNV.SetFuzzyValue(theFuzzyValue);
1075 aTNV.SetVectorOfTNV(aVTNV);
1076 }
1077 // Shake the tree
1078 aTreeFiller.Fill();
1079 //
1080 // Perform intersection
1081 BOPAlgo_TNVCnt::Perform(theRunParallel, aVTNV);
1082 //
1083 // Fence map
1155d05a 1084 TColStd_MapOfInteger aMFence;
8ae442a8 1085 // Build chains of intersecting vertices
1086 for (i = 1; i <= aNbV; ++i) {
1087 if (!aMFence.Add(i)) {
1088 continue;
1089 }
1090 // Start the chain
1155d05a 1091 TColStd_IndexedMapOfInteger aMChain;
8ae442a8 1092 aMChain.Add(i);
1093 //
1094 for (j = 1; j <= aMChain.Extent(); ++j) {
1095 BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1155d05a 1096 const TColStd_ListOfInteger& aLI = aTNV.Indices();
8ae442a8 1097 // Add these vertices into the chain
1155d05a 1098 for (TColStd_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
8ae442a8 1099 if (aMFence.Add(aItLI.Value())) {
1100 aMChain.Add(aItLI.Value());
1101 }
1102 }
1103 }
1104 //
1105 // Put vertices of the chain into the list
1155d05a 1106 TopTools_ListOfShape& aChain = theChains.Append(TopTools_ListOfShape());
8ae442a8 1107 //
1108 Standard_Integer aNbVChain = aMChain.Extent();
1109 for (j = 1; j <= aNbVChain; ++j) {
1110 const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1111 aChain.Append(aVP);
1112 }
1113 }
1114}
977ad983 1115
1116//=======================================================================
1117//function : TreatCompound
1118//purpose :
1119//=======================================================================
1120void BOPAlgo_Tools::TreatCompound(const TopoDS_Shape& theS,
1155d05a 1121 TopTools_MapOfShape& aMFence,
1122 TopTools_ListOfShape& theLS)
977ad983 1123{
1124 TopAbs_ShapeEnum aType = theS.ShapeType();
1125 if (aType != TopAbs_COMPOUND)
1126 {
1127 if (aMFence.Add(theS))
1128 theLS.Append(theS);
1129 return;
1130 }
1131 TopoDS_Iterator aIt(theS);
1132 for (; aIt.More(); aIt.Next())
1133 {
1134 const TopoDS_Shape& aS = aIt.Value();
1135 TreatCompound(aS, aMFence, theLS);
1136 }
1137}
b7cd7c2b 1138
1139//=======================================================================
1140// Classification of the faces relatively solids
1141//=======================================================================
1142
1143//=======================================================================
1144//class : BOPAlgo_ShapeBox
1145//purpose : Auxiliary class defining ShapeBox structure
1146//=======================================================================
1147class BOPAlgo_ShapeBox
1148{
1149public:
1150 //! Empty constructor
1151 BOPAlgo_ShapeBox() {};
1152 //! Sets the shape
1153 void SetShape(const TopoDS_Shape& theS)
1154 {
1155 myShape = theS;
1156 };
1157 //! Returns the shape
1158 const TopoDS_Shape& Shape() const
1159 {
1160 return myShape;
1161 };
1162 //! Sets the bounding box
1163 void SetBox(const Bnd_Box& theBox)
1164 {
1165 myBox = theBox;
1166 };
1167 //! Returns the bounding box
1168 const Bnd_Box& Box() const
1169 {
1170 return myBox;
1171 };
1172private:
1173 TopoDS_Shape myShape;
1174 Bnd_Box myBox;
1175};
1176// Vector of ShapeBox
1155d05a 1177typedef NCollection_Vector<BOPAlgo_ShapeBox> BOPAlgo_VectorOfShapeBox;
b7cd7c2b 1178
1179//=======================================================================
1180//class : BOPAlgo_FillIn3DParts
1181//purpose : Auxiliary class for faces classification in parallel mode
1182//=======================================================================
1183class BOPAlgo_FillIn3DParts : public BOPAlgo_Algo
1184{
1185public:
1186 DEFINE_STANDARD_ALLOC
1187
1188 //! Constructor
1189 BOPAlgo_FillIn3DParts()
1190 {
1191 myBBTree = NULL;
1192 myVShapeBox = NULL;
1193 };
1194
1195 //! Destructor
1196 virtual ~BOPAlgo_FillIn3DParts() {};
1197
1198 //! Sets the solid
1199 void SetSolid(const TopoDS_Solid& theSolid)
1200 {
1201 mySolid = theSolid;
1202 };
1203
1204 //! Returns the solid
1205 const TopoDS_Solid& Solid() const
1206 {
1207 return mySolid;
1208 };
1209
1210 //! Sets the box for the solid
1211 void SetBoxS(const Bnd_Box& theBox)
1212 {
1213 myBoxS = theBox;
1214 };
1215
1216 //! Returns the solid's box
1217 const Bnd_Box& BoxS() const
1218 {
1219 return myBoxS;
1220 };
1221
1222 //! Sets own INTERNAL faces of the solid
1155d05a 1223 void SetOwnIF(const TopTools_ListOfShape& theLIF)
b7cd7c2b 1224 {
1225 myOwnIF = theLIF;
1226 };
1227
1228 //! Returns own INTERNAL faces of the solid
1155d05a 1229 const TopTools_ListOfShape& OwnIF() const
b7cd7c2b 1230 {
1231 return myOwnIF;
1232 };
1233
1234 //! Sets the Bounding Box tree
1155d05a 1235 void SetBBTree(const BOPTools_BoxBndTree& theBBTree)
b7cd7c2b 1236 {
1155d05a 1237 myBBTree = (BOPTools_BoxBndTree*)&theBBTree;
b7cd7c2b 1238 };
1239
1240 //! Sets the ShapeBox structure
1241 void SetShapeBoxVector(const BOPAlgo_VectorOfShapeBox& theShapeBox)
1242 {
1243 myVShapeBox = (BOPAlgo_VectorOfShapeBox*)&theShapeBox;
1244 };
1245
1246 //! Sets the context
1247 void SetContext(const Handle(IntTools_Context)& theContext)
1248 {
1249 myContext = theContext;
1250 }
1251
1252 //! Returns the context
1253 const Handle(IntTools_Context)& Context() const
1254 {
1255 return myContext;
1256 }
1257
1258 //! Performs the classification
1259 virtual void Perform();
1260
1261 //! Returns the faces classified as IN for solid
1155d05a 1262 const TopTools_ListOfShape& InFaces() const
b7cd7c2b 1263 {
1264 return myInFaces;
1265 };
1266
1267private:
1268
1269 //! Prepares Edge-Face connection map of the given shape
1270 void MapEdgesAndFaces(const TopoDS_Shape& theF,
1155d05a 1271 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
b7cd7c2b 1272 const Handle(NCollection_BaseAllocator)& theAlloc);
1273
1274 //! Makes the connexity block of faces using the connection map
1275 void MakeConnexityBlock(const TopoDS_Face& theF,
1155d05a 1276 const TopTools_IndexedMapOfShape& theMEToAvoid,
1277 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1278 TopTools_MapOfShape& theMFDone,
1279 TopTools_ListOfShape& theLCB,
b7cd7c2b 1280 TopoDS_Face& theFaceToClassify);
1281
1282 TopoDS_Solid mySolid; //! Solid
1283 Bnd_Box myBoxS; // Bounding box of the solid
1155d05a 1284 TopTools_ListOfShape myOwnIF; //! Own INTERNAL faces of the solid
1285 TopTools_ListOfShape myInFaces; //! Faces classified as IN
b7cd7c2b 1286
1155d05a 1287 BOPTools_BoxBndTree* myBBTree; //! UB tree of bounding boxes
b7cd7c2b 1288 BOPAlgo_VectorOfShapeBox* myVShapeBox; //! ShapeBoxMap
1289
1290 TopoDS_Iterator myItF; //! Iterators
1291 TopoDS_Iterator myItW;
1292
1293 Handle(IntTools_Context) myContext; //! Context
1294};
1295
1296//=======================================================================
1297//function : BOPAlgo_FillIn3DParts::Perform
1298//purpose :
1299//=======================================================================
1300void BOPAlgo_FillIn3DParts::Perform()
1301{
1302 BOPAlgo_Algo::UserBreak();
1303
1304 myInFaces.Clear();
1305
1306 // 1. Select boxes of faces that are not out of aBoxS
1155d05a 1307 BOPTools_BoxBndTreeSelector aSelector;
b7cd7c2b 1308 aSelector.SetBox(myBoxS);
1309 //
1310 if (!myBBTree->Select(aSelector))
1311 return;
1312
1155d05a 1313 const TColStd_ListOfInteger& aLIFP = aSelector.Indices();
b7cd7c2b 1314
1315 // 2. Fill maps of edges and faces of the solid
1316
1317 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1318
1319 BOPAlgo_VectorOfShapeBox& aVShapeBox = *myVShapeBox;
1320
1155d05a 1321 TopTools_IndexedMapOfShape aMSE(1, anAlloc), aMSF(1, anAlloc);
1322 TopExp::MapShapes(mySolid, TopAbs_EDGE, aMSE);
1323 TopExp::MapShapes(mySolid, TopAbs_FACE, aMSF);
b7cd7c2b 1324
1325 // Check if the Solid contains any faces
1326 Standard_Boolean bIsEmpty = aMSF.IsEmpty();
1327
1328 // Add own internal faces of the solid into aMSF
1155d05a 1329 TopTools_ListIteratorOfListOfShape aItLS(myOwnIF);
b7cd7c2b 1330 for (; aItLS.More(); aItLS.Next())
1331 aMSF.Add(aItLS.Value());
1332
1333 // 3. aIVec - faces to process.
1334 // Filter the selected faces with faces of the solid.
1155d05a 1335 NCollection_Vector<Standard_Integer> aIVec(256, anAlloc);
b7cd7c2b 1336
1155d05a 1337 TColStd_ListIteratorOfListOfInteger aItLI(aLIFP);
b7cd7c2b 1338 for (; aItLI.More(); aItLI.Next()) {
1339 Standard_Integer nFP = aItLI.Value();
1340 const TopoDS_Shape& aFP = aVShapeBox(nFP).Shape();
1341 if (!aMSF.Contains(aFP))
1155d05a 1342 aIVec.Appended() = nFP;
b7cd7c2b 1343 }
1344
1345 // 4. Classify faces relatively solid.
1346 // Store faces that are IN mySolid into <myInFaces>
1347
1155d05a 1348 Standard_Integer k, aNbFP = aIVec.Length();
b7cd7c2b 1349 // Sort indices if necessary
1350 if (aNbFP > 1)
1351 std::sort(aIVec.begin(), aIVec.end());
1352
1353 if (bIsEmpty)
1354 {
1355 // The solid is empty as it does not contain any faces.
1356 // It could happen when the input solid consists of INTERNAL faces only.
1357 // Classification of any point relatively empty solid would always give IN status.
1358 // Thus, we consider all selected faces as IN without real classification.
1359 for (k = 0; k < aNbFP; ++k)
1360 myInFaces.Append(aVShapeBox(aIVec(k)).Shape());
1361
1362 return;
1363 }
1364
1365 // Prepare EF map of faces to process for building connexity blocks
1155d05a 1366 TopTools_IndexedDataMapOfShapeListOfShape aMEFP(1, anAlloc);
b7cd7c2b 1367 if (aNbFP > 1)
1368 {
1369 for (k = 0; k < aNbFP; ++k)
1370 MapEdgesAndFaces(aVShapeBox(aIVec(k)).Shape(), aMEFP, anAlloc);
1371 }
1372
1373 // Map of Edge-Face connection, necessary for solid classification.
1374 // It will be filled when first classification is performed.
1155d05a 1375 TopTools_IndexedDataMapOfShapeListOfShape aMEFDS(1, anAlloc);
b7cd7c2b 1376
1377 // Fence map to avoid processing of the same faces twice
1155d05a 1378 TopTools_MapOfShape aMFDone(1, anAlloc);
b7cd7c2b 1379
1380 for (k = 0; k < aNbFP; ++k)
1381 {
1382 Standard_Integer nFP = aIVec(k);
1383 const TopoDS_Face& aFP = (*(TopoDS_Face*)&aVShapeBox(nFP).Shape());
1384 if (!aMFDone.Add(aFP))
1385 continue;
1386
1387 // Make connexity blocks of faces, avoiding passing through the
1388 // borders of the solid. It helps to reduce significantly the
1389 // number of classified faces.
1155d05a 1390 TopTools_ListOfShape aLCBF(anAlloc);
b7cd7c2b 1391 // The most appropriate face for classification
1392 TopoDS_Face aFaceToClassify;
1393 MakeConnexityBlock(aFP, aMSE, aMEFP, aMFDone, aLCBF, aFaceToClassify);
1394
1395 if (!myBoxS.IsWhole())
1396 {
1397 // First, try fast classification of the whole block by additional
1398 // check on bounding boxes - check that bounding boxes of all vertices
1399 // of the block interfere with the box of the solid.
1400 // If not, the faces are out.
1401 Standard_Boolean bOut = Standard_False;
1402 aItLS.Initialize(aLCBF);
1403 for (; aItLS.More() && !bOut; aItLS.Next())
1404 {
1405 TopExp_Explorer anExpV(aItLS.Value(), TopAbs_VERTEX);
1406 for (; anExpV.More() && !bOut; anExpV.Next())
1407 {
1408 const TopoDS_Vertex& aV = TopoDS::Vertex(anExpV.Current());
1409 Bnd_Box aBBV;
1410 aBBV.Add(BRep_Tool::Pnt(aV));
1411 aBBV.SetGap(BRep_Tool::Tolerance(aV));
1412 bOut = myBoxS.IsOut(aBBV);
1413 }
1414 }
1415 if (bOut)
1416 continue;
1417 }
1418
1419 if (aFaceToClassify.IsNull())
1420 aFaceToClassify = aFP;
1421
1422 if (aMEFDS.IsEmpty())
1423 // Fill EF map for Solid
1155d05a 1424 TopExp::MapShapesAndAncestors(mySolid, TopAbs_EDGE, TopAbs_FACE, aMEFDS);
b7cd7c2b 1425
1426 // All vertices are interfere with the solids box, run classification.
1427 Standard_Boolean bIsIN = BOPTools_AlgoTools::IsInternalFace
1428 (aFaceToClassify, mySolid, aMEFDS, Precision::Confusion(), myContext);
1429 if (bIsIN)
1430 {
1431 aItLS.Initialize(aLCBF);
1432 for (; aItLS.More(); aItLS.Next())
1433 myInFaces.Append(aItLS.Value());
1434 }
1435 }
1436}
1437//=======================================================================
1438// function: MapEdgesAndFaces
1439// purpose:
1440//=======================================================================
1441void BOPAlgo_FillIn3DParts::MapEdgesAndFaces(const TopoDS_Shape& theF,
1155d05a 1442 TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
b7cd7c2b 1443 const Handle(NCollection_BaseAllocator)& theAllocator)
1444{
1445 myItF.Initialize(theF);
1446 for (; myItF.More(); myItF.Next())
1447 {
1448 const TopoDS_Shape& aW = myItF.Value();
1449 if (aW.ShapeType() != TopAbs_WIRE)
1450 continue;
1451
1452 myItW.Initialize(aW);
1453 for (; myItW.More(); myItW.Next())
1454 {
1455 const TopoDS_Shape& aE = myItW.Value();
1456
1155d05a 1457 TopTools_ListOfShape* pLF = theEFMap.ChangeSeek(aE);
b7cd7c2b 1458 if (!pLF)
1155d05a 1459 pLF = &theEFMap(theEFMap.Add(aE, TopTools_ListOfShape(theAllocator)));
b7cd7c2b 1460 pLF->Append(theF);
1461 }
1462 }
1463}
1464//=======================================================================
1465// function: MakeConnexityBlock
1466// purpose:
1467//=======================================================================
1468void BOPAlgo_FillIn3DParts::MakeConnexityBlock(const TopoDS_Face& theFStart,
1155d05a 1469 const TopTools_IndexedMapOfShape& theMEAvoid,
1470 const TopTools_IndexedDataMapOfShapeListOfShape& theEFMap,
1471 TopTools_MapOfShape& theMFDone,
1472 TopTools_ListOfShape& theLCB,
b7cd7c2b 1473 TopoDS_Face& theFaceToClassify)
1474{
1475 // Add start element
1476 theLCB.Append(theFStart);
1477 if (theEFMap.IsEmpty())
1478 return;
1479
1155d05a 1480 TopTools_ListIteratorOfListOfShape aItCB(theLCB);
b7cd7c2b 1481 for (; aItCB.More(); aItCB.Next())
1482 {
1483 const TopoDS_Shape& aF = aItCB.Value();
1484 myItF.Initialize(aF);
1485 for (; myItF.More(); myItF.Next())
1486 {
1487 const TopoDS_Shape& aW = myItF.Value();
1488 if (aW.ShapeType() != TopAbs_WIRE)
1489 continue;
1490
1491 myItW.Initialize(aW);
1492 for (; myItW.More(); myItW.Next())
1493 {
7f3408c8 1494 const TopoDS_Edge& aE = TopoDS::Edge(myItW.Value());
1495 if (theMEAvoid.Contains(aE) || BRep_Tool::Degenerated(aE))
b7cd7c2b 1496 {
1497 if (theFaceToClassify.IsNull())
1498 theFaceToClassify = TopoDS::Face(aF);
1499 continue;
1500 }
1501
1155d05a 1502 const TopTools_ListOfShape* pLF = theEFMap.Seek(aE);
b7cd7c2b 1503 if (!pLF)
1504 continue;
1155d05a 1505 TopTools_ListIteratorOfListOfShape aItLF(*pLF);
b7cd7c2b 1506 for (; aItLF.More(); aItLF.Next())
1507 {
1508 const TopoDS_Shape& aFToAdd = aItLF.Value();
1509 if (theMFDone.Add(aFToAdd))
1510 theLCB.Append(aFToAdd);
1511 }
1512 }
1513 }
1514 }
1515}
1516
1517// Vector of solid classifiers
1155d05a 1518typedef NCollection_Vector<BOPAlgo_FillIn3DParts> BOPAlgo_VectorOfFillIn3DParts;
b7cd7c2b 1519
1520// Functors to perform classification
1155d05a 1521typedef BOPTools_ContextFunctor<BOPAlgo_FillIn3DParts,
1522 BOPAlgo_VectorOfFillIn3DParts,
1523 Handle(IntTools_Context),
1524 IntTools_Context> BOPAlgo_FillIn3DPartsFunctor;
b7cd7c2b 1525
1155d05a 1526typedef BOPTools_ContextCnt<BOPAlgo_FillIn3DPartsFunctor,
1527 BOPAlgo_VectorOfFillIn3DParts,
1528 Handle(IntTools_Context)> BOPAlgo_FillIn3DPartsCnt;
b7cd7c2b 1529
1530//=======================================================================
1531//function : ClassifyFaces
1532//purpose :
1533//=======================================================================
1155d05a 1534void BOPAlgo_Tools::ClassifyFaces(const TopTools_ListOfShape& theFaces,
1535 const TopTools_ListOfShape& theSolids,
b7cd7c2b 1536 const Standard_Boolean theRunParallel,
1537 Handle(IntTools_Context)& theContext,
1155d05a 1538 TopTools_IndexedDataMapOfShapeListOfShape& theInParts,
1539 const TopTools_DataMapOfShapeBox& theShapeBoxMap,
1540 const TopTools_DataMapOfShapeListOfShape& theSolidsIF)
b7cd7c2b 1541{
1542 Handle(NCollection_BaseAllocator) anAlloc = new NCollection_IncAllocator;
1543
1544 // Fill the vector of shape box with faces and its bounding boxes
1545 BOPAlgo_VectorOfShapeBox aVSB(256, anAlloc);
1546
1155d05a 1547 TopTools_ListIteratorOfListOfShape aItLF(theFaces);
b7cd7c2b 1548 for (; aItLF.More(); aItLF.Next())
1549 {
1550 const TopoDS_Shape& aF = aItLF.Value();
1551 // Append face to the vector of shape box
1155d05a 1552 BOPAlgo_ShapeBox& aSB = aVSB.Appended();
b7cd7c2b 1553 aSB.SetShape(aF);
1554
1555 // Get bounding box for the face
1556 const Bnd_Box* pBox = theShapeBoxMap.Seek(aF);
1557 if (pBox)
1558 aSB.SetBox(*pBox);
1559 else
1560 {
1561 // Build the bounding box
1562 Bnd_Box aBox;
1563 BRepBndLib::Add(aF, aBox);
1564 aSB.SetBox(aBox);
1565 }
1566 }
1567
1568 // Prepare UB tree of bounding boxes of the faces to classify
1569 // taking the bounding boxes from the just prepared vector
1155d05a 1570 BOPTools_BoxBndTree aBBTree;
b7cd7c2b 1571 NCollection_UBTreeFiller <Standard_Integer, Bnd_Box> aTreeFiller(aBBTree);
1572
1155d05a 1573 Standard_Integer aNbF = aVSB.Length();
b7cd7c2b 1574 for (Standard_Integer i = 0; i < aNbF; ++i)
1575 {
1576 aTreeFiller.Add(i, aVSB(i).Box());
1577 }
1578
1579 // Shake tree filler
1580 aTreeFiller.Fill();
1581
1582 // Prepare vector of solids to classify
1583 BOPAlgo_VectorOfFillIn3DParts aVFIP;
1584
1155d05a 1585 TopTools_ListIteratorOfListOfShape aItLS(theSolids);
b7cd7c2b 1586 for (; aItLS.More(); aItLS.Next())
1587 {
1588 const TopoDS_Solid& aSolid = TopoDS::Solid(aItLS.Value());
1589 // Append solid to the vector
1155d05a 1590 BOPAlgo_FillIn3DParts& aFIP = aVFIP.Appended();
b7cd7c2b 1591 aFIP.SetSolid(aSolid);
1592
1593 // Get bounding box for the solid
1594 const Bnd_Box* pBox = theShapeBoxMap.Seek(aSolid);
1595 if (pBox)
1596 aFIP.SetBoxS(*pBox);
1597 else
1598 {
1599 // Build the bounding box
1600 Bnd_Box aBox;
1601 BRepBndLib::Add(aSolid, aBox);
1602 if (!aBox.IsWhole())
1603 {
1604 if (BOPTools_AlgoTools::IsInvertedSolid(aSolid))
1605 aBox.SetWhole();
1606 }
1607 aFIP.SetBoxS(aBox);
1608 }
1609
1155d05a 1610 const TopTools_ListOfShape* pLIF = theSolidsIF.Seek(aSolid);
b7cd7c2b 1611 if (pLIF)
1612 aFIP.SetOwnIF(*pLIF);
1613
1614 aFIP.SetBBTree(aBBTree);
1615 aFIP.SetShapeBoxVector(aVSB);
1616 }
1617
1618 // Perform classification
1619 //================================================================
1620 BOPAlgo_FillIn3DPartsCnt::Perform(theRunParallel, aVFIP, theContext);
1621 //================================================================
1622
1623 // Analyze the results and fill the resulting map
1624
1155d05a 1625 Standard_Integer aNbS = aVFIP.Length();
b7cd7c2b 1626 for (Standard_Integer i = 0; i < aNbS; ++i)
1627 {
1628 BOPAlgo_FillIn3DParts& aFIP = aVFIP(i);
1629 const TopoDS_Shape& aS = aFIP.Solid();
1155d05a 1630 const TopTools_ListOfShape& aLFIn = aFIP.InFaces();
b7cd7c2b 1631 theInParts.Add(aS, aLFIn);
1632 }
1633}
Open CASCADE Technology repository