2 // File : Partition_Inter2d.cxx
3 // Created : Thu Aug 02 16:17:31 2001
4 // Author : Benedicte MARTIN
7 // Copyright : Open CASCADE
10 #include "Partition_Inter2d.ixx"
12 #include "utilities.h"
15 #include <TopExp_Explorer.hxx>
17 #include <BRepAlgo_AsDes.hxx>
19 #include <BRep_Builder.hxx>
20 #include <BRep_Tool.hxx>
21 #include <BRepLib_MakeVertex.hxx>
22 #include <BRepAdaptor_Curve.hxx>
26 #include <TopoDS_Edge.hxx>
27 #include <TopoDS_Vertex.hxx>
28 #include <TopOpeBRep_EdgesIntersector.hxx>
29 #include <TopOpeBRep_Point2d.hxx>
30 #include <TopOpeBRepDS_Transition.hxx>
31 #include <TopTools_ListOfShape.hxx>
32 #include <TopTools_ListIteratorOfListOfShape.hxx>
33 #include <TopTools_MapOfShape.hxx>
34 #include <TopTools_MapIteratorOfMapOfShape.hxx>
37 #include <Precision.hxx>
40 static Standard_Boolean TestEdges = 0;
41 static Standard_Integer NbF2d = 0;
42 static Standard_Integer NbE2d = 0;
45 //=======================================================================
46 //function : StorePart2d
48 //=======================================================================
50 // static void StorePart2d (const TopoDS_Edge& E1,
51 // const TopoDS_Edge& E2,
52 // TopTools_ListOfShape& LV1,
53 // TopTools_ListOfShape& LV2,
54 // Handle(BRepAlgo_AsDes) AsDes,
56 TopoDS_Vertex Partition_Inter2d::AddVonE(const TopoDS_Vertex& theV,
57 const TopoDS_Edge& E1,
58 const TopoDS_Edge& E2,
59 const Handle(BRepAlgo_AsDes)& AsDes)
62 //-------------------------------------------------------------
63 // test if the points of intersection already exist. If not,
64 // add as descendants of the edges.
65 // nb: theses points are only vertices of intersection.
66 //-------------------------------------------------------------
67 const TopTools_ListOfShape& VOnE1 = AsDes->Descendant(E1);
68 const TopTools_ListOfShape& VOnE2 = AsDes->Descendant(E2);
69 TopTools_ListOfShape NewVOnE1;
70 TopTools_ListOfShape NewVOnE2;
73 TopTools_ListIteratorOfListOfShape it, itLV1, itLV2;
75 TopAbs_Orientation O1,O2;
77 Standard_Real Tol,Tol1,Tol2;
78 Standard_Boolean OnE1,OnE2;
80 // for (itLV1.Initialize(LV1),itLV2.Initialize(LV2);
82 // itLV1.Next() ,itLV2.Next()) {
84 TopoDS_Vertex V = theV;
85 // TopoDS_Vertex V = TopoDS::Vertex(itLV1.Value());
87 U1 = BRep_Tool::Parameter(V,E1);
88 U2 = BRep_Tool::Parameter(V,E2);
90 O2 = O1;///itLV2.Value().Orientation();
91 P1 = BRep_Tool::Pnt(V);
92 Tol = BRep_Tool::Tolerance( V );
93 OnE1 = OnE2 = Standard_False;
95 //-----------------------------------------------------------------
96 // Search if the point of intersection is a vertex of E1.
97 //-----------------------------------------------------------------
98 for (it.Initialize(VOnE1); it.More(); it.Next()) {
99 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
100 if (V.IsSame( CV )) {
102 OnE1 = Standard_True;
105 P2 = BRep_Tool::Pnt( CV );
106 Tol1 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
107 if (P1.SquareDistance(P2) <= Tol1*Tol1) {
110 OnE1 = Standard_True;
115 //-----------------------------------------------------------------
116 // Search if the vertex found is still on E2.
117 //-----------------------------------------------------------------
118 for (it.Initialize(VOnE2); it.More(); it.Next()) {
119 if (V.IsSame( it.Value() )) {
120 OnE2 = Standard_True;
127 for (it.Initialize(VOnE2); it.More(); it.Next()) {
128 //-----------------------------------------------------------------
129 // Search if the point of intersection is a vertex of E2.
130 //-----------------------------------------------------------------
131 const TopoDS_Vertex& CV = TopoDS::Vertex( it.Value() );
132 P2 = BRep_Tool::Pnt( CV );
133 Tol2 = 1.1*(Tol + BRep_Tool::Tolerance( CV ));
134 if (P1.SquareDistance(P2) <= Tol2*Tol2) {
137 OnE2 = Standard_True;
143 if (!V1.IsSame(V2)) {
147 const TopTools_ListOfShape& EdgeWithV2 = AsDes->Ascendant(V2);
149 for (it.Initialize(EdgeWithV2); it.More(); it.Next()) {
150 EWE2 = TopoDS::Edge(it.Value());
152 VI.Orientation(TopAbs_INTERNAL);
153 UV2 = BRep_Tool::Parameter(VI,EWE2);
155 VI.Orientation(TopAbs_INTERNAL);
156 B.UpdateVertex(VI,UV2,EWE2, Max(Tol1,Tol2));
158 AsDes->Replace(V2,V1);
161 // add existing vertices instead of new ones
164 V.Orientation(TopAbs_INTERNAL);
165 B.UpdateVertex(V,U1,E1, Tol2);
172 V.Orientation(TopAbs_INTERNAL);
173 B.UpdateVertex(V,U2,E2, Tol1);
180 if (!NewVOnE1.IsEmpty()) AsDes->Add(E1,NewVOnE1);
181 if (!NewVOnE2.IsEmpty()) AsDes->Add(E2,NewVOnE2);
186 //=======================================================================
187 //function : FindEndVertex
188 //purpose : Returns a vertex from <VertList> having parameter on
189 // <E> closest to <f> or <l>. <isFirst> is True if
190 // found vertex is closer to <f>. <DU> returns parameter
192 //=======================================================================
194 TopoDS_Vertex Partition_Inter2d::FindEndVertex(const TopTools_ListOfShape& LV,
195 const Standard_Real f,
196 const Standard_Real l,
197 const TopoDS_Edge& E,
198 Standard_Boolean& isFirst,
199 Standard_Real& minDU)
202 Standard_Real U, endU, min;
205 TopTools_ListIteratorOfListOfShape it;
207 for (; it.More(); it.Next()) {
208 const TopoDS_Vertex& v = TopoDS::Vertex(it.Value());
209 U = BRep_Tool::Parameter(v, E);
210 min = Min( Abs(U-f), Abs(U-l) );
217 if (Abs(endU-f) < Abs(endU-l))
218 isFirst = Standard_True;
220 isFirst = Standard_False;
225 //=======================================================================
226 //function : treatClosed
227 //purpose : add second vertex to closed edge. Vertex is one of <LV1>
228 //=======================================================================
230 static void treatClosed (const TopoDS_Edge& E1,
231 const Standard_Real f,
232 const Standard_Real l,
233 TopTools_ListOfShape& LV1,
234 TopTools_ListOfShape& /*LV2*/)
236 Standard_Boolean isFirst=0;
237 Standard_Real minDU = 1.e10;
239 endV = Partition_Inter2d::FindEndVertex(LV1, f,l, E1, isFirst,minDU);
241 if (minDU > Precision::PConfusion())
242 return; // not end point
250 // update end parameter
252 endV.Orientation(TopAbs_INTERNAL);
253 B.UpdateVertex(endV,newU,E1,BRep_Tool::Tolerance(endV));
256 //=======================================================================
257 //function : EdgesPartition
259 //=======================================================================
261 static void EdgesPartition(const TopoDS_Face& F,
262 const TopoDS_Edge& E1,
263 const TopoDS_Edge& E2,
264 const Handle(BRepAlgo_AsDes)& AsDes,
265 const TopTools_MapOfShape& NewEdges,
266 const Standard_Boolean WithOri)
269 Standard_Real f[3],l[3];
270 Standard_Real MilTol2;
271 Standard_Real Tol = Max (BRep_Tool::Tolerance(E1),
272 BRep_Tool::Tolerance(E2));
273 MilTol2 = Tol * Tol * 10;
275 BRep_Tool::Range(E1, f[1], l[1]);
276 BRep_Tool::Range(E2, f[2], l[2]);
278 BRepAdaptor_Curve CE1(E1,F);
279 BRepAdaptor_Curve CE2(E2,F);
281 TopoDS_Edge EI[3]; EI[1] = E1; EI[2] = E2;
282 TopTools_ListOfShape LV1; // new vertices at intersections on E1
283 TopTools_ListOfShape LV2; // ... on E2
286 // if E1 and E2 are results of intersection of F and two connex faces then
287 // no need to intersect edges, they can contact by vertices only
288 // (encounted an exception in TopOpeBRep_EdgesIntersector in such a case)
289 Standard_Boolean intersect = Standard_True;
290 TopTools_IndexedMapOfShape ME;
291 TopExp::MapShapes(F, TopAbs_EDGE, ME);
292 if (!ME.Contains(E1) && ! ME.Contains(E2)) { // if E1 and E2 are new on F
294 const TopTools_ListOfShape& LF1 = AsDes->Ascendant( E1 );
295 F1 = F.IsSame( LF1.First() ) ? LF1.Last() : LF1.First();
296 const TopTools_ListOfShape& LF2 = AsDes->Ascendant( E2 );
297 F2 = F.IsSame( LF2.First() ) ? LF2.Last() : LF2.First();
298 if (!F.IsSame(F2) && !F.IsSame(F1) ) {
299 TopExp_Explorer exp(F2, TopAbs_EDGE);
300 TopExp::MapShapes(F1, TopAbs_EDGE, ME);
301 for (; exp.More(); exp.Next()) {
302 if (ME.Contains( exp.Current())) {
303 intersect = Standard_False;
311 //------------------------------------------------------
312 // compute the points of Intersection in 2D
313 //-----------------------------------------------------
314 // i.e. fill LV1 and LV2
315 TopOpeBRep_EdgesIntersector EInter;
316 EInter.SetFaces(F,F);
317 Standard_Real TolDub = 1.e-7;
318 EInter.ForceTolerances(TolDub,TolDub);
319 Standard_Boolean reducesegments = Standard_False;
320 EInter.Perform (E1,E2,reducesegments);
322 Standard_Boolean rejectreducedsegmentpoints = Standard_False;
323 EInter.InitPoint(rejectreducedsegmentpoints);
324 for (;EInter.MorePoint();EInter.NextPoint()) {
325 const TopOpeBRep_Point2d& P2D = EInter.Point();
326 const gp_Pnt& P = P2D.Value();
327 TopoDS_Vertex V = BRepLib_MakeVertex(P);
329 //-------------------------
330 // control the point found.
331 //-------------------------
332 gp_Pnt P1 = CE1.Value(P2D.Parameter(1));
333 gp_Pnt P2 = CE2.Value(P2D.Parameter(2));
334 Standard_Real sqd1 = P1.SquareDistance(P);
335 Standard_Real sqd2 = P2.SquareDistance(P);
336 if (sqd1 > MilTol2 || sqd2 > MilTol2 ) {
337 //MESSAGE ( "Inter2d : Solution rejected, dist: " << sqrt(Max(sqd1,sqd2)) )
340 MESSAGE ( " edges : E2d_"<<NbE2d-2<<" E2d_"<<NbE2d-1 ); }
345 // add a new vertex to the both edges
346 Standard_Real toler = 1.5 * Max (Tol, sqrt(Max(sqd1,sqd2)) );
348 for (i = 1; i <= 2; i++) {
349 Standard_Real U = P2D.Parameter(i);
351 if (U < f[i]-Tol || U > l[i]+Tol) {
355 V.Orientation(TopAbs_INTERNAL);
356 B.UpdateVertex( V,U,EI[i], toler);
357 TopAbs_Orientation OO = TopAbs_REVERSED;
360 OO = P2D.Vertex(i).Orientation();
361 else if (P2D.Transition(i).Before() == TopAbs_OUT) {
365 if (i == 1) LV1.Append(V);
372 //----------------------------------
373 // Test the extremities of the edges.
374 //----------------------------------
375 // add to LV* vertices for vertex-vertex closeness
377 Standard_Real TolConf2, TolConf;
378 TopoDS_Vertex V1[2],V2[2];
379 TopExp::Vertices(E1,V1[0],V1[1]);
380 TopExp::Vertices(E2,V2[0],V2[1]);
382 Standard_Integer i,j,k;
383 for (j = 0; j < 2; j++) {
384 if (V1[j].IsNull()) continue;
385 for ( k = 0; k < 2; k++) {
386 if (V2[k].IsNull()) continue;
387 gp_Pnt P1 = BRep_Tool::Pnt(V1[j]);
388 gp_Pnt P2 = BRep_Tool::Pnt(V2[k]);
389 TolConf = BRep_Tool::Tolerance(V1[j]) + BRep_Tool::Tolerance(V2[k]);
390 TolConf = Max (Tol, TolConf);
391 TolConf2 = TolConf * TolConf;
394 Standard_Real SqDist = P1.SquareDistance(P2);
396 if (SqDist <= TolConf2) {
397 TopoDS_Vertex V = BRepLib_MakeVertex(P1);
398 V.Orientation(TopAbs_INTERNAL);
399 U1 = (j == 0) ? f[1] : l[1];
400 U2 = (k == 0) ? f[2] : l[2];
401 B.UpdateVertex(V,U1,E1,TolConf);
402 B.UpdateVertex(V,U2,E2,TolConf);
403 LV1.Prepend(V.Oriented(V1[j].Orientation()));
404 LV2.Prepend(V.Oriented(V2[k].Orientation()));
409 Standard_Boolean AffichPurge = Standard_False;
411 if ( LV1.IsEmpty()) return;
413 //----------------------------------
414 // Purge of all the vertices.
415 //----------------------------------
416 // remove one of close vertices
417 TopTools_ListIteratorOfListOfShape it1LV1,it1LV2,it2LV1;
419 Standard_Boolean Purge = Standard_True;
423 Purge = Standard_False;
424 for (it1LV1.Initialize(LV1),it1LV2.Initialize(LV2);
425 it1LV1.More(); it1LV1.Next(),it1LV2.Next()) {
427 it2LV1.Initialize(LV1);
429 const TopoDS_Vertex& VE1 = TopoDS::Vertex(it1LV1.Value());
430 const TopoDS_Vertex& VE2 = TopoDS::Vertex(it2LV1.Value());
431 Standard_Real Tol1 = BRep_Tool::Tolerance( VE1 );
432 Standard_Real Tol2 = BRep_Tool::Tolerance( VE2 );
433 P1 = BRep_Tool::Pnt( VE1 );
434 P2 = BRep_Tool::Pnt( VE2 );
435 if (P1.IsEqual(P2, Tol1 + Tol2)) {
439 MESSAGE ("Vertices confused purged in EdgeInter.")
441 Purge = Standard_True;
452 // care of new closed edges, they always intersect with seam at end
453 if (V1[0].IsSame( V1[1] ) && NewEdges.Contains(E1) )
454 treatClosed (E1,f[1],l[1],LV1,LV2);
455 if (V2[0].IsSame( V2[1] ) && NewEdges.Contains(E2) )
456 treatClosed (E2,f[2],l[2],LV2,LV1);
458 //---------------------------------
460 //---------------------------------
462 //StorePart2d (E1,E2,LV1,LV2,AsDes,Tol);
463 for ( it1LV1.Initialize( LV1 ); it1LV1.More(); it1LV1.Next())
464 Partition_Inter2d::AddVonE ( TopoDS::Vertex( it1LV1.Value()), E1,E2,AsDes);
467 //=======================================================================
468 //function : CompletPart2d
469 //purpose : Computes the intersections between the edges stored
470 // is AsDes as descendants of <F> . Intersections is computed
471 // between two edges if one of them is bound in NewEdges.
472 //=======================================================================
474 void Partition_Inter2d::CompletPart2d (const Handle(BRepAlgo_AsDes)& AsDes,
475 const TopoDS_Face& F,
476 const TopTools_MapOfShape& NewEdges)
484 //Do not intersect the edges of a face
485 TopTools_IndexedMapOfShape EdgesOfFace;
486 TopExp::MapShapes( F, TopAbs_EDGE , EdgesOfFace);
488 //-------------------------------------------------------------------
489 // compute the intersection2D on the faces touched by the intersection3D
490 //-------------------------------------------------------------------
491 TopTools_ListIteratorOfListOfShape it1LE ;
492 TopTools_ListIteratorOfListOfShape it2LE ;
494 //-----------------------------------------------
495 // Intersection edge-edge.
496 //-----------------------------------------------
497 const TopTools_ListOfShape& LE = AsDes->Descendant(F);
499 Standard_Integer j, i = 1;
502 FF.Orientation(TopAbs_FORWARD);
504 for ( it1LE.Initialize(LE) ; it1LE.More(); it1LE.Next()) {
505 const TopoDS_Edge& E1 = TopoDS::Edge(it1LE.Value());
507 it2LE.Initialize(LE);
509 while (j < i && it2LE.More()) {
510 const TopoDS_Edge& E2 = TopoDS::Edge(it2LE.Value());
511 //----------------------------------------------------------
512 // Intersections of the new edges obtained by intersection
513 // between them and with the restrictions edges
514 //----------------------------------------------------------
515 if ( (!EdgesOfFace.Contains(E1) || !EdgesOfFace.Contains(E2)) &&
516 (NewEdges.Contains(E1) || NewEdges.Contains(E2)) ) {
517 EdgesPartition(FF,E1,E2,AsDes,NewEdges,Standard_True);