0029859: Coding - GCC compiler warning -Warray-bounds in IntPatch_InterferencePolyhed...
[occt.git] / src / IntPatch / IntPatch_InterferencePolyhedron.cxx
1 // Created on: 1992-11-09
2 // Created by: Didier PIFFAULT
3 // Copyright (c) 1992-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 <Bnd_BoundSortBox.hxx>
19 #include <Bnd_HArray1OfBox.hxx>
20 #include <gp_Pnt.hxx>
21 #include <gp_Vec.hxx>
22 #include <gp_XYZ.hxx>
23 #include <Intf.hxx>
24 #include <Intf_SectionLine.hxx>
25 #include <Intf_SectionPoint.hxx>
26 #include <Intf_SeqOfSectionLine.hxx>
27 #include <Intf_SeqOfSectionPoint.hxx>
28 #include <Intf_SeqOfTangentZone.hxx>
29 #include <Intf_TangentZone.hxx>
30 #include <IntPatch_InterferencePolyhedron.hxx>
31 #include <IntPatch_Polyhedron.hxx>
32 #include <IntPatch_PolyhedronTool.hxx>
33 #include <NCollection_LocalArray.hxx>
34 #include <TColStd_ListIteratorOfListOfInteger.hxx>
35 #include <TColStd_ListOfInteger.hxx>
36
37 static const int Pourcent3[9] = {0, 1, 2, 0, 1, 2, 0, 1, 2};
38
39 //=======================================================================
40 //function : IntPatch_InterferencePolyhedron
41 //purpose  : Empty constructor.
42 //=======================================================================
43
44 IntPatch_InterferencePolyhedron::IntPatch_InterferencePolyhedron  ()
45 : Intf_Interference(Standard_False)
46 {}
47
48 //=======================================================================
49 //function : IntPatch_InterferencePolyhedron
50 //purpose  : 
51 //=======================================================================
52
53 IntPatch_InterferencePolyhedron::IntPatch_InterferencePolyhedron 
54   (const IntPatch_Polyhedron& FirstPol, const IntPatch_Polyhedron& SeconPol)
55 : Intf_Interference(Standard_False)
56 {
57   if (!IntPatch_PolyhedronTool::Bounding(FirstPol).IsOut
58       (IntPatch_PolyhedronTool::Bounding(SeconPol))) {
59     Tolerance=IntPatch_PolyhedronTool::DeflectionOverEstimation(FirstPol)+
60               IntPatch_PolyhedronTool::DeflectionOverEstimation(SeconPol);
61     if (Tolerance==0.)
62       Tolerance=Epsilon(1000.);
63     Interference(FirstPol, SeconPol);
64   }
65 }
66
67 //=======================================================================
68 //function : IntPatch_InterferencePolyhedron
69 //purpose  : 
70 //=======================================================================
71
72 IntPatch_InterferencePolyhedron::IntPatch_InterferencePolyhedron 
73   (const IntPatch_Polyhedron& Objet)
74 : Intf_Interference(Standard_True)
75 {
76   Tolerance=IntPatch_PolyhedronTool::DeflectionOverEstimation(Objet)*2;
77   if (Tolerance==0.)
78     Tolerance=Epsilon(1000.);
79   Interference(Objet,Objet); //-- lbr le 5 juillet 96
80  }
81
82
83 //=======================================================================
84 //function : Perform 
85 //purpose  : 
86 //=======================================================================
87
88 void IntPatch_InterferencePolyhedron::Perform 
89   (const IntPatch_Polyhedron& FirstPol, const IntPatch_Polyhedron& SeconPol)
90 {
91   SelfInterference(Standard_False);
92   if (!IntPatch_PolyhedronTool::Bounding(FirstPol).IsOut
93       (IntPatch_PolyhedronTool::Bounding(SeconPol))) {
94     Tolerance=IntPatch_PolyhedronTool::DeflectionOverEstimation(FirstPol)+
95               IntPatch_PolyhedronTool::DeflectionOverEstimation(SeconPol);
96     if (Tolerance==0.)
97       Tolerance=Epsilon(1000.);
98     Interference(FirstPol, SeconPol);
99   }
100 }
101
102 //=======================================================================
103 //function : Perform
104 //purpose  : 
105 //=======================================================================
106
107 void IntPatch_InterferencePolyhedron::Perform  
108   (const IntPatch_Polyhedron& Objet)
109 {
110   SelfInterference(Standard_True);
111   Tolerance=IntPatch_PolyhedronTool::DeflectionOverEstimation(Objet)*2;
112   if (Tolerance==0.)
113     Tolerance=Epsilon(1000.);
114   Interference(Objet);
115 }
116
117
118 //=======================================================================
119 //function : Interference
120 //purpose  : 
121 //=======================================================================
122
123 void IntPatch_InterferencePolyhedron::Interference 
124   (const IntPatch_Polyhedron&)
125 {}
126
127 void IntPatch_InterferencePolyhedron::Interference 
128   (const IntPatch_Polyhedron& FirstPol, const IntPatch_Polyhedron& SeconPol)
129 {
130   Standard_Boolean  gridOnFirst=Standard_True;
131   Standard_Integer  NbTrianglesFirstPol  = IntPatch_PolyhedronTool::NbTriangles(FirstPol);
132   Standard_Integer  NbTrianglesSecondPol = IntPatch_PolyhedronTool::NbTriangles(SeconPol);  
133   Standard_Integer iFirst, iSecon;
134
135   //------------------------------------------------------------------------------------------
136   //-- the same number of triangles it is necessary to test better on
137   //-- the size of boxes.
138   //--
139   //-- the second is chosen if nbTri1 > 2*nbTri2   or   if VolBoit1 > 2*VolBoit2
140   //--
141   //--if (!SelfIntf && NbTrianglesFirstPol>NbTrianglesSecondPol)
142   //--  gridOnFirst=Standard_False;
143   
144   if(!SelfIntf) { 
145     if(NbTrianglesFirstPol > NbTrianglesSecondPol+NbTrianglesSecondPol) gridOnFirst=Standard_False;
146
147     Standard_Real vol1,vol2,Xmin, Ymin, Zmin, Xmax, Ymax, Zmax;
148     IntPatch_PolyhedronTool::Bounding(FirstPol).Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
149     vol1 = (Xmax-Xmin)*(Ymax-Ymin)*(Zmax-Zmin);
150
151     IntPatch_PolyhedronTool::Bounding(SeconPol).Get(Xmin, Ymin, Zmin, Xmax, Ymax, Zmax);
152     vol2 = (Xmax-Xmin)*(Ymax-Ymin)*(Zmax-Zmin);
153     
154     if(vol1> 8.0*vol2)  gridOnFirst=Standard_False;
155   }
156
157
158   if (gridOnFirst) {
159     Bnd_BoundSortBox TheGridFirst;
160     TheGridFirst.Initialize(IntPatch_PolyhedronTool::Bounding(FirstPol),
161                             IntPatch_PolyhedronTool::ComponentsBounding(FirstPol));
162
163     for (iSecon=1; iSecon<=NbTrianglesSecondPol; iSecon++) {
164
165       TColStd_ListIteratorOfListOfInteger iLoI(TheGridFirst.Compare
166         (IntPatch_PolyhedronTool::ComponentsBounding(SeconPol)->Value(iSecon)));
167       while (iLoI.More()) {
168         iFirst=iLoI.Value();
169         if (SelfIntf) {
170           if (iFirst<iSecon)
171             Intersect(iFirst, FirstPol, iSecon, SeconPol);
172         }
173         else
174           Intersect(iFirst, FirstPol, iSecon, SeconPol);
175         iLoI.Next();
176       }
177     }
178   }
179
180   else {
181     Bnd_BoundSortBox TheGridSecond;
182     TheGridSecond.Initialize(IntPatch_PolyhedronTool::Bounding(SeconPol), 
183                              IntPatch_PolyhedronTool::ComponentsBounding(SeconPol));
184
185     for (iFirst=1; iFirst<=NbTrianglesFirstPol; iFirst++) {
186       TColStd_ListIteratorOfListOfInteger
187         iLoI(TheGridSecond.Compare
188              (IntPatch_PolyhedronTool::ComponentsBounding(FirstPol)->Value(iFirst)));
189       
190       while (iLoI.More()) {
191         iSecon=iLoI.Value();
192         if (SelfIntf) {
193           if (iFirst<iSecon)
194             Intersect(iFirst, FirstPol, iSecon, SeconPol);
195         }
196         else
197           Intersect(iFirst, FirstPol, iSecon, SeconPol);
198         iLoI.Next();
199       }
200     }
201   }
202 }
203
204
205 //=======================================================================
206 //function : Intersect
207 //purpose  : Intersection of two triangles issue from two Polyhedron.
208 //=======================================================================
209
210 void IntPatch_InterferencePolyhedron::Intersect 
211 (const Standard_Integer Tri1, const IntPatch_Polyhedron& FirstPol,
212  const Standard_Integer Tri2, const IntPatch_Polyhedron& SeconPol)
213 {
214   IntPatch_PolyhedronTool::Triangle(FirstPol, Tri1,OI[0],OI[1],OI[2]);
215   IntPatch_PolyhedronTool::Triangle(SeconPol, Tri2,TI[0],TI[1],TI[2]);
216   
217   // If there is an intersection of a polyhedron with itself, the
218   // intersections are excluded 
219   // from a triangle with connected triangles :
220   
221   if (SelfIntf) {
222     if (OI[0]==TI[0] || OI[0]==TI[1] || OI[0]==TI[2] ||
223         OI[1]==TI[0] || OI[1]==TI[1] || OI[1]==TI[2] ||
224         OI[2]==TI[0] || OI[2]==TI[1] || OI[2]==TI[2] ) return;
225   }
226   
227   // The precision of intersections includes two values ;
228   
229   // - Tolerance :This value allows detecting potential 
230   //              intersections in all cases.  The value should be the
231     //            sum of upper bounds of tops pof two polyhedrons.
232   
233   // - floatGap : This value is the actual precision of calculation 
234   //              of line of section.Its value is very small, it
235   //              allows having the same behaviour for
236   //              geometry tests as for the values used.
237   
238   Standard_Real floatGap=1e-13 ; //-- Epsilon(1000.);
239   
240   
241   // Equation of the triangle plane of the objet 
242   gp_XYZ ONor; // Normal vector.
243   Standard_Real Odp;    // Polar Distance.
244   Intf::PlaneEquation(IntPatch_PolyhedronTool::Point(FirstPol, OI[0]),
245                       IntPatch_PolyhedronTool::Point(FirstPol, OI[1]),
246                       IntPatch_PolyhedronTool::Point(FirstPol, OI[2]),
247                       ONor, Odp);
248
249   
250 // Equation of the triangle plane of the tool
251   gp_XYZ TNor; // Normal vector.
252   Standard_Real Tdp;    // Polar distance.
253   Intf::PlaneEquation(IntPatch_PolyhedronTool::Point(SeconPol, TI[0]),
254                       IntPatch_PolyhedronTool::Point(SeconPol, TI[1]),
255                       IntPatch_PolyhedronTool::Point(SeconPol, TI[2]),
256                       TNor, Tdp);
257
258
259 // Scalar product of two normalized vectors -> cosinus of the angle
260   Incidence= Abs(TNor*ONor);
261
262 // Distance of the plane of the triangle from the object by three points of SeconPol
263   Standard_Real dfOpT[3];
264   dfOpT[0]=ONor*(IntPatch_PolyhedronTool::Point(SeconPol, TI[0]).XYZ())-Odp;
265   dfOpT[1]=ONor*(IntPatch_PolyhedronTool::Point(SeconPol, TI[1]).XYZ())-Odp;
266   dfOpT[2]=ONor*(IntPatch_PolyhedronTool::Point(SeconPol, TI[2]).XYZ())-Odp;
267
268 // Distance of the plane of the triangle from the tool by three points of FirstPol
269   Standard_Real dpOfT[3];
270   dpOfT[0]=TNor*(IntPatch_PolyhedronTool::Point(FirstPol, OI[0]).XYZ())-Tdp;
271   dpOfT[1]=TNor*(IntPatch_PolyhedronTool::Point(FirstPol, OI[1]).XYZ())-Tdp;
272   dpOfT[2]=TNor*(IntPatch_PolyhedronTool::Point(FirstPol, OI[2]).XYZ())-Tdp;
273
274 // Values defining the couple of triangle dpOpT, dpOeT, deOpT
275   CoupleCharacteristics(FirstPol, SeconPol);
276
277 // If three  points  of the triangle of <SeconPol> are in the plane of the
278 // triangle of <Obje> within <Tolerance> the eventual tangency zone is found.
279
280   Intf_TangentZone TheTZ;
281   if ((Abs(dfOpT[0])<=Tolerance && 
282        Abs(dfOpT[1])<=Tolerance &&
283        Abs(dfOpT[2])<=Tolerance)  &&
284       (Abs(dpOfT[0])<=Tolerance && 
285        Abs(dpOfT[1])<=Tolerance &&
286        Abs(dpOfT[2])<=Tolerance) &&
287       (Abs(dfOpT[0]+dfOpT[1]+dfOpT[2])!=
288        Abs(dfOpT[0])+Abs(dfOpT[1])+Abs(dfOpT[2])) &&
289       (Abs(dpOfT[0]+dpOfT[1]+dpOfT[2])!=
290        Abs(dpOfT[0])+Abs(dpOfT[1])+Abs(dpOfT[2]))){
291
292     if (TangentZoneValue(TheTZ, FirstPol, Tri1, SeconPol, Tri2))
293     {
294       if (!Insert(TheTZ)) myTZones.Append(TheTZ);
295     }
296   }
297
298 // Otherwise line of section is calculated:
299   else {
300     Standard_Integer iObj, iToo;
301
302     // Zone de stockage des resultats :
303     Standard_Integer nbpiOT=0;
304     Standard_Integer nbpiO=0;
305     Standard_Integer nbpiT=0;
306     Intf_SeqOfSectionPoint piOT;
307     Standard_Real parO[3];
308     Standard_Real parT[3];
309
310     // Indicateurs d arete touchee 
311     Standard_Integer edOT[3];
312     Standard_Integer edTT[3];
313
314     // Initializations
315     //--for (iObj=0; iObj<3; iObj++) {
316     //  parO[iObj]=parT[iObj]=-1.;
317     //  edOT[iObj]=edTT[iObj]=1;
318     //--}
319     parO[0]=parT[0]=parO[1]=parT[1]=parO[2]=parT[2]=-1.0;
320     edOT[0]=edTT[0]=edOT[1]=edTT[1]=edOT[2]=edTT[2]= 1;
321
322     // Singularite VERTEX VERTEX
323     //for (iObj=0; iObj<3; iObj++) {
324     //  for (iToo=0; iToo<3; iToo++) {
325     //  if (dpOpT[iObj][iToo] <= floatGap) {
326     //    piOT.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(FirstPol, OI[iObj]),
327     //                                  Intf_VERTEX, OI[iObj], 0, 0.,
328     //                                  Intf_VERTEX, TI[iToo], 0, 0.,
329     //                                  Incidence));
330     //    parO[iObj]=0.; 
331     //    parT[iToo]=0.; 
332     //    edOT[Pourcent3[iObj+2]]=0; edOT[iObj]=0;
333     //    edTT[Pourcent3[iToo+2]]=0; edTT[iToo]=0;
334     //    nbpiOT++; nbpiO++; nbpiT++;
335     //  }
336     // }
337     //}
338     //---------------------------->
339     for (iObj=0; iObj<3; iObj++) {
340       for (iToo=0; iToo<3; iToo++) {
341         if (dpOpT[iObj][iToo] <= floatGap) {
342           piOT.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(FirstPol, OI[iObj]),
343                                         Intf_VERTEX, OI[iObj], 0, 0.,
344                                         Intf_VERTEX, TI[iToo], 0, 0.,
345                                         Incidence));
346           parO[iObj]=parT[iToo]=0.0;
347           edOT[Pourcent3[iObj+2]]=edOT[iObj]=edTT[Pourcent3[iToo+2]]=edTT[iToo]=0;
348           nbpiOT++; nbpiO++; nbpiT++;
349         }
350       }
351     }
352       
353       
354       // Singularite VERTEX EDGE
355     Standard_Integer inext, jnext;
356     for (iObj=0; iObj<3; iObj++) {
357       if (parO[iObj]==-1.) {
358         for (iToo=0; iToo<3; iToo++) {
359           inext=Pourcent3[iToo+1];
360           if (edTT[iToo]==1) {
361             if (dpOeT[iObj][iToo] <= floatGap && dpOeT[iObj][iToo]>=-floatGap ) {
362               if ((dpOpT[iObj][iToo]+dpOpT[iObj][inext])<vtt[iToo].Modulus()) {
363                 parT[iToo]=dpOpT[iObj][iToo]/(dpOpT[iObj][iToo]+
364                                               dpOpT[iObj][inext]);
365                 if (TI[iToo]>TI[inext]) parT[iToo]=1.-parT[iToo];
366                 piOT.Append(Intf_SectionPoint
367                             (IntPatch_PolyhedronTool::Point(FirstPol, OI[iObj]),
368                              Intf_VERTEX, OI[iObj], 0, 0.,
369                              Intf_EDGE, Min(TI[iToo],TI[inext]),
370                                         Max(TI[iToo],TI[inext]), parT[iToo],
371                              Incidence));
372                 parO[iObj]=0.; 
373                 edOT[Pourcent3[iObj+2]]=0; edOT[iObj]=0;
374                 edTT[iToo]=0;
375                 nbpiOT++;  nbpiO++; nbpiT++;
376               }
377             }
378           }
379         }
380       }
381     }
382
383     // Singularite EDGE VERTEX
384     for (iToo=0; iToo<3; iToo++) {
385       if (parT[iToo]==-1.) {
386         for (iObj=0; iObj<3; iObj++) {
387           inext=Pourcent3[iObj+1];
388           if (edOT[iObj]==1) {
389             if (Abs(deOpT[iObj][iToo]) <= floatGap) {
390               if ((dpOpT[iObj][iToo]+dpOpT[inext][iToo])<voo[iObj].Modulus()){
391                 parO[iObj]=dpOpT[iObj][iToo]/(dpOpT[iObj][iToo]+
392                                               dpOpT[inext][iToo]); 
393                 if (OI[iObj]>OI[inext]) parO[iObj]=1.-parO[iObj];
394                 piOT.Append(Intf_SectionPoint
395                             (IntPatch_PolyhedronTool::Point(SeconPol, TI[iToo]),
396                              Intf_EDGE, Min(OI[iObj],OI[inext]),
397                                         Max(OI[iObj],OI[inext]), parO[iObj],
398                              Intf_VERTEX, TI[iToo], 0, 0.,
399                              Incidence));
400                 parT[iToo]=0.; 
401                 edOT[iObj]=edTT[Pourcent3[iToo+2]]=edTT[iToo]=0;
402                 nbpiOT++;  nbpiO++; nbpiT++;
403               }
404             }
405           }
406         }
407       }
408     }
409
410     // Singularite FACE VERTEX
411     for (iToo=0; iToo<3; iToo++) {
412       if (parT[iToo]!=0.) {
413         if (Abs(dfOpT[iToo]) <= floatGap) {
414           piOT.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(SeconPol, TI[iToo]),
415                                         Intf_FACE,   Tri1,  0, 0.,
416                                         Intf_VERTEX, TI[iToo], 0, 0.,
417                                         Incidence));
418           parT[iToo]=0.;
419           edTT[Pourcent3[iToo+2]]=edTT[iToo]=0;
420           nbpiOT++; nbpiT++;
421         }
422       }
423     }
424
425     // Singularite VERTEX FACE
426     for (iObj=0; iObj<3; iObj++) {
427       if (parO[iObj]!=0.) {
428         if (Abs(dpOfT[iObj]) <= floatGap) {
429           piOT.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(FirstPol, OI[iObj]),
430                                         Intf_VERTEX, OI[iObj], 0, 0.,
431                                         Intf_FACE,   Tri2,  0, 0.,
432                                         Incidence));
433           parO[iObj]=0.;
434           edOT[Pourcent3[iObj+2]]=edOT[iObj]=0;
435           nbpiOT++; nbpiO++;
436         }
437       }
438     }
439     
440     // Singularite EDGE EDGE
441     gp_Pnt piO;
442     gp_XYZ piT;
443     Standard_Real lg;
444     for (iObj=0; iObj<3; iObj++) {
445       inext=Pourcent3[iObj+1];
446       if (edOT[iObj]==1 && (dpOfT[iObj]*dpOfT[inext])<0.) {
447         lg=dpOfT[iObj]/(dpOfT[iObj]-dpOfT[inext]);
448         if (lg>0. && lg<1.) {
449           for (iToo=0; iToo<3; iToo++) {
450             jnext=Pourcent3[iToo+1];
451             if (edTT[iToo]==1 && (dfOpT[iToo]*dfOpT[jnext])<0.) {
452               lg=dfOpT[iToo]/(dfOpT[iToo]-dfOpT[jnext]);
453               if (lg>0. && lg<1.) {
454                 Standard_Boolean Pb=Standard_False;
455                 if (OI[iObj]>OI[inext]) {
456                   Standard_Real div=(dpOeT[inext][iToo]-dpOeT[iObj][iToo]);
457                   if(div>floatGap || div<-floatGap) { 
458                     parO[iObj]=dpOeT[inext][iToo]/div;
459                     piO=(IntPatch_PolyhedronTool::Point(FirstPol,OI[inext]).XYZ()) +
460                       (voo[iObj].Reversed()*parO[iObj]);
461                   }
462                   else 
463                     Pb=Standard_True;
464                 }
465                 else {
466                   Standard_Real div = dpOeT[iObj][iToo]-dpOeT[inext][iToo];
467                   if(div>floatGap || div<-floatGap) { 
468                     parO[iObj]=dpOeT[iObj][iToo]/
469                       (dpOeT[iObj][iToo]-dpOeT[inext][iToo]);;
470                     piO=(IntPatch_PolyhedronTool::Point(FirstPol,OI[iObj]).XYZ()) +
471                       (voo[iObj]*parO[iObj]);
472                   }
473                   else 
474                     Pb=Standard_True;
475                 }
476                 if (TI[iToo]>TI[jnext]) {
477                   Standard_Real div=(deOpT[iObj][jnext]-deOpT[iObj][iToo]);
478                   if(div>floatGap || div<-floatGap) { 
479                     parT[iToo]=deOpT[iObj][jnext]/div;
480                     piT=(IntPatch_PolyhedronTool::Point(SeconPol,TI[jnext]).XYZ()) +
481                       (vtt[iToo].Reversed()*parT[iToo]);
482                   }
483                   else 
484                     Pb=Standard_True;
485                 }
486                 else {
487                   Standard_Real div=(deOpT[iObj][iToo]-deOpT[iObj][jnext]);
488                   if(div>floatGap || div<-floatGap) {  
489                     parT[iToo]=deOpT[iObj][iToo]/div;               
490                     piT=(IntPatch_PolyhedronTool::Point(SeconPol,TI[iToo]).XYZ()) +
491                       (vtt[iToo]*parT[iToo]);
492                   }
493                   else 
494                     Pb=Standard_True;
495                 }
496                 if(Pb==Standard_False) { 
497                   piT-=piO.XYZ();
498                   lg=piT.Modulus();
499                   if (lg <= floatGap){
500                     piOT.Append(Intf_SectionPoint
501                                 (piO,
502                                  Intf_EDGE, Min(OI[iObj],OI[inext]),
503                                  Max(OI[iObj],OI[inext]), parO[iObj],
504                                  Intf_EDGE, Min(TI[iToo],TI[jnext]), 
505                                  Max(TI[iToo],TI[jnext]), parT[iToo],
506                                  Incidence));
507                     edOT[iObj]=edTT[iToo]=0;
508                     nbpiOT++;  nbpiO++; nbpiT++;
509                   }
510                 }
511               }
512             }
513           }
514         }
515       }
516     }
517
518     // Intersection EDGE FACE
519     for (iObj=0; iObj<3; iObj++) {
520       inext=Pourcent3[iObj+1];
521       if (edOT[iObj]==1 && (dpOfT[iObj]*dpOfT[inext])<0.) {
522         lg=dpOfT[iObj]/(dpOfT[iObj]-dpOfT[inext]);
523         if (lg>0. && lg<1.) {
524           parO[iObj]=lg;
525           piO=(IntPatch_PolyhedronTool::Point(FirstPol, OI[iObj]).XYZ())+
526             (voo[iObj]*parO[iObj]);
527           if (OI[iObj]>OI[inext]) parO[iObj]=1.-parO[iObj];
528           piOT.Append(
529             Intf_SectionPoint (piO,
530                                Intf_EDGE, Min(OI[iObj],OI[inext]),
531                                           Max(OI[iObj],OI[inext]), parO[iObj],
532                                Intf_FACE, Tri2, 0, 0., Incidence));
533           nbpiOT++; nbpiO++;
534         }
535       }
536     }
537
538     // Intersection FACE EDGE
539     for (iToo=0; iToo<3; iToo++) {
540       jnext=Pourcent3[iToo+1];
541       if (edTT[iToo]==1 && (dfOpT[iToo]*dfOpT[jnext])<0.) {
542         lg=dfOpT[iToo]/(dfOpT[iToo]-dfOpT[jnext]);
543         if (lg>0. && lg<1.) {
544           parT[iToo]=lg;
545           piO=(IntPatch_PolyhedronTool::Point(SeconPol, TI[iToo]).XYZ())+
546                (vtt[iToo]*parT[iToo]);
547           if (TI[iToo]>TI[jnext]) parT[iToo]=1.-parT[iToo];
548           piOT.Append(Intf_SectionPoint
549             (piO,
550              Intf_FACE, Tri1, 0, 0.,
551              Intf_EDGE, Min(TI[iToo],TI[jnext]),
552                         Max(TI[iToo],TI[jnext]), parT[iToo],
553              Incidence));
554           nbpiOT++; nbpiT++;
555         }
556       }
557     }
558     
559     NCollection_LocalArray <Standard_Integer> id(Max(nbpiOT, 4));
560
561     Standard_Integer ideb=-1;
562     Standard_Integer ifin=-2;
563
564     if (nbpiOT>1) {
565
566 // Sort the <nbpiOT> sections points along the intersection beetween the
567 // two triangles :
568
569       gp_XYZ dir=ONor^TNor;
570       NCollection_LocalArray <Standard_Real> d(nbpiOT);
571       Standard_Integer iPi, iPs;
572       for (iPi=0; iPi<nbpiOT; iPi++) {
573         d[iPi]=dir*piOT(iPi+1).Pnt().XYZ();
574       }
575
576       Standard_Integer di;
577       id[0]=0;
578       for (iPi=1; iPi<nbpiOT; iPi++) {
579         id[iPi]=iPi;
580         for (iPs=iPi-1; iPs>=0; iPs--) {
581           if (d[id[iPs]] > d[id[iPs+1]]) {
582             di=id[iPs+1];
583             id[iPs+1]=id[iPs];
584             id[iPs]=di;
585           }
586           else break;
587         }
588       }
589     }
590
591 // Possibility of line of section :
592
593     if (nbpiO==2 && nbpiT==2) {
594
595       // In the case when an edge is in the plane of the other triangle
596       // it is necessary to check if it has not been already processed
597       // on a connected triangle :
598
599     // Pour l objet :
600       Standard_Integer pivo=-1;
601       Standard_Integer pedg=-1;
602       if (parO[0]==0.) {
603         pivo=0;
604         if      (parO[1]==0.) pedg=1;
605         else if (parO[2]==0.) pedg=2;
606       }
607       else if (parO[1]==0.) {
608         pivo=1;
609         if (parO[2]==0.) pedg=2;
610       }
611       if (pivo>=0 && pedg>=0) {
612         IntPatch_PolyhedronTool::TriConnex(FirstPol, Tri1,OI[pivo],OI[pedg],pivo,pedg);
613         if (pivo > Tri1) { 
614           nbpiOT=0;
615           ideb=-1;        // On a deja trouve celle ci
616           ifin=-2;
617         }
618       }
619
620     // For the tool :
621       pivo=-1;
622       pedg=-1;
623       if (parT[0]==0.) {
624         pivo=0;
625         if      (parT[1]==0.) pedg=1;
626         else if (parT[2]==0.) pedg=2;
627       }
628       else if (parT[1]==0.) {
629         pivo=1;
630         if (parT[2]==0.) pedg=2;
631       }
632       if (pivo>=0 && pedg>=0) {
633         IntPatch_PolyhedronTool::TriConnex(SeconPol, Tri2,TI[pivo],TI[pedg],pivo,pedg);
634         if (pivo > Tri2) {
635           nbpiOT=0;
636           ideb=-1;        // It has been already found
637           ifin=-2;
638         }
639       }
640
641       if (nbpiOT>0) {
642
643 // If there is a covering up : insert the section  line in  the existent
644 // list or create a new section line :
645
646         if (piOT(id[0]+1).TypeOnFirst()==Intf_FACE) {
647           if (piOT(id[1]+1).TypeOnFirst()==Intf_FACE) {
648             ideb=-id[0]-1;        // No line of section possible
649             ifin=-id[1]-1;        // 
650           }
651           else if (piOT(id[1]+1).TypeOnSecond()!=Intf_FACE) {
652             ideb=id[1];     // No line of section possible
653             ifin=id[1];     // only a pointersec
654           }
655           else if (nbpiOT>=3) {
656             ideb=id[1];     // Retrieve 2 segments of section
657             ifin=id[2];     //
658           }
659           else {
660             ideb=-999;        // No line of section possible
661             ifin=-999;
662           }
663         }
664         else  if (piOT(id[0]+1).TypeOnSecond()==Intf_FACE) {
665           if (piOT(id[1]+1).TypeOnSecond()==Intf_FACE) {
666             ideb=-id[0]-1;        // No line of section possible
667             ifin=-id[1]-1;        // 
668           }
669           else if (piOT(id[1]+1).TypeOnFirst()!=Intf_FACE) {
670             ideb=id[1];     // No line of section possible
671             ifin=id[1];     // only a pointersec
672           }
673           else if (nbpiOT>=3) {
674             ideb=id[1];     // Recouvrement des 2 segments de section
675             ifin=id[2];     //
676           }
677           else {
678             ideb=-999;        // No line of section possible
679             ifin=-999;
680           }
681         }
682
683         else { // Singularity on the first point there is only two or
684           ideb=id[0];   // three pointersec, so the first is a solution
685           ifin=id[1];   // and the second too.
686         }
687       }
688
689
690 // Insertion of the segment found in the existing section lines :
691
692       if(ideb<0) { 
693         if(ifin<0) {
694           if(ideb!=-999) { 
695             //static unsigned nisp=0;
696             Standard_Real d=piOT(-ideb).Pnt().Distance(piOT(-ifin).Pnt());        
697             if(d<Tolerance) { 
698               Insert(piOT(-ideb), piOT(-ifin));       
699               //-- cout<<"Insertion Point IntPatch_InterferencePolyhedron 1,2 d="<<d<<" Tol="<<Tolerance<<" num:"<<++nisp<<endl;
700               //-- piOT(-ideb).Dump(1);  piOT(-ifin).Dump(0);
701               //-- cout<<"point p"<<++nisp<<" "<<piOT(-ideb).Pnt().X()<<" "<<piOT(-ideb).Pnt().Y()<<" "<<piOT(-ideb).Pnt().Z()<<endl;
702             }
703             else { 
704               //-- cout<<"Insertion Point IntPatch_InterferencePolyhedron 1,2 d="<<d<<" Tol="<<Tolerance<<" NON INSERE "<<endl;
705             }
706           }
707         }
708       }
709       else if (ideb>=0) {
710         if (ideb!=ifin) { 
711           Insert(piOT(ideb+1), piOT(ifin+1));
712           
713           //    else
714           //     un pointersec : It is necessary to check if it has not been already found 
715           //                       and if not insert it in the list.     
716           //                       Attention! It is necessary to check
717           //                       for each new segment if a point is in the list
718           //                       and in this case remove it from the list.
719         }
720       }
721     }
722   }
723 }
724
725
726 //=======================================================================
727 //function : TangentZoneValue
728 //purpose  : 
729 //=======================================================================
730
731 Standard_Boolean IntPatch_InterferencePolyhedron::TangentZoneValue
732   (Intf_TangentZone& TheTZ,
733    const IntPatch_Polyhedron& FirstPol,
734    const Standard_Integer Tri1,
735    const IntPatch_Polyhedron& SeconPol,
736    const Standard_Integer Tri2) const
737 {
738   // Potential tangent Zone !
739   // ------------------------
740
741   Standard_Boolean finished=Standard_False;
742   Standard_Integer nob, nou, nob2, nou2;
743   Standard_Real par;
744
745   Intf_PIType tOP[3];
746   Intf_PIType tTP[3];
747   for (nou=0; nou<3; nou++) {
748     tOP[nou]= Intf_EXTERNAL;
749     tTP[nou]= Intf_EXTERNAL;
750   }
751
752   Standard_Integer nbpInt=0;
753   Intf_SeqOfSectionPoint Tpi;
754
755   // Compute the positions of the points of <Tri1> in the triangle <Tri2>.
756   for (nob=0; nob<=2; nob++) {
757     nob2=Pourcent3[nob+1];
758     for (nou=0; nou<=2; nou++) {
759       nou2=Pourcent3[nou+1];
760       if (dpOpT[nob][nou]<=Tolerance) {
761         Tpi.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(FirstPol, OI[nob]), 
762                                      Intf_VERTEX, OI[nob], 0, 0., 
763                                      Intf_VERTEX, TI[nou], 0, 0.,
764                                      1.));
765         tOP[nob]=Intf_VERTEX;
766         tTP[nou]=Intf_VERTEX;
767         nbpInt++;
768         break;
769       }
770       else if (Abs(dpOeT[nob][nou])<=Tolerance) {
771         if (dpOpT[nob][nou]+dpOpT[nob][nou2]<vtt[nou].Modulus()) {
772           par=dpOpT[nob][nou]/(dpOpT[nob][nou]+dpOpT[nob][nou2]); 
773           if (TI[nou]>TI[nou2]) par=1.-par;
774           Tpi.Append(Intf_SectionPoint (IntPatch_PolyhedronTool::Point(FirstPol, OI[nob]), 
775                                         Intf_VERTEX, OI[nob], 0, 0., 
776                                         Intf_EDGE, Min(TI[nou], TI[nou2]),
777                                         Max(TI[nou], TI[nou2]), par,
778                                         1.));
779           tOP[nob]=Intf_EDGE;
780           nbpInt++;
781           break;
782         }
783       }
784     }
785     if (tOP[nob]==Intf_EXTERNAL) {
786       if (Intf::Contain(IntPatch_PolyhedronTool::Point(SeconPol, TI[0]),
787                         IntPatch_PolyhedronTool::Point(SeconPol, TI[1]),
788                         IntPatch_PolyhedronTool::Point(SeconPol, TI[2]),
789                         IntPatch_PolyhedronTool::Point(FirstPol, OI[nob]))) {
790         Tpi.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(FirstPol, OI[nob]),
791                                      Intf_VERTEX, OI[nob],  0, 0., 
792                                      Intf_FACE,   Tri2, 0, 0.,
793                                      1.));
794         tOP[nob]=Intf_FACE;
795         nbpInt++;
796       }
797     }
798   }
799
800   // If the three points of <Tri1> are in <Tri2> the triangle Tri1 is 
801   // itself the tangent zone else compute the positions of the points
802   // of <Tri2> in <Tri1>.
803   if (nbpInt < 3) {
804     for (nou=0; nou<=2; nou++) {
805       nou2=Pourcent3[nou+1];
806       if (tTP[nou]==Intf_EXTERNAL) {
807         for (nob=0; nob<=2; nob++) {
808           nob2=Pourcent3[nob+1];
809           if (Abs(deOpT[nob][nou])<=Tolerance) {
810             if (dpOpT[nob][nou]+dpOpT[nob2][nou]<voo[nob].Modulus()) {
811               par=dpOpT[nob][nou]/(dpOpT[nob][nou]+dpOpT[nob2][nou]); 
812               if (OI[nob]>OI[nob2]) par=1.-par;
813               Tpi.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(SeconPol,TI[nou]), 
814                                            Intf_EDGE, Min(OI[nob], OI[nob2]),
815                                            Max(OI[nob], OI[nob2]), par, 
816                                            Intf_VERTEX, TI[nou], 0, 0., 1.));
817               tTP[nou]=Intf_EDGE;
818               nbpInt++;
819               break;
820             }
821           }
822         }
823         if (tTP[nou]==Intf_EXTERNAL) {
824           if (Intf::Contain(IntPatch_PolyhedronTool::Point(FirstPol, OI[0]),
825                             IntPatch_PolyhedronTool::Point(FirstPol, OI[1]),
826                             IntPatch_PolyhedronTool::Point(FirstPol, OI[2]),
827                             IntPatch_PolyhedronTool::Point(SeconPol, TI[nou]))) {
828             Tpi.Append(Intf_SectionPoint(IntPatch_PolyhedronTool::Point(SeconPol, TI[nou]),
829                                          Intf_FACE,   Tri1, 0, 0.,
830                                          Intf_VERTEX, TI[nou], 0, 0., 
831                                          1.));
832             tTP[nou]=Intf_FACE;
833             nbpInt++;
834           }
835         }
836       }
837     }
838     if (tTP[0]!=Intf_EXTERNAL && 
839         tTP[1]!=Intf_EXTERNAL && 
840         tTP[2]!=Intf_EXTERNAL)
841       finished=Standard_True;
842   }
843   else
844     finished=Standard_True;
845
846   // Insertion of the points of intersection in the zone of tangency :
847   for (nob=1; nob<=nbpInt; nob++) 
848     TheTZ.Append(Tpi(nob));
849
850   if (!finished) {
851     // If one of the triangles is not in the zone of tangency, it is necessary to find
852     // the points of intersection edge/edge :
853
854     // Last indexes are not used.
855     // Arrays are increased to eliminate gcc warning.
856     Standard_Real parO[10], parT[10];
857     Standard_Integer nbNoInserted=0;
858     Standard_Integer piToInsert[10];
859
860     for (nob=0; nob<3; nob++) {
861       //processing of the object segment P[nob], P[nob+1]
862       nob2=Pourcent3[nob+1];
863
864       for (nou=0; nou<3; nou++) {
865         //processing of the segment of the tool P[nou], P[nou+1]
866         nou2=Pourcent3[nou+1];
867         
868         if (dpOeT[nob][nou]*dpOeT[nob2][nou]<0. &&
869             deOpT[nob][nou]*deOpT[nob][nou2]<0.) {
870
871           if (nbpInt>=5) {
872             break;
873           }
874           else {
875             parO[nbpInt]=dpOeT[nob][nou]/(dpOeT[nob][nou]-dpOeT[nob2][nou]);
876             parT[nbpInt]=deOpT[nob][nou]/(deOpT[nob][nou]-deOpT[nob][nou2]);
877             gp_Pnt lepi=IntPatch_PolyhedronTool::Point(SeconPol, TI[nou]).Translated
878               (gp_Vec(vtt[nou]*parT[nbpInt]));
879             if (OI[nob]>OI[nob2]) parO[nbpInt]=1.-parO[nbpInt];
880             if (TI[nou]>TI[nou2]) parT[nbpInt]=1.-parT[nbpInt];
881             Tpi.Append(Intf_SectionPoint(lepi,
882                                          Intf_EDGE, Min(OI[nob],OI[nob2]),
883                                          Max(OI[nob],OI[nob2]), parO[nbpInt],
884                                          Intf_EDGE, Min(TI[nou],TI[nou2]),
885                                          Max(TI[nou],TI[nou2]), parT[nbpInt],
886                                          Incidence));
887             nbpInt++;
888             if (!TheTZ.Insert(Tpi(nbpInt))) {
889               piToInsert[nbNoInserted]=nbpInt;
890               nbNoInserted++;
891             }
892           }
893         }
894       }
895       if (nbpInt>=5) break; // Number of pi passed in TZ !
896     }
897     nob=nbNoInserted-1;
898     while (nob>=0) {
899       while (!TheTZ.Insert(Tpi(piToInsert[nob]))) {
900         nob--;
901         if (nob<0) break;
902       }
903       if (nob>=0) {
904         nbNoInserted--;
905         while (nob < nbNoInserted) {
906           piToInsert[nob]=piToInsert[nob+1];
907           nob++;
908         }
909         nob=nbNoInserted-1;
910       }
911     }
912     if (nbNoInserted>0) {
913       nob=nbNoInserted-1;
914       while (nob>=0) {
915         Tpi(piToInsert[nob--]).Dump(4);
916       }
917     }
918   }
919   if (nbpInt<3) nbpInt=0;
920   return nbpInt>0;
921 }
922
923
924 //=======================================================================
925 //function : CoupleCharacteristics
926 //purpose  : 
927 //=======================================================================
928
929 void IntPatch_InterferencePolyhedron::CoupleCharacteristics (const IntPatch_Polyhedron& FirstPol,
930                                                          const IntPatch_Polyhedron& SeconPol)
931 {
932   Standard_Integer n1, n2;
933   Standard_Real lg;
934
935   for (n1=0; n1<3; n1++) {
936     n2=Pourcent3[n1+1];
937     voo[n1]=IntPatch_PolyhedronTool::Point(FirstPol, OI[n2]).XYZ()-
938             IntPatch_PolyhedronTool::Point(FirstPol, OI[n1]).XYZ();
939     vtt[n1]=IntPatch_PolyhedronTool::Point(SeconPol, TI[n2]).XYZ()-
940             IntPatch_PolyhedronTool::Point(SeconPol, TI[n1]).XYZ();
941   }
942
943   gp_XYZ vvec=(voo[0]^voo[1])+(voo[1]^voo[2])+(voo[2]^voo[0]);
944   gp_XYZ vnorT=(vtt[0]^vtt[1])+(vtt[1]^vtt[2])+(vtt[2]^vtt[0]);
945   if (vnorT.Modulus()>vvec.Modulus())
946     vvec=vnorT;
947
948   for (n1=0; n1<3; n1++) {
949
950     for (n2=0; n2<3; n2++) {
951
952       gp_XYZ vto=IntPatch_PolyhedronTool::Point(FirstPol, OI[n1]).XYZ()-
953                  IntPatch_PolyhedronTool::Point(SeconPol, TI[n2]).XYZ();
954       dpOpT[n1][n2]=vto.Modulus();
955
956       lg=vtt[n2].Modulus();
957       if (lg > 1e-16) { //-- RealEpsilon()
958         gp_XYZ vv=vto^vtt[n2];
959         lg=(vvec*vv)>0.0 ? lg : -lg;
960         dpOeT[n1][n2]=vv.Modulus()/lg;
961       }
962       else
963         dpOeT[n1][n2]=dpOpT[n1][n2];
964
965       lg=voo[n1].Modulus();
966       if (lg > 1e-16) { //-- RealEpsilon())
967         gp_XYZ vv=vto^voo[n1];
968         lg=(vvec*vv)>0.0 ? -lg : lg;
969         deOpT[n1][n2]=vv.Modulus()/lg;
970       }
971       else
972         deOpT[n1][n2]=dpOpT[n1][n2];
973     }
974   }
975 }