0030198: Regression to 7.1.0: BRepAlgoAPI_Fuse unlimited memory usage
[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-2014 OPEN CASCADE SAS
5 //
6 // This file is part of Open CASCADE Technology software library.
7 //
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
13 //
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
16
17
18 #include <Adaptor3d_HSurface.hxx>
19 #include <Bnd_Box.hxx>
20 #include <IntPolyh_Edge.hxx>
21 #include <IntPolyh_Point.hxx>
22 #include <IntPolyh_Triangle.hxx>
23
24 #include <stdio.h>
25 #define MyTolerance 10.0e-7
26 #define MyConfusionPrecision 10.0e-12
27 #define SquareMyConfusionPrecision 10.0e-24
28
29 static
30   void GetInfoTA(const Standard_Integer numP1,
31                  const Standard_Integer numP2,
32                  const Standard_Integer numTA,
33                  const IntPolyh_ArrayOfTriangles & TTriangles,
34                  Standard_Integer & numP3b,
35                  Standard_Integer & P3bIndex,
36                  Standard_Integer & Edge2b,
37                  Standard_Integer & Edge3b);
38 static
39   void NewTriangle(const Standard_Integer P1,
40                    const Standard_Integer P2,
41                    const Standard_Integer P3,
42                    IntPolyh_ArrayOfTriangles &TTriangles,
43                    const Handle(Adaptor3d_HSurface)& MySurface,
44                    IntPolyh_ArrayOfPoints &TPoints);
45 static
46   void NewEdge(const Standard_Integer P1,
47                const Standard_Integer P2,
48                const Standard_Integer T1,
49                const Standard_Integer T2,
50              IntPolyh_ArrayOfEdges & TEdges); 
51 static
52   void OldEdge(const Standard_Integer EdgeN,
53                const Standard_Integer NumTri,
54                const Standard_Integer NewTriNum,
55                IntPolyh_ArrayOfEdges & TEdges) ;
56
57 //=======================================================================
58 //function : ComputeDeflection
59 //purpose  : Computes the deflection of the triangle.
60 //           It is computed as a distance between triangles plane and
61 //           barycenter of the triangle in UV space.
62 //=======================================================================
63 Standard_Real
64   IntPolyh_Triangle::ComputeDeflection(const Handle(Adaptor3d_HSurface)& theSurface,
65                                        const IntPolyh_ArrayOfPoints& TPoints)
66 {
67   myDeflection = 0.;
68   //
69   const IntPolyh_Point & P1 = TPoints[myPoints[0]];
70   const IntPolyh_Point & P2 = TPoints[myPoints[1]];
71   const IntPolyh_Point & P3 = TPoints[myPoints[2]];
72   //
73   {
74     // check if the triangle is not degenerated - no more than one point
75     // has a degenerated flag
76     Standard_Integer iDeg = (P1.Degenerated() ? 1 : 0) +
77                             (P2.Degenerated() ? 1 : 0) +
78                             (P3.Degenerated() ? 1 : 0);
79     if (iDeg > 1) {
80       myIsDegenerated = Standard_True;
81       return myDeflection;
82     }
83   }
84   //
85   // Plane of the triangle
86   IntPolyh_Point NormaleTri;
87   NormaleTri.Cross(P2-P1,P3-P1);
88   Standard_Real SqNorm = NormaleTri.SquareModulus();
89   if (SqNorm < SquareMyConfusionPrecision) {
90     // The triangle is degenerated
91     myIsDegenerated = Standard_True;
92     return myDeflection;
93   }
94   //
95   // Compute point on the surface
96   Standard_Real Gu=(P1.U()+P2.U()+P3.U())/3.0;
97   Standard_Real Gv=(P1.V()+P2.V()+P3.V())/3.0;
98   gp_Pnt PtXYZ = theSurface->Value( Gu, Gv);
99   // Point on the surface
100   IntPolyh_Point BarycentreReel(PtXYZ.X(), PtXYZ.Y(), PtXYZ.Z(), Gu, Gv);
101   // compute distance to plane
102   NormaleTri = NormaleTri / sqrt(SqNorm);
103   myDeflection = Abs(NormaleTri.Dot(BarycentreReel - P1));
104   return myDeflection;
105 }
106
107 //=======================================================================
108 //function : GetNextTriangle
109 //purpose  : 
110 //=======================================================================
111 Standard_Integer
112   IntPolyh_Triangle::GetNextTriangle(const Standard_Integer theTriangle,
113                                      const Standard_Integer theEdgeNum,
114                                      const IntPolyh_ArrayOfEdges& TEdges) const
115 {
116   Standard_Integer aNextTriangle = -1;
117   if (theEdgeNum < 1 || theEdgeNum > 3) {
118     return aNextTriangle;
119   }
120   //
121   const IntPolyh_Edge & anEdge = TEdges[myEdges[theEdgeNum-1]];
122   aNextTriangle = ((anEdge.FirstTriangle() == theTriangle) ?
123     anEdge.SecondTriangle() : anEdge.FirstTriangle());
124   return aNextTriangle;
125 }
126
127 //=======================================================================
128 //function : LinkEdges2Triangle
129 //purpose  : 
130 //=======================================================================
131 void IntPolyh_Triangle::LinkEdges2Triangle(const IntPolyh_ArrayOfEdges& TEdges,
132                                            const Standard_Integer theEdge1,
133                                            const Standard_Integer theEdge2,
134                                            const Standard_Integer theEdge3)
135 {
136   if (theEdge1 < 0 || theEdge2 < 0 || theEdge3 < 0) {
137     return;
138   }
139   //
140   myEdges[0] = theEdge1;
141   myEdges[1] = theEdge2;
142   myEdges[2] = theEdge3;
143   //
144   myEdgesOrientations[0] = ((TEdges[myEdges[0]].FirstPoint() == myPoints[0]) ? 1 : -1);
145   myEdgesOrientations[1] = ((TEdges[myEdges[1]].FirstPoint() == myPoints[1]) ? 1 : -1);
146   myEdgesOrientations[2] = ((TEdges[myEdges[2]].FirstPoint() == myPoints[2]) ? 1 : -1);
147 }
148
149 //=======================================================================
150 //function : GetInfoTA
151 //purpose  : 
152 //=======================================================================
153 void GetInfoTA(const Standard_Integer numP1,
154                const Standard_Integer numP2,
155                const Standard_Integer numTA,
156                const IntPolyh_ArrayOfTriangles & TTriangles,
157                Standard_Integer & numP3b,
158                Standard_Integer & P3bIndex,
159                Standard_Integer & Edge2b,
160                Standard_Integer & Edge3b)
161 {
162   /// On veut savoir quel est le troisieme point du triangle
163   /// adjacent (TriAdj) et quel sont les edges partant de ce point
164   const IntPolyh_Triangle & TriAdj=TTriangles[numTA];
165   Standard_Integer P1b=TriAdj.FirstPoint();
166   Standard_Integer P2b=TriAdj.SecondPoint();
167   Standard_Integer P3b=TriAdj.ThirdPoint();
168
169   if ( (P1b!=numP1)&&(P1b!=numP2) ) { 
170     numP3b=P1b; 
171     P3bIndex=1;
172     if (P2b==numP1) {
173       ///P1bP2b==numP3bnumP1:Edge3b donc dans ce cas
174      Edge3b=TriAdj.FirstEdge();
175      /// Donc P1bP3b==numP3bnumP2:Edge2b
176      Edge2b=TriAdj.ThirdEdge();
177    }
178     else {
179      Edge2b=TriAdj.FirstEdge();
180      Edge3b=TriAdj.ThirdEdge();
181     }
182   }
183   else if( (P2b!=numP1)&&(P2b!=numP2) ) { 
184     numP3b=P2b; 
185     P3bIndex=2;
186     if (P1b==numP1) {
187       ///P2bP1b==numP3bnumP1:Edge3b donc dans ce cas
188      Edge3b=TriAdj.FirstEdge();
189      /// Donc P2bP3b==numP3bnumP2:Edge2b
190      Edge2b=TriAdj.SecondEdge();
191    }
192     else {
193      Edge2b=TriAdj.FirstEdge();
194      Edge3b=TriAdj.SecondEdge();
195     }
196   }
197   else if( (P3b!=numP1)&&(P3b!=numP2) ) { 
198     numP3b=P3b; 
199     P3bIndex=3; 
200     if (P2b==numP1) {
201       ///P3bP2b==numP3bnumP1:Edge3b donc dans ce cas
202      Edge3b=TriAdj.SecondEdge();
203      /// Donc P3bP1b==numP3bnumP2:Edge2b
204      Edge2b=TriAdj.ThirdEdge();
205    }
206     else {
207      Edge2b=TriAdj.SecondEdge();
208      Edge3b=TriAdj.ThirdEdge();
209     }
210   }      
211 }
212
213 //=======================================================================
214 //function : NewTriangle
215 //purpose  : 
216 //=======================================================================
217 void NewTriangle(const Standard_Integer P1,
218                  const Standard_Integer P2,
219                  const Standard_Integer P3,
220                  IntPolyh_ArrayOfTriangles &TTriangles,
221                  const Handle(Adaptor3d_HSurface)& MySurface,
222                  IntPolyh_ArrayOfPoints &TPoints) {
223   const Standard_Integer FinTT = TTriangles.NbItems();
224   TTriangles[FinTT].SetFirstPoint(P1);
225   TTriangles[FinTT].SetSecondPoint(P2);
226   TTriangles[FinTT].SetThirdPoint(P3);
227   TTriangles[FinTT].ComputeDeflection(MySurface, TPoints);
228   TTriangles.IncrementNbItems();
229 }
230
231 //=======================================================================
232 //function : NewEdge
233 //purpose  : 
234 //=======================================================================
235 void NewEdge(const Standard_Integer P1,
236              const Standard_Integer P2,
237              const Standard_Integer T1,
238              const Standard_Integer T2,
239              IntPolyh_ArrayOfEdges & TEdges)
240 {
241
242   const Standard_Integer FinTE = TEdges.NbItems();
243
244   TEdges[FinTE].SetFirstPoint(P1);
245   TEdges[FinTE].SetSecondPoint(P2);
246   TEdges[FinTE].SetFirstTriangle(T1);
247   TEdges[FinTE].SetSecondTriangle(T2);
248   TEdges.IncrementNbItems();
249 }
250
251 //=======================================================================
252 //function : OldEdge
253 //purpose  : 
254 //=======================================================================
255 void OldEdge(const Standard_Integer EdgeN,
256              const Standard_Integer NumTri,
257              const Standard_Integer NewTriNum,
258              IntPolyh_ArrayOfEdges & TEdges) 
259 {
260   if(TEdges[EdgeN].FirstTriangle()==NumTri){
261     TEdges[EdgeN].SetFirstTriangle(NewTriNum);
262   }
263   else{
264     TEdges[EdgeN].SetSecondTriangle(NewTriNum);
265   }
266 }
267
268 //=======================================================================
269 //function : MiddleRefinement
270 //purpose  : 
271 //=======================================================================
272 void IntPolyh_Triangle::MiddleRefinement(const Standard_Integer NumTri,
273                                          const Handle(Adaptor3d_HSurface)& MySurface,
274                                          IntPolyh_ArrayOfPoints &TPoints,
275                                          IntPolyh_ArrayOfTriangles &TTriangles,
276                                          IntPolyh_ArrayOfEdges & TEdges)
277 {
278
279   Standard_Integer FinTE = TEdges.NbItems();
280   Standard_Integer FinTT = TTriangles.NbItems();
281
282   // Refinement of the mesh by the middle of the largest dimensions
283   Standard_Integer numP1 = FirstPoint();
284   Standard_Integer numP2 = SecondPoint();
285   Standard_Integer numP3 = ThirdPoint();
286
287   const IntPolyh_Point& P1 = TPoints[numP1];
288   const IntPolyh_Point& P2 = TPoints[numP2];
289   const IntPolyh_Point& P3 = TPoints[numP3];
290
291   // compute the largest dimension
292   Standard_Real L12 = P1.SquareDistance(P2);
293   Standard_Real L23 = P2.SquareDistance(P3);
294   Standard_Real L31 = P3.SquareDistance(P1);
295
296   if ((L12>L23) && (L12>L31)) {
297     const Standard_Integer FinTP = TPoints.NbItems();
298     (TPoints[FinTP]).Middle( MySurface,P1, P2);
299     
300     ///les nouveaux triangles
301     Standard_Integer T1,T2,T3,T4;
302
303     T1=FinTT;
304     NewTriangle(numP2,numP3,FinTP,TTriangles,MySurface,TPoints);
305     FinTT++;
306     T2=FinTT;;
307     NewTriangle(numP3,numP1,FinTP,TTriangles,MySurface,TPoints);
308     FinTT++;
309
310     ///***AFFINAGE DU TRIANGLE ADJACENT***
311
312     Standard_Integer numTA = GetNextTriangle(NumTri,1,TEdges);
313
314     if (numTA>=0) {
315       Standard_Integer numP3b = -1;
316       Standard_Integer P3bIndex = -1;
317
318       Standard_Integer Edge2b = -1;
319       Standard_Integer Edge3b = -1;
320       
321       GetInfoTA(numP1,numP2,numTA,TTriangles,numP3b,P3bIndex,Edge2b,Edge3b);
322       
323       T3=FinTT;
324       NewTriangle(numP2,numP3b,FinTP,TTriangles,MySurface,TPoints);
325       FinTT++;
326       T4=FinTT;
327       NewTriangle(numP3b,numP1,FinTP,TTriangles,MySurface,TPoints);
328
329       ///On cree les nouveaux edges
330       Standard_Integer E1,E2,E3,E4;
331       
332       E1=FinTE;
333       NewEdge(numP1,FinTP,T2,T4,TEdges);
334       FinTE++;
335       E2=FinTE;
336       NewEdge(FinTP,numP2,T1,T3,TEdges);
337       FinTE++;
338       E3=FinTE;
339       NewEdge(FinTP,numP3,T1,T2,TEdges);
340       FinTE++;
341       E4=FinTE;
342       NewEdge(FinTP,numP3b,T3,T4,TEdges);
343
344       ///On met a jour les anciens edges
345       OldEdge(myEdges[1],NumTri,T1,TEdges);
346       OldEdge(myEdges[2],NumTri,T2,TEdges);
347       OldEdge(Edge2b,numTA,T3,TEdges);
348       OldEdge(Edge3b,numTA,T4,TEdges);
349       
350       /// On remplit les nouveaux triangles avec les edges
351       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[1],E3,E2);
352       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[2],E1,E3);
353       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge2b,E4,E2);
354       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge3b,E1,E4);
355
356       ///On tue le triangle adjacent
357       TTriangles[numTA].SetDeflection(-1.0);
358       TTriangles[numTA].SetIntersectionPossible(Standard_False);
359
360     }
361     else { ///seulement deux nouveaux triangles
362       //on cree les nouveaux edges avec T1 et T2
363       Standard_Integer E1,E2,E3;
364       
365       E1=FinTE;
366       NewEdge(numP1,FinTP,T2,-1,TEdges);
367       FinTE++;
368       E2=FinTE;
369       NewEdge(FinTP,numP2,T1,-1,TEdges);
370       FinTE++;
371       E3=FinTE;
372       NewEdge(FinTP,numP3,T1,T2,TEdges);
373
374       ///On met a jour les anciens edges
375       OldEdge(myEdges[1],NumTri,T1,TEdges);
376       OldEdge(myEdges[2],NumTri,T2,TEdges);
377       
378       /// On remplit les nouveaux triangles avec les edges
379       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[1],E3,E2);
380       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[2],E1,E3);
381     }
382   }
383   
384   else if ((L23>L31) && (L23>L12)){
385     const Standard_Integer FinTP = TPoints.NbItems();
386     (TPoints[FinTP]).Middle(MySurface, P2,P3);
387
388     ///les nouveaux triangles
389     Standard_Integer T1,T2,T3,T4;    
390     
391     T1=FinTT;
392     NewTriangle(numP1,numP2,FinTP,TTriangles,MySurface,TPoints);
393     FinTT++;
394     T2=FinTT;
395     NewTriangle(numP3,numP1,FinTP,TTriangles,MySurface,TPoints);
396     FinTT++;
397     
398     ///*RAFFINAGE DU TRIANGLE ADJACENT***
399
400     Standard_Integer numTA = GetNextTriangle(NumTri,2,TEdges);
401
402     if (numTA>=0) {
403       Standard_Integer numP1b=-1;
404       Standard_Integer P1bIndex = -1;
405
406       Standard_Integer Edge1b = -1;
407       Standard_Integer Edge3b = -1;
408
409       GetInfoTA(numP2,numP3,numTA,TTriangles,numP1b,P1bIndex,Edge3b,Edge1b);     
410
411       T3=FinTT;
412       NewTriangle(numP2,numP1b,FinTP,TTriangles,MySurface,TPoints);
413       FinTT++;
414       T4=FinTT;
415       NewTriangle(numP1b,numP3,FinTP,TTriangles,MySurface,TPoints);
416
417       ///Nouveaux Edges
418       Standard_Integer E1,E2,E3,E4;
419
420       E1=FinTE;
421       NewEdge(numP2,FinTP,T1,T3,TEdges);
422       FinTE++;
423       E2=FinTE;
424       NewEdge(FinTP,numP3,T2,T4,TEdges);
425       FinTE++;
426       E3=FinTE;
427       NewEdge(FinTP,numP1,T1,T2,TEdges);
428       FinTE++;
429       E4=FinTE;
430       NewEdge(FinTP,numP1b,T3,T4,TEdges);
431
432       ///On met a jour les anciens edges
433       OldEdge(myEdges[0],NumTri,T1,TEdges);
434       OldEdge(myEdges[2],NumTri,T2,TEdges);
435       OldEdge(Edge1b,numTA,T3,TEdges);
436       OldEdge(Edge3b,numTA,T4,TEdges);
437       
438       /// On remplit les nouveaux triangles avec les edges
439       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[0],E1,E3);
440       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[2],E3,E2);
441       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge1b,E4,E1);
442       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge3b,E2,E4);
443
444       ///On tue le triangle adjacent
445       TTriangles[numTA].SetDeflection(-1.0);
446       TTriangles[numTA].SetIntersectionPossible(Standard_False);
447     }
448     else { ///seulement deux nouveaux triangles
449       ///Nouveaux Edges
450       Standard_Integer E1,E2,E3;
451
452       E1=FinTE;
453       NewEdge(numP2,FinTP,T1,-1,TEdges);
454       FinTE++;
455       E2=FinTE;
456       NewEdge(FinTP,numP3,T2,-1,TEdges);
457       FinTE++;
458       E3=FinTE;
459       NewEdge(FinTP,numP1,T1,T2,TEdges);
460
461       ///On met a jour les anciens edges
462       OldEdge(myEdges[0],NumTri,T1,TEdges);
463       OldEdge(myEdges[2],NumTri,T2,TEdges);
464       
465       /// On remplit les nouveaux triangles avec les edges
466       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[0],E1,E3);
467       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[2],E3,E2);
468     }
469   }
470     else {
471     const Standard_Integer FinTP = TPoints.NbItems();
472     (TPoints[FinTP]).Middle(MySurface, P3,P1);
473
474     Standard_Integer T1,T2,T3,T4;
475     
476     T1=FinTT;
477     NewTriangle(numP1,numP2,FinTP,TTriangles,MySurface,TPoints);
478     FinTT++;
479     T2=FinTT;
480     NewTriangle(numP2,numP3,FinTP,TTriangles,MySurface,TPoints);
481     FinTT++;
482     
483     ///*RAFFINAGE DU TRIANGLE ADJACENT***
484
485     Standard_Integer numTA = GetNextTriangle(NumTri,3,TEdges);
486
487     if (numTA>=0) {
488
489       Standard_Integer numP2b = -1;
490       Standard_Integer P2bIndex = -1;
491       
492       Standard_Integer Edge1b = -1;
493       Standard_Integer Edge2b = -1;
494      
495       GetInfoTA(numP3,numP1,numTA,TTriangles,numP2b,P2bIndex,Edge1b,Edge2b);
496
497       T3=FinTT;
498       NewTriangle(numP1,numP2b,FinTP,TTriangles,MySurface,TPoints);
499       FinTT++;
500       T4=FinTT;
501       NewTriangle(numP2b,numP3,FinTP,TTriangles,MySurface,TPoints);
502
503       ///Nouveaux Edges
504       Standard_Integer E1,E2,E3,E4;
505
506       E1=FinTE;
507       NewEdge(numP2,FinTP,T1,T2,TEdges);
508       FinTE++;
509       E2=FinTE;
510       NewEdge(FinTP,numP3,T2,T4,TEdges);
511       FinTE++;
512       E3=FinTE;
513       NewEdge(FinTP,numP2b,T4,T3,TEdges);
514       FinTE++;
515       E4=FinTE;
516       NewEdge(FinTP,numP1,T1,T3,TEdges);
517
518       ///On met a jour les anciens edges
519       OldEdge(myEdges[0],NumTri,T1,TEdges);
520       OldEdge(myEdges[1],NumTri,T2,TEdges);
521       OldEdge(Edge1b,numTA,T3,TEdges);
522       OldEdge(Edge2b,numTA,T4,TEdges);
523       
524       /// On remplit les nouveaux triangles avec les edges
525       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[0],E1,E4);
526       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[1],E2,E1);
527       TTriangles[T3].LinkEdges2Triangle(TEdges,Edge1b,E3,E4);
528       TTriangles[T4].LinkEdges2Triangle(TEdges,Edge2b,E2,E3);
529
530       ///On tue le triangle adjacent
531       TTriangles[numTA].SetDeflection(-1.0);
532       TTriangles[numTA].SetIntersectionPossible(Standard_False);
533     }
534     else { ///seulement deux nouveaux triangles
535       ///Nouveaux Edges
536       Standard_Integer E1,E2,E4;
537
538       E1=FinTE;
539       NewEdge(numP2,FinTP,T1,T2,TEdges);
540       FinTE++;
541       E2=FinTE;
542       NewEdge(FinTP,numP3,T2,-1,TEdges);
543       FinTE++;
544       E4=FinTE;
545       NewEdge(FinTP,numP1,T1,-1,TEdges);
546
547       ///On met a jour les anciens edges
548       OldEdge(myEdges[0],NumTri,T1,TEdges);
549       OldEdge(myEdges[1],NumTri,T2,TEdges);
550
551       /// On remplit les nouveaux triangles avec les edges
552       TTriangles[T1].LinkEdges2Triangle(TEdges,myEdges[0],E1,E4);
553       TTriangles[T2].LinkEdges2Triangle(TEdges,myEdges[1],E2,E1);
554     }
555   }
556   TPoints.IncrementNbItems();
557
558   // make the triangle obsolete
559   myDeflection = -1.0;
560   myIsIntersectionPossible = Standard_False;
561 }
562
563 //=======================================================================
564 //function : MultipleMiddleRefinement
565 //purpose  : 
566 //=======================================================================
567 void IntPolyh_Triangle::MultipleMiddleRefinement(const Standard_Real theRefineCriterion,
568                                                  const Bnd_Box& theBox,
569                                                  const Standard_Integer theTriangleNumber,
570                                                  const Handle(Adaptor3d_HSurface)& theSurface,
571                                                  IntPolyh_ArrayOfPoints& TPoints,
572                                                  IntPolyh_ArrayOfTriangles& TTriangles,
573                                                  IntPolyh_ArrayOfEdges& TEdges)
574 {
575   // Number of triangles before refinement of current triangle
576   const Standard_Integer FinTTInit = TTriangles.NbItems();
577   // Criteria to stop splitting - double of the initial number of triangles,
578   // i.e. allow each triangle to be split at least once. Add a constant
579   // to allow the splits of triangles to be checked.
580   const Standard_Integer MaxNbTT = 2*FinTTInit + 1000;
581   // Split the current triangle
582   MiddleRefinement(theTriangleNumber, theSurface, TPoints, TTriangles, TEdges);
583   // Refine the new triangles
584   for (Standard_Integer i = FinTTInit; i < TTriangles.NbItems() && i < MaxNbTT; ++i) {
585     IntPolyh_Triangle& aTriangle = TTriangles[i];
586     if(theBox.IsOut(aTriangle.BoundingBox(TPoints))) {
587       aTriangle.SetIntersectionPossible(Standard_False);
588     }
589     else if (aTriangle.Deflection() > theRefineCriterion) {
590       aTriangle.MiddleRefinement(i, theSurface, TPoints, TTriangles, TEdges);
591     }
592   }
593 }
594
595 //=======================================================================
596 //function : SetEdgeAndOrientation
597 //purpose  : 
598 //=======================================================================
599 void IntPolyh_Triangle::SetEdgeAndOrientation(const IntPolyh_Edge& theEdge,
600                                               const Standard_Integer theEdgeIndex)
601 {
602   // Points on the edge - pe1, pe2
603   Standard_Integer pe1 = theEdge.FirstPoint(), pe2 = theEdge.SecondPoint();
604   //
605   // We have points on the triangle - p1, p2 and p3;
606   // And points on the edge - pe1, pe2;
607   // By comparing these points we should define which
608   // edge it is for the triangle and its orientation on it:
609   // e1 = p1->p2;
610   // e2 = p2->p3;
611   // e3 = p3->p1;
612   // In case the order of points on the edge is forward,
613   // the orientation is positive, otherwise it is negative.
614
615   for (Standard_Integer i = 0, i1 = 1; i < 3; ++i, ++i1) {
616     if (i1 > 2) {
617       i1 = 0;
618     }
619     //
620     if (pe1 == myPoints[i] && pe2 == myPoints[i1]) {
621       myEdges[i] = theEdgeIndex;
622       myEdgesOrientations[i] = 1;
623       break;
624     }
625     if (pe1 == myPoints[i1] && pe2 == myPoints[i]) {
626       myEdges[i] = theEdgeIndex;
627       myEdgesOrientations[i] = -1;
628       break;
629     }
630   }
631 }
632
633 //=======================================================================
634 //function : BoundingBox
635 //purpose  : 
636 //=======================================================================
637 const Bnd_Box& IntPolyh_Triangle::BoundingBox(const IntPolyh_ArrayOfPoints& thePoints)
638 {
639   if (myBox.IsVoid()) {
640     const IntPolyh_Point& aP1 = thePoints[myPoints[0]];
641     const IntPolyh_Point& aP2 = thePoints[myPoints[1]];
642     const IntPolyh_Point& aP3 = thePoints[myPoints[2]];
643     myBox.Add(gp_Pnt(aP1.X(), aP1.Y(), aP1.Z()));
644     myBox.Add(gp_Pnt(aP2.X(), aP2.Y(), aP2.Z()));
645     myBox.Add(gp_Pnt(aP3.X(), aP3.Y(), aP3.Z()));
646     myBox.SetGap(myDeflection + Precision::Confusion());
647   }
648   return myBox;
649 }
650 //=======================================================================
651 //function : Dump
652 //purpose  : 
653 //=======================================================================
654 void IntPolyh_Triangle::Dump (const Standard_Integer i) const
655
656   printf("\nTriangle(%3d) : Points %5d %5d %5d Edges %5d %5d %5d deflection: %8f "
657          "intersection possible %8d  intersection: %5d\n",
658          i, myPoints[0], myPoints[1], myPoints[2],
659          myEdges[0], myEdges[1], myEdges[2],
660          myDeflection, (myIsIntersectionPossible ? 1 : 0), (myHasIntersection ? 1 : 0));
661 }