src/SelectMgr/SelectMgr_TriangularFrustumSet.cxx

   1 // Created on: 2014-11-21
   2 // Created by: Varvara POSKONINA
   3 // Copyright (c) 2005-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <SelectMgr_TriangularFrustumSet.hxx>
  17
  18 #include <BRepMesh_DataStructureOfDelaun.hxx>
  19 #include <BRepMesh_Delaun.hxx>
  20 #include <NCollection_IncAllocator.hxx>
  21 #include <SelectMgr_FrustumBuilder.hxx>
  22
  23 namespace
  24 {
  25   static const size_t MEMORY_BLOCK_SIZE = 512 * 7;
  26 }
  27
  28 // =======================================================================
  29 // function : SelectMgr_TriangularFrustumSet
  30 // purpose  :
  31 // =======================================================================
  32 SelectMgr_TriangularFrustumSet::SelectMgr_TriangularFrustumSet()
  33 : myToAllowOverlap (Standard_False)
  34 {
  35 }
  36
  37 // =======================================================================
  38 // function : ~SelectMgr_TriangularFrustumSet
  39 // purpose  :
  40 // =======================================================================
  41 SelectMgr_TriangularFrustumSet::~SelectMgr_TriangularFrustumSet()
  42 {
  43   //
  44 }
  45
  46 // =======================================================================
  47 // function : Init
  48 // purpose  :
  49 // =======================================================================
  50 void SelectMgr_TriangularFrustumSet::Init (const TColgp_Array1OfPnt2d& thePoints)
  51 {
  52   if (mySelPolyline.Points.IsNull())
  53   {
  54     mySelPolyline.Points = new TColgp_HArray1OfPnt2d (thePoints.Lower(), thePoints.Upper());
  55   }
  56   mySelPolyline.Points->Resize (thePoints.Lower(), thePoints.Upper(), false);
  57   *mySelPolyline.Points = thePoints;
  58   mySelectionType = SelectMgr_SelectionType_Polyline;
  59 }
  60
  61 // =======================================================================
  62 // function : Build
  63 // purpose  : Meshes polygon bounded by polyline. Than organizes a set of
  64 //            triangular frustums, where each triangle's projection onto
  65 //            near and far view frustum planes is considered as a frustum
  66 //            base
  67 // =======================================================================
  68 void SelectMgr_TriangularFrustumSet::Build()
  69 {
  70   Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline || !mySelPolyline.Points.IsNull(),
  71     "Error! SelectMgr_TriangularFrustumSet::Build() should be called after selection frustum initialization");
  72
  73   myFrustums.Clear();
  74
  75   Handle(NCollection_IncAllocator) anAllocator = new NCollection_IncAllocator (MEMORY_BLOCK_SIZE);
  76   Handle(BRepMesh_DataStructureOfDelaun) aMeshStructure = new BRepMesh_DataStructureOfDelaun (anAllocator);
  77   Standard_Integer aPtsLower = mySelPolyline.Points->Lower();
  78   Standard_Integer aPtsUpper = mySelPolyline.Points->Upper();
  79   IMeshData::VectorOfInteger anIndexes (mySelPolyline.Points->Size(), anAllocator);
  80   myBoundaryPoints.Resize (aPtsLower, aPtsLower + 2 * (mySelPolyline.Points->Size()) - 1, Standard_False);
  81
  82   for (Standard_Integer aPtIdx = aPtsLower; aPtIdx <= aPtsUpper; ++aPtIdx)
  83   {
  84     BRepMesh_Vertex aVertex (mySelPolyline.Points->Value (aPtIdx).XY(), aPtIdx, BRepMesh_Frontier);
  85     anIndexes.Append (aMeshStructure->AddNode (aVertex));
  86     const gp_Pnt aNearPnt = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 0.0);
  87     const gp_Pnt aFarPnt  = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 1.0);
  88     myBoundaryPoints.SetValue (aPtIdx, aNearPnt);
  89     myBoundaryPoints.SetValue (aPtIdx + mySelPolyline.Points->Size(), aFarPnt);
  90   }
  91
  92   Standard_Real aPtSum = 0;
  93   for (Standard_Integer aIdx = aPtsLower; aIdx <= aPtsUpper; ++aIdx)
  94   {
  95     Standard_Integer aNextIdx = (aIdx % mySelPolyline.Points->Length()) + 1;
  96     aPtSum += (mySelPolyline.Points->Value (aNextIdx).Coord().X() - mySelPolyline.Points->Value (aIdx).Coord().X())
  97             * (mySelPolyline.Points->Value (aNextIdx).Coord().Y() + mySelPolyline.Points->Value (aIdx).Coord().Y());
  98   }
  99   Standard_Boolean isClockwiseOrdered = aPtSum < 0;
 100
 101   for (Standard_Integer aIdx = 0; aIdx < anIndexes.Length(); ++aIdx)
 102   {
 103     Standard_Integer aPtIdx = isClockwiseOrdered ? aIdx : (aIdx + 1) % anIndexes.Length();
 104     Standard_Integer aNextPtIdx = isClockwiseOrdered ? (aIdx + 1) % anIndexes.Length() : aIdx;
 105     BRepMesh_Edge anEdge (anIndexes.Value (aPtIdx),
 106                           anIndexes.Value (aNextPtIdx),
 107                           BRepMesh_Frontier);
 108     aMeshStructure->AddLink (anEdge);
 109   }
 110
 111   BRepMesh_Delaun aTriangulation (aMeshStructure, anIndexes);
 112   const IMeshData::MapOfInteger& aTriangles = aMeshStructure->ElementsOfDomain();
 113   if (aTriangles.Extent() < 1)
 114     return;
 115
 116   IMeshData::IteratorOfMapOfInteger aTriangleIt (aTriangles);
 117   for (; aTriangleIt.More(); aTriangleIt.Next())
 118   {
 119     const Standard_Integer aTriangleId = aTriangleIt.Key();
 120     const BRepMesh_Triangle& aCurrentTriangle = aMeshStructure->GetElement (aTriangleId);
 121
 122     if (aCurrentTriangle.Movability() == BRepMesh_Deleted)
 123       continue;
 124
 125     Standard_Integer aTriangleVerts[3];
 126     aMeshStructure->ElementNodes (aCurrentTriangle, aTriangleVerts);
 127
 128     gp_Pnt2d aPts[3];
 129     for (Standard_Integer aVertIdx = 0; aVertIdx < 3; ++aVertIdx)
 130     {
 131       const BRepMesh_Vertex& aVertex = aMeshStructure->GetNode (aTriangleVerts[aVertIdx]);
 132       aPts[aVertIdx] = aVertex.Coord();
 133     }
 134
 135     Handle(SelectMgr_TriangularFrustum) aTrFrustum = new SelectMgr_TriangularFrustum();
 136     aTrFrustum->Init (aPts[0], aPts[1], aPts[2]);
 137     aTrFrustum->SetBuilder (myBuilder);
 138     aTrFrustum->Build();
 139     myFrustums.Append (aTrFrustum);
 140   }
 141
 142   aMeshStructure.Nullify();
 143   anAllocator.Nullify();
 144 }
 145
 146 // =======================================================================
 147 // function : ScaleAndTransform
 148 // purpose  : IMPORTANT: Scaling makes sense only for frustum built on a single point!
 149 //            Note that this method does not perform any checks on type of the frustum.
 150 //            Returns a copy of the frustum resized according to the scale factor given
 151 //            and transforms it using the matrix given.
 152 //            There are no default parameters, but in case if:
 153 //                - transformation only is needed: @theScaleFactor must be initialized
 154 //                  as any negative value;
 155 //                - scale only is needed: @theTrsf must be set to gp_Identity.
 156 // =======================================================================
 157 Handle(SelectMgr_BaseIntersector) SelectMgr_TriangularFrustumSet::ScaleAndTransform (const Standard_Integer theScale,
 158                                                                                      const gp_GTrsf& theTrsf,
 159                                                                                      const Handle(SelectMgr_FrustumBuilder)& theBuilder) const
 160 {
 161   Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
 162     "Error! SelectMgr_TriangularFrustumSet::ScaleAndTransform() should be called after selection frustum initialization");
 163
 164   Handle(SelectMgr_TriangularFrustumSet) aRes = new SelectMgr_TriangularFrustumSet();
 165   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 166   {
 167     aRes->myFrustums.Append (Handle(SelectMgr_TriangularFrustum)::DownCast (anIter.Value()->ScaleAndTransform (theScale, theTrsf, theBuilder)));
 168   }
 169
 170   aRes->myBoundaryPoints.Resize (myBoundaryPoints.Lower(), myBoundaryPoints.Upper(), Standard_False);
 171   for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx <= myBoundaryPoints.Upper(); anIdx++)
 172   {
 173     gp_Pnt aPoint = myBoundaryPoints.Value (anIdx);
 174     theTrsf.Transforms (aPoint.ChangeCoord());
 175     aRes->myBoundaryPoints.SetValue (anIdx, aPoint);
 176   }
 177
 178   aRes->mySelectionType = mySelectionType;
 179   aRes->mySelPolyline.Points = mySelPolyline.Points;
 180   aRes->SetBuilder (theBuilder);
 181   return aRes;
 182 }
 183
 184 // =======================================================================
 185 // function : OverlapsBox
 186 // purpose  :
 187 // =======================================================================
 188 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
 189                                                               const SelectMgr_Vec3& theMaxPnt,
 190                                                               const SelectMgr_ViewClipRange& theClipRange,
 191                                                               SelectBasics_PickResult& thePickResult) const
 192 {
 193   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 194     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 195
 196   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 197   {
 198     if (anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, theClipRange, thePickResult))
 199     {
 200       return Standard_True;
 201     }
 202   }
 203
 204   return Standard_False;
 205 }
 206
 207 // =======================================================================
 208 // function : OverlapsBox
 209 // purpose  :
 210 // =======================================================================
 211 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
 212                                                               const SelectMgr_Vec3& theMaxPnt,
 213                                                               Standard_Boolean* theInside) const
 214 {
 215   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 216     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 217
 218   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 219   {
 220     if (!anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, NULL))
 221     {
 222       continue;
 223     }
 224
 225     if (myToAllowOverlap || theInside == NULL)
 226     {
 227       return Standard_True;
 228     }
 229
 230     gp_Pnt aMinMaxPnts[2] = { gp_Pnt (theMinPnt.x(), theMinPnt.y(), theMinPnt.z()),
 231                               gp_Pnt (theMaxPnt.x(), theMaxPnt.y(), theMaxPnt.z())};
 232
 233     gp_Pnt anOffset[3] = { gp_Pnt (aMinMaxPnts[1].X() - aMinMaxPnts[0].X(), 0.0, 0.0),
 234                             gp_Pnt (0.0, aMinMaxPnts[1].Y() - aMinMaxPnts[0].Y(), 0.0),
 235                             gp_Pnt (0.0, 0.0, aMinMaxPnts[1].Z() - aMinMaxPnts[0].Z()) };
 236
 237     Standard_Integer aSign = 1;
 238     for (Standard_Integer aPntsIdx = 0; aPntsIdx < 2; aPntsIdx++)
 239     {
 240       for (Standard_Integer aCoordIdx = 0; aCoordIdx < 3; aCoordIdx++)
 241       {
 242         gp_Pnt anOffsetPnt = aMinMaxPnts [aPntsIdx].XYZ() + aSign * anOffset [aCoordIdx].XYZ();
 243         if (isIntersectBoundary (aMinMaxPnts [aPntsIdx], anOffsetPnt)
 244           || isIntersectBoundary (anOffsetPnt, anOffsetPnt.XYZ() + aSign * anOffset [(aCoordIdx + 1) % 3].XYZ()))
 245         {
 246           *theInside &= Standard_False;
 247           return Standard_True;
 248         }
 249       }
 250       aSign = -aSign;
 251     }
 252     return Standard_True;
 253   }
 254
 255   return Standard_False;
 256 }
 257
 258 // =======================================================================
 259 // function : OverlapsPoint
 260 // purpose  :
 261 // =======================================================================
 262 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPoint (const gp_Pnt& thePnt,
 263                                                                 const SelectMgr_ViewClipRange& theClipRange,
 264                                                                 SelectBasics_PickResult& thePickResult) const
 265 {
 266   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 267     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 268
 269   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 270   {
 271     if (anIter.Value()->OverlapsPoint (thePnt, theClipRange, thePickResult))
 272     {
 273       return Standard_True;
 274     }
 275   }
 276
 277   return Standard_False;
 278 }
 279
 280 // =======================================================================
 281 // function : OverlapsPolygon
 282 // purpose  :
 283 // =======================================================================
 284 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPolygon (const TColgp_Array1OfPnt& theArrayOfPts,
 285                                                                   Select3D_TypeOfSensitivity theSensType,
 286                                                                   const SelectMgr_ViewClipRange& theClipRange,
 287                                                                   SelectBasics_PickResult& thePickResult) const
 288 {
 289   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 290     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 291
 292   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 293   {
 294     if (!anIter.Value()->OverlapsPolygon (theArrayOfPts, theSensType, theClipRange, thePickResult))
 295     {
 296       continue;
 297     }
 298
 299     if (myToAllowOverlap)
 300     {
 301       return Standard_True;
 302     }
 303
 304     Standard_Integer aPtsLower = theArrayOfPts.Lower();
 305     Standard_Integer aPtsUpper = theArrayOfPts.Upper();
 306     for (Standard_Integer anIdx = aPtsLower; anIdx <= aPtsUpper; anIdx++)
 307     {
 308       if (isIntersectBoundary (theArrayOfPts.Value (anIdx), theArrayOfPts.Value (anIdx < aPtsUpper ? anIdx + 1 : aPtsLower)))
 309       {
 310         return Standard_False;
 311       }
 312     }
 313     return Standard_True;
 314   }
 315
 316   return Standard_False;
 317 }
 318
 319 // =======================================================================
 320 // function : OverlapsSegment
 321 // purpose  :
 322 // =======================================================================
 323 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsSegment (const gp_Pnt& thePnt1,
 324                                                                   const gp_Pnt& thePnt2,
 325                                                                   const SelectMgr_ViewClipRange& theClipRange,
 326                                                                   SelectBasics_PickResult& thePickResult) const
 327 {
 328   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 329     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 330
 331   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 332   {
 333     if (!anIter.Value()->OverlapsSegment (thePnt1, thePnt2, theClipRange, thePickResult))
 334     {
 335       continue;
 336     }
 337
 338     if (myToAllowOverlap)
 339     {
 340       return Standard_True;
 341     }
 342
 343     if (isIntersectBoundary (thePnt1, thePnt2))
 344     {
 345       return Standard_False;
 346     }
 347     return Standard_True;
 348   }
 349
 350   return Standard_False;
 351 }
 352
 353 // =======================================================================
 354 // function : OverlapsTriangle
 355 // purpose  :
 356 // =======================================================================
 357 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsTriangle (const gp_Pnt& thePnt1,
 358                                                                    const gp_Pnt& thePnt2,
 359                                                                    const gp_Pnt& thePnt3,
 360                                                                    Select3D_TypeOfSensitivity theSensType,
 361                                                                    const SelectMgr_ViewClipRange& theClipRange,
 362                                                                    SelectBasics_PickResult& thePickResult) const
 363 {
 364   Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
 365     "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
 366
 367   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 368   {
 369     if (!anIter.Value()->OverlapsTriangle (thePnt1, thePnt2, thePnt3, theSensType, theClipRange, thePickResult))
 370     {
 371       continue;
 372     }
 373
 374     if (myToAllowOverlap)
 375     {
 376       return Standard_True;
 377     }
 378
 379     if (isIntersectBoundary (thePnt1, thePnt2)
 380      || isIntersectBoundary (thePnt2, thePnt3)
 381      || isIntersectBoundary (thePnt3, thePnt1))
 382     {
 383       return Standard_False;
 384     }
 385     return Standard_True;
 386   }
 387
 388   return Standard_False;
 389 }
 390
 391 // =======================================================================
 392 // function : GetPlanes
 393 // purpose  :
 394 // =======================================================================
 395 void SelectMgr_TriangularFrustumSet::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
 396 {
 397   thePlaneEquations.Clear();
 398
 399   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 400   {
 401     anIter.Value()->GetPlanes (thePlaneEquations);
 402   }
 403 }
 404
 405 //=======================================================================
 406 // function : SetAllowOverlapDetection
 407 // purpose  :
 408 //=======================================================================
 409 void SelectMgr_TriangularFrustumSet::SetAllowOverlapDetection (const Standard_Boolean theIsToAllow)
 410 {
 411   myToAllowOverlap = theIsToAllow;
 412 }
 413
 414 //=======================================================================
 415 // function : isIntersectBoundary
 416 // purpose  :
 417 //=======================================================================
 418 Standard_Boolean SelectMgr_TriangularFrustumSet::isIntersectBoundary (const gp_Pnt& thePnt1, const gp_Pnt& thePnt2) const
 419 {
 420   Standard_Integer aFacesNb = myBoundaryPoints.Size() / 2;
 421   gp_Vec aDir = thePnt2.XYZ() - thePnt1.XYZ();
 422   gp_Pnt anOrig = thePnt1;
 423
 424   for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < aFacesNb + myBoundaryPoints.Lower(); anIdx++)
 425   {
 426     gp_Pnt aFace[4] = { myBoundaryPoints.Value (anIdx),
 427                         myBoundaryPoints.Value (anIdx + aFacesNb),
 428                         myBoundaryPoints.Value (anIdx % aFacesNb + 1 + aFacesNb),
 429                         myBoundaryPoints.Value (anIdx % aFacesNb + 1) };
 430
 431     if (segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[1], aFace[2])
 432      || segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[2], aFace[3]))
 433     {
 434       return Standard_True;
 435     }
 436   }
 437   return Standard_False;
 438 }
 439
 440 //=======================================================================
 441 // function : segmentTriangleIntersection
 442 // purpose  : Moller-Trumbore ray-triangle intersection test
 443 //=======================================================================
 444 Standard_Boolean SelectMgr_TriangularFrustumSet::segmentTriangleIntersection (const gp_Pnt& theOrig, const gp_Vec& theDir,
 445                                                                               const gp_Pnt& theV1, const gp_Pnt& theV2, const gp_Pnt& theV3) const
 446 {
 447   gp_Vec        aPVec, aTVec, aQVec;
 448   Standard_Real aD, aInvD, anU, aV, aT;
 449
 450   gp_Vec anEdge1 = theV2.XYZ() - theV1.XYZ();
 451   gp_Vec anEdge2 = theV3.XYZ() - theV1.XYZ();
 452
 453   aPVec = theDir.Crossed (anEdge2);
 454   aD = anEdge1.Dot (aPVec);
 455   if (fabs (aD) < gp::Resolution())
 456   {
 457     return Standard_False;
 458   }
 459
 460   aInvD = 1.0 / aD;
 461   aTVec = theOrig.XYZ() - theV1.XYZ();
 462   anU = aInvD * aTVec.Dot (aPVec);
 463   if (anU < 0.0 || anU > 1.0)
 464   {
 465     return Standard_False;
 466   }
 467
 468   aQVec = aTVec.Crossed (anEdge1);
 469   aV = aInvD * theDir.Dot (aQVec);
 470   if (aV < 0.0 || anU + aV > 1.0)
 471   {
 472     return Standard_False;
 473   }
 474
 475   aT = aInvD * anEdge2.Dot (aQVec);
 476   if (aT < 0 || aT > 1)
 477   {
 478     return Standard_False;
 479   }
 480
 481   return Standard_True;
 482 }
 483
 484 // =======================================================================
 485 // function : DetectedPoint
 486 // purpose  :
 487 // =======================================================================
 488 gp_Pnt SelectMgr_TriangularFrustumSet::DetectedPoint (const Standard_Real theDepth) const
 489 {
 490   (void )theDepth;
 491   throw Standard_ProgramError ("SelectMgr_TriangularFrustumSet::DetectedPoint() should not be called for Polyline selection type");
 492 }
 493
 494 //=======================================================================
 495 //function : DumpJson
 496 //purpose  :
 497 //=======================================================================
 498 void SelectMgr_TriangularFrustumSet::DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth) const
 499 {
 500   OCCT_DUMP_CLASS_BEGIN (theOStream, SelectMgr_TriangularFrustumSet)
 501   OCCT_DUMP_BASE_CLASS (theOStream, theDepth, SelectMgr_BaseFrustum)
 502
 503   for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
 504   {
 505     const Handle(SelectMgr_TriangularFrustum)& aFrustum = anIter.Value();
 506     OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, aFrustum.get())
 507   }
 508 }