0023548: Boolean operation between two faces fails
[occt.git] / src / IntPolyh / IntPolyh_Triangle.cxx
1 // Created on: 1999-03-08
2 // Created by: Fabrice SERVANT
3 // Copyright (c) 1999-1999 Matra Datavision
4 // Copyright (c) 1999-2012 OPEN CASCADE SAS
5 //
6 // The content of this file is subject to the Open CASCADE Technology Public
7 // License Version 6.5 (the "License"). You may not use the content of this file
8 // except in compliance with the License. Please obtain a copy of the License
9 // at http://www.opencascade.org and read it completely before using this file.
10 //
11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
13 //
14 // The Original Code and all software distributed under the License is
15 // distributed on an "AS IS" basis, without warranty of any kind, and the
16 // Initial Developer hereby disclaims all such warranties, including without
17 // limitation, any warranties of merchantability, fitness for a particular
18 // purpose or non-infringement. Please see the License for the specific terms
19 // and conditions governing the rights and limitations under the License.
20
21
22
23 #include <IntPolyh_Triangle.ixx>
24 #include <IntPolyh_Point.ixx>
25 #include <IntPolyh_Edge.ixx>
26 #include <IntPolyh_StartPoint.ixx>
27 #include <IntPolyh_Couple.ixx>
28 #include <stdio.h>
29
30 #define MyTolerance 10.0e-7
31 #define MyConfusionPrecision 10.0e-12
32 #define SquareMyConfusionPrecision 10.0e-24
33
34 static
35   void GetInfoTA(const Standard_Integer numP1,
36                  const Standard_Integer numP2,
37                  const Standard_Integer numTA,
38                  const IntPolyh_ArrayOfTriangles & TTriangles,
39                  Standard_Integer & numP3b,
40                  Standard_Integer & P3bIndex,
41                  Standard_Integer & Edge2b,
42                  Standard_Integer & Edge3b);
43 static
44   void NewTriangle(const Standard_Integer P1,
45                    const Standard_Integer P2,
46                    const Standard_Integer P3,
47                    IntPolyh_ArrayOfTriangles &TTriangles,
48                    const Handle(Adaptor3d_HSurface)& MySurface,
49                    IntPolyh_ArrayOfPoints &TPoints);
50 static
51   void NewEdge(const Standard_Integer P1,
52                const Standard_Integer P2,
53                const Standard_Integer T1,
54                const Standard_Integer T2,
55              IntPolyh_ArrayOfEdges & TEdges); 
56 static
57   void OldEdge(const Standard_Integer EdgeN,
58                const Standard_Integer NumTri,
59                const Standard_Integer NewTriNum,
60                IntPolyh_ArrayOfEdges & TEdges) ;
61 static
62   void TestOldEdgeB(const Standard_Integer NumTA,
63                     const Standard_Integer numPtT1,
64                     const Standard_Integer numPtT2,
65                     const Standard_Integer T1,
66                     const Standard_Integer T2,
67                     const IntPolyh_ArrayOfTriangles & TTriangles,
68                     const Standard_Integer Edge1,
69                     const Standard_Integer Edge3,
70                     IntPolyh_ArrayOfEdges & TEdges );
71
72 //=======================================================================
73 //function : IntPolyh_Triangle
74 //purpose  : 
75 //=======================================================================
76 IntPolyh_Triangle::IntPolyh_Triangle() 
77
78   p1(-1),p2(-1),p3(-1),
79   e1(-1),oe1(0),e2(-1),oe2(0),e3(-1),oe3(0),
80   II(0),IP(1),Fleche(0.0) 
81 {
82
83 //=======================================================================
84 //function : IntPolyh_Triangle
85 //purpose  : 
86 //=======================================================================
87 IntPolyh_Triangle::IntPolyh_Triangle(const Standard_Integer a,
88                                      const Standard_Integer b,
89                                      const Standard_Integer c) 
90 :
91   p1(a),p2(b),p3(c),
92   e1(-1),oe1(0),e2(-1),oe2(0),e3(-1),oe3(0),
93   II(0),IP(1),Fleche(0.0) 
94
95 }
96 //=======================================================================
97 //function : FirstPoint
98 //purpose  : 
99 //=======================================================================
100 Standard_Integer IntPolyh_Triangle::FirstPoint() const 
101
102   return(p1); 
103
104 //=======================================================================
105 //function : SecondPoint
106 //purpose  : 
107 //=======================================================================
108 Standard_Integer IntPolyh_Triangle::SecondPoint() const 
109
110   return(p2); 
111 }
112 //=======================================================================
113 //function : ThirdPoint
114 //purpose  : 
115 //=======================================================================
116 Standard_Integer IntPolyh_Triangle::ThirdPoint() const 
117 {
118   return(p3); 
119 }
120 //=======================================================================
121 //function : FirstEdge
122 //purpose  : 
123 //=======================================================================
124 Standard_Integer IntPolyh_Triangle::FirstEdge() const
125 {
126   return(e1); 
127 }
128 //=======================================================================
129 //function : FirstEdgeOrientation
130 //purpose  : 
131 //=======================================================================
132 Standard_Integer IntPolyh_Triangle::FirstEdgeOrientation() const 
133 {
134   return(oe1); 
135 }
136 //=======================================================================
137 //function : SecondEdge
138 //purpose  : 
139 //=======================================================================
140 Standard_Integer IntPolyh_Triangle::SecondEdge() const 
141 {
142   return(e2); 
143 }
144 //=======================================================================
145 //function : SecondEdgeOrientation
146 //purpose  : 
147 //=======================================================================
148 Standard_Integer IntPolyh_Triangle::SecondEdgeOrientation() const 
149
150   return(oe2); 
151 }
152 //=======================================================================
153 //function : ThirdEdge
154 //purpose  : 
155 //=======================================================================
156 Standard_Integer IntPolyh_Triangle::ThirdEdge() const 
157 {
158   return(e3); 
159 }
160 //=======================================================================
161 //function : ThirdEdgeOrientation
162 //purpose  : 
163 //=======================================================================
164 Standard_Integer IntPolyh_Triangle::ThirdEdgeOrientation() const
165 {
166   return(oe3); 
167 }
168 //=======================================================================
169 //function : GetFleche
170 //purpose  : 
171 //=======================================================================
172 Standard_Real IntPolyh_Triangle::GetFleche() const 
173 {
174   return(Fleche); 
175 }
176 //=======================================================================
177 //function : IndiceIntersectionPossible
178 //purpose  : 
179 //=======================================================================
180 Standard_Integer IntPolyh_Triangle::IndiceIntersectionPossible() const 
181 {
182   return(IP); 
183 }
184 //=======================================================================
185 //function : IndiceIntersection
186 //purpose  : 
187 //=======================================================================
188 Standard_Integer IntPolyh_Triangle::IndiceIntersection() const 
189 {
190   return(II); 
191 }
192 //=======================================================================
193 //function : SetFirstPoint
194 //purpose  : 
195 //=======================================================================
196 void IntPolyh_Triangle::SetFirstPoint(const Standard_Integer a) 
197 {
198   p1=a; 
199
200 //=======================================================================
201 //function : SetSecondPoint
202 //purpose  : 
203 //=======================================================================
204 void IntPolyh_Triangle::SetSecondPoint(const Standard_Integer b)
205 {
206   p2=b; 
207 }    
208 //=======================================================================
209 //function : SetThirdPoint
210 //purpose  : 
211 //=======================================================================
212 void IntPolyh_Triangle::SetThirdPoint(const Standard_Integer c) 
213
214   p3=c;
215 }
216 //=======================================================================
217 //function : SetFirstEdge
218 //purpose  : 
219 //=======================================================================
220 void IntPolyh_Triangle::SetFirstEdge(const Standard_Integer e, 
221                                      const Standard_Integer oe) 
222 {
223   e1=e; 
224   oe1=oe;
225 }
226 //=======================================================================
227 //function : SetSecondEdge
228 //purpose  : 
229 //=======================================================================
230 void IntPolyh_Triangle::SetSecondEdge(const Standard_Integer f, 
231                                       const Standard_Integer of) 
232 {
233   e2=f; 
234   oe2=of; 
235 }
236 //=======================================================================
237 //function : SetThirdEdge
238 //purpose  : 
239 //=======================================================================
240 void IntPolyh_Triangle::SetThirdEdge(const Standard_Integer g, 
241                                      const Standard_Integer og) 
242 {
243   e3=g; 
244   oe3=og; 
245 }
246 //=======================================================================
247 //function : SetFleche
248 //purpose  : 
249 //=======================================================================
250 void IntPolyh_Triangle::SetFleche(const Standard_Real A) 
251 {
252   Fleche=A;
253 }
254 //=======================================================================
255 //function : SetIndiceIntersectionPossible
256 //purpose  : 
257 //=======================================================================
258 void IntPolyh_Triangle::SetIndiceIntersectionPossible(const Standard_Integer I) 
259 {
260   IP=I; 
261 }
262 //=======================================================================
263 //function : SetIndiceIntersection
264 //purpose  : 
265 //=======================================================================
266 void IntPolyh_Triangle::SetIndiceIntersection(const Standard_Integer I)
267 {
268   II=I; 
269 }
270 //=======================================================================
271 //function : GetEdgeNumber
272 //purpose  : 
273 //=======================================================================
274 Standard_Integer 
275   IntPolyh_Triangle::GetEdgeNumber(const Standard_Integer EdgeIndex) const 
276
277   if(EdgeIndex==1)
278     return(e1);
279   if(EdgeIndex==2)
280     return(e2);
281   if(EdgeIndex==3)
282     return(e3);
283
284   return 0;
285 }  
286 //=======================================================================
287 //function : SetEdge
288 //purpose  : 
289 //=======================================================================
290 void IntPolyh_Triangle::SetEdge(const Standard_Integer EdgeIndex,
291                                 const Standard_Integer EdgeNumber) 
292 {
293   if(EdgeIndex==1)
294     e1=EdgeNumber;
295   if(EdgeIndex==2)
296     e2=EdgeNumber;
297   if(EdgeIndex==3)
298     e3=EdgeNumber;
299 }  
300 //=======================================================================
301 //function : GetEdgeOrientation
302 //purpose  : 
303 //=======================================================================
304 Standard_Integer 
305   IntPolyh_Triangle::GetEdgeOrientation(const Standard_Integer EdgeIndex) const 
306 {
307   if(EdgeIndex==1)
308     return(oe1);
309   if(EdgeIndex==2)
310     return(oe2);
311   if(EdgeIndex==3)
312     return(oe3);
313
314   return 0;
315
316 }  
317 //=======================================================================
318 //function : SetEdgeOrientation
319 //purpose  : 
320 //=======================================================================
321 void IntPolyh_Triangle::SetEdgeOrientation(const Standard_Integer EdgeIndex,
322                                            const Standard_Integer OrEd) 
323 {
324   if(EdgeIndex==1)
325     oe1=OrEd;
326   if(EdgeIndex==2)
327     oe2=OrEd;
328   if(EdgeIndex==3)
329     oe3=OrEd;
330 }  
331
332       
333 //=======================================================================
334 //function : TriangleDeflection
335 //purpose  : 
336 /*Calcul de la fleche pour un triangle**************
337   Distance entre le plan forme par le triangle et
338   le barycentre situe sur la surface calcule avec les coordonnees Gu,Gv
339   (coordonnees du barycentre du triangle dans l'espace UV)*/
340 //=======================================================================
341 void IntPolyh_Triangle::TriangleDeflection(const Handle(Adaptor3d_HSurface)& MySurface,
342                                            const IntPolyh_ArrayOfPoints& TPoints)
343 {
344   const IntPolyh_Point & P1 = TPoints[p1];
345   const IntPolyh_Point & P2 = TPoints[p2];
346   const IntPolyh_Point & P3 = TPoints[p3];
347   //
348   //modified by NIZNHY-PKV Fri Jan 20 14:25:11 2012f
349   {
350     Standard_Integer iDeg1, iDeg2, iDeg3, iDeg;
351     //
352     iDeg1=(P1.Degenerated()) ? 1 : 0;
353     iDeg2=(P2.Degenerated()) ? 1 : 0;
354     iDeg3=(P3.Degenerated()) ? 1 : 0;
355     iDeg=iDeg1+iDeg2+iDeg3;
356     if (iDeg>1) {
357       Fleche=0.;
358       return;
359     }
360   }
361   //modified by NIZNHY-PKV Fri Jan 20 14:25:13 2012t
362   Standard_Real Gu, Gv, SqNorme;
363   gp_Pnt PtXYZ;
364   //
365   Gu=(P1.U()+P2.U()+P3.U())/3.0;
366   Gv=(P1.V()+P2.V()+P3.V())/3.0;
367
368   PtXYZ = (MySurface)->Value( Gu, Gv);
369   IntPolyh_Point BarycentreReel(PtXYZ.X(), PtXYZ.Y(), PtXYZ.Z(), Gu, Gv);
370   IntPolyh_Point NormaleTri;
371   NormaleTri.Cross(P2-P1,P3-P1);
372   SqNorme=NormaleTri.SquareModulus();
373   
374   if (SqNorme > SquareMyConfusionPrecision) {
375     NormaleTri=NormaleTri/sqrt(SqNorme);
376     Fleche=Abs(NormaleTri.Dot( BarycentreReel-P1));
377   }
378   else {
379     // On calcule la fleche sur le plus grand des edges
380     // calcul des longueurs des cotes au carre
381       Standard_Real L12 = P1.SquareDistance(P2);
382       Standard_Real L23 = P2.SquareDistance(P3);
383       Standard_Real L31 = P3.SquareDistance(P1);
384
385       IntPolyh_Point Milieu; // milieu du plus grand des edges
386
387       if ((L12>L23) && (L12>L31))
388         Milieu.Middle( MySurface,P1, P2);
389       else if ((L23>L31) && (L23>L12))
390         Milieu.Middle( MySurface,P2, P3);
391       else if ((L31>L12) && (L31>L23))
392         Milieu.Middle( MySurface,P3, P1);
393         
394         
395       gp_Pnt PtXYZ = (MySurface)->Value( Milieu.U(), Milieu.V());
396       IntPolyh_Point MilieuReel(PtXYZ.X(), PtXYZ.Y(), PtXYZ.Z(), Milieu.U(), Milieu.V());
397       Fleche = sqrt(Milieu.SquareDistance(MilieuReel));
398     }
399 }
400
401 //=======================================================================
402 //function : CheckCommonEdge
403 //purpose  : 
404 //=======================================================================
405 Standard_Integer 
406   IntPolyh_Triangle::CheckCommonEdge(const Standard_Integer PT1,
407                                      const Standard_Integer PT2,
408                                      const Standard_Integer PT3,
409                                      const Standard_Integer Index,
410                                      const IntPolyh_ArrayOfTriangles &TTriangles)  const 
411 {
412   Standard_Integer P1,P2,P3,res=-1;
413   P1=TTriangles[Index].FirstPoint();
414   P2=TTriangles[Index].SecondPoint();
415   P3=TTriangles[Index].ThirdPoint();
416   
417   if ( (P1==PT1)||(P1==PT2) ) {
418     if ( ( (P2==PT1)||(P2==PT2) )&&(P3!=PT3) ) res = Index; //edge commun P1P2
419     else if ( ( (P3==PT1)||(P3==PT2) )&&(P2!=PT3) ) res = Index;//edge commun P1P3
420   }
421   else if ( (P2==PT1)||(P2==PT2) ) {
422     if ( ( (P3==PT1)||(P3==PT2) )&&(P1!=PT3) ) res = Index; //edge commun P2P3
423   }
424   else res=-1;
425   return(res);
426 }
427 //=======================================================================
428 //function : GetNextTriangle2
429 //purpose  : 
430 //=======================================================================
431 Standard_Integer 
432   IntPolyh_Triangle::GetNextTriangle2(const Standard_Integer NumTri,
433                                       const Standard_Integer NumEdge,
434                                       const IntPolyh_ArrayOfEdges &TEdges) const 
435 {
436   Standard_Integer NumNextTri=-1;
437   if (NumEdge==1) {
438     const IntPolyh_Edge & Edge1=TEdges[e1];
439     if(Edge1.FirstTriangle()==NumTri)
440       NumNextTri=Edge1.SecondTriangle();
441     else
442       NumNextTri=Edge1.FirstTriangle();
443   }
444   else if (NumEdge==2) {
445     const IntPolyh_Edge & Edge2=TEdges[e2];
446     if(Edge2.FirstTriangle()==NumTri)
447       NumNextTri=Edge2.SecondTriangle();
448     else
449       NumNextTri=Edge2.FirstTriangle();
450   }
451   else if (NumEdge==3) {
452     const IntPolyh_Edge & Edge3=TEdges[e3];
453     if(Edge3.FirstTriangle()==NumTri)
454       NumNextTri=Edge3.SecondTriangle();
455     else
456       NumNextTri=Edge3.FirstTriangle();
457   }
458   return (NumNextTri);
459 }
460
461
462 //=======================================================================
463 //function : LinkEdges2Triangle
464 //purpose  : 
465 //=======================================================================
466 void IntPolyh_Triangle::LinkEdges2Triangle(const IntPolyh_ArrayOfEdges & TEdges,
467                                            const Standard_Integer edge1,
468                                            const Standard_Integer edge2,
469                                            const Standard_Integer edge3) {
470   if( (edge1<0)||(edge2<0)||(edge3<0) ) {
471
472   }
473   else {
474     e1=edge1;  
475     e2=edge2;
476     e3=edge3;
477     
478     if(TEdges[e1].FirstPoint()==p1) oe1=1;
479     else oe1=-1;
480     if(TEdges[e2].FirstPoint()==p2) oe2=1;
481     else oe2=-1;
482     if(TEdges[e3].FirstPoint()==p3) oe3=1;
483     else oe3=-1;
484   }
485 }
486
487 //=======================================================================
488 //function : GetInfoTA
489 //purpose  : 
490 //=======================================================================
491 void GetInfoTA(const Standard_Integer numP1,
492                const Standard_Integer numP2,
493                const Standard_Integer numTA,
494                const IntPolyh_ArrayOfTriangles & TTriangles,
495                Standard_Integer & numP3b,
496                Standard_Integer & P3bIndex,
497                Standard_Integer & Edge2b,
498                Standard_Integer & Edge3b)
499 {
500   /// On veut savoir quel est le troisieme point du triangle
501   /// adjacent (TriAdj) et quel sont les edges partant de ce point
502   const IntPolyh_Triangle & TriAdj=TTriangles[numTA];
503   Standard_Integer P1b=TriAdj.FirstPoint();
504   Standard_Integer P2b=TriAdj.SecondPoint();
505   Standard_Integer P3b=TriAdj.ThirdPoint();
506
507   if ( (P1b!=numP1)&&(P1b!=numP2) ) { 
508     numP3b=P1b; 
509     P3bIndex=1;
510     if (P2b==numP1) {
511       ///P1bP2b==numP3bnumP1:Edge3b donc dans ce cas
512      Edge3b=TriAdj.FirstEdge();
513      /// Donc P1bP3b==numP3bnumP2:Edge2b
514      Edge2b=TriAdj.ThirdEdge();
515    }
516     else {
517      Edge2b=TriAdj.FirstEdge();
518      Edge3b=TriAdj.ThirdEdge();
519     }
520   }
521   else if( (P2b!=numP1)&&(P2b!=numP2) ) { 
522     numP3b=P2b; 
523     P3bIndex=2;
524     if (P1b==numP1) {
525       ///P2bP1b==numP3bnumP1:Edge3b donc dans ce cas
526      Edge3b=TriAdj.FirstEdge();
527      /// Donc P2bP3b==numP3bnumP2:Edge2b
528      Edge2b=TriAdj.SecondEdge();
529    }
530     else {
531      Edge2b=TriAdj.FirstEdge();
532      Edge3b=TriAdj.SecondEdge();
533     }
534   }
535   else if( (P3b!=numP1)&&(P3b!=numP2) ) { 
536     numP3b=P3b; 
537     P3bIndex=3; 
538     if (P2b==numP1) {
539       ///P3bP2b==numP3bnumP1:Edge3b donc dans ce cas
540      Edge3b=TriAdj.SecondEdge();
541      /// Donc P3bP1b==numP3bnumP2:Edge2b
542      Edge2b=TriAdj.ThirdEdge();
543    }
544     else {
545      Edge2b=TriAdj.SecondEdge();
546      Edge3b=TriAdj.ThirdEdge();
547     }
548   }      
549 }
550
551 //=======================================================================
552 //function : NewTriangle
553 //purpose  : 
554 //=======================================================================
555 void NewTriangle(const Standard_Integer P1,
556                  const Standard_Integer P2,
557                  const Standard_Integer P3,
558                  IntPolyh_ArrayOfTriangles &TTriangles,
559                  const Handle(Adaptor3d_HSurface)& MySurface,
560                  IntPolyh_ArrayOfPoints &TPoints) {
561   const Standard_Integer FinTT = TTriangles.NbItems();
562   TTriangles[FinTT].SetFirstPoint(P1);
563   TTriangles[FinTT].SetSecondPoint(P2);
564   TTriangles[FinTT].SetThirdPoint(P3);
565   TTriangles[FinTT].TriangleDeflection(MySurface, TPoints);
566   TTriangles.IncrementNbItems();
567 }
568
569 //=======================================================================
570 //function : NewEdge
571 //purpose  : 
572 //=======================================================================
573 void NewEdge(const Standard_Integer P1,
574              const Standard_Integer P2,
575              const Standard_Integer T1,
576              const Standard_Integer T2,
577              IntPolyh_ArrayOfEdges & TEdges)
578 {
579
580   const Standard_Integer FinTE = TEdges.NbItems();
581
582   TEdges[FinTE].SetFirstPoint(P1);
583   TEdges[FinTE].SetSecondPoint(P2);
584   TEdges[FinTE].SetFirstTriangle(T1);
585   TEdges[FinTE].SetSecondTriangle(T2);
586   TEdges.IncrementNbItems();
587 }
588
589 //=======================================================================
590 //function : OldEdge
591 //purpose  : 
592 //=======================================================================
593 void OldEdge(const Standard_Integer EdgeN,
594              const Standard_Integer NumTri,
595              const Standard_Integer NewTriNum,
596              IntPolyh_ArrayOfEdges & TEdges) 
597 {
598   if(TEdges[EdgeN].FirstTriangle()==NumTri){
599     TEdges[EdgeN].SetFirstTriangle(NewTriNum);
600   }
601   else{
602     TEdges[EdgeN].SetSecondTriangle(NewTriNum);
603   }
604 }
605
606 //=======================================================================
607 //function : TestOldEdgeB
608 //purpose  : 
609 //=======================================================================
610 void TestOldEdgeB(const Standard_Integer NumTA,
611                   const Standard_Integer numPtT1,
612                   const Standard_Integer numPtT2,
613                   const Standard_Integer T1,
614                   const Standard_Integer T2,
615                   const IntPolyh_ArrayOfTriangles & TTriangles,
616                   const Standard_Integer Edge1,
617                   const Standard_Integer Edge3,
618                   IntPolyh_ArrayOfEdges & TEdges )
619 {
620
621   if( (TEdges[Edge1].FirstPoint() == numPtT1)
622      ||(TEdges[Edge1].SecondPoint()== numPtT1) ) {
623     /// L'edge1 est commun aux triangles NumTA et T1 
624     if(TEdges[Edge1].FirstTriangle()==NumTA) 
625       TEdges[Edge1].SetFirstTriangle(T1);
626     else TEdges[Edge1].SetSecondTriangle(T1);
627     
628     if(TEdges[Edge3].FirstTriangle()==NumTA) 
629       TEdges[Edge3].SetFirstTriangle(T2);
630     else TEdges[Edge3].SetSecondTriangle(T2);
631   }
632   else {
633     /// L'edge3 est commun aux triangles NumTA et T1 
634     if(TEdges[Edge3].FirstTriangle()==NumTA) 
635       TEdges[Edge3].SetFirstTriangle(T1);
636     else TEdges[Edge3].SetSecondTriangle(T1);      
637     if(TEdges[Edge1].FirstTriangle()==NumTA) 
638       TEdges[Edge1].SetFirstTriangle(T2);
639     else TEdges[Edge1].SetSecondTriangle(T2);
640   }
641 }
642 //=======================================================================
643 //function : MiddleRefinement
644 //purpose  : 
645 //=======================================================================
646 void IntPolyh_Triangle::MiddleRefinement(const Standard_Integer NumTri,
647                                          const Handle(Adaptor3d_HSurface)& MySurface,
648                                          IntPolyh_ArrayOfPoints &TPoints,
649                                          IntPolyh_ArrayOfTriangles &TTriangles,
650                                          IntPolyh_ArrayOfEdges & TEdges) {
651
652   Standard_Integer FinTE = TEdges.NbItems();
653   Standard_Integer FinTT = TTriangles.NbItems();
654   
655   ///Raffinage de la maille et de ses voisines par le milieu du plus grand des cotes
656
657   Standard_Integer numP1 = FirstPoint();
658   Standard_Integer numP2 = SecondPoint();
659   Standard_Integer numP3 = ThirdPoint();
660
661   IntPolyh_Point P1 = TPoints[numP1];
662   IntPolyh_Point P2 = TPoints[numP2];
663   IntPolyh_Point P3 = TPoints[numP3];
664
665
666   ///calcul des longueurs des cotes au carre
667         
668   Standard_Real L12 = P1.SquareDistance(P2);
669   Standard_Real L23 = P2.SquareDistance(P3);
670   Standard_Real L31 = P3.SquareDistance(P1);
671
672   if ((L12>L23) && (L12>L31)) {
673     const Standard_Integer FinTP = TPoints.NbItems();
674     (TPoints[FinTP]).Middle( MySurface,P1, P2);
675     
676     ///les nouveaux triangles
677     Standard_Integer T1,T2,T3,T4;
678
679     T1=FinTT;
680     NewTriangle(numP2,numP3,FinTP,TTriangles,MySurface,TPoints);
681     FinTT++;
682     T2=FinTT;;
683     NewTriangle(numP3,numP1,FinTP,TTriangles,MySurface,TPoints);
684     FinTT++;
685
686     ///***AFFINAGE DU TRIANGLE ADJACENT***
687
688     Standard_Integer numTA = GetNextTriangle2(NumTri,1,TEdges);
689
690     if (numTA>=0) {
691       Standard_Integer numP3b = -1;
692       Standard_Integer P3bIndex = -1;
693
694       Standard_Integer Edge2b = -1;
695       Standard_Integer Edge3b = -1;
696       
697       GetInfoTA(numP1,numP2,numTA,TTriangles,numP3b,P3bIndex,Edge2b,Edge3b);
698       
699       T3=FinTT;
700       NewTriangle(numP2,numP3b,FinTP,TTriangles,MySurface,TPoints);
701       FinTT++;
702       T4=FinTT;
703       NewTriangle(numP3b,numP1,FinTP,TTriangles,MySurface,TPoints);
704
705       ///On cree les nouveaux edges
706       Standard_Integer E1,E2,E3,E4;
707       
708       E1=FinTE;
709       NewEdge(numP1,FinTP,T2,T4,TEdges);
710       FinTE++;
711       E2=FinTE;
712       NewEdge(FinTP,numP2,T1,T3,TEdges);
713       FinTE++;
714       E3=FinTE;
715       NewEdge(FinTP,numP3,T1,T2,TEdges);
716       FinTE++;
717       E4=FinTE;
718       NewEdge(FinTP,numP3b,T3,T4,TEdges);
719
720       ///On met a jour les anciens edges
721       OldEdge(e2,NumTri,T1,TEdges);
722       OldEdge(e3,NumTri,T2,TEdges);
723       OldEdge(Edge2b,numTA,T3,TEdges);
724       OldEdge(Edge3b,numTA,T4,TEdges);
725       
726       /// On remplit les nouveaux triangles avec les edges
727       TTriangles[T1].LinkEdges2Triangle(TEdges,e2,E3,E2);
728       TTriangles[T2].LinkEdges2Triangle(TEdges,e3,E1,E3);
729       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge2b,E4,E2);
730       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge3b,E1,E4);
731
732       ///On tue le triangle adjacent
733       TTriangles[numTA].Fleche=-1.0;
734       TTriangles[numTA].IP=0;
735
736     }
737     else { ///seulement deux nouveaux triangles
738       //on cree les nouveaux edges avec T1 et T2
739       Standard_Integer E1,E2,E3;
740       
741       E1=FinTE;
742       NewEdge(numP1,FinTP,T2,-1,TEdges);
743       FinTE++;
744       E2=FinTE;
745       NewEdge(FinTP,numP2,T1,-1,TEdges);
746       FinTE++;
747       E3=FinTE;
748       NewEdge(FinTP,numP3,T1,T2,TEdges);
749
750       ///On met a jour les anciens edges
751       OldEdge(e2,NumTri,T1,TEdges);
752       OldEdge(e3,NumTri,T2,TEdges);
753       
754       /// On remplit les nouveaux triangles avec les edges
755       TTriangles[T1].LinkEdges2Triangle(TEdges,e2,E3,E2);
756       TTriangles[T2].LinkEdges2Triangle(TEdges,e3,E1,E3);
757     }
758   }
759   
760   else if ((L23>L31) && (L23>L12)){
761     const Standard_Integer FinTP = TPoints.NbItems();
762     (TPoints[FinTP]).Middle(MySurface, P2,P3);
763
764     ///les nouveaux triangles
765     Standard_Integer T1,T2,T3,T4;    
766     
767     T1=FinTT;
768     NewTriangle(numP1,numP2,FinTP,TTriangles,MySurface,TPoints);
769     FinTT++;
770     T2=FinTT;
771     NewTriangle(numP3,numP1,FinTP,TTriangles,MySurface,TPoints);
772     FinTT++;
773     
774     ///*RAFFINAGE DU TRIANGLE ADJACENT***
775
776     Standard_Integer numTA = GetNextTriangle2(NumTri,2,TEdges);
777
778     if (numTA>=0) {
779       Standard_Integer numP1b=-1;
780       Standard_Integer P1bIndex = -1;
781
782       Standard_Integer Edge1b = -1;
783       Standard_Integer Edge3b = -1;
784
785       GetInfoTA(numP2,numP3,numTA,TTriangles,numP1b,P1bIndex,Edge3b,Edge1b);     
786
787       T3=FinTT;
788       NewTriangle(numP2,numP1b,FinTP,TTriangles,MySurface,TPoints);
789       FinTT++;
790       T4=FinTT;
791       NewTriangle(numP1b,numP3,FinTP,TTriangles,MySurface,TPoints);
792
793       ///Nouveaux Edges
794       Standard_Integer E1,E2,E3,E4;
795
796       E1=FinTE;
797       NewEdge(numP2,FinTP,T1,T3,TEdges);
798       FinTE++;
799       E2=FinTE;
800       NewEdge(FinTP,numP3,T2,T4,TEdges);
801       FinTE++;
802       E3=FinTE;
803       NewEdge(FinTP,numP1,T1,T2,TEdges);
804       FinTE++;
805       E4=FinTE;
806       NewEdge(FinTP,numP1b,T3,T4,TEdges);
807
808       ///On met a jour les anciens edges
809       OldEdge(e1,NumTri,T1,TEdges);
810       OldEdge(e3,NumTri,T2,TEdges);
811       OldEdge(Edge1b,numTA,T3,TEdges);
812       OldEdge(Edge3b,numTA,T4,TEdges);
813       
814       /// On remplit les nouveaux triangles avec les edges
815       TTriangles[T1].LinkEdges2Triangle(TEdges,e1,E1,E3);
816       TTriangles[T2].LinkEdges2Triangle(TEdges,e3,E3,E2);
817       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge1b,E4,E1);
818       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge3b,E2,E4);
819
820       ///On tue le triangle adjacent
821       TTriangles[numTA].Fleche=-1.0;
822       TTriangles[numTA].IP=0;
823     }
824     else { ///seulement deux nouveaux triangles
825       ///Nouveaux Edges
826       Standard_Integer E1,E2,E3;
827
828       E1=FinTE;
829       NewEdge(numP2,FinTP,T1,-1,TEdges);
830       FinTE++;
831       E2=FinTE;
832       NewEdge(FinTP,numP3,T2,-1,TEdges);
833       FinTE++;
834       E3=FinTE;
835       NewEdge(FinTP,numP1,T1,T2,TEdges);
836
837       ///On met a jour les anciens edges
838       OldEdge(e1,NumTri,T1,TEdges);
839       OldEdge(e3,NumTri,T2,TEdges);
840       
841       /// On remplit les nouveaux triangles avec les edges
842       TTriangles[T1].LinkEdges2Triangle(TEdges,e1,E1,E3);
843       TTriangles[T2].LinkEdges2Triangle(TEdges,e3,E3,E2);
844     }
845   }
846     else {
847     const Standard_Integer FinTP = TPoints.NbItems();
848     (TPoints[FinTP]).Middle(MySurface, P3,P1);
849
850     Standard_Integer T1,T2,T3,T4;
851     
852     T1=FinTT;
853     NewTriangle(numP1,numP2,FinTP,TTriangles,MySurface,TPoints);
854     FinTT++;
855     T2=FinTT;
856     NewTriangle(numP2,numP3,FinTP,TTriangles,MySurface,TPoints);
857     FinTT++;
858     
859     ///*RAFFINAGE DU TRIANGLE ADJACENT***
860
861     Standard_Integer numTA = GetNextTriangle2(NumTri,3,TEdges);
862
863     if (numTA>=0) {
864
865       Standard_Integer numP2b = -1;
866       Standard_Integer P2bIndex = -1;
867       
868       Standard_Integer Edge1b = -1;
869       Standard_Integer Edge2b = -1;
870      
871       GetInfoTA(numP3,numP1,numTA,TTriangles,numP2b,P2bIndex,Edge1b,Edge2b);
872
873       T3=FinTT;
874       NewTriangle(numP1,numP2b,FinTP,TTriangles,MySurface,TPoints);
875       FinTT++;
876       T4=FinTT;
877       NewTriangle(numP2b,numP3,FinTP,TTriangles,MySurface,TPoints);
878
879       ///Nouveaux Edges
880       Standard_Integer E1,E2,E3,E4;
881
882       E1=FinTE;
883       NewEdge(numP2,FinTP,T1,T2,TEdges);
884       FinTE++;
885       E2=FinTE;
886       NewEdge(FinTP,numP3,T2,T4,TEdges);
887       FinTE++;
888       E3=FinTE;
889       NewEdge(FinTP,numP2b,T4,T3,TEdges);
890       FinTE++;
891       E4=FinTE;
892       NewEdge(FinTP,numP1,T1,T3,TEdges);
893
894       ///On met a jour les anciens edges
895       OldEdge(e1,NumTri,T1,TEdges);
896       OldEdge(e2,NumTri,T2,TEdges);
897       OldEdge(Edge1b,numTA,T3,TEdges);
898       OldEdge(Edge2b,numTA,T4,TEdges);
899       
900       /// On remplit les nouveaux triangles avec les edges
901       TTriangles[T1].LinkEdges2Triangle(TEdges,e1,E1,E4);
902       TTriangles[T2].LinkEdges2Triangle(TEdges,e2,E2,E1);
903       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge1b,E3,E4);
904       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge2b,E2,E3);
905
906       ///On tue le triangle adjacent
907       TTriangles[numTA].Fleche=-1.0;
908       TTriangles[numTA].IP=0;
909     }
910     else { ///seulement deux nouveaux triangles
911       ///Nouveaux Edges
912       Standard_Integer E1,E2,E4;
913
914       E1=FinTE;
915       NewEdge(numP2,FinTP,T1,T2,TEdges);
916       FinTE++;
917       E2=FinTE;
918       NewEdge(FinTP,numP3,T2,-1,TEdges);
919       FinTE++;
920       E4=FinTE;
921       NewEdge(FinTP,numP1,T1,-1,TEdges);
922
923       ///On met a jour les anciens edges
924       OldEdge(e1,NumTri,T1,TEdges);
925       OldEdge(e2,NumTri,T2,TEdges);
926
927       /// On remplit les nouveaux triangles avec les edges
928       TTriangles[T1].LinkEdges2Triangle(TEdges,e1,E1,E4);
929       TTriangles[T2].LinkEdges2Triangle(TEdges,e2,E2,E1);
930     }
931   }
932   /// Le triangle traite est maintenant obsolete 
933   ///***On tue le triangle***
934   Fleche=-1.0;
935   IP=0;
936
937   TPoints.IncrementNbItems();
938 }
939
940 //=======================================================================
941 //function : MultipleMiddleRefinement
942 //purpose  : 
943 //=======================================================================
944 void IntPolyh_Triangle::MultipleMiddleRefinement(const Standard_Integer NbAffinages,
945                                                  const Standard_Integer NumTri,
946                                                  const Handle(Adaptor3d_HSurface)& MySurface,
947                                                  IntPolyh_ArrayOfPoints &TPoints,
948                                                  IntPolyh_ArrayOfTriangles &TTriangles,
949                                                  IntPolyh_ArrayOfEdges & TEdges) {
950
951   const Standard_Integer FinTTInit = TTriangles.NbItems();
952
953   //On sait qu'il faut affiner au moins une fois
954   TTriangles[NumTri].MiddleRefinement(NumTri,MySurface,TPoints,
955                                       TTriangles,TEdges);
956
957   if (NbAffinages>1) {
958     Standard_Integer MyNbAffinages=0;
959     if (NbAffinages > 5)
960       MyNbAffinages = 4;//5 est le maximum et on a deja affine une fois
961     //On a decide d'arreter a 5 car avec un triangle on peut en obtenir 1024
962     else MyNbAffinages = NbAffinages-1;//dans tous les cas MyNbAffinages>0
963     
964
965     //Un affinage peut donner deux ou quatre nouveaux triangles
966     // ils seront ajoute a la fin du tableau de triangles, et auront comme indice
967     // FinTTInit, FinTTInit+1,... 
968
969
970     Standard_Integer NombreReelsAffinages = 4;
971     for(Standard_Integer iii=1; iii<MyNbAffinages; iii++) 
972       NombreReelsAffinages*=4;
973     //Avec ce calcul on fait l'hypothese que chaque triangle affine donne quatre nouveaux triangles
974     //ce qui peut etre faux si on n'affine pas le triangle adjacent
975     //dans quel cas on n'obtient que deux nouveaux triangles
976     
977     Standard_Integer FinTTAffinage = FinTTInit + NombreReelsAffinages;
978     
979     for(Standard_Integer NumTriangle=FinTTInit; NumTriangle < FinTTAffinage; NumTriangle++)
980       TTriangles[NumTriangle].MiddleRefinement(NumTriangle,MySurface,TPoints,
981                                                TTriangles,TEdges);
982   }
983 }
984
985 //=======================================================================
986 //function : CompareBoxTriangle
987 //purpose  : 
988 //=======================================================================
989 Standard_Integer IntPolyh_Triangle::CompareBoxTriangle(const Bnd_Box &b,
990                                                        const IntPolyh_ArrayOfPoints &TPoints) const{
991   Standard_Integer Test=0;
992   Bnd_Box maboite;
993   const IntPolyh_Point&    PA=TPoints[p1]; 
994   const IntPolyh_Point&    PB=TPoints[p2]; 
995   const IntPolyh_Point&    PC=TPoints[p3]; 
996   gp_Pnt pntA(PA.X(),PA.Y(),PA.Z());
997   gp_Pnt pntB(PB.X(),PB.Y(),PB.Z());
998   gp_Pnt pntC(PC.X(),PC.Y(),PC.Z());
999   maboite.Add(pntA);
1000   maboite.Add(pntB);
1001   maboite.Add(pntC);
1002   maboite.Enlarge(Fleche+MyTolerance);
1003   if (maboite.IsOut(b))
1004     Test=0;
1005   else  
1006     Test=1;
1007   return(Test);
1008   //Pour gagner du temps on pourrait envisager de garder la boite englobante dans la structure du triangle
1009 }
1010
1011 //=======================================================================
1012 //function : MultipleMiddleRefinement2
1013 //purpose  : 
1014 //=======================================================================
1015 void IntPolyh_Triangle::MultipleMiddleRefinement2(const Standard_Real CritereAffinage,
1016                                                   const Bnd_Box &b,//boite englobante de l'autre surface
1017                                                   const Standard_Integer NumTri,
1018                                                   const Handle(Adaptor3d_HSurface)& MySurface,
1019                                                   IntPolyh_ArrayOfPoints &TPoints,
1020                                                   IntPolyh_ArrayOfTriangles &TTriangles,
1021                                                   IntPolyh_ArrayOfEdges & TEdges) {
1022
1023   const Standard_Integer FinTTInit = TTriangles.NbItems();
1024   Standard_Integer CritereArret=FinTTInit+250;
1025
1026   //On sait qu'il faut affiner une fois au moins
1027   MiddleRefinement(NumTri,MySurface,TPoints,
1028                    TTriangles,TEdges);
1029
1030   Standard_Integer FinTT = TTriangles.NbItems();// FinTT n'est pas une constante, elle augmente avec l'affinage
1031
1032   for(Standard_Integer iii=FinTTInit; iii<(FinTT=TTriangles.NbItems()); iii++) {
1033     IntPolyh_Triangle& TriangleCourant = TTriangles[iii];
1034     if(TriangleCourant.CompareBoxTriangle(b,TPoints)==0)
1035       //On n'affine pas le triangle
1036       TriangleCourant.IP=0;
1037     else if (TriangleCourant.Fleche > CritereAffinage)
1038       TriangleCourant.MiddleRefinement(iii,MySurface,TPoints,
1039                                        TTriangles,TEdges);
1040       
1041     if ( FinTT > CritereArret )//critere d'arret 250 nouveaux triangles
1042       iii = FinTT;
1043   }
1044 }
1045
1046 //=======================================================================
1047 //function : SetEdgeandOrientation
1048 //purpose  : 
1049 //=======================================================================
1050 void IntPolyh_Triangle::SetEdgeandOrientation(const Standard_Integer EdgeIndex,
1051                                               const IntPolyh_ArrayOfEdges &TEdges) {
1052   const Standard_Integer FinTE = TEdges.NbItems();
1053
1054   Standard_Integer PE1 =0,PE2 =0;
1055
1056   Standard_Integer Test=1;
1057
1058   if (EdgeIndex==1) { PE1=p1; PE2=p2; }
1059   else if (EdgeIndex==2) { PE1=p2; PE2=p3; }
1060   else if (EdgeIndex==3) { PE1=p3; PE2=p1; }
1061   else { 
1062     Test=0;
1063   }
1064   if (Test!=0) {
1065     for(Standard_Integer iioo=0; iioo<FinTE; iioo++) {
1066       Standard_Integer EFP=TEdges[iioo].FirstPoint();
1067       if (EFP==PE1) {
1068         Standard_Integer ESP=TEdges[iioo].SecondPoint();
1069         if (ESP!=EFP) {
1070           if (ESP==PE2) {
1071             SetEdgeOrientation(EdgeIndex,1);
1072             SetEdge(EdgeIndex,iioo);
1073             iioo=FinTE;
1074           }
1075         }
1076         else {
1077
1078           Test=0;
1079         }
1080       }
1081       else if (EFP==PE2) {
1082         Standard_Integer ESP=TEdges[iioo].SecondPoint();
1083         if (ESP!=EFP) {
1084           if (ESP==PE1) {
1085             SetEdgeOrientation(EdgeIndex,-1);
1086             SetEdge(EdgeIndex,iioo);
1087             iioo=FinTE;
1088           }
1089         }
1090         else {
1091
1092         }   
1093       }
1094     }
1095   }
1096 }
1097
1098
1099 //=======================================================================
1100 //function : Dump
1101 //purpose  : 
1102 //=======================================================================
1103 void IntPolyh_Triangle::Dump (const Standard_Integer i) const
1104
1105   printf("\nTriangle(%3d) : Points %5d %5d %5d Edges %5d %5d %5d fleche: %8f  intersection possible %8d  intersection: %5d\n"
1106          ,i,p1,p2,p3,e1,e2,e3,Fleche,IP,II);
1107 }
1108
1109
1110 //=======================================================================
1111 //function : DumpFleche
1112 //purpose  : 
1113 //=======================================================================
1114 void IntPolyh_Triangle::DumpFleche (const Standard_Integer i) const { 
1115   printf("\nTriangle(%3d) fleche: %5f\n",i,Fleche);
1116 }
1117