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