Integration of OCCT 6.5.0 from SVN
[occt.git] / src / IntPoly / IntPoly_PlaneSection.cxx
1 // File:        IntPoly_PlaneSection.cxx
2 // Created:     Mon Jul 17 10:46:23 1995
3 // Author:      Stagiaire Alain JOURDAIN
4 //              <ajo@phobox>
5
6
7 #include <IntPoly_PlaneSection.ixx>
8
9 #include <IntPoly_SequenceOfSequenceOfPnt2d.hxx>
10 #include <IntPoly_IndexedMapOfPnt2d.hxx>
11 #include <IntPoly_Pnt2dHasher.hxx>
12 #include <Precision.hxx>
13 #include <TopExp_Explorer.hxx>
14 #include <TopoDS_Shape.hxx>
15 #include <TopoDS_Edge.hxx>
16 #include <BRep_Tool.hxx>
17 #include <BRep_Builder.hxx>
18 #include <TopoDS.hxx>
19 #include <Poly_Triangulation.hxx>
20 #include <Poly_Polygon3D.hxx>
21 #include <OSD_Chronometer.hxx>
22
23
24 //=======================================================================
25 //function : IntPoly_PlaneSection
26 //purpose  : 
27 //=======================================================================
28
29 IntPoly_PlaneSection::IntPoly_PlaneSection()
30 {}
31
32
33 //=======================================================================
34 //function : IntPoly_PlaneSection
35 //purpose  : 
36 //=======================================================================
37
38 IntPoly_PlaneSection::IntPoly_PlaneSection(const TopoDS_Shape& S,
39                                            const gp_Pln& P)
40 {
41   myShape = S;
42   myTransform.SetTransformation(P.Position()); 
43   gp_Ax3 Ax0(gp_Pnt(0,0,0),gp_Dir(0,0,1));
44   myBackTransform.SetTransformation(P.Position(),Ax0);
45   Section();
46 }
47
48
49 //=======================================================================
50 //function : Section
51 //purpose  : 
52 //=======================================================================
53
54 void IntPoly_PlaneSection::Section()
55
56   TopExp_Explorer ex;
57   Standard_Integer NbTrian,i,i1,i2,i3,Result;
58   Standard_Real Big = Precision::Infinite();
59   Standard_Boolean Inter;
60   //gp_Pnt Nod1,Nod2,Nod3;
61   gp_Pnt2d BegPoint,EndPoint,OutPoint;
62   TopLoc_Location Loc;
63   Handle(Poly_Triangulation) Tr;
64   myCpt = 0;
65   
66   for (ex.Init(myShape,TopAbs_FACE);ex.More();ex.Next()) {
67     Tr = (BRep_Tool::Triangulation(TopoDS::Face(ex.Current()),Loc));
68     if (!Tr.IsNull()) {
69       NbTrian = Tr->NbTriangles();
70       const Poly_Array1OfTriangle& TabTrian = Tr->Triangles();
71       const TColgp_Array1OfPnt&    TabNodes = Tr->Nodes();
72       TColgp_Array1OfPnt  TabTransfNodes(1,Tr->NbNodes());      
73       for (i = 1;i <= Tr->NbNodes();i++) {
74         if (!Loc.IsIdentity())
75           TabTransfNodes(i) = 
76             (TabNodes(i).Transformed(Loc.Transformation()))
77               .Transformed(myTransform);
78         else 
79           TabTransfNodes(i) = TabNodes(i).Transformed(myTransform);
80       }
81       for (i = 1;i <= NbTrian;i++) {
82         TabTrian(i).Get(i1,i2,i3);
83         Inter = Intersect(TabTransfNodes(i1),
84                           TabTransfNodes(i2),
85                           TabTransfNodes(i3),
86                           BegPoint,EndPoint);
87         if (Inter) {
88           if (myMapBegPoints.Contains(BegPoint)) {
89             Standard_Integer Index = myMapBegPoints.FindIndex(BegPoint);
90             Insert(myMapEndPoints.FindKey(Index),BegPoint,EndPoint);
91             myCpt++;
92             myMapBegPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
93             myMapEndPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
94           }
95           else if (myMapEndPoints.Contains(EndPoint)) {
96             Standard_Integer Index = myMapEndPoints.FindIndex(EndPoint);
97             Insert(myMapBegPoints.FindKey(Index),EndPoint,BegPoint);
98             myCpt++;
99             myMapBegPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
100             myMapEndPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
101           }
102           else {
103             myMapBegPoints.Add(BegPoint);
104             myMapEndPoints.Add(EndPoint);
105           }  
106         }
107       }
108     } 
109   }
110   
111   Standard_Integer NbLinks = myMapBegPoints.Extent();
112   i = 1;
113   while (i <= NbLinks) {
114     if (!(Precision::IsInfinite((myMapBegPoints.FindKey(i)).X()))) {
115       BegPoint = myMapBegPoints.FindKey(i);
116       EndPoint = myMapEndPoints.FindKey(i);
117       myCpt++;
118       myMapBegPoints.Substitute(i,gp_Pnt2d(Big,myCpt));
119       myMapEndPoints.Substitute(i,gp_Pnt2d(Big,myCpt));
120       Result = Concat(BegPoint,EndPoint,OutPoint);
121       if (Result == 2) 
122         ForwConstruction(OutPoint);
123       else
124         if (Result == 1)
125           PrevConstruction(OutPoint);
126         else {
127           ForwConstruction(EndPoint);
128           PrevConstruction(BegPoint);   
129         }
130     }
131     i++;
132   }
133   
134   i = 1;
135   while (i < mySection.Length()) {
136     ConcatSection(mySection.ChangeValue(i),mySection.Length(),i+1);
137     i++;
138   }
139   myNbEdges = mySection.Length();
140 }
141
142
143 //=======================================================================
144 //function : Intersect
145 //purpose  : Determines the 2 2D-points resulting of the intersection
146 //           of the triangle (Point1,Point2,Point3) by the plane
147 //=======================================================================
148
149 Standard_Boolean IntPoly_PlaneSection::Intersect(const gp_Pnt& Point1,
150                                                  const gp_Pnt& Point2,
151                                                  const gp_Pnt& Point3,
152                                                  gp_Pnt2d& OutPoint1,
153                                                  gp_Pnt2d& OutPoint2)
154 {
155   gp_Pnt Pt1 = Point1;
156   gp_Pnt Pt2 = Point2;
157   gp_Pnt Pt3 = Point3;
158   Standard_Real z1 = Pt1.Z();
159   Standard_Real z2 = Pt2.Z();
160   Standard_Real z3 = Pt3.Z();
161   Standard_Boolean intersection = Standard_False;
162
163   if ((z1 == 0) && (z2 == 0) && (z3 == 0)) 
164     return intersection;
165   if ((z1 == 0) && (z2 == 0)) {
166     intersection = Standard_True;
167     OutPoint1.SetCoord(Pt1.X(),Pt1.Y());
168     OutPoint2.SetCoord(Pt2.X(),Pt2.Y());
169     return intersection;
170   }
171   if ((z2 == 0) && (z3 == 0)) {
172     intersection = Standard_True;
173     OutPoint1.SetCoord(Pt2.X(),Pt2.Y());
174     OutPoint2.SetCoord(Pt3.X(),Pt3.Y());
175     return intersection;
176   }
177   if ((z3 == 0) && (z1 == 0)) {
178     intersection = Standard_True;
179     OutPoint1.SetCoord(Pt3.X(),Pt3.Y());
180     OutPoint2.SetCoord(Pt1.X(),Pt1.Y());
181     return intersection;
182   }
183   if (z1 == 0) {
184     if ((z2 < 0) && (z3 > 0)) 
185       intersection = Standard_True;
186     if ((z2 > 0) && (z3 < 0)) {
187       intersection = Standard_True;
188       gp_Pnt Pt = Pt2;
189       Pt2 = Pt3;
190       Pt3 = Pt; 
191     }
192     if (intersection) {
193       Standard_Real u1 = Pt2.X();
194       Standard_Real v1 = Pt2.Y();
195       z1 = Pt2.Z();
196       Standard_Real u2 = Pt3.X();
197       Standard_Real v2 = Pt3.Y();
198       z2 = Pt3.Z();
199       Standard_Real U = u1 - z1 * (u2 - u1)/(z2 - z1);
200       Standard_Real V = v1 - z1 * (v2 - v1)/(z2 - z1);
201       OutPoint1.SetCoord(Pt1.X(),Pt1.Y());
202       OutPoint2.SetCoord(U,V); 
203       return intersection;
204     }
205   }
206   else
207     if (z2 == 0) {
208       if ((z1 < 0) && (z3 > 0)) 
209         intersection = Standard_True;
210       if ((z1 > 0) && (z3 < 0)) {
211         intersection = Standard_True;
212         gp_Pnt Pt = Pt1;
213         Pt1 = Pt3;
214         Pt3 = Pt; 
215       }
216       if (intersection) {
217         Standard_Real u1 = Pt1.X();
218         Standard_Real v1 = Pt1.Y();
219         z1 = Pt1.Z();
220         Standard_Real u2 = Pt3.X();
221         Standard_Real v2 = Pt3.Y();
222         z2 = Pt3.Z();
223         Standard_Real U = u1 - z1 * (u2 - u1)/(z2 - z1);
224         Standard_Real V = v1 - z1 * (v2 - v1)/(z2 - z1);
225         OutPoint1.SetCoord(Pt2.X(),Pt2.Y());
226         OutPoint2.SetCoord(U,V); 
227         return intersection;
228       }
229     }
230     else
231       if (z3 == 0) {
232         if ((z2 < 0) && (z1 > 0)) 
233           intersection = Standard_True;
234         if ((z2 > 0) && (z1 < 0)) {
235           intersection = Standard_True;
236           gp_Pnt Pt = Pt2;
237           Pt2 = Pt1;
238           Pt1 = Pt; 
239         }
240         if (intersection) {
241           Standard_Real u1 = Pt2.X();
242           Standard_Real v1 = Pt2.Y();
243           z1 = Pt2.Z();
244           Standard_Real u2 = Pt1.X();
245           Standard_Real v2 = Pt1.Y();
246           z2 = Pt1.Z();
247           Standard_Real U = u1 - z1 * (u2 - u1)/(z2 - z1);
248           Standard_Real V = v1 - z1 * (v2 - v1)/(z2 - z1);
249           OutPoint1.SetCoord(Pt3.X(),Pt3.Y());
250           OutPoint2.SetCoord(U,V); 
251           return intersection;
252         }
253       }
254   
255   if ((z1 < 0) && (z2 > 0)) 
256     intersection = Standard_True;
257   if ((z1 > 0) && (z2 < 0)) { 
258     intersection = Standard_True;
259     gp_Pnt Pt = Pt1;
260     Pt1 = Pt2;
261     Pt2 = Pt; 
262   }
263   if (intersection) {
264     Standard_Real u1 = Pt1.X();
265     Standard_Real v1 = Pt1.Y();
266     z1 = Pt1.Z();
267     Standard_Real u2 = Pt2.X();
268     Standard_Real v2 = Pt2.Y();
269     z2 = Pt2.Z();
270     Standard_Real U = u1 - z1 * (u2 - u1)/(z2 - z1);
271     Standard_Real V = v1 - z1 * (v2 - v1)/(z2 - z1);
272     OutPoint1.SetCoord(U,V); 
273     intersection = Standard_False;
274     Pt1 = Point1;
275     Pt2 = Point2;
276     z1 = Pt1.Z();
277     z2 = Pt2.Z();
278     if ((z2 < 0) && (z3 > 0)) 
279       intersection = Standard_True;
280     if ((z2 > 0) && (z3 < 0)) {
281       intersection = Standard_True;
282       gp_Pnt Pt = Pt2;
283       Pt2 = Pt3;
284       Pt3 = Pt; 
285     }
286     if (intersection) {
287       u1 = Pt2.X();
288       v1 = Pt2.Y();
289       z1 = Pt2.Z();
290       u2 = Pt3.X();
291       v2 = Pt3.Y();
292       z2 = Pt3.Z();
293       U = u1 - z1 * (u2 - u1)/(z2 - z1);
294       V = v1 - z1 * (v2 - v1)/(z2 - z1);
295       OutPoint2.SetCoord(U,V); 
296       return intersection;
297     }
298     else {
299       intersection = Standard_True;
300       Pt3 = Point3;
301       z3 = Pt3.Z();
302       if ((z3 > 0) && (z1 < 0)) {
303         gp_Pnt Pt = Pt3;
304         Pt3 = Pt1;
305         Pt1 = Pt; 
306       }
307       u1 = Pt3.X();
308       v1 = Pt3.Y();
309       z1 = Pt3.Z();
310       u2 = Pt1.X();
311       v2 = Pt1.Y();
312       z2 = Pt1.Z();
313       U = u1 - z1 * (u2 - u1)/(z2 - z1);
314       V = v1 - z1 * (v2 - v1)/(z2 - z1);
315       OutPoint2.SetCoord(U,V); 
316       return intersection;
317     }
318   }
319   else {
320     if ((z2 < 0) && (z3 > 0)) 
321       intersection = Standard_True;
322     if ((z2 > 0) && (z3 < 0)) {
323       intersection = Standard_True;
324       gp_Pnt Pt = Pt2;
325       Pt2 = Pt3;
326       Pt3 = Pt; 
327     }
328     if (intersection) {
329       Standard_Real u1 = Pt2.X();
330       Standard_Real v1 = Pt2.Y();
331       z1 = Pt2.Z();
332       Standard_Real u2 = Pt3.X();
333       Standard_Real v2 = Pt3.Y();
334       z2 = Pt3.Z();
335       Standard_Real U = u1 - z1 * (u2 - u1)/(z2 - z1);
336       Standard_Real V = v1 - z1 * (v2 - v1)/(z2 - z1);
337       OutPoint1.SetCoord(U,V); 
338       Pt3 = Point3;
339       z3 = Pt3.Z();
340       if ((z3 > 0) && (z1 < 0)) {
341         gp_Pnt Pt = Pt3;
342         Pt3 = Pt1;
343         Pt1 = Pt; 
344       }
345       u1 = Pt3.X();
346       v1 = Pt3.Y();
347       z1 = Pt3.Z();
348       u2 = Pt1.X();
349       v2 = Pt1.Y();
350       z2 = Pt1.Z();
351       U = u1 - z1 * (u2 - u1)/(z2 - z1);
352       V = v1 - z1 * (v2 - v1)/(z2 - z1);
353       OutPoint2.SetCoord(U,V); 
354       return intersection;
355     }
356   }
357   return intersection;
358 }
359
360
361 //=======================================================================
362 //function : Insert
363 //purpose  : Sees whether OldPnt and NewPnt begins or ends a section
364 //           created before and adds the 2 others points.
365 //           If not, creates a section
366 //=======================================================================
367
368 void IntPoly_PlaneSection::Insert(const gp_Pnt2d& OldPnt,
369                                   const gp_Pnt2d& ComPnt,
370                                   const gp_Pnt2d& NewPnt)
371 {
372   Standard_Integer i = 0;
373   Standard_Integer NbSection = mySection.Length();
374   Standard_Boolean IsInSection = Standard_False;
375   
376   while (i < NbSection) {
377     i++;
378     TColgp_SequenceOfPnt2d& CurSection = mySection.ChangeValue(i);
379     if (IntPoly_Pnt2dHasher::IsEqual(OldPnt,CurSection.First())) {
380       IsInSection = Standard_True;
381       CurSection.Prepend(ComPnt);
382       CurSection.Prepend(NewPnt);
383       break;
384     }
385     if (IntPoly_Pnt2dHasher::IsEqual(OldPnt,CurSection.Last())) {
386       IsInSection = Standard_True;
387       CurSection.Append(ComPnt);
388       CurSection.Append(NewPnt);
389       break;
390     }
391     if (IntPoly_Pnt2dHasher::IsEqual(NewPnt,CurSection.First())) {
392       IsInSection = Standard_True;
393       CurSection.Prepend(ComPnt);
394       CurSection.Prepend(OldPnt);
395       break;
396     }
397     if (IntPoly_Pnt2dHasher::IsEqual(NewPnt,CurSection.Last())) {
398       IsInSection = Standard_True;
399       CurSection.Append(ComPnt);
400       CurSection.Append(OldPnt);
401       break;
402     }
403   }
404   if (!(IsInSection)) {
405     TColgp_SequenceOfPnt2d EmptySec;
406     EmptySec.Append(OldPnt);
407     EmptySec.Append(ComPnt);
408     EmptySec.Append(NewPnt);
409     mySection.Append(EmptySec);
410   }  
411 }
412
413
414 //=======================================================================
415 //function : Concat
416 //purpose  : sees whether BegPnt or EndPnt begins or ends a section
417 //           created before, and returns the other point to continue 
418 //           the construction
419 //           Returns 2 if the construction is 'Forward'
420 //           Returns 1 if the construction is 'Previous'
421 //           Returns 0 if not and creates a section
422 //=======================================================================
423
424 Standard_Integer IntPoly_PlaneSection::Concat(const gp_Pnt2d& BegPnt,
425                                               const gp_Pnt2d& EndPnt,
426                                               gp_Pnt2d& OutPnt)
427 {
428   Standard_Integer i = 0;
429   Standard_Integer NbSection = mySection.Length();
430   Standard_Integer ConcatIdx = 0;
431   
432   while (i < NbSection) {
433     i++;
434     TColgp_SequenceOfPnt2d& CurSection = mySection.ChangeValue(i);
435     if (IntPoly_Pnt2dHasher::IsEqual(BegPnt,CurSection.First())) {
436       ConcatIdx = 1;
437       myIndex = i;
438       CurSection.Prepend(EndPnt);
439       OutPnt = EndPnt;
440       break;
441     }
442     if (IntPoly_Pnt2dHasher::IsEqual(BegPnt,CurSection.Last())) {
443       ConcatIdx = 2;
444       myIndex = i;
445       CurSection.Append(EndPnt);
446       OutPnt = EndPnt;
447       break;
448     }
449     if (IntPoly_Pnt2dHasher::IsEqual(EndPnt,CurSection.First())) {
450       ConcatIdx = 1;
451       myIndex = i;
452       CurSection.Prepend(BegPnt);
453       OutPnt = BegPnt;
454       break;
455     }
456     if (IntPoly_Pnt2dHasher::IsEqual(EndPnt,CurSection.Last())) {
457       ConcatIdx = 2;
458       myIndex = i;
459       CurSection.Append(BegPnt);
460       OutPnt = BegPnt;
461       break;
462     }
463   }
464   if (ConcatIdx == 0) {
465     TColgp_SequenceOfPnt2d EmptySec;
466     EmptySec.Append(BegPnt);
467     EmptySec.Append(EndPnt);
468     mySection.Append(EmptySec);
469     NbSection++;
470     myIndex = NbSection;
471   }  
472   return ConcatIdx;
473 }
474
475
476 //=======================================================================
477 //function : ConcatSection
478 //purpose  : Sees whether Section begins or ends another one in  mySection,
479 //           from the rank 'Index' to the last one 'NbSection'
480 //=======================================================================
481
482 void IntPoly_PlaneSection::ConcatSection(TColgp_SequenceOfPnt2d& Section,
483                                          const Standard_Integer NbSection,
484                                          const Standard_Integer Index)
485 {
486   Standard_Integer j;
487   Standard_Integer i = Index;
488   gp_Pnt2d BegPnt = Section.First();
489   gp_Pnt2d EndPnt = Section.Last();
490
491   while (i <= NbSection) {
492     TColgp_SequenceOfPnt2d& CurSection = mySection.ChangeValue(i);
493     Standard_Integer CurSection_Length = CurSection.Length(); 
494     if (IntPoly_Pnt2dHasher::IsEqual(BegPnt,CurSection.First())) {
495       for (j = 2;j <= CurSection_Length;j++) 
496         Section.Prepend(CurSection.Value(j));
497       mySection.Remove(i);
498       ConcatSection(Section,NbSection-1,Index);
499       break;
500     }
501     else
502       if (IntPoly_Pnt2dHasher::IsEqual(BegPnt,CurSection.Last())) {
503         for (j = CurSection_Length-1;j >= 1;j--) 
504           Section.Prepend(CurSection.Value(j));
505         mySection.Remove(i);
506         ConcatSection(Section,NbSection-1,Index);
507         break;
508       }
509       else
510         if (IntPoly_Pnt2dHasher::IsEqual(EndPnt,CurSection.First())) {
511           for (j = 2;j <= CurSection_Length;j++) 
512             Section.Append(CurSection.Value(j));
513           mySection.Remove(i);
514           ConcatSection(Section,NbSection-1,Index);
515           break;
516         }
517         else
518           if (IntPoly_Pnt2dHasher::IsEqual(EndPnt,CurSection.Last())) {
519             for (j = CurSection_Length-1;j >= 1;j--) 
520               Section.Append(CurSection.Value(j));
521             mySection.Remove(i);
522             ConcatSection(Section,NbSection-1,Index);
523             break;
524           }
525     i++;
526   }
527 }
528
529
530 //=======================================================================
531 //function : ForwContruction
532 //purpose  : Builds a section from Point in this way  
533 //                    ___   ___   ___   ___
534 //               <---/__/--/__/--/__/--/__/--Point
535 //=======================================================================
536
537 void IntPoly_PlaneSection::ForwConstruction(const gp_Pnt2d& Point)
538 {
539   if (myMapBegPoints.Contains(Point)) {
540     Standard_Integer Index = myMapBegPoints.FindIndex(Point);
541     gp_Pnt2d Pnt = myMapEndPoints.FindKey(Index);
542     (mySection.ChangeValue(myIndex)).Append(Pnt);
543     Standard_Real Big = Precision::Infinite();
544     myCpt++;
545     myMapBegPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
546     myMapEndPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
547     ForwConstruction(Pnt);
548   }
549 }
550
551
552 //=======================================================================
553 //function : PrevContruction
554 //purpose  : Builds a section from Point in this way  
555 //                      ___   ___   ___   ___
556 //              Point--/__/--/__/--/__/--/__/--->
557 //=======================================================================
558
559 void IntPoly_PlaneSection::PrevConstruction(const gp_Pnt2d& Point)
560 {
561   if (myMapEndPoints.Contains(Point)) {
562     Standard_Integer Index = myMapEndPoints.FindIndex(Point);
563     gp_Pnt2d Pnt = myMapBegPoints.FindKey(Index);
564     (mySection.ChangeValue(myIndex)).Prepend(Pnt);
565     Standard_Real Big = Precision::Infinite();
566     myCpt++;
567     myMapBegPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
568     myMapEndPoints.Substitute(Index,gp_Pnt2d(Big,myCpt));
569     PrevConstruction(Pnt);
570   }
571 }
572
573
574 //=======================================================================
575 //function : NbEdges
576 //purpose  : Returns the final number of edges in the section
577 //=======================================================================
578
579 Standard_Integer IntPoly_PlaneSection::NbEdges()
580 { return myNbEdges; }
581
582
583 //=======================================================================
584 //function : Edge
585 //purpose  : Builds the edges of the section
586 //=======================================================================
587
588 TopoDS_Edge IntPoly_PlaneSection::Edge(const Standard_Integer Index)
589 {
590   const TColgp_SequenceOfPnt2d& CurSection = mySection.ChangeValue(Index);
591   Standard_Integer NbPoints = CurSection.Length();
592   TColgp_Array1OfPnt TabPnt(1,NbPoints);
593   gp_Pnt CurPoint;
594   for (Standard_Integer i = 1 ; i <= NbPoints ; i++) {
595     CurPoint.SetX((CurSection.Value(i)).X());
596     CurPoint.SetY((CurSection.Value(i)).Y());
597     CurPoint.SetZ(0);
598     TabPnt.SetValue(i,CurPoint.Transformed(myBackTransform));
599   }
600   Handle(Poly_Polygon3D) Pol = new Poly_Polygon3D(TabPnt);
601   TopoDS_Edge Edge;
602   BRep_Builder B;
603   B.MakeEdge(Edge,Pol);
604   return Edge;
605 }
606
607
608
609
610
611
612
613