projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0028786: Refactoring of the Warning/Error reporting system of Boolean Operations...
[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
18#include <gp_Pnt.hxx>
19#include <gp_Vec.hxx>
20#include <gp_Dir.hxx>
21#include <gp_Pln.hxx>
22#include <gp_Circ.hxx>
23#include <gp_Elips.hxx>
24#include <gp_Hypr.hxx>
25#include <gp_Parab.hxx>
26
27#include <Standard_ErrorHandler.hxx>
28#include <Standard_Failure.hxx>
29
30#include <TopoDS.hxx>
31#include <TopoDS_Edge.hxx>
32
8ae442a8 33#include <BOPCol_BoxBndTree.hxx>
e6ae74fd 34#include <BOPCol_IndexedMapOfShape.hxx>
42cf5bc1 35#include <BOPCol_IndexedMapOfInteger.hxx>
e6ae74fd 36#include <BOPCol_IndexedDataMapOfShapeListOfShape.hxx>
8ae442a8 37#include <BOPCol_MapOfShape.hxx>
38#include <BOPCol_NCVector.hxx>
39#include <BOPCol_Parallel.hxx>
e6ae74fd 40
41#include <TopExp_Explorer.hxx>
42
43#include <BRepAdaptor_Curve.hxx>
44
45#include <BRepBuilderAPI_MakeFace.hxx>
46
47#include <BRep_Tool.hxx>
48#include <BRep_Builder.hxx>
49
50#include <GeomAPI_ProjectPointOnCurve.hxx>
51#include <GeomAPI_ProjectPointOnSurf.hxx>
52
53#include <BOPAlgo_Builder.hxx>
54#include <BOPAlgo_BuilderFace.hxx>
55
4e57c75e 56#include <BOPDS_CommonBlock.hxx>
57#include <BOPDS_DataMapOfPaveBlockListOfPaveBlock.hxx>
42cf5bc1 58#include <BOPDS_DS.hxx>
59#include <BOPDS_IndexedMapOfPaveBlock.hxx>
60#include <BOPDS_MapOfPaveBlock.hxx>
61#include <BOPDS_PaveBlock.hxx>
e6ae74fd 62
63#include <BOPTools.hxx>
64#include <BOPTools_AlgoTools.hxx>
65#include <BOPTools_AlgoTools2D.hxx>
66
8ae442a8 67#include <NCollection_UBTreeFiller.hxx>
68
3510db62 69#include <IntTools_Context.hxx>
e6ae74fd 70
71typedef NCollection_IndexedDataMap
72 <TopoDS_Shape, gp_Dir, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapeDir;
73typedef NCollection_IndexedDataMap
74 <TopoDS_Shape, gp_Pln, TopTools_ShapeMapHasher> BOPAlgo_IndexedDataMapOfShapePln;
75
76static
77 void MakeWires(const BOPCol_IndexedMapOfShape& theEdges,
78 TopoDS_Compound& theWires,
79 const Standard_Boolean theCheckUniquePlane,
80 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
81 BOPCol_MapOfShape& theMEdgesNoUniquePlane);
82
83static
84 Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
85 gp_Pln& thePlane);
86
87static
88 Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
89 gp_Pln& thePlane,
90 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
91 BOPCol_MapOfShape& theMEdgesNoUniquePlane);
92
93static
94 Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
95 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
96 gp_Dir& theTgt);
97
98static
99 Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
100 gp_Vec& theTangent);
4e57c75e 101
4e57c75e 102//=======================================================================
103//function : FillMap
104//purpose :
105//=======================================================================
3510db62 106void BOPAlgo_Tools::FillMap(const Handle(BOPDS_PaveBlock)& aPB,
107 const Standard_Integer nF,
108 BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
109 const Handle(NCollection_BaseAllocator)& aAllocator)
4e57c75e 110{
edfa30de 111 BOPCol_ListOfInteger *pLI = aMPBLI.ChangeSeek(aPB);
112 if (!pLI) {
113 pLI = &aMPBLI(aMPBLI.Add(aPB, BOPCol_ListOfInteger(aAllocator)));
4e57c75e 114 }
edfa30de 115 pLI->Append(nF);
4e57c75e 116}
117//=======================================================================
118//function : PerformCommonBlocks
119//purpose :
120//=======================================================================
3510db62 121void BOPAlgo_Tools::PerformCommonBlocks(BOPDS_IndexedDataMapOfPaveBlockListOfPaveBlock& aMPBLPB,
122 const Handle(NCollection_BaseAllocator)& aAllocator,
123 BOPDS_PDS& pDS)
4e57c75e 124{
125 Standard_Integer aNbCB;
126 //
127 aNbCB=aMPBLPB.Extent();
128 if (!aNbCB) {
129 return;
130 }
131 //
4e57c75e 132 Handle(BOPDS_CommonBlock) aCB;
edfa30de 133 NCollection_List<BOPDS_ListOfPaveBlock> aMBlocks(aAllocator);
4e57c75e 134 //
edfa30de 135 BOPAlgo_Tools::MakeBlocks<Handle(BOPDS_PaveBlock), TColStd_MapTransientHasher>(aMPBLPB, aMBlocks, aAllocator);
4e57c75e 136 //
edfa30de 137 NCollection_List<BOPDS_ListOfPaveBlock>::Iterator aItB(aMBlocks);
138 for (; aItB.More(); aItB.Next()) {
139 const BOPDS_ListOfPaveBlock& aLPB = aItB.Value();
140 Standard_Integer aNbPB = aLPB.Extent();
4e57c75e 141 if (aNbPB>1) {
142 aCB=new BOPDS_CommonBlock;
edfa30de 143 aCB->SetPaveBlocks(aLPB);
4e57c75e 144 //
edfa30de 145 BOPDS_ListIteratorOfListOfPaveBlock aItLPB(aLPB);
4e57c75e 146 for (; aItLPB.More(); aItLPB.Next()) {
edfa30de 147 pDS->SetCommonBlock(aItLPB.Value(), aCB);
4e57c75e 148 }
149 }//if (aNbPB>1) {
150 }
151}
152//=======================================================================
153//function : PerformCommonBlocks
154//purpose :
155//=======================================================================
3510db62 156void BOPAlgo_Tools::PerformCommonBlocks(const BOPDS_IndexedDataMapOfPaveBlockListOfInteger& aMPBLI,
157 const Handle(NCollection_BaseAllocator)& ,//aAllocator
158 BOPDS_PDS& pDS)
4e57c75e 159{
160 Standard_Integer nF, i, aNb;
161 BOPCol_ListIteratorOfListOfInteger aItLI;
162 Handle(BOPDS_PaveBlock) aPB;
163 Handle(BOPDS_CommonBlock) aCB;
164 //
165 aNb=aMPBLI.Extent();
166 for (i=1; i<=aNb; ++i) {
167 aPB=aMPBLI.FindKey(i);
5a77460e 168 if (pDS->IsCommonBlock(aPB)) {
169 aCB=pDS->CommonBlock(aPB);
4e57c75e 170 }
171 else {
172 aCB=new BOPDS_CommonBlock;
173 aCB->AddPaveBlock(aPB);
174 }
175 //
176 const BOPCol_ListOfInteger& aLI=aMPBLI.FindFromKey(aPB);
3510db62 177 BOPCol_ListOfInteger aNewFaces;
178 const BOPCol_ListOfInteger& anOldFaces = aCB->Faces();
4e57c75e 179 aItLI.Initialize(aLI);
180 for (; aItLI.More(); aItLI.Next()) {
181 nF=aItLI.Value();
3510db62 182 // the both lists aLI and anOldFaces are expected to be short,
183 // so we can allow to run nested loop here
184 BOPCol_ListIteratorOfListOfInteger it(anOldFaces);
185 for (; it.More(); it.Next()) {
186 if (it.Value() == nF)
187 break;
188 }
189 if (!it.More()) {
190 aNewFaces.Append(nF);
191 }
4e57c75e 192 }
3510db62 193 aCB->AppendFaces(aNewFaces);
5a77460e 194 pDS->SetCommonBlock(aPB, aCB);
4e57c75e 195 }
196}
3510db62 197//=======================================================================
198//function : ComputeToleranceOfCB
199//purpose :
200//=======================================================================
201Standard_Real BOPAlgo_Tools::ComputeToleranceOfCB
202 (const Handle(BOPDS_CommonBlock)& theCB,
203 const BOPDS_PDS theDS,
204 const Handle(IntTools_Context)& theContext)
205{
206 Standard_Real aTolMax = 0.;
207 if (theCB.IsNull()) {
208 return aTolMax;
209 }
210 //
211 const Handle(BOPDS_PaveBlock)& aPBR = theCB->PaveBlock1();
212 Standard_Integer nE = aPBR->OriginalEdge();
213 const TopoDS_Edge& aEOr = *(TopoDS_Edge*)&theDS->Shape(nE);
214 aTolMax = BRep_Tool::Tolerance(aEOr);
215 //
216 const BOPDS_ListOfPaveBlock& aLPB = theCB->PaveBlocks();
217 const BOPCol_ListOfInteger& aLFI = theCB->Faces();
218 //
219 if ((aLPB.Extent() < 2) && aLFI.IsEmpty()) {
220 return aTolMax;
221 }
222 //
223 const Standard_Integer aNbPnt = 11;
224 Standard_Real aTol, aT, aT1, aT2, aDt;
225 gp_Pnt aP;
226 //
227 const Handle(Geom_Curve)& aC3D = BRep_Tool::Curve(aEOr, aT1, aT2);
228 //
229 aPBR->Range(aT1, aT2);
230 aDt = (aT2 - aT1) / (aNbPnt + 1);
231 //
232 // compute max tolerance for common blocks on edges
233 if (aLPB.Extent() > 1) {
234 // compute max distance between edges
235 BOPDS_ListIteratorOfListOfPaveBlock aItPB;
236 GeomAPI_ProjectPointOnCurve aProjPC;
237 //
238 aItPB.Initialize(aLPB);
239 for (; aItPB.More(); aItPB.Next()) {
240 const Handle(BOPDS_PaveBlock)& aPB = aItPB.Value();
241 if (aPB == aPBR) {
242 continue;
243 }
244 //
245 nE = aPB->OriginalEdge();
246 const TopoDS_Edge& aE = *(TopoDS_Edge*)&theDS->Shape(nE);
247 aTol = BRep_Tool::Tolerance(aE);
248 //
249 aProjPC = theContext->ProjPC(aE);
250 //
251 aT = aT1;
252 for (Standard_Integer i=1; i <= aNbPnt; i++) {
253 aT += aDt;
254 aC3D->D0(aT, aP);
255 aProjPC.Perform(aP);
256 if (aProjPC.NbPoints()) {
257 Standard_Real aTolNew = aTol + aProjPC.LowerDistance();
258 if (aTolNew > aTolMax) {
259 aTolMax = aTolNew;
260 }
261 }
262 }
263 }
264 }
265 //
266 // compute max tolerance for common blocks on faces
267 if (aLFI.Extent()) {
268 Standard_Integer nF;
269 GeomAPI_ProjectPointOnSurf aProjPS;
270 BOPCol_ListIteratorOfListOfInteger aItLI;
271 //
272 aItLI.Initialize(aLFI);
273 for (; aItLI.More(); aItLI.Next()) {
274 nF = aItLI.Value();
275 const TopoDS_Face& aF = *(TopoDS_Face*)&theDS->Shape(nF);
276 aTol = BRep_Tool::Tolerance(aF);
277 //
278 aProjPS = theContext->ProjPS(aF);
279 //
280 aT = aT1;
281 for (Standard_Integer i=1; i <= aNbPnt; i++) {
282 aT += aDt;
283 aC3D->D0(aT, aP);
284 aProjPS.Perform(aP);
285 if (aProjPS.NbPoints()) {
286 Standard_Real aTolNew = aTol + aProjPS.LowerDistance();
287 if (aTolNew > aTolMax) {
288 aTolMax = aTolNew;
289 }
290 }
291 }
292 }
293 }
294 //
295 return aTolMax;
296}
e6ae74fd 297
298//=======================================================================
299//function : EdgesToWires
300//purpose :
301//=======================================================================
302Standard_Integer BOPAlgo_Tools::EdgesToWires(const TopoDS_Shape& theEdges,
303 TopoDS_Shape& theWires,
304 const Standard_Boolean theShared,
305 const Standard_Real theAngTol)
306{
307 Standard_Integer iErr = 0;
308 //
309 // 1. Check the input edges
310 //
311 // List of edges to process
312 BOPCol_ListOfShape aLE;
313 //
314 TopExp_Explorer aExp(theEdges, TopAbs_EDGE);
315 for (; aExp.More(); aExp.Next()) {
316 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
317 if (!BRep_Tool::Degenerated(aE) && BRep_Tool::IsGeometric(aE)) {
318 aLE.Append(aExp.Current());
319 }
320 }
321 //
322 if (aLE.IsEmpty()) {
323 // no edges to process
324 iErr = 1;
325 return iErr;
326 }
327 //
328 BRep_Builder aBB;
329 TopoDS_Compound aRWires;
330 aBB.MakeCompound(aRWires);
331 //
332 if (aLE.Extent() == 1) {
333 TopoDS_Wire aWire;
334 aBB.MakeWire(aWire);
335 aBB.Add(aWire, aLE.First());
336 aBB.Add(aRWires, aWire);
337 theWires = aRWires;
338 return iErr;
339 }
340 //
341 // 2. Make compound of shared edges
342 TopoDS_Shape aSEdges;
343 //
344 if (!theShared) {
345 // intersect the edges if necessary
346 BOPAlgo_Builder aGF;
347 aGF.SetArguments(aLE);
348 aGF.Perform();
33ba8565 349 if (aGF.HasErrors()) {
e6ae74fd 350 // unable to share the edges
351 iErr = 2;
352 return iErr;
353 }
354 //
355 aSEdges = aGF.Shape();
356 }
357 else {
358 aBB.MakeCompound(TopoDS::Compound(aSEdges));
359 BOPCol_ListIteratorOfListOfShape aItLE(aLE);
360 for (; aItLE.More(); aItLE.Next()) {
361 aBB.Add(aSEdges, aItLE.Value());
362 }
363 }
364 //
365 // 3. Find edges located in the same planes and make wires from them.
366 // If the plane cannot be found for a single edge, then it is necessary
367 // to find all pairs of connected edges with the same cross product.
368
369 // Try to compute the plane in which the edge is located
370 BOPAlgo_IndexedDataMapOfShapePln aDMEdgePln;
371 // Compute the tangent direction for the edges for which the plane is not defined
372 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
373 //
374 // edges for which the plane is not found
375 BOPCol_MapOfShape aMEdgesNoUniquePlane;
376 //
377 // edges for which the plane cannot be found on a single edge
378 TopoDS_Compound aLEdges;
379 aBB.MakeCompound(aLEdges);
380 //
381 aExp.Init(aSEdges, TopAbs_EDGE);
382 for (; aExp.More(); aExp.Next()) {
383 const TopoDS_Edge& aE = TopoDS::Edge(aExp.Current());
384 BRepAdaptor_Curve aBAC(aE);
385 //
386 gp_Pln aPln;
387 if (FindPlane(aBAC, aPln)) {
388 aDMEdgePln.Add(aE, aPln);
389 }
390 else {
391 gp_Vec aVT;
392 if (FindEdgeTangent(aBAC, aVT)) {
393 aDMEdgeTgt.Add(aE, gp_Dir(aVT));
394 aBB.Add(aLEdges, aE);
395 aMEdgesNoUniquePlane.Add(aE);
396 }
397 }
398 }
399 //
400 typedef NCollection_List<gp_Dir> BOPAlgo_ListOfDir;
401 //
402 // to avoid processing of the same edges in the same plane store
403 // the processed planes into a list and use it as a fence map
404 BOPAlgo_ListOfDir aLPFence;
405 //
406 // used edges
407 BOPCol_MapOfShape aMEFence;
408 //
409 // look for a planes on the single edges
410 Standard_Integer i, j, aNbPlanes = aDMEdgePln.Extent(), aNbEdges = aDMEdgeTgt.Extent();
411 for (i = 1; i <= aNbPlanes; ++i) {
412 const TopoDS_Shape& aEI = aDMEdgePln.FindKey(i);
413 if (!aMEFence.Add(aEI)) {
414 continue;
415 }
416 //
417 const gp_Pln& aPlnI = aDMEdgePln(i);
418 const gp_Dir& aDI = aPlnI.Position().Direction();
419 //
420 aLPFence.Append(aDI);
421 //
422 BOPCol_IndexedMapOfShape aMEPln;
423 aMEPln.Add(aEI);
424 //
425 BOPCol_IndexedMapOfShape aMV;
426 BOPTools::MapShapes(aEI, TopAbs_VERTEX, aMV);
427 //
428 // look for other edges with the plane parallel to current one
429 for (j = i + 1; j <= aNbPlanes; ++j) {
430 const gp_Dir& aDJ = aDMEdgePln(j).Position().Direction();
431 if (aDI.IsParallel(aDJ, theAngTol)) {
432 const TopoDS_Shape& aEJ = aDMEdgePln.FindKey(j);
433 aMEPln.Add(aEJ);
434 aMEFence.Add(aEJ);
435 BOPTools::MapShapes(aEJ, TopAbs_VERTEX, aMV);
436 }
437 }
438 //
439 // look for all other edges located in the plane parallel to current one
440 TopoDS_Compound aCEPln;
441 aBB.MakeCompound(aCEPln);
442 //
443 for (j = 1; j <= aNbEdges; ++j) {
444 const gp_Dir& aDJ = aDMEdgeTgt(j);
445 if (aDI.IsNormal(aDJ, theAngTol)) {
446 aBB.Add(aCEPln, aDMEdgeTgt.FindKey(j));
447 }
448 }
449 //
450 // make blocks of these edges and check blocks to be connected
451 // to any of the already added edges or forming a wire themselves
452 BOPCol_ListOfShape aLCBE;
453 BOPTools_AlgoTools::MakeConnexityBlocks(aCEPln, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
454 //
455 // make wire from each block
456 BOPCol_ListIteratorOfListOfShape aItLCB(aLCBE);
457 for (; aItLCB.More(); aItLCB.Next()) {
458 const TopoDS_Shape& aCBE = aItLCB.Value();
459 //
460 // check connectivity
461 TopExp_Explorer aExpV(aCBE, TopAbs_VERTEX);
462 for (; aExpV.More(); aExpV.Next()) {
463 if (aMV.Contains(aExpV.Current())) {
464 break;
465 }
466 }
467 //
468 Standard_Boolean bAddBlock = aExpV.More();
469 if (!bAddBlock) {
470 // check if the edges are forming a wire
471 gp_Pln aPln;
472 bAddBlock = FindPlane(aCBE, aPln, aDMEdgeTgt, aMEdgesNoUniquePlane);
473 }
474 //
475 if (bAddBlock) {
476 // add edges
477 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
478 aMEPln.Add(aItE.Value());
479 }
480 }
481 }
482 //
483 MakeWires(aMEPln, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
484 }
485 //
486 // make connection map from vertices to edges to find the connected pairs
487 BOPCol_IndexedDataMapOfShapeListOfShape aDMVE;
488 BOPTools::MapShapesAndAncestors(aLEdges, TopAbs_VERTEX, TopAbs_EDGE, aDMVE);
489 //
490 // find planes for connected edges
491 Standard_Integer aNbV = aDMVE.Extent();
492 for (i = 1; i <= aNbV; ++i) {
493 const BOPCol_ListOfShape& aLEI = aDMVE(i);
494 if (aLEI.Extent() < 2) {
495 continue;
496 }
497 //
498 BOPCol_ListIteratorOfListOfShape aItLEI1(aLEI);
499 for (; aItLEI1.More(); aItLEI1.Next()) {
500 const TopoDS_Shape& aEI1 = aItLEI1.Value();
501 const gp_Dir& aDI1 = aDMEdgeTgt.FindFromKey(aEI1);
502 //
503 BOPCol_ListIteratorOfListOfShape aItLEI2(aLEI);
504 for (; aItLEI2.More(); aItLEI2.Next()) {
505 const TopoDS_Shape& aEI2 = aItLEI2.Value();
506 if (aEI2.IsSame(aEI1)) {
507 continue;
508 }
509 //
510 const gp_Dir& aDI2 = aDMEdgeTgt.FindFromKey(aEI2);
511 //
512 if (aDI1.IsParallel(aDI2, theAngTol)) {
513 continue;
514 }
515 //
516 gp_Dir aDNI = aDI1^aDI2;
517 //
518 // check if this normal direction has not been checked yet
519 BOPAlgo_ListOfDir::Iterator aItLPln(aLPFence);
520 for (; aItLPln.More(); aItLPln.Next()) {
521 if (aDNI.IsParallel(aItLPln.Value(), theAngTol)) {
522 break;
523 }
524 }
525 if (aItLPln.More()) {
526 continue;
527 }
528 //
529 aLPFence.Append(aDNI);
530 //
531 // find all other edges in the plane parallel to current one
532 BOPCol_IndexedMapOfShape aMEPln;
533 aMEPln.Add(aEI1);
534 aMEPln.Add(aEI2);
535 //
536 // iterate on all other edges to find all edges lying in the plane parallel to current one
537 for (j = 1; j <= aNbEdges; ++j) {
538 const gp_Dir& aDJ = aDMEdgeTgt(j);
539 if (aDNI.IsNormal(aDJ, theAngTol)) {
540 aMEPln.Add(aDMEdgeTgt.FindKey(j));
541 }
542 }
543 //
544 MakeWires(aMEPln, aRWires, Standard_True, aDMEdgeTgt, aMEdgesNoUniquePlane);
545 } // for (; aItLEI2.More(); aItLEI2.Next()) {
546 } // for (; aItLEI1.More(); aItLEI1.Next()) {
547 } // for (i = 1; i < aNb; ++i) {
548 //
549 // 4. Find unused edges and make wires from them
550 BOPCol_IndexedMapOfShape aMEAlone, aMEUsed;
551 BOPTools::MapShapes(aRWires, TopAbs_EDGE, aMEUsed);
552 //
553 for (i = 1; i <= aNbEdges; ++i) {
554 const TopoDS_Shape& aE = aDMEdgeTgt.FindKey(i);
555 if (!aMEUsed.Contains(aE)) {
556 aMEAlone.Add(aE);
557 }
558 }
559 //
560 MakeWires(aMEAlone, aRWires, Standard_False, aDMEdgeTgt, aMEdgesNoUniquePlane);
561 //
562 theWires = aRWires;
563 //
564 return iErr;
565}
566
567//=======================================================================
568//function : WiresToFaces
569//purpose :
570//=======================================================================
571Standard_Boolean BOPAlgo_Tools::WiresToFaces(const TopoDS_Shape& theWires,
572 TopoDS_Shape& theFaces,
573 const Standard_Real theAngTol)
574{
575 BRep_Builder aBB;
576 BOPCol_MapOfShape aMFence;
577 TopoDS_Compound aRFaces;
578 aBB.MakeCompound(aRFaces);
579 //
580 const Standard_Real aMax = 1.e+8;
581 //
582 // map to store the tangent vectors for the edges
583 BOPAlgo_IndexedDataMapOfShapeDir aDMEdgeTgt;
584 // maps to store the planes found for the wires
585 BOPAlgo_IndexedDataMapOfShapePln aDMWirePln;
586 // map to store the tolerance for the wire
587 NCollection_DataMap<TopoDS_Shape, Standard_Real, TopTools_ShapeMapHasher> aDMWireTol;
588 // edges for which the plane is not found
589 BOPCol_MapOfShape aMEdgesNoUniquePlane;
590 //
591 // Find planes for the wires
592 TopExp_Explorer aExpW(theWires, TopAbs_WIRE);
593 for (; aExpW.More(); aExpW.Next()) {
594 const TopoDS_Wire& aWire = TopoDS::Wire(aExpW.Current());
595 gp_Pln aPlane;
596 if (FindPlane(aWire, aPlane, aDMEdgeTgt, aMEdgesNoUniquePlane)) {
597 aDMWirePln.Add(aWire, aPlane);
598 // find tolerance for the wire - max tolerance of its edges
599 aDMWireTol.Bind(aWire, BRep_Tool::MaxTolerance(aWire, TopAbs_EDGE));
600 }
601 }
602 //
603 Standard_Integer i, j, aNb = aDMWirePln.Extent();
604 for (i = 1; i <= aNb; ++i) {
605 const TopoDS_Shape& aWireI = aDMWirePln.FindKey(i);
606 if (aMFence.Contains(aWireI)) {
607 continue;
608 }
609 //
610 const gp_Pln& aPlnI = aDMWirePln(i);
611 //
612 BOPCol_ListOfShape aLW;
613 aLW.Append(aWireI);
614 aMFence.Add(aWireI);
615 //
616 Standard_Real aTolI = aDMWireTol.Find(aWireI);
617 //
618 // Find other wires in the same plane
619 for (j = i + 1; j <= aNb; ++j) {
620 const TopoDS_Shape& aWireJ = aDMWirePln.FindKey(j);
621 if (aMFence.Contains(aWireJ)) {
622 continue;
623 }
624 //
625 // check if the planes are the same
626 const gp_Pln& aPlnJ = aDMWirePln(j);
627 // check direction of the planes
628 if (!aPlnI.Position().Direction().IsParallel(aPlnJ.Position().Direction(), theAngTol)) {
629 continue;
630 }
631 // check distance between the planes
632 Standard_Real aDist = aPlnI.Distance(aPlnJ.Location());
633 Standard_Real aTolJ = aDMWireTol.Find(aWireJ);
634 if (aDist > (aTolI + aTolJ)) {
635 continue;
636 }
637 //
638 aLW.Append(aWireJ);
639 aMFence.Add(aWireJ);
640 }
641 //
642 // Take the edges to build the face
643 BOPCol_ListOfShape aLE;
644 BOPCol_ListIteratorOfListOfShape aItLW(aLW);
645 for (; aItLW.More(); aItLW.Next()) {
646 TopoDS_Iterator aItE(aItLW.Value());
647 for (; aItE.More(); aItE.Next()) {
648 aLE.Append(aItE.Value().Oriented(TopAbs_FORWARD));
649 aLE.Append(aItE.Value().Oriented(TopAbs_REVERSED));
650 }
651 }
652 //
653 // build planar face
654 TopoDS_Face aFF = BRepBuilderAPI_MakeFace
655 (aPlnI, -aMax, aMax, -aMax, aMax).Face();
656 aFF.Orientation(TopAbs_FORWARD);
657 //
658 try {
659 OCC_CATCH_SIGNALS
660 //
661 // build pcurves for edges on this face
662 BOPTools_AlgoTools2D::BuildPCurveForEdgesOnPlane(aLE, aFF);
663 //
664 // split the face with the edges
665 BOPAlgo_BuilderFace aBF;
666 aBF.SetShapes(aLE);
667 aBF.SetFace(aFF);
668 aBF.Perform();
33ba8565 669 if (aBF.HasErrors()) {
e6ae74fd 670 continue;
671 }
672 //
673 const BOPCol_ListOfShape& aLFSp = aBF.Areas();
674 BOPCol_ListIteratorOfListOfShape aItLF(aLFSp);
675 for (; aItLF.More(); aItLF.Next()) {
676 const TopoDS_Shape& aFSp = aItLF.ChangeValue();
677 aBB.Add(aRFaces, aFSp);
678 }
679 }
680 catch (Standard_Failure) {
681 continue;
682 }
683 }
684 //
685 // fix tolerances of the resulting faces
686 BOPCol_IndexedMapOfShape aMEmpty;
687 BOPTools_AlgoTools::CorrectTolerances(aRFaces, aMEmpty, 0.05, Standard_False);
688 BOPTools_AlgoTools::CorrectShapeTolerances(aRFaces, aMEmpty, Standard_False);
689 //
690 theFaces = aRFaces;
691 TopoDS_Iterator aItF(theFaces);
692 return aItF.More();
693}
694
695//=======================================================================
696//function : MakeWires
697//purpose : Makes wires from the separate blocks of the given edges
698//=======================================================================
699void MakeWires(const BOPCol_IndexedMapOfShape& theEdges,
700 TopoDS_Compound& theWires,
701 const Standard_Boolean theCheckUniquePlane,
702 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
703 BOPCol_MapOfShape& theMEdgesNoUniquePlane)
704{
705 TopoDS_Compound aCE;
706 BRep_Builder().MakeCompound(aCE);
707 Standard_Integer i, aNbE = theEdges.Extent();
708 for (i = 1; i <= aNbE; ++i) {
709 BRep_Builder().Add(aCE, theEdges(i));
710 }
711 //
712 BOPCol_ListOfShape aLCBE;
713 BOPTools_AlgoTools::MakeConnexityBlocks(aCE, TopAbs_VERTEX, TopAbs_EDGE, aLCBE);
714 //
715 // make wire from each block
716 BOPCol_ListIteratorOfListOfShape aItLCB(aLCBE);
717 for (; aItLCB.More(); aItLCB.Next()) {
718 const TopoDS_Shape& aCBE = aItLCB.Value();
719 //
720 if (theCheckUniquePlane) {
721 gp_Pln aPln;
722 if (!FindPlane(aCBE, aPln, theDMEdgeTgt, theMEdgesNoUniquePlane)) {
723 continue;
724 }
725 }
726 //
727 TopoDS_Wire aWire;
728 BRep_Builder().MakeWire(aWire);
729 for (TopoDS_Iterator aItE(aCBE); aItE.More(); aItE.Next()) {
730 BRep_Builder().Add(aWire, aItE.Value());
731 }
732 //
733 BRep_Builder().Add(theWires, aWire);
734 }
735}
736
737//=======================================================================
738//function : FindEdgeTangent
739//purpose : Finds the tangent for the edge using the map
740//=======================================================================
741Standard_Boolean FindEdgeTangent(const TopoDS_Edge& theEdge,
742 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
743 gp_Dir& theTgt)
744{
745 gp_Dir *pDTE = theDMEdgeTgt.ChangeSeek(theEdge);
746 if (!pDTE) {
747 gp_Vec aVTE;
748 BRepAdaptor_Curve aBAC(theEdge);
749 if (!FindEdgeTangent(aBAC, aVTE)) {
750 return Standard_False;
751 }
752 pDTE = &theDMEdgeTgt(theDMEdgeTgt.Add(theEdge, gp_Dir(aVTE)));
753 }
754 theTgt = *pDTE;
755 return Standard_True;
756}
757
758//=======================================================================
759//function : FindEdgeTangent
760//purpose : Finds the tangent for the edge
761//=======================================================================
762Standard_Boolean FindEdgeTangent(const BRepAdaptor_Curve& theCurve,
763 gp_Vec& theTangent)
764{
765 if (!theCurve.Is3DCurve()) {
766 return Standard_False;
767 }
768 // for the line the tangent is defined by the direction
769 if (theCurve.GetType() == GeomAbs_Line) {
770 theTangent = theCurve.Line().Position().Direction();
771 return Standard_True;
772 }
773 //
774 // for other curves take D1 and check for its length
775 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
776 const Standard_Integer aNbP = 11;
777 const Standard_Real aDt = (aT2 - aT1) / aNbP;
778 //
779 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
780 gp_Pnt aP;
781 theCurve.D1(aT, aP, theTangent);
782 if (theTangent.Magnitude() > Precision::Confusion()) {
783 return Standard_True;
784 }
785 }
786 //
787 return Standard_False;
788}
789
790//=======================================================================
791//function : FindPlane
792//purpose : Finds the plane in which the edge is located
793//=======================================================================
794Standard_Boolean FindPlane(const BRepAdaptor_Curve& theCurve,
795 gp_Pln& thePlane)
796{
797 if (!theCurve.Is3DCurve()) {
798 return Standard_False;
799 }
800 //
801 Standard_Boolean bFound = Standard_True;
802 gp_Vec aVN;
803 switch (theCurve.GetType()) {
804 case GeomAbs_Line:
805 return Standard_False;
806 case GeomAbs_Circle:
807 aVN = theCurve.Circle().Position().Direction();
808 break;
809 case GeomAbs_Ellipse:
810 aVN = theCurve.Ellipse().Position().Direction();
811 break;
812 case GeomAbs_Hyperbola:
813 aVN = theCurve.Hyperbola().Position().Direction();
814 break;
815 case GeomAbs_Parabola:
816 aVN = theCurve.Parabola().Position().Direction();
817 break;
818 default: {
819 // for all other types of curve compute two tangent vectors
820 // on the curve and cross them
821 bFound = Standard_False;
822 Standard_Real aT, aT1(theCurve.FirstParameter()), aT2(theCurve.LastParameter());
823 const Standard_Integer aNbP = 11;
824 const Standard_Real aDt = (aT2 - aT1) / aNbP;
825 //
826 aT = aT1;
827 gp_Pnt aP1;
828 gp_Vec aV1;
829 theCurve.D1(aT, aP1, aV1);
830 //
831 for (aT = aT1 + aDt; aT <= aT2; aT += aDt) {
832 gp_Pnt aP2;
833 gp_Vec aV2;
834 theCurve.D1(aT, aP2, aV2);
835 //
836 aVN = aV1^aV2;
837 if (aVN.Magnitude() > Precision::Confusion()) {
838 bFound = Standard_True;
839 break;
840 }
841 }
842 break;
843 }
844 }
845 //
846 if (bFound) {
847 thePlane = gp_Pln(theCurve.Value(theCurve.FirstParameter()), gp_Dir(aVN));
848 }
849 return bFound;
850}
851
852//=======================================================================
853//function : FindPlane
854//purpose : Finds the plane in which the wire is located
855//=======================================================================
856Standard_Boolean FindPlane(const TopoDS_Shape& theWire,
857 gp_Pln& thePlane,
858 BOPAlgo_IndexedDataMapOfShapeDir& theDMEdgeTgt,
859 BOPCol_MapOfShape& theMEdgesNoUniquePlane)
860{
861 TopExp_Explorer aExpE1(theWire, TopAbs_EDGE);
862 if (!aExpE1.More()) {
863 return Standard_False;
864 }
865 //
866 // try to find two not parallel edges in wire to get normal of the plane
867 for (; aExpE1.More(); aExpE1.Next()) {
868 // get the first edge in the wire
869 const TopoDS_Edge& aE1 = TopoDS::Edge(aExpE1.Current());
870 //
871 // find tangent for the first edge
872 gp_Dir aDTE1;
873 if (!FindEdgeTangent(aE1, theDMEdgeTgt, aDTE1)) {
874 continue;
875 }
876 //
877 // find the other edge not parallel to the first one
878 TopExp_Explorer aExpE2(theWire, TopAbs_EDGE);
879 for (; aExpE2.More(); aExpE2.Next()) {
880 const TopoDS_Edge& aE2 = TopoDS::Edge(aExpE2.Current());
881 if (aE1.IsSame(aE2)) {
882 continue;
883 }
884 //
885 // find tangent for the second edge
886 gp_Dir aDTE2;
887 if (!FindEdgeTangent(aE2, theDMEdgeTgt, aDTE2)) {
888 continue;
889 }
890 //
891 if (aDTE1.IsParallel(aDTE2, Precision::Angular())) {
892 continue;
893 }
894 //
895 gp_Dir aDN = aDTE1^aDTE2;
896 //
897 TopoDS_Iterator aItV(aE1);
898 thePlane = gp_Pln(BRep_Tool::Pnt(TopoDS::Vertex(aItV.Value())), aDN);
899 return Standard_True;
900 }
901 }
902 //
903 // try to compute normal on the single edge
904 aExpE1.Init(theWire, TopAbs_EDGE);
905 for (; aExpE1.More(); aExpE1.Next()) {
906 const TopoDS_Edge& aE = TopoDS::Edge(aExpE1.Current());
907 if (theMEdgesNoUniquePlane.Contains(aE)) {
908 continue;
909 }
910 BRepAdaptor_Curve aBAC(aE);
911 if (FindPlane(aBAC, thePlane)) {
912 return Standard_True;
913 }
914 theMEdgesNoUniquePlane.Add(aE);
915 }
916 return Standard_False;
917}
8ae442a8 918
919/////////////////////////////////////////////////////////////////////////
920//=======================================================================
921//class : BOPAlgo_TNV
922//purpose :
923//=======================================================================
924class BOPAlgo_TNV;
925typedef BOPCol_NCVector
926 <BOPAlgo_TNV> BOPAlgo_VectorOfTNV;
927//
928typedef BOPCol_Functor
929 <BOPAlgo_TNV,
930 BOPAlgo_VectorOfTNV> BOPAlgo_TNVFunctor;
931//
932typedef BOPCol_Cnt
933 <BOPAlgo_TNVFunctor,
934 BOPAlgo_VectorOfTNV> BOPAlgo_TNVCnt;
935//=======================================================================
936class BOPAlgo_TNV : public BOPCol_BoxBndTreeSelector{
937 public:
938 BOPAlgo_TNV()
939 : BOPCol_BoxBndTreeSelector(),
940 myTol (0.), myFuzzyValue(0.), myTree(NULL), myVecTNV(NULL) {
941 };
942 //
943 ~BOPAlgo_TNV(){
944 };
945 //
946 void SetVertex(const TopoDS_Vertex& aV) {
947 myV=aV;
948 myPnt = BRep_Tool::Pnt(myV);
949 }
950 //
951 const TopoDS_Vertex& Vertex()const {
952 return myV;
953 }
954 //
955 void SetTree(BOPCol_BoxBndTree& aTree) {
956 myTree=&aTree;
957 }
958 //
959 void SetTolerance(const Standard_Real theTol) {
960 myTol = theTol;
961 }
962 //
963 Standard_Real Tolerance() const {
964 return myTol;
965 }
966 //
967 const gp_Pnt& Pnt() const {
968 return myPnt;
969 }
970 //
971 void SetFuzzyValue(const Standard_Real theFuzzyValue) {
972 myFuzzyValue = theFuzzyValue;
973 }
974 //
975 void SetVectorOfTNV(const BOPAlgo_VectorOfTNV& theVec) {
976 myVecTNV = &theVec;
977 }
978 //
979 virtual Standard_Boolean Accept(const Standard_Integer& theIndex)
980 {
981 const BOPAlgo_TNV& aTNV = myVecTNV->Value(theIndex - 1);
982 Standard_Real aTolSum2 = myTol + aTNV.Tolerance() + myFuzzyValue;
983 aTolSum2 *= aTolSum2;
984 Standard_Real aD2 = myPnt.SquareDistance(aTNV.Pnt());
985 if (aD2 < aTolSum2)
986 return BOPCol_BoxBndTreeSelector::Accept(theIndex);
987 return Standard_False;
988 }
989 //
990 void Perform() {
991 myTree->Select(*this);
992 }
993 //
994 protected:
995 Standard_Real myTol;
996 Standard_Real myFuzzyValue;
997 gp_Pnt myPnt;
998 TopoDS_Vertex myV;
999 BOPCol_BoxBndTree *myTree;
1000 const BOPAlgo_VectorOfTNV *myVecTNV;
1001};
1002//
1003/////////////////////////////////////////////////////////////////////////
1004
1005//=======================================================================
1006//function : IntersectVertices
1007//purpose : Builds the chains of intersecting vertices
1008//=======================================================================
1009void BOPAlgo_Tools::IntersectVertices(const BOPCol_IndexedDataMapOfShapeReal& theVertices,
1010 const Standard_Boolean theRunParallel,
1011 const Standard_Real theFuzzyValue,
1012 BOPCol_ListOfListOfShape& theChains)
1013{
1014 Standard_Integer i, j, aNbV = theVertices.Extent();
1015 if (aNbV <= 1) {
1016 if (aNbV == 1) {
1017 theChains.Append(BOPCol_ListOfShape()).Append(theVertices.FindKey(1));
1018 }
1019 return;
1020 }
1021 //
1022 // Use unbalanced binary tree of bounding boxes for sorting of the vertices.
1023 BOPCol_BoxBndTree aBBTree;
1024 NCollection_UBTreeFiller <Standard_Integer,
1025 Bnd_Box> aTreeFiller(aBBTree);
1026 // Perform intersection of the vertices
1027 BOPAlgo_VectorOfTNV aVTNV;
1028 //
1029 // Use additional tolerance for intersection
1030 Standard_Real aTolAdd = theFuzzyValue / 2.;
1031 // Prepare the tree
1032 for (i = 1; i <= aNbV; ++i) {
1033 const TopoDS_Vertex& aV = TopoDS::Vertex(theVertices.FindKey(i));
1034 Standard_Real aTol = BRep_Tool::Tolerance(aV);
1035 if (aTol < theVertices(i)) {
1036 aTol = theVertices(i);
1037 }
1038 // Build bnd box for vertex
1039 Bnd_Box aBox;
1040 aBox.Add(BRep_Tool::Pnt(aV));
1041 aBox.SetGap(aTol + aTolAdd);
1042 //
1043 aTreeFiller.Add(i, aBox);
1044 //
1045 BOPAlgo_TNV& aTNV=aVTNV.Append1();
1046 aTNV.SetTree(aBBTree);
1047 aTNV.SetBox(aBox);
1048 aTNV.SetVertex(aV);
1049 aTNV.SetTolerance(aTol);
1050 aTNV.SetFuzzyValue(theFuzzyValue);
1051 aTNV.SetVectorOfTNV(aVTNV);
1052 }
1053 // Shake the tree
1054 aTreeFiller.Fill();
1055 //
1056 // Perform intersection
1057 BOPAlgo_TNVCnt::Perform(theRunParallel, aVTNV);
1058 //
1059 // Fence map
1060 BOPCol_MapOfInteger aMFence;
1061 // Build chains of intersecting vertices
1062 for (i = 1; i <= aNbV; ++i) {
1063 if (!aMFence.Add(i)) {
1064 continue;
1065 }
1066 // Start the chain
1067 BOPCol_IndexedMapOfInteger aMChain;
1068 aMChain.Add(i);
1069 //
1070 for (j = 1; j <= aMChain.Extent(); ++j) {
1071 BOPAlgo_TNV& aTNV = aVTNV(aMChain(j) - 1);
1072 const BOPCol_ListOfInteger& aLI = aTNV.Indices();
1073 // Add these vertices into the chain
1074 for (BOPCol_ListIteratorOfListOfInteger aItLI(aLI); aItLI.More(); aItLI.Next()) {
1075 if (aMFence.Add(aItLI.Value())) {
1076 aMChain.Add(aItLI.Value());
1077 }
1078 }
1079 }
1080 //
1081 // Put vertices of the chain into the list
1082 BOPCol_ListOfShape& aChain = theChains.Append(BOPCol_ListOfShape());
1083 //
1084 Standard_Integer aNbVChain = aMChain.Extent();
1085 for (j = 1; j <= aNbVChain; ++j) {
1086 const TopoDS_Vertex& aVP = aVTNV(aMChain(j) - 1).Vertex();
1087 aChain.Append(aVP);
1088 }
1089 }
1090}
Open CASCADE Technology repository