1 // GEOM PARTITION : partition algorithm
3 // Copyright (C) 2003 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R& D, LEG, PRINCIPIA R& D, BUREAU VERITAS
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
24 // File : Partition_Inter2d.cxx
25 // Author : Benedicte MARTIN
29 #include "Partition_Inter2d.ixx"
31 #include "utilities.h"
33 #include <BRepAdaptor_Curve.hxx>
34 #include <BRepAlgo_AsDes.hxx>
35 #include <BRepLib_MakeVertex.hxx>
36 #include <BRep_Builder.hxx>
37 #include <BRep_Tool.hxx>
38 #include <Geom_Surface.hxx>
39 #include <Precision.hxx>
41 #include <TopExp_Explorer.hxx>
42 #include <TopOpeBRepDS_Transition.hxx>
43 #include <TopOpeBRep_EdgesIntersector.hxx>
44 #include <TopOpeBRep_Point2d.hxx>
45 #include <TopTools_ListIteratorOfListOfShape.hxx>
46 #include <TopTools_ListOfShape.hxx>
47 #include <TopTools_MapIteratorOfMapOfShape.hxx>
48 #include <TopTools_MapOfShape.hxx>
50 #include <TopoDS_Edge.hxx>
51 #include <TopoDS_Vertex.hxx>
55 static Standard_Boolean TestEdges = 0;
56 static Standard_Integer NbF2d = 0;
57 static Standard_Integer NbE2d = 0;
62 //=======================================================================
63 //function : getOtherShape
65 //=======================================================================
67 static TopoDS_Shape getOtherShape(const TopoDS_Shape& theS,
68 const TopTools_ListOfShape& theSList)
70 TopTools_ListIteratorOfListOfShape anIt( theSList );
71 for ( ; anIt.More(); anIt.Next() )
72 if (!theS.IsSame( anIt.Value() ))
75 return TopoDS_Shape();
78 //=======================================================================
80 //purpose : on theE, find a vertex close to theV, such that an edge
81 // passing through it is an itersection of theF1 and theF2.
82 // theE intersects theE2 at theV
83 //=======================================================================
85 static Standard_Boolean findVOnE(const TopoDS_Vertex & theV,
86 const TopoDS_Edge& theE,
87 const TopoDS_Edge& theE2,
88 const TopoDS_Shape& theF1,
89 const TopoDS_Shape& theF2,
90 const Handle(BRepAlgo_AsDes)& theAsDes,
91 TopoDS_Vertex & theFoundV)
93 Standard_Real MinDist2 = ::RealLast();
96 // check all vertices on theE
97 const TopTools_ListOfShape& aVList = theAsDes->Descendant( theE );
98 TopTools_ListIteratorOfListOfShape anIt( aVList );
100 P = BRep_Tool::Pnt( theV );
101 for ( ; anIt.More(); anIt.Next() )
104 TopoDS_Vertex & V = TopoDS::Vertex( anIt.Value() );
105 Standard_Real dist2 = P.SquareDistance( BRep_Tool::Pnt( V ));
106 if (dist2 < MinDist2)
111 // V is a candidate if among edges passing through V there is one
112 // which is an intersection of theF1 and theF2
113 TopTools_ListIteratorOfListOfShape anEIt( theAsDes->Ascendant( V ));
114 Standard_Boolean isOk = Standard_False;
115 for ( ; !isOk && anEIt.More(); anEIt.Next() )
117 const TopoDS_Shape & E2 = anEIt.Value();
118 if ( theE2.IsSame( E2 ))
120 const TopTools_ListOfShape & aFList = theAsDes->Ascendant( E2 );
121 if (aFList.IsEmpty())
123 if ( theF1.IsSame( aFList.First() ))
124 isOk = theF2.IsSame( aFList.Last() );
126 isOk = theF2.IsSame( aFList.First() ) && theF1.IsSame( aFList.Last() );
132 if (theFoundV.IsNull())
133 return Standard_False;
135 // check that MinDist2 is not too large
138 Handle(Geom_Curve) aCurve = BRep_Tool::Curve( theE, L, f, l );
139 gp_Pnt P1 = aCurve->Value( f );
140 gp_Pnt P2 = aCurve->Value( 0.3 * f + 0.7 * l );
141 //gp_Pnt P2 = aCurve->Value( 0.5 * ( f + l ));
142 if (MinDist2 > P1.SquareDistance( P2 ))
143 return Standard_False;
146 MESSAGE("findVOnE: found MinDist = " << sqrt (MinDist2));
149 return Standard_True;
152 //=======================================================================
154 //purpose : Put V in AsDes as intersection of E1 and E2.
155 // Check that vertex equal to V already exists on one
156 // of edges, in such a case, V is not added but
157 // existing vertex is updated to be on E1 and E2 and
158 // is returned insead of V.
159 //=======================================================================
161 TopoDS_Vertex Partition_Inter2d::AddVonE(const TopoDS_Vertex& theV,
162 const TopoDS_Edge& E1,
163 const TopoDS_Edge& E2,
164 const Handle(BRepAlgo_AsDes)& AsDes,
165 const TopoDS_Face& theF)
168 //-------------------------------------------------------------
169 // test if the points of intersection already exist. If not,
170 // add as descendants of the edges.
171 // nb: theses points are only vertices of intersection.
172 //-------------------------------------------------------------
173 const TopTools_ListOfShape& VOnE1 = AsDes->Descendant(E1);
174 const TopTools_ListOfShape& VOnE2 = AsDes->Descendant(E2);
177 TopTools_ListIteratorOfListOfShape it;
179 TopAbs_Orientation O1,O2;
181 Standard_Real Tol,Tol1,Tol2;
182 Standard_Boolean OnE1,OnE2;
184 TopoDS_Vertex V = theV;
186 U1 = BRep_Tool::Parameter(V,E1);
187 U2 = BRep_Tool::Parameter(V,E2);
188 O1 = V.Orientation();
190 P1 = BRep_Tool::Pnt(V);
191 Tol = BRep_Tool::Tolerance( V );
192 OnE1 = OnE2 = Standard_False;
194 //-----------------------------------------------------------------
195 // Search if the point of intersection is a vertex of E1.
196 //-----------------------------------------------------------------
197 for (it.Initialize(VOnE1); it.More(); it.Next()) {
198 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
199 if (V.IsSame( CV )) {
201 OnE1 = Standard_True;
204 P2 = BRep_Tool::Pnt( CV );
205 Tol1 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
206 if (P1.SquareDistance(P2) <= Tol1*Tol1) {
209 OnE1 = Standard_True;
214 //-----------------------------------------------------------------
215 // Search if the vertex found is still on E2.
216 //-----------------------------------------------------------------
217 for (it.Initialize(VOnE2); it.More(); it.Next()) {
218 if (V.IsSame( it.Value() )) {
219 OnE2 = Standard_True;
226 for (it.Initialize(VOnE2); it.More(); it.Next()) {
227 //-----------------------------------------------------------------
228 // Search if the point of intersection is a vertex of E2.
229 //-----------------------------------------------------------------
230 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
231 P2 = BRep_Tool::Pnt( CV );
232 Tol2 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
233 if (P1.SquareDistance(P2) <= Tol2*Tol2) {
236 OnE2 = Standard_True;
243 if (!OnE1 && !OnE2 && !theF.IsNull())
245 // if 3 faces intersects each others, 3 new edges on them must pass
246 // through one vertex but real intersection points of each
247 // pair of edges are sometimes more far than a tolerance.
248 // Try to analitically find vertices that E1 and E2 must pass trough
250 TopoDS_Shape F1 = getOtherShape( theF, AsDes->Ascendant( E1 ));
251 TopoDS_Shape F2 = getOtherShape( theF, AsDes->Ascendant( E2 ));
252 if (!F1.IsNull() && !F2.IsNull() && !F1.IsSame( F2 ))
254 OnE1 = findVOnE ( theV, E1, E2, F1, F2, AsDes, V1 );
255 OnE2 = findVOnE ( theV, E2, E1, F1, F2, AsDes, V2 );
262 if (!V1.IsSame(V2)) {
263 // replace V1 with V2 on all edges V1 is on
267 const TopTools_ListOfShape& EdgeWithV1 = AsDes->Ascendant(V1);
269 for (it.Initialize(EdgeWithV1); it.More(); it.Next()) {
270 EWE1 = TopoDS::Edge(it.Value());
272 VI.Orientation(TopAbs_INTERNAL);
273 UV1 = BRep_Tool::Parameter(VI,EWE1);
275 VI.Orientation(TopAbs_INTERNAL);
276 B.UpdateVertex( VI, UV1, EWE1, GetTolerance( VI, UV1, EWE1, AsDes));
278 AsDes->Replace(V1,V2);
283 // add existing vertices instead of new ones
286 V.Orientation(TopAbs_INTERNAL);
287 B.UpdateVertex (V, U1, E1, GetTolerance( V, U1, E1, AsDes));
294 V.Orientation(TopAbs_INTERNAL);
295 B.UpdateVertex (V, U2, E2, GetTolerance( V, U2, E2, AsDes ));
304 //=======================================================================
305 //function : FindEndVertex
306 //purpose : Returns a vertex from <VertList> having parameter on
307 // <E> closest to <f> or <l>. <isFirst> is True if
308 // found vertex is closer to <f>. <DU> returns parameter
310 //=======================================================================
312 TopoDS_Vertex Partition_Inter2d::FindEndVertex(const TopTools_ListOfShape& LV,
313 const Standard_Real f,
314 const Standard_Real l,
315 const TopoDS_Edge& E,
316 Standard_Boolean& isFirst,
317 Standard_Real& minDU)
320 Standard_Real U, endU, min;
323 TopTools_ListIteratorOfListOfShape it;
325 for (; it.More(); it.Next()) {
326 const TopoDS_Vertex& v = TopoDS::Vertex(it.Value());
327 U = BRep_Tool::Parameter(v, E);
328 min = Min( Abs(U-f), Abs(U-l) );
335 if (Abs(endU-f) < Abs(endU-l))
336 isFirst = Standard_True;
338 isFirst = Standard_False;
343 //=======================================================================
344 //function : treatClosed
345 //purpose : add second vertex to closed edge. Vertex is one of <LV1>
346 //=======================================================================
348 static void treatClosed (const TopoDS_Edge& E1,
349 const Standard_Real f,
350 const Standard_Real l,
351 TopTools_ListOfShape& LV1,
352 TopTools_ListOfShape& /*LV2*/)
354 Standard_Boolean isFirst=0;
355 Standard_Real minDU = 1.e10;
357 endV = Partition_Inter2d::FindEndVertex(LV1, f,l, E1, isFirst,minDU);
359 if (minDU > Precision::PConfusion())
360 return; // not end point
368 // update end parameter
370 endV.Orientation(TopAbs_INTERNAL);
371 B.UpdateVertex(endV,newU,E1,BRep_Tool::Tolerance(endV));
374 //=======================================================================
375 //function : EdgesPartition
377 //=======================================================================
379 static void EdgesPartition(const TopoDS_Face& F,
380 const TopoDS_Edge& E1,
381 const TopoDS_Edge& E2,
382 const Handle(BRepAlgo_AsDes)& AsDes,
383 const TopTools_MapOfShape& NewEdges,
384 const Standard_Boolean WithOri)
387 Standard_Real f[3],l[3];
388 Standard_Real MilTol2;
389 Standard_Real Tol = Max (BRep_Tool::Tolerance(E1),
390 BRep_Tool::Tolerance(E2));
391 MilTol2 = Tol * Tol * 10;
393 BRep_Tool::Range(E1, f[1], l[1]);
394 BRep_Tool::Range(E2, f[2], l[2]);
396 BRepAdaptor_Curve CE1(E1,F);
397 BRepAdaptor_Curve CE2(E2,F);
399 TopoDS_Edge EI[3]; EI[1] = E1; EI[2] = E2;
400 TopTools_ListOfShape LV1; // new vertices at intersections on E1
401 TopTools_ListOfShape LV2; // ... on E2
404 // if E1 and E2 are results of intersection of F and two connex faces then
405 // no need to intersect edges, they can contact by vertices only
406 // (encounted an exception in TopOpeBRep_EdgesIntersector in such a case)
407 Standard_Boolean intersect = Standard_True;
408 TopTools_IndexedMapOfShape ME;
409 TopExp::MapShapes(F, TopAbs_EDGE, ME);
410 if (!ME.Contains(E1) && ! ME.Contains(E2)) { // if E1 and E2 are new on F
412 const TopTools_ListOfShape& LF1 = AsDes->Ascendant( E1 );
413 F1 = F.IsSame( LF1.First() ) ? LF1.Last() : LF1.First();
414 const TopTools_ListOfShape& LF2 = AsDes->Ascendant( E2 );
415 F2 = F.IsSame( LF2.First() ) ? LF2.Last() : LF2.First();
416 if (!F.IsSame(F2) && !F.IsSame(F1) ) {
417 TopExp_Explorer exp(F2, TopAbs_EDGE);
418 TopExp::MapShapes(F1, TopAbs_EDGE, ME);
419 for (; exp.More(); exp.Next()) {
420 if (ME.Contains( exp.Current())) {
421 intersect = Standard_False;
429 //------------------------------------------------------
430 // compute the points of Intersection in 2D
431 //-----------------------------------------------------
432 // i.e. fill LV1 and LV2
433 TopOpeBRep_EdgesIntersector EInter;
434 EInter.SetFaces(F,F);
435 Standard_Real TolDub = 1.e-7;
436 EInter.ForceTolerances(TolDub,TolDub);
437 Standard_Boolean reducesegments = Standard_False;
438 EInter.Perform (E1,E2,reducesegments);
440 Standard_Boolean rejectreducedsegmentpoints = Standard_False;
441 EInter.InitPoint(rejectreducedsegmentpoints);
442 for ( ; EInter.MorePoint(); EInter.NextPoint() )
444 const TopOpeBRep_Point2d& P2D = EInter.Point();
445 const gp_Pnt& P = P2D.Value();
446 TopoDS_Vertex V = BRepLib_MakeVertex(P);
448 //-------------------------
449 // control the point found.
450 //-------------------------
451 gp_Pnt P1 = CE1.Value(P2D.Parameter(1));
452 gp_Pnt P2 = CE2.Value(P2D.Parameter(2));
453 Standard_Real sqd1 = P1.SquareDistance(P);
454 Standard_Real sqd2 = P2.SquareDistance(P);
455 if (sqd1 > MilTol2 || sqd2 > MilTol2 )
458 // add a new vertex to the both edges
459 Standard_Real toler = Max( Tol, sqrt( Max( sqd1, sqd2 )));
461 for (i = 1; i <= 2; i++) {
462 Standard_Real U = P2D.Parameter(i);
463 V.Orientation(TopAbs_INTERNAL);
464 B.UpdateVertex( V,U,EI[i], toler);
465 TopAbs_Orientation OO = TopAbs_REVERSED;
468 OO = P2D.Vertex(i).Orientation();
469 else if (P2D.Transition(i).Before() == TopAbs_OUT) {
473 if (i == 1) LV1.Append(V);
480 //----------------------------------
481 // Test the extremities of the edges.
482 //----------------------------------
483 // add to LV* vertices for vertex-vertex closeness
485 Standard_Real TolConf2, TolConf;
486 TopoDS_Vertex V1[2],V2[2];
487 TopExp::Vertices(E1,V1[0],V1[1]);
488 TopExp::Vertices(E2,V2[0],V2[1]);
490 Standard_Integer i,j,k;
491 for (j = 0; j < 2; j++) {
492 if (V1[j].IsNull()) continue;
493 for ( k = 0; k < 2; k++) {
494 if (V2[k].IsNull()) continue;
495 gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
496 gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
497 TolConf = BRep_Tool::Tolerance(V1[j]) + BRep_Tool::Tolerance(V2[k]);
498 TolConf = Max (Tol, TolConf);
499 TolConf2 = TolConf * TolConf;
502 Standard_Real SqDist = P1.SquareDistance(P2);
504 if (SqDist <= TolConf2) {
505 TopoDS_Vertex V = BRepLib_MakeVertex(P1);
506 V.Orientation(TopAbs_INTERNAL);
507 U1 = (j == 0) ? f[1] : l[1];
508 U2 = (k == 0) ? f[2] : l[2];
509 B.UpdateVertex(V,U1,E1,TolConf);
510 B.UpdateVertex(V,U2,E2,TolConf);
511 LV1.Prepend(V.Oriented(V1[j].Orientation()));
512 LV2.Prepend(V.Oriented(V2[k].Orientation()));
517 Standard_Boolean AffichPurge = Standard_False;
519 if ( LV1.IsEmpty()) return;
521 //----------------------------------
522 // Purge of all the vertices.
523 //----------------------------------
524 // remove one of close vertices
525 TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
527 Standard_Boolean Purge = Standard_True;
531 Purge = Standard_False;
532 for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2);
534 it1LV1.Next(),it1LV2.Next()) {
536 it2LV1.Initialize(LV1);
538 const TopoDS_Vertex& VE1 = TopoDS::Vertex(it1LV1.Value());
539 const TopoDS_Vertex& VE2 = TopoDS::Vertex(it2LV1.Value());
540 Standard_Real Tol1 = BRep_Tool::Tolerance( VE1 );
541 Standard_Real Tol2 = BRep_Tool::Tolerance( VE2 );
542 P1 = BRep_Tool::Pnt( VE1 );
543 P2 = BRep_Tool::Pnt( VE2 );
544 if (P1.IsEqual(P2, Tol1 + Tol2)) {
547 Purge = Standard_True;
558 // care of new closed edges, they always intersect with seam at end
559 if (V1[0].IsSame( V1[1] ) && NewEdges.Contains(E1) )
560 treatClosed (E1, f[1], l[1], LV1, LV2);
561 if (V2[0].IsSame( V2[1] ) && NewEdges.Contains(E2) )
562 treatClosed (E2, f[2], l[2], LV2, LV1);
568 for ( it1LV1.Initialize( LV1 ); it1LV1.More(); it1LV1.Next())
569 Partition_Inter2d::AddVonE (TopoDS::Vertex( it1LV1.Value()),
573 //=======================================================================
574 //function : CompletPart2d
575 //purpose : Computes the intersections between the edges stored
576 // is AsDes as descendants of <F> . Intersections is computed
577 // between two edges if one of them is bound in NewEdges.
578 //=======================================================================
580 void Partition_Inter2d::CompletPart2d (const Handle(BRepAlgo_AsDes)& AsDes,
581 const TopoDS_Face& F,
582 const TopTools_MapOfShape& NewEdges)
590 //Do not intersect the edges of a face
591 TopTools_IndexedMapOfShape EdgesOfFace;
592 TopExp::MapShapes( F, TopAbs_EDGE , EdgesOfFace);
594 //-------------------------------------------------------------------
595 // compute the intersection2D on the faces touched by the intersection3D
596 //-------------------------------------------------------------------
597 TopTools_ListIteratorOfListOfShape it1LE ;
598 TopTools_ListIteratorOfListOfShape it2LE ;
600 //-----------------------------------------------
601 // Intersection edge-edge.
602 //-----------------------------------------------
603 const TopTools_ListOfShape& LE = AsDes->Descendant(F);
605 Standard_Integer j, i = 1;
608 FF.Orientation(TopAbs_FORWARD);
610 for ( it1LE.Initialize(LE) ; it1LE.More(); it1LE.Next()) {
611 const TopoDS_Edge& E1 = TopoDS::Edge(it1LE.Value());
613 it2LE.Initialize(LE);
615 while (j < i && it2LE.More()) {
616 const TopoDS_Edge& E2 = TopoDS::Edge(it2LE.Value());
617 //----------------------------------------------------------
618 // Intersections of the new edges obtained by intersection
619 // between them and with the restrictions edges
620 //----------------------------------------------------------
621 if ( (!EdgesOfFace.Contains(E1) || !EdgesOfFace.Contains(E2)) &&
622 (NewEdges.Contains(E1) || NewEdges.Contains(E2)) ) {
623 EdgesPartition(FF,E1,E2,AsDes,NewEdges,Standard_True);
632 //=======================================================================
633 //function : GetTolerance
634 //purpose : Returns tolerance theV must have atfer its
635 // addition to theE with theU parameter. theAsDes is
636 // used to find pcurves of theE
637 //=======================================================================
639 Standard_Real Partition_Inter2d::GetTolerance
640 (const TopoDS_Vertex & theV,
641 const Standard_Real theU,
642 const TopoDS_Edge & theE,
643 const Handle(BRepAlgo_AsDes)& theAsDes)
645 Standard_Real aTol = BRep_Tool::Tolerance( theV );
646 gp_Pnt aPnt = BRep_Tool::Pnt( theV );
648 // check point on 3D curve
650 Handle(Geom_Curve) C = BRep_Tool::Curve( theE, f, l );
652 aTol = Max ( aTol, aPnt.Distance( C->Value( theU )));
654 // check points on pcurves
655 const TopTools_ListOfShape& aFList = theAsDes->Ascendant( theE );
656 TopTools_ListIteratorOfListOfShape aFIt( aFList );
657 for ( ; aFIt.More(); aFIt.Next() )
659 const TopoDS_Face& F = TopoDS::Face( aFIt.Value() );
660 Handle(Geom2d_Curve) pcurve = BRep_Tool::CurveOnSurface( theE, F, f, l );
661 if (!pcurve.IsNull())
663 gp_Pnt2d aPnt2d = pcurve->Value( theU );
665 Handle(Geom_Surface) S = BRep_Tool::Surface( F, L );
666 gp_Pnt aPntOnS = S->Value( aPnt2d.X(), aPnt2d.Y() );
668 aPntOnS.Transform( L.Transformation() );
669 aTol = Max ( aTol, aPnt.Distance( aPntOnS ));