src/SelectMgr/SelectMgr_ViewerSelector.cxx

   1 // Created on: 1995-02-15
   2 // Created by: Roberc Coublanc
   3 // Copyright (c) 1995-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 #include <SelectMgr_ViewerSelector.hxx>
  18
  19 #include <BVH_Tree.hxx>
  20 #include <gp_GTrsf.hxx>
  21 #include <gp_Pnt.hxx>
  22 #include <OSD_Environment.hxx>
  23 #include <Precision.hxx>
  24 #include <Select3D_SensitiveEntity.hxx>
  25 #include <SelectBasics_PickResult.hxx>
  26 #include <SelectMgr_EntityOwner.hxx>
  27 #include <SelectMgr_SortCriterion.hxx>
  28 #include <SelectMgr_SensitiveEntitySet.hxx>
  29 #include <TColStd_Array1OfInteger.hxx>
  30 #include <TCollection_AsciiString.hxx>
  31 #include <TColStd_HArray1OfInteger.hxx>
  32 #include <TColStd_ListOfInteger.hxx>
  33
  34 #include <algorithm>
  35
  36 IMPLEMENT_STANDARD_RTTIEXT(SelectMgr_ViewerSelector, Standard_Transient)
  37
  38 namespace {
  39   // Comparison operator for sorting selection results
  40   class CompareResults
  41   {
  42   public:
  43
  44     CompareResults (const SelectMgr_IndexedDataMapOfOwnerCriterion& aMapOfCriterion)
  45       : myMapOfCriterion (aMapOfCriterion)
  46     {
  47     }
  48
  49     Standard_Boolean operator() (Standard_Integer theLeft, Standard_Integer theRight) const
  50     {
  51       return myMapOfCriterion.FindFromIndex(theLeft) > myMapOfCriterion.FindFromIndex(theRight);
  52     }
  53
  54   private:
  55     void operator = (const CompareResults&);
  56
  57   private:
  58     const SelectMgr_IndexedDataMapOfOwnerCriterion&  myMapOfCriterion;
  59   };
  60
  61   static const Graphic3d_Mat4d SelectMgr_ViewerSelector_THE_IDENTITY_MAT;
  62 }
  63
  64 //=======================================================================
  65 // function : updatePoint3d
  66 // purpose  :
  67 //=======================================================================
  68 void SelectMgr_ViewerSelector::updatePoint3d (SelectMgr_SortCriterion& theCriterion,
  69                                               const SelectBasics_PickResult& thePickResult,
  70                                               const Handle(Select3D_SensitiveEntity)& theEntity,
  71                                               const gp_GTrsf& theInversedTrsf,
  72                                               const SelectMgr_SelectingVolumeManager& theMgr) const
  73 {
  74   if (theMgr.GetActiveSelectionType() != SelectMgr_SelectingVolumeManager::Point)
  75   {
  76     return;
  77   }
  78
  79   if (thePickResult.HasPickedPoint())
  80   {
  81     theCriterion.Point = thePickResult.PickedPoint();
  82   }
  83   else if (!thePickResult.IsValid())
  84   {
  85     theCriterion.Point = thePickResult.PickedPoint();
  86     return;
  87   }
  88   else
  89   {
  90     theCriterion.Point = theMgr.DetectedPoint (theCriterion.Depth);
  91   }
  92
  93   gp_GTrsf anInvTrsf = theInversedTrsf;
  94   if (theCriterion.Entity->HasInitLocation())
  95   {
  96     anInvTrsf = theCriterion.Entity->InvInitLocation() * anInvTrsf;
  97   }
  98   if (anInvTrsf.Form() != gp_Identity)
  99   {
 100     anInvTrsf.Inverted().Transforms (theCriterion.Point.ChangeCoord());
 101   }
 102
 103   if (mySelectingVolumeMgr.Camera().IsNull())
 104   {
 105     theCriterion.Tolerance = theEntity->SensitivityFactor() / 33.0;
 106   }
 107   else if (mySelectingVolumeMgr.Camera()->IsOrthographic())
 108   {
 109     theCriterion.Tolerance = myCameraScale * theEntity->SensitivityFactor();
 110   }
 111   else
 112   {
 113     const Standard_Real aDistFromEye = Abs ((theCriterion.Point.XYZ() - myCameraEye.XYZ()).Dot (myCameraDir.XYZ()));
 114     theCriterion.Tolerance = aDistFromEye * myCameraScale * theEntity->SensitivityFactor();
 115   }
 116 }
 117
 118 //==================================================
 119 // Function: Initialize
 120 // Purpose :
 121 //==================================================
 122 SelectMgr_ViewerSelector::SelectMgr_ViewerSelector():
 123 preferclosest(Standard_True),
 124 myToUpdateTolerance (Standard_True),
 125 myCameraScale (1.0),
 126 myCurRank (0),
 127 myIsLeftChildQueuedFirst (Standard_False),
 128 myEntityIdx (0)
 129 {
 130   myEntitySetBuilder = new BVH_BinnedBuilder<Standard_Real, 3, 4> (BVH_Constants_LeafNodeSizeSingle, BVH_Constants_MaxTreeDepth, Standard_True);
 131 }
 132
 133 //==================================================
 134 // Function: Activate
 135 // Purpose :
 136 //==================================================
 137 void SelectMgr_ViewerSelector::Activate (const Handle(SelectMgr_Selection)& theSelection)
 138 {
 139   for (NCollection_Vector<Handle(SelectMgr_SensitiveEntity)>::Iterator aSelEntIter (theSelection->Entities()); aSelEntIter.More(); aSelEntIter.Next())
 140   {
 141     aSelEntIter.Value()->SetActiveForSelection();
 142   }
 143
 144   if (theSelection->GetSelectionState() != SelectMgr_SOS_Activated)
 145   {
 146     theSelection->SetSelectionState (SelectMgr_SOS_Activated);
 147
 148     myTolerances.Add (theSelection->Sensitivity());
 149     myToUpdateTolerance = Standard_True;
 150   }
 151 }
 152
 153 //==================================================
 154 // Function: Deactivate
 155 // Purpose :
 156 //==================================================
 157 void SelectMgr_ViewerSelector::Deactivate (const Handle(SelectMgr_Selection)& theSelection)
 158 {
 159   for (NCollection_Vector<Handle(SelectMgr_SensitiveEntity)>::Iterator aSelEntIter (theSelection->Entities()); aSelEntIter.More(); aSelEntIter.Next())
 160   {
 161     aSelEntIter.Value()->ResetSelectionActiveStatus();
 162   }
 163
 164   if (theSelection->GetSelectionState() == SelectMgr_SOS_Activated)
 165   {
 166     theSelection->SetSelectionState (SelectMgr_SOS_Deactivated);
 167
 168     myTolerances.Decrement (theSelection->Sensitivity());
 169     myToUpdateTolerance = Standard_True;
 170   }
 171 }
 172
 173 //==================================================
 174 // Function: Clear
 175 // Purpose :
 176 //==================================================
 177 void SelectMgr_ViewerSelector::Clear()
 178 {
 179   mystored.Clear();
 180 }
 181
 182 //=======================================================================
 183 // function: isToScaleFrustum
 184 // purpose : Checks if the entity given requires to scale current selecting frustum
 185 //=======================================================================
 186 Standard_Boolean SelectMgr_ViewerSelector::isToScaleFrustum (const Handle(Select3D_SensitiveEntity)& theEntity)
 187 {
 188   return mySelectingVolumeMgr.GetActiveSelectionType() == SelectMgr_SelectingVolumeManager::Point
 189     && sensitivity (theEntity) < myTolerances.Tolerance();
 190 }
 191
 192 //=======================================================================
 193 // function: sensitivity
 194 // purpose : In case if custom tolerance is set, this method will return sum of entity
 195 //           sensitivity and custom tolerance.
 196 //=======================================================================
 197 Standard_Integer SelectMgr_ViewerSelector::sensitivity (const Handle(Select3D_SensitiveEntity)& theEntity) const
 198 {
 199   return myTolerances.IsCustomTolSet() ?
 200     theEntity->SensitivityFactor() + myTolerances.CustomTolerance() : theEntity->SensitivityFactor();
 201 }
 202
 203 //=======================================================================
 204 // function: checkOverlap
 205 // purpose : Internal function that checks if a particular sensitive
 206 //           entity theEntity overlaps current selecting volume precisely
 207 //=======================================================================
 208 void SelectMgr_ViewerSelector::checkOverlap (const Handle(Select3D_SensitiveEntity)& theEntity,
 209                                              const gp_GTrsf& theInversedTrsf,
 210                                              SelectMgr_SelectingVolumeManager& theMgr)
 211 {
 212   const Handle(SelectMgr_EntityOwner)& anOwner = theEntity->OwnerId();
 213   Handle(SelectMgr_SelectableObject) aSelectable = !anOwner.IsNull() ? anOwner->Selectable() : Handle(SelectMgr_SelectableObject)();
 214   SelectBasics_PickResult aPickResult;
 215   const Standard_Boolean isMatched = theEntity->Matches(theMgr, aPickResult);
 216   if (!isMatched
 217     || anOwner.IsNull())
 218   {
 219     return;
 220   }
 221
 222   SelectMgr_SortCriterion aCriterion;
 223   myZLayerOrderMap.Find (!aSelectable.IsNull() ? aSelectable->ZLayer() : Graphic3d_ZLayerId_Default, aCriterion.ZLayerPosition);
 224   aCriterion.Entity    = theEntity;
 225   aCriterion.Priority  = anOwner->Priority();
 226   aCriterion.Depth     = aPickResult.Depth();
 227   aCriterion.MinDist   = aPickResult.DistToGeomCenter();
 228   aCriterion.ToPreferClosest = preferclosest;
 229
 230   if (SelectMgr_SortCriterion* aPrevCriterion = mystored.ChangeSeek (anOwner))
 231   {
 232     ++aPrevCriterion->NbOwnerMatches;
 233     aCriterion.NbOwnerMatches = aPrevCriterion->NbOwnerMatches;
 234     if (theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Box)
 235     {
 236       if (aCriterion > *aPrevCriterion)
 237       {
 238         updatePoint3d (aCriterion, aPickResult, theEntity, theInversedTrsf, theMgr);
 239         *aPrevCriterion = aCriterion;
 240       }
 241     }
 242   }
 243   else
 244   {
 245     aCriterion.NbOwnerMatches = 1;
 246     updatePoint3d (aCriterion, aPickResult, theEntity, theInversedTrsf, theMgr);
 247     mystored.Add (anOwner, aCriterion);
 248   }
 249 }
 250
 251 //=======================================================================
 252 // function: computeFrustum
 253 // purpose :
 254 //=======================================================================
 255 void SelectMgr_ViewerSelector::computeFrustum (const Handle(Select3D_SensitiveEntity)& theEnt,
 256                                                const SelectMgr_SelectingVolumeManager& theMgrGlobal,
 257                                                const SelectMgr_SelectingVolumeManager& theMgrObject,
 258                                                const gp_GTrsf& theInvTrsf,
 259                                                SelectMgr_FrustumCache& theCachedMgrs,
 260                                                SelectMgr_SelectingVolumeManager& theResMgr)
 261 {
 262   Standard_Integer aScale = isToScaleFrustum (theEnt) ? sensitivity (theEnt) : 1;
 263   const gp_GTrsf aTrsfMtr = theEnt->HasInitLocation() ? theEnt->InvInitLocation() * theInvTrsf : theInvTrsf;
 264   const Standard_Boolean toScale = aScale != 1;
 265   const Standard_Boolean toTransform = aTrsfMtr.Form() != gp_Identity;
 266   if (toScale && toTransform)
 267   {
 268     theResMgr = theMgrGlobal.ScaleAndTransform (aScale, aTrsfMtr, NULL);
 269     theResMgr.SetViewClipping (theMgrObject);
 270   }
 271   else if (toScale)
 272   {
 273     if (!theCachedMgrs.Find (aScale, theResMgr))
 274     {
 275       theResMgr = theMgrGlobal.ScaleAndTransform (aScale, gp_Trsf(), NULL);
 276       theCachedMgrs.Bind (aScale, theResMgr);
 277     }
 278     theResMgr.SetViewClipping (theMgrObject);
 279   }
 280   else if (toTransform)
 281   {
 282     theResMgr = theMgrGlobal.ScaleAndTransform (1, aTrsfMtr, NULL);
 283     theResMgr.SetViewClipping (theMgrObject);
 284   }
 285   else
 286   {
 287     theResMgr = theMgrObject;
 288   }
 289 }
 290
 291 //=======================================================================
 292 // function: traverseObject
 293 // purpose : Internal function that checks if there is possible overlap
 294 //           between some entity of selectable object theObject and
 295 //           current selecting volume
 296 //=======================================================================
 297 void SelectMgr_ViewerSelector::traverseObject (const Handle(SelectMgr_SelectableObject)& theObject,
 298                                                const SelectMgr_SelectingVolumeManager& theMgr,
 299                                                const Handle(Graphic3d_Camera)& theCamera,
 300                                                const Graphic3d_Mat4d& theProjectionMat,
 301                                                const Graphic3d_Mat4d& theWorldViewMat,
 302                                                const Standard_Integer theViewportWidth,
 303                                                const Standard_Integer theViewportHeight)
 304 {
 305   Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = myMapOfObjectSensitives.ChangeFind (theObject);
 306   if (anEntitySet->Size() == 0)
 307   {
 308     return;
 309   }
 310
 311   const opencascade::handle<BVH_Tree<Standard_Real, 3> >& aSensitivesTree = anEntitySet->BVH();
 312   gp_GTrsf aInversedTrsf;
 313   if (theObject->HasTransformation() || !theObject->TransformPersistence().IsNull())
 314   {
 315     if (theObject->TransformPersistence().IsNull())
 316     {
 317       aInversedTrsf = theObject->InversedTransformation();
 318     }
 319     else
 320     {
 321       gp_GTrsf aTPers;
 322       Graphic3d_Mat4d aMat = theObject->TransformPersistence()->Compute (theCamera, theProjectionMat, theWorldViewMat, theViewportWidth, theViewportHeight);
 323
 324       aTPers.SetValue (1, 1, aMat.GetValue (0, 0));
 325       aTPers.SetValue (1, 2, aMat.GetValue (0, 1));
 326       aTPers.SetValue (1, 3, aMat.GetValue (0, 2));
 327       aTPers.SetValue (2, 1, aMat.GetValue (1, 0));
 328       aTPers.SetValue (2, 2, aMat.GetValue (1, 1));
 329       aTPers.SetValue (2, 3, aMat.GetValue (1, 2));
 330       aTPers.SetValue (3, 1, aMat.GetValue (2, 0));
 331       aTPers.SetValue (3, 2, aMat.GetValue (2, 1));
 332       aTPers.SetValue (3, 3, aMat.GetValue (2, 2));
 333       aTPers.SetTranslationPart (gp_XYZ (aMat.GetValue (0, 3), aMat.GetValue (1, 3), aMat.GetValue (2, 3)));
 334
 335       aInversedTrsf = (aTPers * gp_GTrsf (theObject->Transformation())).Inverted();
 336     }
 337   }
 338
 339   SelectMgr_SelectingVolumeManager aMgr = aInversedTrsf.Form() != gp_Identity
 340                                         ? theMgr.ScaleAndTransform (1, aInversedTrsf, NULL)
 341                                         : theMgr;
 342   if (!aMgr.Overlaps (aSensitivesTree->MinPoint (0),
 343                       aSensitivesTree->MaxPoint (0)))
 344   {
 345     return;
 346   }
 347
 348   if (!theObject->ClipPlanes().IsNull()
 349     && theObject->ClipPlanes()->ToOverrideGlobal())
 350   {
 351     aMgr.SetViewClipping (Handle(Graphic3d_SequenceOfHClipPlane)(), theObject->ClipPlanes());
 352   }
 353   else if (!theObject->TransformPersistence().IsNull())
 354   {
 355     if (theObject->TransformPersistence()->IsZoomOrRotate()
 356     && !theMgr.ViewClipping().IsNull())
 357     {
 358       // Zoom/rotate persistence object lives in two worlds at the same time.
 359       // Global clipping planes can not be trivially applied without being converted
 360       // into local space of transformation persistence object.
 361       // As more simple alternative - just clip entire object by its anchor point defined in the world space.
 362       const gp_Pnt anAnchor = theObject->TransformPersistence()->AnchorPoint();
 363       for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (*theMgr.ViewClipping()); aPlaneIt.More(); aPlaneIt.Next())
 364       {
 365         const Handle(Graphic3d_ClipPlane)& aPlane = aPlaneIt.Value();
 366         if (!aPlane->IsOn())
 367         {
 368           continue;
 369         }
 370
 371         const Graphic3d_Vec4d aCheckPnt (anAnchor.X(), anAnchor.Y(), anAnchor.Z(), 1.0);
 372         if (aPlane->ProbePoint (aCheckPnt) == Graphic3d_ClipState_Out)
 373         {
 374           return;
 375         }
 376       }
 377     }
 378
 379     aMgr.SetViewClipping (Handle(Graphic3d_SequenceOfHClipPlane)(), theObject->ClipPlanes());
 380   }
 381   else if (!theObject->ClipPlanes().IsNull()
 382         && !theObject->ClipPlanes()->IsEmpty())
 383   {
 384     aMgr.SetViewClipping (theMgr.ViewClipping(), theObject->ClipPlanes());
 385   }
 386
 387   if (!theMgr.ViewClipping().IsNull() &&
 388       theMgr.GetActiveSelectionType() == SelectBasics_SelectingVolumeManager::Box)
 389   {
 390     Graphic3d_BndBox3d aBBox (aSensitivesTree->MinPoint (0), aSensitivesTree->MaxPoint (0));
 391     // If box selection is active, and the whole sensitive tree is out of the clip planes
 392     // selection is empty for this object
 393     const Handle(Graphic3d_SequenceOfHClipPlane)& aViewPlanes = theMgr.ViewClipping();
 394
 395     for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (*aViewPlanes); aPlaneIt.More(); aPlaneIt.Next())
 396     {
 397       const Handle(Graphic3d_ClipPlane)& aPlane = aPlaneIt.Value();
 398       if (!aPlane->IsOn())
 399       {
 400         continue;
 401       }
 402
 403       Graphic3d_ClipState aState = aPlane->ProbeBox (aBBox);
 404       if (aState == Graphic3d_ClipState_Out) // do not process only whole trees, next check on the tree node
 405       {
 406         return;
 407       }
 408     }
 409   }
 410
 411   const Standard_Integer aFirstStored = mystored.Extent() + 1;
 412
 413   Standard_Integer aStack[BVH_Constants_MaxTreeDepth];
 414   Standard_Integer aHead = -1;
 415   Standard_Integer aNode = 0; // a root node
 416   SelectMgr_FrustumCache aScaledTrnsfFrustums;
 417   SelectMgr_SelectingVolumeManager aTmpMgr (false);
 418   for (;;)
 419   {
 420     if (!aSensitivesTree->IsOuter (aNode))
 421     {
 422       const Standard_Integer aLeftChildIdx  = aSensitivesTree->Child<0> (aNode);
 423       const Standard_Integer aRightChildIdx = aSensitivesTree->Child<1> (aNode);
 424       const Standard_Boolean isLeftChildIn  =  aMgr.Overlaps (aSensitivesTree->MinPoint (aLeftChildIdx),
 425                                                               aSensitivesTree->MaxPoint (aLeftChildIdx));
 426       const Standard_Boolean isRightChildIn = aMgr.Overlaps (aSensitivesTree->MinPoint (aRightChildIdx),
 427                                                              aSensitivesTree->MaxPoint (aRightChildIdx));
 428       if (isLeftChildIn
 429           && isRightChildIn)
 430       {
 431         aNode = aLeftChildIdx;
 432         ++aHead;
 433         aStack[aHead] = aRightChildIdx;
 434       }
 435       else if (isLeftChildIn
 436         || isRightChildIn)
 437       {
 438         aNode = isLeftChildIn ? aLeftChildIdx : aRightChildIdx;
 439       }
 440       else
 441       {
 442         if (aHead < 0)
 443         {
 444           break;
 445         }
 446
 447         aNode = aStack[aHead];
 448         --aHead;
 449       }
 450     }
 451     else
 452     {
 453       bool aClipped = false;
 454       if (!theMgr.ViewClipping().IsNull() &&
 455           theMgr.GetActiveSelectionType() == SelectBasics_SelectingVolumeManager::Box)
 456       {
 457         Graphic3d_BndBox3d aBBox (aSensitivesTree->MinPoint (aNode), aSensitivesTree->MaxPoint (aNode));
 458         // If box selection is active, and the whole sensitive tree is out of the clip planes
 459         // selection is empty for this object
 460         const Handle(Graphic3d_SequenceOfHClipPlane)& aViewPlanes = theMgr.ViewClipping();
 461
 462         for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (*aViewPlanes); aPlaneIt.More(); aPlaneIt.Next())
 463         {
 464           const Handle(Graphic3d_ClipPlane)& aPlane = aPlaneIt.Value();
 465           if (!aPlane->IsOn())
 466           {
 467             continue;
 468           }
 469           Graphic3d_ClipState aState = aPlane->ProbeBox (aBBox);
 470           if (aState == Graphic3d_ClipState_Out)
 471           {
 472             aClipped = true;
 473             break;
 474           }
 475           if (aState == Graphic3d_ClipState_On && !mySelectingVolumeMgr.IsOverlapAllowed()) // partially clipped
 476           {
 477             if (aPlane->ProbeBoxTouch (aBBox))
 478               continue;
 479             aClipped = true;
 480             break;
 481           }
 482         }
 483       }
 484       if (!aClipped)
 485       {
 486         Standard_Integer aStartIdx = aSensitivesTree->BegPrimitive (aNode);
 487         Standard_Integer anEndIdx = aSensitivesTree->EndPrimitive (aNode);
 488         for (Standard_Integer anIdx = aStartIdx; anIdx <= anEndIdx; ++anIdx)
 489         {
 490           const Handle(SelectMgr_SensitiveEntity)& aSensitive = anEntitySet->GetSensitiveById (anIdx);
 491           if (aSensitive->IsActiveForSelection())
 492           {
 493             const Handle(Select3D_SensitiveEntity)& anEnt = aSensitive->BaseSensitive();
 494             computeFrustum (anEnt, theMgr, aMgr, aInversedTrsf, aScaledTrnsfFrustums, aTmpMgr);
 495             checkOverlap (anEnt, aInversedTrsf, aTmpMgr);
 496           }
 497         }
 498       }
 499       if (aHead < 0)
 500       {
 501         break;
 502       }
 503
 504       aNode = aStack[aHead];
 505       --aHead;
 506     }
 507   }
 508
 509   // in case of Box/Polyline selection - keep only Owners having all Entities detected
 510   if (mySelectingVolumeMgr.IsOverlapAllowed()
 511   || (theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Box
 512    && theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Polyline))
 513   {
 514     return;
 515   }
 516
 517   for (Standard_Integer aStoredIter = mystored.Extent(); aStoredIter >= aFirstStored; --aStoredIter)
 518   {
 519     const SelectMgr_SortCriterion& aCriterion = mystored.FindFromIndex (aStoredIter);
 520     const Handle(SelectMgr_EntityOwner)& anOwner = aCriterion.Entity->OwnerId();
 521     Standard_Integer aNbOwnerEntities = 0;
 522     for (SelectMgr_IndexedMapOfHSensitive::Iterator aSensIter (anEntitySet->Sensitives()); aSensIter.More(); aSensIter.Next())
 523     {
 524       if (aSensIter.Value()->BaseSensitive()->OwnerId() == anOwner)
 525       {
 526         if (++aNbOwnerEntities > aCriterion.NbOwnerMatches)
 527         {
 528           // Remove from index map.
 529           // Considering NCollection_IndexedDataMap implementation, the values for lower indexes will not be modified.
 530           // Hence, just keep iterating in backward direction.
 531           mystored.RemoveFromIndex (aStoredIter);
 532           break;
 533         }
 534       }
 535     }
 536   }
 537 }
 538
 539 //=======================================================================
 540 // function: TraverseSensitives
 541 // purpose : Traverses BVH containing all added selectable objects and
 542 //           finds candidates for further search of overlap
 543 //=======================================================================
 544 void SelectMgr_ViewerSelector::TraverseSensitives()
 545 {
 546   mystored.Clear();
 547
 548   Standard_Integer aWidth;
 549   Standard_Integer aHeight;
 550   mySelectingVolumeMgr.WindowSize (aWidth, aHeight);
 551   mySelectableObjects.UpdateBVH (mySelectingVolumeMgr.Camera(),
 552                                  mySelectingVolumeMgr.ProjectionMatrix(),
 553                                  mySelectingVolumeMgr.WorldViewMatrix(),
 554                                  mySelectingVolumeMgr.WorldViewProjState(),
 555                                  aWidth, aHeight);
 556   const Handle(Graphic3d_Camera)& aCamera = mySelectingVolumeMgr.Camera();
 557   if (!aCamera.IsNull())
 558   {
 559     myCameraEye = aCamera->Eye().XYZ();
 560     myCameraDir = aCamera->Direction().XYZ();
 561     myCameraScale = aCamera->IsOrthographic()
 562                   ? aCamera->Scale()
 563                   : 2.0 * Tan (aCamera->FOVy() * M_PI / 360.0);
 564     const double aPixelSize = Max (1.0 / aWidth, 1.0 / aHeight);
 565     myCameraScale *= aPixelSize;
 566   }
 567
 568   for (Standard_Integer aBVHSetIt = 0; aBVHSetIt < SelectMgr_SelectableObjectSet::BVHSubsetNb; ++aBVHSetIt)
 569   {
 570     SelectMgr_SelectableObjectSet::BVHSubset aBVHSubset =
 571       static_cast<SelectMgr_SelectableObjectSet::BVHSubset> (aBVHSetIt);
 572
 573     if (mySelectableObjects.IsEmpty (aBVHSubset))
 574     {
 575       continue;
 576     }
 577
 578     gp_GTrsf aTFrustum;
 579
 580     SelectMgr_SelectingVolumeManager aMgr (Standard_False);
 581
 582     // for 2D space selection transform selecting volumes to perform overap testing
 583     // directly in camera's eye space omitting the camera position, which is not
 584     // needed there at all
 585     if (aBVHSubset == SelectMgr_SelectableObjectSet::BVHSubset_2dPersistent)
 586     {
 587       const Graphic3d_Mat4d& aMat = mySelectingVolumeMgr.WorldViewMatrix();
 588       aTFrustum.SetValue (1, 1, aMat.GetValue (0, 0));
 589       aTFrustum.SetValue (1, 2, aMat.GetValue (0, 1));
 590       aTFrustum.SetValue (1, 3, aMat.GetValue (0, 2));
 591       aTFrustum.SetValue (2, 1, aMat.GetValue (1, 0));
 592       aTFrustum.SetValue (2, 2, aMat.GetValue (1, 1));
 593       aTFrustum.SetValue (2, 3, aMat.GetValue (1, 2));
 594       aTFrustum.SetValue (3, 1, aMat.GetValue (2, 0));
 595       aTFrustum.SetValue (3, 2, aMat.GetValue (2, 1));
 596       aTFrustum.SetValue (3, 3, aMat.GetValue (2, 2));
 597       aTFrustum.SetTranslationPart (gp_XYZ (aMat.GetValue (0, 3), aMat.GetValue (1, 3), aMat.GetValue (2, 3)));
 598
 599       // define corresponding frustum builder parameters
 600       Handle(SelectMgr_FrustumBuilder) aBuilder = new SelectMgr_FrustumBuilder();
 601       aBuilder->SetProjectionMatrix (mySelectingVolumeMgr.ProjectionMatrix());
 602       aBuilder->SetWorldViewMatrix (SelectMgr_ViewerSelector_THE_IDENTITY_MAT);
 603       aBuilder->SetWindowSize (aWidth, aHeight);
 604       aMgr = mySelectingVolumeMgr.ScaleAndTransform (1, aTFrustum, aBuilder);
 605     }
 606     else
 607     {
 608       aMgr = mySelectingVolumeMgr;
 609     }
 610
 611     const Graphic3d_Mat4d& aProjectionMat   = mySelectingVolumeMgr.ProjectionMatrix();
 612     const Graphic3d_Mat4d& aWorldViewMat    = aBVHSubset != SelectMgr_SelectableObjectSet::BVHSubset_2dPersistent
 613                                             ? mySelectingVolumeMgr.WorldViewMatrix()
 614                                             : SelectMgr_ViewerSelector_THE_IDENTITY_MAT;
 615
 616     const opencascade::handle<BVH_Tree<Standard_Real, 3> >& aBVHTree = mySelectableObjects.BVH (aBVHSubset);
 617
 618     Standard_Integer aNode = 0;
 619     if (!aMgr.Overlaps (aBVHTree->MinPoint (0), aBVHTree->MaxPoint (0)))
 620     {
 621       continue;
 622     }
 623
 624     Standard_Integer aStack[BVH_Constants_MaxTreeDepth];
 625     Standard_Integer aHead = -1;
 626     for (;;)
 627     {
 628       if (!aBVHTree->IsOuter (aNode))
 629       {
 630         const Standard_Integer aLeftChildIdx  = aBVHTree->Child<0> (aNode);
 631         const Standard_Integer aRightChildIdx = aBVHTree->Child<1> (aNode);
 632         const Standard_Boolean isLeftChildIn  =
 633           aMgr.Overlaps (aBVHTree->MinPoint (aLeftChildIdx), aBVHTree->MaxPoint (aLeftChildIdx));
 634         const Standard_Boolean isRightChildIn =
 635           aMgr.Overlaps (aBVHTree->MinPoint (aRightChildIdx), aBVHTree->MaxPoint (aRightChildIdx));
 636         if (isLeftChildIn
 637           && isRightChildIn)
 638         {
 639           aNode = aLeftChildIdx;
 640           ++aHead;
 641           aStack[aHead] = aRightChildIdx;
 642         }
 643         else if (isLeftChildIn
 644           || isRightChildIn)
 645         {
 646           aNode = isLeftChildIn ? aLeftChildIdx : aRightChildIdx;
 647         }
 648         else
 649         {
 650           if (aHead < 0)
 651           {
 652             break;
 653           }
 654
 655           aNode = aStack[aHead];
 656           --aHead;
 657         }
 658       }
 659       else
 660       {
 661         Standard_Integer aStartIdx = aBVHTree->BegPrimitive (aNode);
 662         Standard_Integer anEndIdx  = aBVHTree->EndPrimitive (aNode);
 663         for (Standard_Integer anIdx = aStartIdx; anIdx <= anEndIdx; ++anIdx)
 664         {
 665           const Handle(SelectMgr_SelectableObject)& aSelectableObject =
 666             mySelectableObjects.GetObjectById (aBVHSubset, anIdx);
 667
 668           traverseObject (aSelectableObject, aMgr, aCamera, aProjectionMat, aWorldViewMat, aWidth, aHeight);
 669         }
 670         if (aHead < 0)
 671         {
 672           break;
 673         }
 674
 675         aNode = aStack[aHead];
 676         --aHead;
 677       }
 678     }
 679   }
 680
 681   SortResult();
 682 }
 683
 684 //==================================================
 685 // Function: ClearPicked
 686 // Purpose :
 687 //==================================================
 688 void SelectMgr_ViewerSelector::ClearPicked()
 689 {
 690   mystored.Clear();
 691 }
 692
 693 //==================================================
 694 // Function: Picked
 695 // Purpose :
 696 //==================================================
 697 Handle(SelectMgr_EntityOwner) SelectMgr_ViewerSelector::Picked() const
 698 {
 699   const Standard_Integer aRankInMap = myIndexes->Value (myCurRank);
 700   const Handle(SelectMgr_EntityOwner)& anOwner = mystored.FindKey (aRankInMap);
 701   return anOwner;
 702 }
 703
 704 //=======================================================================
 705 //function : Picked
 706 //purpose  :
 707 //=======================================================================
 708 Handle(SelectMgr_EntityOwner) SelectMgr_ViewerSelector::Picked (const Standard_Integer theRank) const
 709 {
 710   if (theRank < 1 || theRank > NbPicked())
 711   {
 712     return Handle(SelectMgr_EntityOwner)();
 713   }
 714
 715   const Standard_Integer anOwnerIdx = myIndexes->Value (theRank);
 716   const Handle(SelectMgr_EntityOwner)& aStoredOwner = mystored.FindKey (anOwnerIdx);
 717   return aStoredOwner;
 718 }
 719
 720 //=======================================================================
 721 //function : PickedData
 722 //purpose  :
 723 //=======================================================================
 724 const SelectMgr_SortCriterion& SelectMgr_ViewerSelector::PickedData(const Standard_Integer theRank) const
 725 {
 726   Standard_OutOfRange_Raise_if (theRank < 1 || theRank > NbPicked(), "SelectMgr_ViewerSelector::PickedData() out of range index");
 727   const Standard_Integer anOwnerIdx = myIndexes->Value (theRank);
 728   return mystored.FindFromIndex (anOwnerIdx);
 729 }
 730
 731 //===================================================
 732 //
 733 //       INTERNAL METHODS ....
 734 //
 735 //==================================================
 736
 737 //==================================================
 738 // Function: SetEntitySetBuilder
 739 // Purpose :
 740 //==================================================
 741 void SelectMgr_ViewerSelector::SetEntitySetBuilder (const Handle(Select3D_BVHBuilder3d)& theBuilder)
 742 {
 743   myEntitySetBuilder = theBuilder;
 744   for (SelectMgr_MapOfObjectSensitives::Iterator aSetIter (myMapOfObjectSensitives); aSetIter.More(); aSetIter.Next())
 745   {
 746     aSetIter.ChangeValue()->SetBuilder (myEntitySetBuilder);
 747   }
 748 }
 749
 750 //==================================================
 751 // Function: Contains
 752 // Purpose :
 753 //==================================================
 754 Standard_Boolean SelectMgr_ViewerSelector::Contains (const Handle(SelectMgr_SelectableObject)& theObject) const
 755 {
 756   return mySelectableObjects.Contains (theObject);
 757 }
 758
 759 //==================================================
 760 // Function: ActiveModes
 761 // Purpose : return all the  modes with a given state for an object
 762 //==================================================
 763 Standard_Boolean SelectMgr_ViewerSelector::Modes (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
 764                                                   TColStd_ListOfInteger& theModeList,
 765                                                   const SelectMgr_StateOfSelection theWantedState) const
 766 {
 767   Standard_Boolean hasActivatedStates = Contains (theSelectableObject);
 768   for (SelectMgr_SequenceOfSelection::Iterator aSelIter (theSelectableObject->Selections()); aSelIter.More(); aSelIter.Next())
 769   {
 770     if (theWantedState == SelectMgr_SOS_Any)
 771     {
 772       theModeList.Append (aSelIter.Value()->Mode());
 773     }
 774     else if (theWantedState == aSelIter.Value()->GetSelectionState())
 775     {
 776       theModeList.Append (aSelIter.Value()->Mode());
 777     }
 778   }
 779
 780   return hasActivatedStates;
 781 }
 782
 783 //==================================================
 784 // Function: IsActive
 785 // Purpose :
 786 //==================================================
 787 Standard_Boolean SelectMgr_ViewerSelector::IsActive (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
 788                                                      const Standard_Integer theMode) const
 789 {
 790   if (!Contains (theSelectableObject))
 791     return Standard_False;
 792
 793   const Handle(SelectMgr_Selection)& aSel = theSelectableObject->Selection (theMode);
 794   return !aSel.IsNull()
 795        && aSel->GetSelectionState() == SelectMgr_SOS_Activated;
 796 }
 797
 798 //==================================================
 799 // Function: IsInside
 800 // Purpose :
 801 //==================================================
 802 Standard_Boolean SelectMgr_ViewerSelector::IsInside (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
 803                                                      const Standard_Integer theMode) const
 804 {
 805   if (!Contains (theSelectableObject))
 806     return Standard_False;
 807
 808   const Handle(SelectMgr_Selection)& aSel = theSelectableObject->Selection (theMode);
 809   return !aSel.IsNull()
 810        && aSel->GetSelectionState() != SelectMgr_SOS_Unknown;
 811 }
 812
 813
 814 //=======================================================================
 815 //function : Status
 816 //purpose  :
 817 //=======================================================================
 818
 819 SelectMgr_StateOfSelection SelectMgr_ViewerSelector::Status (const Handle(SelectMgr_Selection)& theSelection) const
 820 {
 821   return theSelection->GetSelectionState();
 822 }
 823
 824 //==================================================
 825 // Function: Status
 826 // Purpose : gives Information about selectors
 827 //==================================================
 828
 829 TCollection_AsciiString SelectMgr_ViewerSelector::Status (const Handle(SelectMgr_SelectableObject)& theSelectableObject) const
 830 {
 831   TCollection_AsciiString aStatus ("Status Object :\n\t");
 832   for (SelectMgr_SequenceOfSelection::Iterator aSelIter (theSelectableObject->Selections()); aSelIter.More(); aSelIter.Next())
 833   {
 834     if (aSelIter.Value()->GetSelectionState() != SelectMgr_SOS_Unknown)
 835     {
 836       aStatus = aStatus + "Mode " + TCollection_AsciiString (aSelIter.Value()->Mode()) + " present - "
 837               + (aSelIter.Value()->GetSelectionState() == SelectMgr_SOS_Activated ? " Active \n\t" : " Inactive \n\t");
 838     }
 839   }
 840
 841   if (!Contains (theSelectableObject))
 842   {
 843     aStatus = aStatus + "Not Present in the selector\n\n";
 844   }
 845
 846   return aStatus;
 847 }
 848
 849 //=======================================================================
 850 //function : SortResult
 851 //purpose  :  there is a certain number of entities ranged by criteria
 852 //            (depth, size, priority, mouse distance from borders or
 853 //            CDG of the detected primitive. Parsing :
 854 //             maximum priorities .
 855 //             then a reasonable compromise between depth and distance...
 856 // finally the ranges are stored in myindexes depending on the parsing.
 857 // so, it is possible to only read
 858 //=======================================================================
 859 void SelectMgr_ViewerSelector::SortResult()
 860 {
 861   if(mystored.IsEmpty()) return;
 862
 863   const Standard_Integer anExtent = mystored.Extent();
 864   if(myIndexes.IsNull() || anExtent != myIndexes->Length())
 865     myIndexes = new TColStd_HArray1OfInteger (1, anExtent);
 866
 867   TColStd_Array1OfInteger& anIndexArray = myIndexes->ChangeArray1();
 868   for (Standard_Integer anIndexIter = 1; anIndexIter <= anExtent; ++anIndexIter)
 869   {
 870     anIndexArray.SetValue (anIndexIter, anIndexIter);
 871   }
 872   std::sort (anIndexArray.begin(), anIndexArray.end(), CompareResults (mystored));
 873 }
 874
 875 //=======================================================================
 876 // function : AddSelectableObject
 877 // purpose  : Adds new object to the map of selectable objects
 878 //=======================================================================
 879 void SelectMgr_ViewerSelector::AddSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
 880 {
 881   if (!myMapOfObjectSensitives.IsBound (theObject))
 882   {
 883     mySelectableObjects.Append (theObject);
 884     Handle(SelectMgr_SensitiveEntitySet) anEntitySet = new SelectMgr_SensitiveEntitySet (myEntitySetBuilder);
 885     myMapOfObjectSensitives.Bind (theObject, anEntitySet);
 886   }
 887 }
 888
 889 //=======================================================================
 890 // function : AddSelectionToObject
 891 // purpose  : Adds new selection to the object and builds its BVH tree
 892 //=======================================================================
 893 void SelectMgr_ViewerSelector::AddSelectionToObject (const Handle(SelectMgr_SelectableObject)& theObject,
 894                                                      const Handle(SelectMgr_Selection)& theSelection)
 895 {
 896   if (Handle(SelectMgr_SensitiveEntitySet)* anEntitySet = myMapOfObjectSensitives.ChangeSeek (theObject))
 897   {
 898     (*anEntitySet)->Append (theSelection);
 899     (*anEntitySet)->BVH();
 900   }
 901   else
 902   {
 903     AddSelectableObject (theObject);
 904     AddSelectionToObject (theObject, theSelection);
 905   }
 906 }
 907
 908 //=======================================================================
 909 // function : MoveSelectableObject
 910 // purpose  :
 911 //=======================================================================
 912 void SelectMgr_ViewerSelector::MoveSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
 913 {
 914   mySelectableObjects.ChangeSubset (theObject);
 915 }
 916
 917 //=======================================================================
 918 // function : RemoveSelectableObject
 919 // purpose  : Removes selectable object from map of selectable ones
 920 //=======================================================================
 921 void SelectMgr_ViewerSelector::RemoveSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
 922 {
 923   Handle(SelectMgr_SelectableObject) anObj = theObject;
 924   if (myMapOfObjectSensitives.UnBind (theObject))
 925   {
 926     mySelectableObjects.Remove (theObject);
 927   }
 928 }
 929
 930 //=======================================================================
 931 // function : RemoveSelectionOfObject
 932 // purpose  : Removes selection of the object and marks its BVH tree
 933 //            for rebuild
 934 //=======================================================================
 935 void SelectMgr_ViewerSelector::RemoveSelectionOfObject (const Handle(SelectMgr_SelectableObject)& theObject,
 936                                                         const Handle(SelectMgr_Selection)& theSelection)
 937 {
 938   if (Handle(SelectMgr_SensitiveEntitySet)* anEntitySet = myMapOfObjectSensitives.ChangeSeek (theObject))
 939   {
 940     (*anEntitySet)->Remove (theSelection);
 941   }
 942 }
 943
 944 //=======================================================================
 945 // function : RebuildObjectsTree
 946 // purpose  : Marks BVH of selectable objects for rebuild
 947 //=======================================================================
 948 void SelectMgr_ViewerSelector::RebuildObjectsTree (const Standard_Boolean theIsForce)
 949 {
 950   mySelectableObjects.MarkDirty();
 951
 952   if (theIsForce)
 953   {
 954     Standard_Integer aViewportWidth, aViewportHeight;
 955     mySelectingVolumeMgr.WindowSize (aViewportWidth, aViewportHeight);
 956
 957     Standard_Integer aWidth;
 958     Standard_Integer aHeight;
 959     mySelectingVolumeMgr.WindowSize (aWidth, aHeight);
 960     mySelectableObjects.UpdateBVH (mySelectingVolumeMgr.Camera(),
 961                                    mySelectingVolumeMgr.ProjectionMatrix(),
 962                                    mySelectingVolumeMgr.WorldViewMatrix(),
 963                                    mySelectingVolumeMgr.WorldViewProjState(),
 964                                    aWidth, aHeight);
 965   }
 966 }
 967
 968 //=======================================================================
 969 // function : RebuildSensitivesTree
 970 // purpose  : Marks BVH of sensitive entities of particular selectable
 971 //            object for rebuild
 972 //=======================================================================
 973 void SelectMgr_ViewerSelector::RebuildSensitivesTree (const Handle(SelectMgr_SelectableObject)& theObject,
 974                                                       const Standard_Boolean theIsForce)
 975 {
 976   if (!Contains (theObject))
 977     return;
 978
 979   Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = myMapOfObjectSensitives.ChangeFind (theObject);
 980   anEntitySet->MarkDirty();
 981
 982   if (theIsForce)
 983   {
 984     anEntitySet->BVH();
 985   }
 986 }
 987
 988 //=======================================================================
 989 // function : resetSelectionActivationStatus
 990 // purpose  : Marks all added sensitive entities of all objects as
 991 //            non-selectable
 992 //=======================================================================
 993 void SelectMgr_ViewerSelector::ResetSelectionActivationStatus()
 994 {
 995   for (SelectMgr_MapOfObjectSensitivesIterator aSensitivesIter (myMapOfObjectSensitives); aSensitivesIter.More(); aSensitivesIter.Next())
 996   {
 997     Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = aSensitivesIter.ChangeValue();
 998     const Standard_Integer anEntitiesNb = anEntitySet->Size();
 999     for (Standard_Integer anIdx = 0; anIdx < anEntitiesNb; ++anIdx)
1000     {
1001       anEntitySet->GetSensitiveById (anIdx)->ResetSelectionActiveStatus();
1002     }
1003   }
1004 }
1005
1006 //=======================================================================
1007 // function : DetectedEntity
1008 // purpose  : Returns sensitive entity that was detected during the
1009 //            previous run of selection algorithm
1010 //=======================================================================
1011 const Handle(Select3D_SensitiveEntity)& SelectMgr_ViewerSelector::DetectedEntity() const
1012 {
1013   const Standard_Integer aRankInMap = myIndexes->Value(myCurRank);
1014   return mystored.FindFromIndex (aRankInMap).Entity;
1015 }
1016
1017 //=======================================================================
1018 // function : ActiveOwners
1019 // purpose  : Returns the list of active entity owners
1020 //=======================================================================
1021 void SelectMgr_ViewerSelector::ActiveOwners (NCollection_List<Handle(SelectMgr_EntityOwner)>& theOwners) const
1022 {
1023   for (SelectMgr_MapOfObjectSensitivesIterator anIter (myMapOfObjectSensitives); anIter.More(); anIter.Next())
1024   {
1025     const Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = anIter.Value();
1026     const Standard_Integer anEntitiesNb = anEntitySet->Size();
1027     for (Standard_Integer anIdx = 0; anIdx < anEntitiesNb; ++anIdx)
1028     {
1029       const Handle(SelectMgr_SensitiveEntity)& aSensitive = anEntitySet->GetSensitiveById (anIdx);
1030       if (aSensitive->IsActiveForSelection())
1031       {
1032         theOwners.Append (aSensitive->BaseSensitive()->OwnerId());
1033       }
1034     }
1035   }
1036 }
1037
1038 //=======================================================================
1039 //function : AllowOverlapDetection
1040 //purpose  : Sets the detection type: if theIsToAllow is false,
1041 //           only fully included sensitives will be detected, otherwise
1042 //           the algorithm will mark both included and overlapped entities
1043 //           as matched
1044 //=======================================================================
1045 void SelectMgr_ViewerSelector::AllowOverlapDetection (const Standard_Boolean theIsToAllow)
1046 {
1047   mySelectingVolumeMgr.AllowOverlapDetection (theIsToAllow);
1048 }