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         while (nob<nbNoInserted) {
 905           piToInsert[nob]=piToInsert[nob+1];
 906           nob++;
 907         }
 908         nbNoInserted--;
 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 }