src/IntPolyh/IntPolyh_Triangle.cxx

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