src/BRepExtrema/BRepExtrema_DistShapeShape.cxx

   1 // Created on: 1996-04-22
   2 // Created by: Herve LOUESSARD
   3 // Copyright (c) 1996-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 // Modified: Mps(10-04-97) portage WNT
  18
  19 #include <BRepExtrema_DistShapeShape.hxx>
  20
  21 #include <Standard_OStream.hxx>
  22 #include <TopTools_IndexedMapOfShape.hxx>
  23 #include <BRepBndLib.hxx>
  24 #include <Bnd_Box.hxx>
  25 #include <TopExp.hxx>
  26 #include <BRepExtrema_DistanceSS.hxx>
  27 #include <TopoDS.hxx>
  28 #include <TopAbs.hxx>
  29 #include <TopoDS_Vertex.hxx>
  30 #include <TopoDS_Edge.hxx>
  31 #include <TopoDS_Face.hxx>
  32 #include <TopAbs_ShapeEnum.hxx>
  33 #include <Precision.hxx>
  34 #include <Bnd_SeqOfBox.hxx>
  35 #include <BRepExtrema_UnCompatibleShape.hxx>
  36 #include <BRep_Tool.hxx>
  37 #include <BRepClass3d_SolidClassifier.hxx>
  38 #include <NCollection_Vector.hxx>
  39 #include <StdFail_NotDone.hxx>
  40
  41 #include <algorithm>
  42 namespace
  43 {
  44
  45   static void Decomposition(const TopoDS_Shape&         S,
  46                             TopTools_IndexedMapOfShape& MapV,
  47                             TopTools_IndexedMapOfShape& MapE,
  48                             TopTools_IndexedMapOfShape& MapF)
  49   {
  50     MapV.Clear();
  51     MapE.Clear();
  52     MapF.Clear();
  53     TopExp::MapShapes(S,TopAbs_VERTEX,MapV);
  54     TopExp::MapShapes(S,TopAbs_EDGE,MapE);
  55     TopExp::MapShapes(S,TopAbs_FACE,MapF);
  56   }
  57
  58   static void BoxCalculation(const TopTools_IndexedMapOfShape& Map,
  59                              Bnd_SeqOfBox&                     SBox)
  60   {
  61     for (Standard_Integer i = 1; i <= Map.Extent(); i++)
  62     {
  63       Bnd_Box box;
  64       BRepBndLib::Add(Map(i), box);
  65       SBox.Append(box);
  66     }
  67   }
  68
  69   inline Standard_Real DistanceInitiale(const TopoDS_Vertex V1,
  70                                         const TopoDS_Vertex V2)
  71   {
  72     return (BRep_Tool::Pnt(V1).Distance(BRep_Tool::Pnt(V2)));
  73   }
  74
  75   //! Pair of objects to check extrema.
  76   struct BRepExtrema_CheckPair
  77   {
  78     Standard_Integer Index1;   //!< Index of the 1st sub-shape
  79     Standard_Integer Index2;   //!< Index of the 2nd sub-shape
  80     Standard_Real    Distance; //!< Distance between sub-shapes
  81
  82     //! Uninitialized constructor for collection.
  83     BRepExtrema_CheckPair() {}
  84
  85     //! Creates new pair of sub-shapes.
  86     BRepExtrema_CheckPair (Standard_Integer theIndex1,
  87                            Standard_Integer theIndex2,
  88                            Standard_Real    theDistance)
  89     : Index1   (theIndex1),
  90       Index2   (theIndex2),
  91       Distance (theDistance) {}
  92   };
  93
  94   // Used by std::sort function
  95   static Standard_Boolean BRepExtrema_CheckPair_Comparator (const BRepExtrema_CheckPair& theLeft,
  96                                                             const BRepExtrema_CheckPair& theRight)
  97   {
  98     return (theLeft.Distance < theRight.Distance);
  99   }
 100 }
 101
 102 //=======================================================================
 103 //function : DistanceMapMap
 104 //purpose  :
 105 //=======================================================================
 106
 107 void BRepExtrema_DistShapeShape::DistanceMapMap (const TopTools_IndexedMapOfShape& theMap1,
 108                                                  const TopTools_IndexedMapOfShape& theMap2,
 109                                                  const Bnd_SeqOfBox&               theLBox1,
 110                                                  const Bnd_SeqOfBox&               theLBox2)
 111 {
 112   NCollection_Vector<BRepExtrema_CheckPair> aPairList;
 113   const Standard_Integer aCount1 = theMap1.Extent();
 114   const Standard_Integer aCount2 = theMap2.Extent();
 115   for (Standard_Integer anIdx1 = 1; anIdx1 <= aCount1; ++anIdx1)
 116   {
 117     for (Standard_Integer anIdx2 = 1; anIdx2 <= aCount2; ++anIdx2)
 118     {
 119       const Bnd_Box& aBox1 = theLBox1.Value (anIdx1);
 120       const Bnd_Box& aBox2 = theLBox2.Value (anIdx2);
 121       if (aBox1.IsVoid()
 122        || aBox2.IsVoid())
 123       {
 124         continue;
 125       }
 126
 127       const Standard_Real aDist = aBox1.Distance (aBox2);
 128       if (aDist < myDistRef - myEps || fabs (aDist - myDistRef) < myEps)
 129       {
 130         aPairList.Append (BRepExtrema_CheckPair (anIdx1, anIdx2, aDist));
 131       }
 132     }
 133   }
 134
 135   std::stable_sort(aPairList.begin(), aPairList.end(), BRepExtrema_CheckPair_Comparator);
 136
 137   for (NCollection_Vector<BRepExtrema_CheckPair>::Iterator aPairIter (aPairList);
 138        aPairIter.More(); aPairIter.Next())
 139   {
 140     const BRepExtrema_CheckPair& aPair = aPairIter.Value();
 141     if (aPair.Distance > myDistRef + myEps)
 142     {
 143       break; // early search termination
 144     }
 145
 146     const Bnd_Box& aBox1 = theLBox1.Value (aPair.Index1);
 147     const Bnd_Box& aBox2 = theLBox2.Value (aPair.Index2);
 148
 149     const TopoDS_Shape& aShape1 = theMap1 (aPair.Index1);
 150     const TopoDS_Shape& aShape2 = theMap2 (aPair.Index2);
 151
 152     BRepExtrema_DistanceSS aDistTool (aShape1, aShape2, aBox1, aBox2, myDistRef, myEps);
 153     if (aDistTool.IsDone())
 154     {
 155       if (aDistTool.DistValue() < myDistRef - myEps)
 156       {
 157         mySolutionsShape1.Clear();
 158         mySolutionsShape2.Clear();
 159
 160         BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
 161         BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
 162
 163         mySolutionsShape1.Append (aSeq1);
 164         mySolutionsShape2.Append (aSeq2);
 165
 166         myDistRef = aDistTool.DistValue();
 167       }
 168       else if (fabs (aDistTool.DistValue() - myDistRef) < myEps)
 169       {
 170         BRepExtrema_SeqOfSolution aSeq1 = aDistTool.Seq1Value();
 171         BRepExtrema_SeqOfSolution aSeq2 = aDistTool.Seq2Value();
 172
 173         mySolutionsShape1.Append (aSeq1);
 174         mySolutionsShape2.Append (aSeq2);
 175
 176         if (myDistRef > aDistTool.DistValue())
 177         {
 178           myDistRef = aDistTool.DistValue();
 179         }
 180       }
 181     }
 182   }
 183 }
 184
 185 //=======================================================================
 186 //function : BRepExtrema_DistShapeShape
 187 //purpose  :
 188 //=======================================================================
 189
 190 BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape()
 191 : myDistRef (0.0),
 192   myIsDone (Standard_False),
 193   myInnerSol (Standard_False),
 194   myEps (Precision::Confusion()),
 195   myIsInitS1 (Standard_False),
 196   myIsInitS2 (Standard_False),
 197   myFlag (Extrema_ExtFlag_MINMAX),
 198   myAlgo (Extrema_ExtAlgo_Grad)
 199 {
 200   //
 201 }
 202
 203 //=======================================================================
 204 //function : BRepExtrema_DistShapeShape
 205 //purpose  :
 206 //=======================================================================
 207 BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,
 208                                                        const TopoDS_Shape& Shape2,
 209                                                        const Extrema_ExtFlag F,
 210                                                        const Extrema_ExtAlgo A)
 211 : myDistRef (0.0),
 212   myIsDone (Standard_False),
 213   myInnerSol (Standard_False),
 214   myEps (Precision::Confusion()),
 215   myIsInitS1 (Standard_False),
 216   myIsInitS2 (Standard_False),
 217   myFlag (F),
 218   myAlgo (A)
 219 {
 220   LoadS1(Shape1);
 221   LoadS2(Shape2);
 222   Perform();
 223 }
 224
 225 //=======================================================================
 226 //function : BRepExtrema_DistShapeShape
 227 //purpose  :
 228 //=======================================================================
 229
 230 BRepExtrema_DistShapeShape::BRepExtrema_DistShapeShape(const TopoDS_Shape& Shape1,
 231                                                        const TopoDS_Shape& Shape2,
 232                                                        const Standard_Real theDeflection,
 233                                                        const Extrema_ExtFlag F,
 234                                                        const Extrema_ExtAlgo A)
 235 : myDistRef (0.0),
 236   myIsDone (Standard_False),
 237   myInnerSol (Standard_False),
 238   myEps (theDeflection),
 239   myIsInitS1 (Standard_False),
 240   myIsInitS2 (Standard_False),
 241   myFlag (F),
 242   myAlgo (A)
 243 {
 244   LoadS1(Shape1);
 245   LoadS2(Shape2);
 246   Perform();
 247 }
 248
 249 //=======================================================================
 250 //function : LoadS1
 251 //purpose  :
 252 //=======================================================================
 253
 254 void BRepExtrema_DistShapeShape::LoadS1 (const TopoDS_Shape& Shape1)
 255 {
 256   myShape1 = Shape1;
 257   myIsInitS1 = Standard_False;
 258   Decomposition (Shape1, myMapV1, myMapE1, myMapF1);
 259 }
 260
 261 //=======================================================================
 262 //function : LoadS2
 263 //purpose  :
 264 //=======================================================================
 265
 266 void BRepExtrema_DistShapeShape::LoadS2 (const TopoDS_Shape& Shape2)
 267 {
 268   myShape2 = Shape2;
 269   myIsInitS2 = Standard_False;
 270   Decomposition (Shape2, myMapV2, myMapE2, myMapF2);
 271 }
 272
 273 //=======================================================================
 274 //function : Perform
 275 //purpose  :
 276 //=======================================================================
 277
 278 Standard_Boolean BRepExtrema_DistShapeShape::Perform()
 279 {
 280   myIsDone=Standard_False;
 281   myInnerSol=Standard_False;
 282   mySolutionsShape1.Clear();
 283   mySolutionsShape2.Clear();
 284
 285   if ( myShape1.IsNull() || myShape2.IsNull() )
 286     return Standard_False;
 287
 288   TopoDS_Vertex V;
 289   const Standard_Real tol = 0.001;
 290
 291   // Treatment of solids
 292   const TopAbs_ShapeEnum Type1 = myShape1.ShapeType();
 293   if ((Type1==TopAbs_SOLID) || (Type1 == TopAbs_COMPSOLID))
 294   {
 295     BRepClass3d_SolidClassifier Classi(myShape1);
 296     const Standard_Integer nbv2 = myMapV2.Extent();
 297     Standard_Integer nbv1 = 0;
 298     while ( (nbv1<nbv2) && (!myInnerSol) )
 299     {
 300       nbv1++;
 301       V = TopoDS::Vertex(myMapV2(nbv1));
 302       const gp_Pnt &P = BRep_Tool::Pnt(V);
 303       Classi.Perform(P,tol);
 304       if (Classi.State()==TopAbs_IN)
 305       {
 306         myInnerSol = Standard_True;
 307         myDistRef = 0.;
 308         myIsDone = Standard_True;
 309         BRepExtrema_SolutionElem Sol(0,P,BRepExtrema_IsVertex,V);
 310         mySolutionsShape1.Append(Sol);
 311         mySolutionsShape2.Append(Sol);
 312       }
 313     }
 314   }
 315
 316   const TopAbs_ShapeEnum Type2 = myShape2.ShapeType();
 317   if (((Type2==TopAbs_SOLID) || (Type2==TopAbs_COMPSOLID)) && (!myInnerSol))
 318   {
 319     BRepClass3d_SolidClassifier Classi(myShape2);
 320     const Standard_Integer nbv1 = myMapV1.Extent();
 321     Standard_Integer nbv2 = 0;
 322     while ( (nbv2<nbv1) && (!myInnerSol) )
 323     {
 324       nbv2++;
 325       V = TopoDS::Vertex(myMapV1(nbv2));
 326       const gp_Pnt &P = BRep_Tool::Pnt(V);
 327       Classi.Perform(P,tol);
 328       if (Classi.State()==TopAbs_IN) {
 329         myInnerSol = Standard_True;
 330         myDistRef = 0;
 331         myIsDone = Standard_True;
 332         BRepExtrema_SolutionElem Sol (0,P,BRepExtrema_IsVertex,V);
 333         mySolutionsShape1.Append(Sol);
 334         mySolutionsShape2.Append(Sol);
 335       }
 336     }
 337   }
 338
 339   if (!myInnerSol)
 340   {
 341     if (!myIsInitS1) // rebuild cached data for 1st shape
 342     {
 343       myBV1.Clear();
 344       myBE1.Clear();
 345       myBF1.Clear();
 346
 347       BoxCalculation (myMapV1, myBV1);
 348       BoxCalculation (myMapE1, myBE1);
 349       BoxCalculation (myMapF1, myBF1);
 350
 351       myIsInitS1 = Standard_True;
 352     }
 353
 354     if (!myIsInitS2) // rebuild cached data for 2nd shape
 355     {
 356       myBV2.Clear();
 357       myBE2.Clear();
 358       myBF2.Clear();
 359
 360       BoxCalculation (myMapV2, myBV2);
 361       BoxCalculation (myMapE2, myBE2);
 362       BoxCalculation (myMapF2, myBF2);
 363
 364       myIsInitS2 = Standard_True;
 365     }
 366
 367     if (myMapV1.Extent() && myMapV2.Extent())
 368     {
 369       TopoDS_Vertex V1 = TopoDS::Vertex(myMapV1(1));
 370       TopoDS_Vertex V2 = TopoDS::Vertex(myMapV2(1));
 371       myDistRef = DistanceInitiale(V1, V2);
 372     }
 373     else
 374       myDistRef= 1.e30; //szv:!!!
 375
 376     DistanceMapMap (myMapV1, myMapV2, myBV1, myBV2);
 377     DistanceMapMap (myMapV1, myMapE2, myBV1, myBE2);
 378     DistanceMapMap (myMapE1, myMapV2, myBE1, myBV2);
 379     DistanceMapMap (myMapV1, myMapF2, myBV1, myBF2);
 380     DistanceMapMap (myMapF1, myMapV2, myBF1, myBV2);
 381     DistanceMapMap (myMapE1, myMapE2, myBE1, myBE2);
 382     DistanceMapMap (myMapE1, myMapF2, myBE1, myBF2);
 383     DistanceMapMap (myMapF1, myMapE2, myBF1, myBE2);
 384
 385     if (fabs (myDistRef) > myEps)
 386     {
 387       DistanceMapMap (myMapF1, myMapF2, myBF1, myBF2);
 388     }
 389
 390     //  Modified by Sergey KHROMOV - Tue Mar  6 11:55:03 2001 Begin
 391     Standard_Integer i = 1;
 392     for (; i <= mySolutionsShape1.Length(); i++)
 393       if (mySolutionsShape1.Value(i).Dist() > myDistRef + myEps)
 394       {
 395         mySolutionsShape1.Remove(i);
 396         mySolutionsShape2.Remove(i);
 397       }
 398     //  Modified by Sergey KHROMOV - Tue Mar  6 11:55:04 2001 End
 399     myIsDone = ( mySolutionsShape1.Length() > 0 );
 400   }
 401   return myIsDone;
 402 }
 403
 404 //=======================================================================
 405 //function : Value
 406 //purpose  :
 407 //=======================================================================
 408
 409 Standard_Real BRepExtrema_DistShapeShape::Value() const
 410 {
 411   if (!myIsDone)
 412     throw StdFail_NotDone("BRepExtrema_DistShapeShape::Value: There's no solution ");
 413
 414   return myDistRef;
 415 }
 416
 417 //=======================================================================
 418 //function : SupportOnShape1
 419 //purpose  :
 420 //=======================================================================
 421
 422 TopoDS_Shape BRepExtrema_DistShapeShape::SupportOnShape1(const Standard_Integer N) const
 423 {
 424   if (!myIsDone)
 425     throw StdFail_NotDone("BRepExtrema_DistShapeShape::SupportOnShape1: There's no solution ");
 426
 427   const BRepExtrema_SolutionElem &sol = mySolutionsShape1.Value(N);
 428   switch (sol.SupportKind())
 429   {
 430     case BRepExtrema_IsVertex : return sol.Vertex();
 431     case BRepExtrema_IsOnEdge : return sol.Edge();
 432     case BRepExtrema_IsInFace : return sol.Face();
 433   }
 434   return TopoDS_Shape();
 435 }
 436
 437 //=======================================================================
 438 //function : SupportOnShape2
 439 //purpose  :
 440 //=======================================================================
 441
 442 TopoDS_Shape BRepExtrema_DistShapeShape::SupportOnShape2(const Standard_Integer N) const
 443 {
 444   if (!myIsDone)
 445     throw StdFail_NotDone("BRepExtrema_DistShapeShape::SupportOnShape2: There's no solution ");
 446
 447   const BRepExtrema_SolutionElem &sol = mySolutionsShape2.Value(N);
 448   switch (sol.SupportKind())
 449   {
 450     case BRepExtrema_IsVertex : return sol.Vertex();
 451     case BRepExtrema_IsOnEdge : return sol.Edge();
 452     case BRepExtrema_IsInFace : return sol.Face();
 453   }
 454   return TopoDS_Shape();
 455 }
 456
 457 //=======================================================================
 458 //function : ParOnEdgeS1
 459 //purpose  :
 460 //=======================================================================
 461
 462 void BRepExtrema_DistShapeShape::ParOnEdgeS1(const Standard_Integer N, Standard_Real& t) const
 463 {
 464   if (!myIsDone)
 465     throw StdFail_NotDone("BRepExtrema_DistShapeShape::ParOnEdgeS1: There's no solution");
 466
 467   const BRepExtrema_SolutionElem &sol = mySolutionsShape1.Value(N);
 468   if (sol.SupportKind() != BRepExtrema_IsOnEdge)
 469     throw BRepExtrema_UnCompatibleShape("BRepExtrema_DistShapeShape::ParOnEdgeS1: ParOnEdgeS1 is impossible without EDGE");
 470
 471   sol.EdgeParameter(t);
 472 }
 473
 474 //=======================================================================
 475 //function : ParOnEdgeS2
 476 //purpose  :
 477 //=======================================================================
 478
 479 void BRepExtrema_DistShapeShape::ParOnEdgeS2(const Standard_Integer N,  Standard_Real& t) const
 480 {
 481   if (!myIsDone)
 482     throw StdFail_NotDone("BRepExtrema_DistShapeShape::ParOnEdgeS2: There's no solution");
 483
 484   const BRepExtrema_SolutionElem &sol = mySolutionsShape2.Value(N);
 485   if (sol.SupportKind() != BRepExtrema_IsOnEdge)
 486     throw BRepExtrema_UnCompatibleShape("BRepExtrema_DistShapeShape::ParOnEdgeS2: ParOnEdgeS2 is impossible without EDGE");
 487
 488   sol.EdgeParameter(t);
 489 }
 490
 491 //=======================================================================
 492 //function : ParOnFaceS1
 493 //purpose  :
 494 //=======================================================================
 495
 496 void BRepExtrema_DistShapeShape::ParOnFaceS1(const Standard_Integer N,  Standard_Real& u,  Standard_Real& v) const
 497 {
 498   if (!myIsDone)
 499     throw StdFail_NotDone("BRepExtrema_DistShapeShape::ParOnFaceS1: There's no solution");
 500
 501   const BRepExtrema_SolutionElem &sol = mySolutionsShape1.Value(N);
 502   if (sol.SupportKind() != BRepExtrema_IsInFace)
 503     throw BRepExtrema_UnCompatibleShape("BRepExtrema_DistShapeShape::ParOnFaceS1: ParOnFaceS1 is impossible without FACE");
 504
 505   sol.FaceParameter(u, v);
 506 }
 507
 508 //=======================================================================
 509 //function : ParOnFaceS2
 510 //purpose  :
 511 //=======================================================================
 512
 513 void BRepExtrema_DistShapeShape::ParOnFaceS2(const Standard_Integer N,  Standard_Real& u, Standard_Real& v) const
 514 {
 515   if (!myIsDone)
 516     throw StdFail_NotDone("BRepExtrema_DistShapeShape::ParOnFaceS2: There's no solution");
 517
 518   const BRepExtrema_SolutionElem &sol = mySolutionsShape2.Value(N);
 519   if (sol.SupportKind() != BRepExtrema_IsInFace)
 520     throw BRepExtrema_UnCompatibleShape("BRepExtrema_DistShapeShape::ParOnFaceS2:ParOnFaceS2 is impossible without FACE ");
 521
 522   sol.FaceParameter(u, v);
 523 }
 524
 525 //=======================================================================
 526 //function : Dump
 527 //purpose  :
 528 //=======================================================================
 529
 530 void BRepExtrema_DistShapeShape::Dump(Standard_OStream& o) const
 531 {
 532   Standard_Integer i;
 533   Standard_Real r1,r2;
 534
 535   o<< "the distance  value is :  " << Value()<<std::endl;
 536   o<< "the number of solutions is :"<<NbSolution()<<std::endl;
 537   o<<std::endl;
 538   for (i=1;i<=NbSolution();i++)
 539   {
 540     o<<"solution number "<<i<<": "<< std::endl;
 541     o<<"the type of the solution on the first shape is " <<Standard_Integer( SupportTypeShape1(i)) <<std::endl;
 542     o<<"the type of the solution on the second shape is "<<Standard_Integer( SupportTypeShape2(i))<< std::endl;
 543     o<< "the coordinates of  the point on the first shape are: "<<std::endl;
 544     o<<"X=" <<PointOnShape1(i).X()<<" Y=" <<PointOnShape1(i).Y()<<" Z="<<PointOnShape1(i).Z()<<std::endl;
 545     o<< "the coordinates of  the point on the second shape are: "<<std::endl;
 546     o<<"X="<< PointOnShape2(i).X()<< " Y="<<PointOnShape2(i).Y()<<" Z="<< PointOnShape2(i).Z()<<std::endl;
 547
 548     switch (SupportTypeShape1(i))
 549     {
 550       case BRepExtrema_IsVertex:
 551         break;
 552       case BRepExtrema_IsOnEdge:
 553         ParOnEdgeS1(i,r1);
 554         o << "parameter on the first edge :  t= " << r1 << std::endl;
 555         break;
 556       case BRepExtrema_IsInFace:
 557         ParOnFaceS1(i,r1,r2);
 558         o << "parameters on the first face :  u= " << r1 << " v=" <<  r2 << std::endl;
 559         break;
 560     }
 561     switch (SupportTypeShape2(i))
 562     {
 563       case BRepExtrema_IsVertex:
 564         break;
 565       case BRepExtrema_IsOnEdge:
 566         ParOnEdgeS2(i,r1);
 567         o << "parameter on the second edge : t=" << r1 << std::endl;
 568         break;
 569       case BRepExtrema_IsInFace:
 570         ParOnFaceS2(i,r1,r2);
 571         o << "parameters on the second face : u= " << r1 << " v=" <<  r2 << std::endl;
 572         break;
 573     }
 574     o<<std::endl;
 575   }
 576 }