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.opencascade.org/SALOME/ or email : webmaster.salome@opencascade.org
24 // File : Partition_Inter2d.cxx
25 // Author : Benedicte MARTIN
30 #include "Partition_Inter2d.ixx"
32 #include "utilities.h"
35 #include <TopExp_Explorer.hxx>
37 #include <BRepAlgo_AsDes.hxx>
39 #include <BRep_Builder.hxx>
40 #include <BRep_Tool.hxx>
41 #include <BRepLib_MakeVertex.hxx>
42 #include <BRepAdaptor_Curve.hxx>
46 #include <TopoDS_Edge.hxx>
47 #include <TopoDS_Vertex.hxx>
48 #include <TopOpeBRep_EdgesIntersector.hxx>
49 #include <TopOpeBRep_Point2d.hxx>
50 #include <TopOpeBRepDS_Transition.hxx>
51 #include <TopTools_ListOfShape.hxx>
52 #include <TopTools_ListIteratorOfListOfShape.hxx>
53 #include <TopTools_MapOfShape.hxx>
54 #include <TopTools_MapIteratorOfMapOfShape.hxx>
57 #include <Precision.hxx>
60 static Standard_Boolean TestEdges = 0;
61 static Standard_Integer NbF2d = 0;
62 static Standard_Integer NbE2d = 0;
65 //=======================================================================
66 //function : StorePart2d
68 //=======================================================================
70 // static void StorePart2d (const TopoDS_Edge& E1,
71 // const TopoDS_Edge& E2,
72 // TopTools_ListOfShape& LV1,
73 // TopTools_ListOfShape& LV2,
74 // Handle(BRepAlgo_AsDes) AsDes,
76 TopoDS_Vertex Partition_Inter2d::AddVonE(const TopoDS_Vertex& theV,
77 const TopoDS_Edge& E1,
78 const TopoDS_Edge& E2,
79 const Handle(BRepAlgo_AsDes)& AsDes)
82 //-------------------------------------------------------------
83 // test if the points of intersection already exist. If not,
84 // add as descendants of the edges.
85 // nb: theses points are only vertices of intersection.
86 //-------------------------------------------------------------
87 const TopTools_ListOfShape& VOnE1 = AsDes->Descendant(E1);
88 const TopTools_ListOfShape& VOnE2 = AsDes->Descendant(E2);
89 TopTools_ListOfShape NewVOnE1;
90 TopTools_ListOfShape NewVOnE2;
93 TopTools_ListIteratorOfListOfShape it, itLV1, itLV2;
95 TopAbs_Orientation O1,O2;
97 Standard_Real Tol,Tol1,Tol2;
98 Standard_Boolean OnE1,OnE2;
100 // for (itLV1.Initialize(LV1),itLV2.Initialize(LV2);
102 // itLV1.Next() ,itLV2.Next()) {
104 TopoDS_Vertex V = theV;
105 // TopoDS_Vertex V = TopoDS::Vertex(itLV1.Value());
107 U1 = BRep_Tool::Parameter(V,E1);
108 U2 = BRep_Tool::Parameter(V,E2);
109 O1 = V.Orientation();
110 O2 = O1;///itLV2.Value().Orientation();
111 P1 = BRep_Tool::Pnt(V);
112 Tol = BRep_Tool::Tolerance( V );
113 OnE1 = OnE2 = Standard_False;
115 //-----------------------------------------------------------------
116 // Search if the point of intersection is a vertex of E1.
117 //-----------------------------------------------------------------
118 for (it.Initialize(VOnE1); it.More(); it.Next()) {
119 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
120 if (V.IsSame( CV )) {
122 OnE1 = Standard_True;
125 P2 = BRep_Tool::Pnt( CV );
126 Tol1 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
127 if (P1.SquareDistance(P2) <= Tol1*Tol1) {
130 OnE1 = Standard_True;
135 //-----------------------------------------------------------------
136 // Search if the vertex found is still on E2.
137 //-----------------------------------------------------------------
138 for (it.Initialize(VOnE2); it.More(); it.Next()) {
139 if (V.IsSame( it.Value() )) {
140 OnE2 = Standard_True;
147 for (it.Initialize(VOnE2); it.More(); it.Next()) {
148 //-----------------------------------------------------------------
149 // Search if the point of intersection is a vertex of E2.
150 //-----------------------------------------------------------------
151 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
152 P2 = BRep_Tool::Pnt( CV );
153 Tol2 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
154 if (P1.SquareDistance(P2) <= Tol2*Tol2) {
157 OnE2 = Standard_True;
163 if (!V1.IsSame(V2)) {
167 const TopTools_ListOfShape& EdgeWithV2 = AsDes->Ascendant(V2);
169 for (it.Initialize(EdgeWithV2); it.More(); it.Next()) {
170 EWE2 = TopoDS::Edge(it.Value());
172 VI.Orientation(TopAbs_INTERNAL);
173 UV2 = BRep_Tool::Parameter(VI,EWE2);
175 VI.Orientation(TopAbs_INTERNAL);
176 B.UpdateVertex(VI,UV2,EWE2, Max(Tol1,Tol2));
178 AsDes->Replace(V2,V1);
181 // add existing vertices instead of new ones
184 V.Orientation(TopAbs_INTERNAL);
185 B.UpdateVertex(V,U1,E1, Tol2);
192 V.Orientation(TopAbs_INTERNAL);
193 B.UpdateVertex(V,U2,E2, Tol1);
200 if (!NewVOnE1.IsEmpty()) AsDes->Add(E1,NewVOnE1);
201 if (!NewVOnE2.IsEmpty()) AsDes->Add(E2,NewVOnE2);
206 //=======================================================================
207 //function : FindEndVertex
208 //purpose : Returns a vertex from <VertList> having parameter on
209 // <E> closest to <f> or <l>. <isFirst> is True if
210 // found vertex is closer to <f>. <DU> returns parameter
212 //=======================================================================
214 TopoDS_Vertex Partition_Inter2d::FindEndVertex(const TopTools_ListOfShape& LV,
215 const Standard_Real f,
216 const Standard_Real l,
217 const TopoDS_Edge& E,
218 Standard_Boolean& isFirst,
219 Standard_Real& minDU)
222 Standard_Real U, endU, min;
225 TopTools_ListIteratorOfListOfShape it;
227 for (; it.More(); it.Next()) {
228 const TopoDS_Vertex& v = TopoDS::Vertex(it.Value());
229 U = BRep_Tool::Parameter(v, E);
230 min = Min( Abs(U-f), Abs(U-l) );
237 if (Abs(endU-f) < Abs(endU-l))
238 isFirst = Standard_True;
240 isFirst = Standard_False;
245 //=======================================================================
246 //function : treatClosed
247 //purpose : add second vertex to closed edge. Vertex is one of <LV1>
248 //=======================================================================
250 static void treatClosed (const TopoDS_Edge& E1,
251 const Standard_Real f,
252 const Standard_Real l,
253 TopTools_ListOfShape& LV1,
254 TopTools_ListOfShape& /*LV2*/)
256 Standard_Boolean isFirst=0;
257 Standard_Real minDU = 1.e10;
259 endV = Partition_Inter2d::FindEndVertex(LV1, f,l, E1, isFirst,minDU);
261 if (minDU > Precision::PConfusion())
262 return; // not end point
270 // update end parameter
272 endV.Orientation(TopAbs_INTERNAL);
273 B.UpdateVertex(endV,newU,E1,BRep_Tool::Tolerance(endV));
276 //=======================================================================
277 //function : EdgesPartition
279 //=======================================================================
281 static void EdgesPartition(const TopoDS_Face& F,
282 const TopoDS_Edge& E1,
283 const TopoDS_Edge& E2,
284 const Handle(BRepAlgo_AsDes)& AsDes,
285 const TopTools_MapOfShape& NewEdges,
286 const Standard_Boolean WithOri)
289 Standard_Real f[3],l[3];
290 Standard_Real MilTol2;
291 Standard_Real Tol = Max (BRep_Tool::Tolerance(E1),
292 BRep_Tool::Tolerance(E2));
293 MilTol2 = Tol * Tol * 10;
295 BRep_Tool::Range(E1, f[1], l[1]);
296 BRep_Tool::Range(E2, f[2], l[2]);
298 BRepAdaptor_Curve CE1(E1,F);
299 BRepAdaptor_Curve CE2(E2,F);
301 TopoDS_Edge EI[3]; EI[1] = E1; EI[2] = E2;
302 TopTools_ListOfShape LV1; // new vertices at intersections on E1
303 TopTools_ListOfShape LV2; // ... on E2
306 // if E1 and E2 are results of intersection of F and two connex faces then
307 // no need to intersect edges, they can contact by vertices only
308 // (encounted an exception in TopOpeBRep_EdgesIntersector in such a case)
309 Standard_Boolean intersect = Standard_True;
310 TopTools_IndexedMapOfShape ME;
311 TopExp::MapShapes(F, TopAbs_EDGE, ME);
312 if (!ME.Contains(E1) && ! ME.Contains(E2)) { // if E1 and E2 are new on F
314 const TopTools_ListOfShape& LF1 = AsDes->Ascendant( E1 );
315 F1 = F.IsSame( LF1.First() ) ? LF1.Last() : LF1.First();
316 const TopTools_ListOfShape& LF2 = AsDes->Ascendant( E2 );
317 F2 = F.IsSame( LF2.First() ) ? LF2.Last() : LF2.First();
318 if (!F.IsSame(F2) && !F.IsSame(F1) ) {
319 TopExp_Explorer exp(F2, TopAbs_EDGE);
320 TopExp::MapShapes(F1, TopAbs_EDGE, ME);
321 for (; exp.More(); exp.Next()) {
322 if (ME.Contains( exp.Current())) {
323 intersect = Standard_False;
331 //------------------------------------------------------
332 // compute the points of Intersection in 2D
333 //-----------------------------------------------------
334 // i.e. fill LV1 and LV2
335 TopOpeBRep_EdgesIntersector EInter;
336 EInter.SetFaces(F,F);
337 Standard_Real TolDub = 1.e-7;
338 EInter.ForceTolerances(TolDub,TolDub);
339 Standard_Boolean reducesegments = Standard_False;
340 EInter.Perform (E1,E2,reducesegments);
342 Standard_Boolean rejectreducedsegmentpoints = Standard_False;
343 EInter.InitPoint(rejectreducedsegmentpoints);
344 for (;EInter.MorePoint();EInter.NextPoint()) {
345 const TopOpeBRep_Point2d& P2D = EInter.Point();
346 const gp_Pnt& P = P2D.Value();
347 TopoDS_Vertex V = BRepLib_MakeVertex(P);
349 //-------------------------
350 // control the point found.
351 //-------------------------
352 gp_Pnt P1 = CE1.Value(P2D.Parameter(1));
353 gp_Pnt P2 = CE2.Value(P2D.Parameter(2));
354 Standard_Real sqd1 = P1.SquareDistance(P);
355 Standard_Real sqd2 = P2.SquareDistance(P);
356 if (sqd1 > MilTol2 || sqd2 > MilTol2 ) {
357 //MESSAGE ( "Inter2d : Solution rejected, dist: " << sqrt(Max(sqd1,sqd2)) )
360 MESSAGE ( " edges : E2d_"<<NbE2d-2<<" E2d_"<<NbE2d-1 ); }
365 // add a new vertex to the both edges
366 Standard_Real toler = 1.5 * Max (Tol, sqrt(Max(sqd1,sqd2)) );
368 for (i = 1; i <= 2; i++) {
369 Standard_Real U = P2D.Parameter(i);
371 if (U < f[i]-Tol || U > l[i]+Tol) {
375 V.Orientation(TopAbs_INTERNAL);
376 B.UpdateVertex( V,U,EI[i], toler);
377 TopAbs_Orientation OO = TopAbs_REVERSED;
380 OO = P2D.Vertex(i).Orientation();
381 else if (P2D.Transition(i).Before() == TopAbs_OUT) {
385 if (i == 1) LV1.Append(V);
392 //----------------------------------
393 // Test the extremities of the edges.
394 //----------------------------------
395 // add to LV* vertices for vertex-vertex closeness
397 Standard_Real TolConf2, TolConf;
398 TopoDS_Vertex V1[2],V2[2];
399 TopExp::Vertices(E1,V1[0],V1[1]);
400 TopExp::Vertices(E2,V2[0],V2[1]);
402 Standard_Integer i,j,k;
403 for (j = 0; j < 2; j++) {
404 if (V1[j].IsNull()) continue;
405 for ( k = 0; k < 2; k++) {
406 if (V2[k].IsNull()) continue;
407 gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
408 gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
409 TolConf = BRep_Tool::Tolerance(V1[j]) + BRep_Tool::Tolerance(V2[k]);
410 TolConf = Max (Tol, TolConf);
411 TolConf2 = TolConf * TolConf;
414 Standard_Real SqDist = P1.SquareDistance(P2);
416 if (SqDist <= TolConf2) {
417 TopoDS_Vertex V = BRepLib_MakeVertex(P1);
418 V.Orientation(TopAbs_INTERNAL);
419 U1 = (j == 0) ? f[1] : l[1];
420 U2 = (k == 0) ? f[2] : l[2];
421 B.UpdateVertex(V,U1,E1,TolConf);
422 B.UpdateVertex(V,U2,E2,TolConf);
423 LV1.Prepend(V.Oriented(V1[j].Orientation()));
424 LV2.Prepend(V.Oriented(V2[k].Orientation()));
429 Standard_Boolean AffichPurge = Standard_False;
431 if ( LV1.IsEmpty()) return;
433 //----------------------------------
434 // Purge of all the vertices.
435 //----------------------------------
436 // remove one of close vertices
437 TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
439 Standard_Boolean Purge = Standard_True;
443 Purge = Standard_False;
444 for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2);
445 it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
447 it2LV1.Initialize(LV1);
449 const TopoDS_Vertex& VE1 = TopoDS::Vertex(it1LV1.Value());
450 const TopoDS_Vertex& VE2 = TopoDS::Vertex(it2LV1.Value());
451 Standard_Real Tol1 = BRep_Tool::Tolerance( VE1 );
452 Standard_Real Tol2 = BRep_Tool::Tolerance( VE2 );
453 P1 = BRep_Tool::Pnt( VE1 );
454 P2 = BRep_Tool::Pnt( VE2 );
455 if (P1.IsEqual(P2, Tol1 + Tol2)) {
459 MESSAGE ("Vertices confused purged in EdgeInter.")
461 Purge = Standard_True;
472 // care of new closed edges, they always intersect with seam at end
473 if (V1[0].IsSame( V1[1] ) && NewEdges.Contains(E1) )
474 treatClosed (E1,f[1],l[1],LV1,LV2);
475 if (V2[0].IsSame( V2[1] ) && NewEdges.Contains(E2) )
476 treatClosed (E2,f[2],l[2],LV2,LV1);
478 //---------------------------------
480 //---------------------------------
482 //StorePart2d (E1,E2,LV1,LV2,AsDes,Tol);
483 for ( it1LV1.Initialize( LV1 ); it1LV1.More(); it1LV1.Next())
484 Partition_Inter2d::AddVonE ( TopoDS::Vertex( it1LV1.Value()), E1,E2,AsDes);
487 //=======================================================================
488 //function : CompletPart2d
489 //purpose : Computes the intersections between the edges stored
490 // is AsDes as descendants of <F> . Intersections is computed
491 // between two edges if one of them is bound in NewEdges.
492 //=======================================================================
494 void Partition_Inter2d::CompletPart2d (const Handle(BRepAlgo_AsDes)& AsDes,
495 const TopoDS_Face& F,
496 const TopTools_MapOfShape& NewEdges)
504 //Do not intersect the edges of a face
505 TopTools_IndexedMapOfShape EdgesOfFace;
506 TopExp::MapShapes( F, TopAbs_EDGE , EdgesOfFace);
508 //-------------------------------------------------------------------
509 // compute the intersection2D on the faces touched by the intersection3D
510 //-------------------------------------------------------------------
511 TopTools_ListIteratorOfListOfShape it1LE ;
512 TopTools_ListIteratorOfListOfShape it2LE ;
514 //-----------------------------------------------
515 // Intersection edge-edge.
516 //-----------------------------------------------
517 const TopTools_ListOfShape& LE = AsDes->Descendant(F);
519 Standard_Integer j, i = 1;
522 FF.Orientation(TopAbs_FORWARD);
524 for ( it1LE.Initialize(LE) ; it1LE.More(); it1LE.Next()) {
525 const TopoDS_Edge& E1 = TopoDS::Edge(it1LE.Value());
527 it2LE.Initialize(LE);
529 while (j < i && it2LE.More()) {
530 const TopoDS_Edge& E2 = TopoDS::Edge(it2LE.Value());
531 //----------------------------------------------------------
532 // Intersections of the new edges obtained by intersection
533 // between them and with the restrictions edges
534 //----------------------------------------------------------
535 if ( (!EdgesOfFace.Contains(E1) || !EdgesOfFace.Contains(E2)) &&
536 (NewEdges.Contains(E1) || NewEdges.Contains(E2)) ) {
537 EdgesPartition(FF,E1,E2,AsDes,NewEdges,Standard_True);