[occt.git] / src / SelectMgr / SelectMgr_ViewerSelector.cxx

// Created on: 1995-02-15
// Created by: Roberc Coublanc
// Copyright (c) 1995-1999 Matra Datavision
// Copyright (c) 1999-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#include <SelectMgr_ViewerSelector.hxx>

#include <BVH_Tree.hxx>
#include <gp_GTrsf.hxx>
#include <gp_Pnt.hxx>
#include <OSD_Environment.hxx>
#include <Precision.hxx>
#include <Select3D_SensitiveEntity.hxx>
#include <SelectBasics_PickResult.hxx>
#include <SelectMgr_EntityOwner.hxx>
#include <SelectMgr_SortCriterion.hxx>
#include <SelectMgr_SensitiveEntitySet.hxx>
#include <TColStd_Array1OfInteger.hxx>
#include <TCollection_AsciiString.hxx>
#include <TColStd_HArray1OfInteger.hxx>
#include <TColStd_ListOfInteger.hxx>

#include <algorithm>

IMPLEMENT_STANDARD_RTTIEXT(SelectMgr_ViewerSelector, Standard_Transient)

namespace {
  // Comparison operator for sorting selection results
  class CompareResults
  {
  public:
   
    CompareResults (const SelectMgr_IndexedDataMapOfOwnerCriterion& aMapOfCriterion)
      : myMapOfCriterion (aMapOfCriterion)
    {
    }

    Standard_Boolean operator() (Standard_Integer theLeft, Standard_Integer theRight) const
    {
      return myMapOfCriterion.FindFromIndex(theLeft) > myMapOfCriterion.FindFromIndex(theRight);
    }

  private:
    void operator = (const CompareResults&);

  private:
    const SelectMgr_IndexedDataMapOfOwnerCriterion&  myMapOfCriterion;
  };

  static const Graphic3d_Mat4d SelectMgr_ViewerSelector_THE_IDENTITY_MAT;
}

//=======================================================================
// function : updatePoint3d
// purpose  :
//=======================================================================
void SelectMgr_ViewerSelector::updatePoint3d (SelectMgr_SortCriterion& theCriterion,
                                              const SelectBasics_PickResult& thePickResult,
                                              const Handle(Select3D_SensitiveEntity)& theEntity,
                                              const gp_GTrsf& theInversedTrsf,
                                              const SelectMgr_SelectingVolumeManager& theMgr) const
{
  if (theMgr.GetActiveSelectionType() != SelectMgr_SelectingVolumeManager::Point)
  {
    return;
  }

  if (thePickResult.HasPickedPoint())
  {
    theCriterion.Point = thePickResult.PickedPoint();
  }
  else if (!thePickResult.IsValid())
  {
    theCriterion.Point = thePickResult.PickedPoint();
    return;
  }
  else
  {
    theCriterion.Point = theMgr.DetectedPoint (theCriterion.Depth);
  }

  gp_GTrsf anInvTrsf = theInversedTrsf;
  if (theCriterion.Entity->HasInitLocation())
  {
    anInvTrsf = theCriterion.Entity->InvInitLocation() * anInvTrsf;
  }
  if (anInvTrsf.Form() != gp_Identity)
  {
    anInvTrsf.Inverted().Transforms (theCriterion.Point.ChangeCoord());
  }

  if (mySelectingVolumeMgr.Camera().IsNull())
  {
    theCriterion.Tolerance = theEntity->SensitivityFactor() / 33.0;
  }
  else if (mySelectingVolumeMgr.Camera()->IsOrthographic())
  {
    theCriterion.Tolerance = myCameraScale * theEntity->SensitivityFactor();
  }
  else
  {
    const Standard_Real aDistFromEye = Abs ((theCriterion.Point.XYZ() - myCameraEye.XYZ()).Dot (myCameraDir.XYZ()));
    theCriterion.Tolerance = aDistFromEye * myCameraScale * theEntity->SensitivityFactor();
  }
}

//==================================================
// Function: Initialize
// Purpose :
//==================================================
SelectMgr_ViewerSelector::SelectMgr_ViewerSelector():
preferclosest(Standard_True),
myToUpdateTolerance (Standard_True),
myCameraScale (1.0),
myCurRank (0),
myIsLeftChildQueuedFirst (Standard_False),
myEntityIdx (0)
{
  myEntitySetBuilder = new BVH_BinnedBuilder<Standard_Real, 3, 4> (BVH_Constants_LeafNodeSizeSingle, BVH_Constants_MaxTreeDepth, Standard_True);
}

//==================================================
// Function: Activate
// Purpose :
//==================================================
void SelectMgr_ViewerSelector::Activate (const Handle(SelectMgr_Selection)& theSelection)
{
  for (NCollection_Vector<Handle(SelectMgr_SensitiveEntity)>::Iterator aSelEntIter (theSelection->Entities()); aSelEntIter.More(); aSelEntIter.Next())
  {
    aSelEntIter.Value()->SetActiveForSelection();
  }

  if (theSelection->GetSelectionState() != SelectMgr_SOS_Activated)
  {
    theSelection->SetSelectionState (SelectMgr_SOS_Activated);

    myTolerances.Add (theSelection->Sensitivity());
    myToUpdateTolerance = Standard_True;
  }
}

//==================================================
// Function: Deactivate
// Purpose :
//==================================================
void SelectMgr_ViewerSelector::Deactivate (const Handle(SelectMgr_Selection)& theSelection)
{
  for (NCollection_Vector<Handle(SelectMgr_SensitiveEntity)>::Iterator aSelEntIter (theSelection->Entities()); aSelEntIter.More(); aSelEntIter.Next())
  {
    aSelEntIter.Value()->ResetSelectionActiveStatus();
  }

  if (theSelection->GetSelectionState() == SelectMgr_SOS_Activated)
  {
    theSelection->SetSelectionState (SelectMgr_SOS_Deactivated);

    myTolerances.Decrement (theSelection->Sensitivity());
    myToUpdateTolerance = Standard_True;
  }
}

//==================================================
// Function: Clear
// Purpose :
//==================================================
void SelectMgr_ViewerSelector::Clear()
{
  mystored.Clear();
}

//=======================================================================
// function: isToScaleFrustum
// purpose : Checks if the entity given requires to scale current selecting frustum
//=======================================================================
Standard_Boolean SelectMgr_ViewerSelector::isToScaleFrustum (const Handle(Select3D_SensitiveEntity)& theEntity)
{
  return mySelectingVolumeMgr.GetActiveSelectionType() == SelectMgr_SelectingVolumeManager::Point
    && sensitivity (theEntity) < myTolerances.Tolerance();
}

//=======================================================================
// function: sensitivity
// purpose : In case if custom tolerance is set, this method will return sum of entity
//           sensitivity and custom tolerance.
//=======================================================================
Standard_Integer SelectMgr_ViewerSelector::sensitivity (const Handle(Select3D_SensitiveEntity)& theEntity) const
{
  return myTolerances.IsCustomTolSet() ?
    theEntity->SensitivityFactor() + myTolerances.CustomTolerance() : theEntity->SensitivityFactor();
}

//=======================================================================
// function: checkOverlap
// purpose : Internal function that checks if a particular sensitive
//           entity theEntity overlaps current selecting volume precisely
//=======================================================================
void SelectMgr_ViewerSelector::checkOverlap (const Handle(Select3D_SensitiveEntity)& theEntity,
                                             const gp_GTrsf& theInversedTrsf,
                                             SelectMgr_SelectingVolumeManager& theMgr)
{
  const Handle(SelectMgr_EntityOwner)& anOwner = theEntity->OwnerId();
  Handle(SelectMgr_SelectableObject) aSelectable;
  Standard_Boolean toRestoresViewClipEnabled = Standard_False;
  if (!anOwner.IsNull())
  {
    aSelectable = anOwner->Selectable();
  }
  if (!aSelectable.IsNull())
  {
    if (!aSelectable->ClipPlanes().IsNull()
      && aSelectable->ClipPlanes()->ToOverrideGlobal())
    {
      theMgr.SetViewClippingEnabled (Standard_False);
      toRestoresViewClipEnabled = Standard_True;
    }
    else if (!aSelectable->TransformPersistence().IsNull())
    {
      if (aSelectable->TransformPersistence()->IsZoomOrRotate()
      && !theMgr.ViewClipping().IsNull())
      {
        // Zoom/rotate persistence object lives in two worlds at the same time.
        // Global clipping planes can not be trivially applied without being converted
        // into local space of transformation persistence object.
        // As more simple alternative - just clip entire object by its anchor point defined in the world space.
        const Handle(Graphic3d_SequenceOfHClipPlane)& aViewPlanes = theMgr.ViewClipping();

        const gp_Pnt anAnchor = aSelectable->TransformPersistence()->AnchorPoint();
        for (Graphic3d_SequenceOfHClipPlane::Iterator aPlaneIt (*aViewPlanes); aPlaneIt.More(); aPlaneIt.Next())
        {
          const Handle(Graphic3d_ClipPlane)& aPlane = aPlaneIt.Value();
          if (!aPlane->IsOn())
          {
            continue;
          }

          const Graphic3d_Vec4d aCheckPnt (anAnchor.X(), anAnchor.Y(), anAnchor.Z(), 1.0);
          if (aPlane->ProbePoint (aCheckPnt) == Graphic3d_ClipState_Out)
          {
            return;
          }
        }
      }

      theMgr.SetViewClippingEnabled (Standard_False);
      toRestoresViewClipEnabled = Standard_True;
    }
  }

  SelectBasics_PickResult aPickResult;
  const Standard_Boolean isMatched = theEntity->Matches(theMgr, aPickResult);
  if (toRestoresViewClipEnabled)
  {
    theMgr.SetViewClippingEnabled (Standard_True);
  }

  if (!isMatched
    || anOwner.IsNull())
  {
    return;
  }

  if (HasDepthClipping (anOwner)
  && !aSelectable.IsNull()
  &&  theMgr.GetActiveSelectionType() == SelectMgr_SelectingVolumeManager::Point)
  {
    Standard_Boolean isClipped = mySelectingVolumeMgr.IsClipped (*aSelectable->ClipPlanes(),
                                                                  aPickResult.Depth());
    if (isClipped)
      return;
  }

  SelectMgr_SortCriterion aCriterion;
  myZLayerOrderMap.Find (!aSelectable.IsNull() ? aSelectable->ZLayer() : Graphic3d_ZLayerId_Default, aCriterion.ZLayerPosition);
  aCriterion.Entity    = theEntity;
  aCriterion.Priority  = anOwner->Priority();
  aCriterion.Depth     = aPickResult.Depth();
  aCriterion.MinDist   = aPickResult.DistToGeomCenter();
  aCriterion.ToPreferClosest = preferclosest;

  if (SelectMgr_SortCriterion* aPrevCriterion = mystored.ChangeSeek (anOwner))
  {
    ++aPrevCriterion->NbOwnerMatches;
    aCriterion.NbOwnerMatches = aPrevCriterion->NbOwnerMatches;
    if (theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Box)
    {
      if (aCriterion > *aPrevCriterion)
      {
        updatePoint3d (aCriterion, aPickResult, theEntity, theInversedTrsf, theMgr);
        *aPrevCriterion = aCriterion;
      }
    }
  }
  else
  {
    aCriterion.NbOwnerMatches = 1;
    updatePoint3d (aCriterion, aPickResult, theEntity, theInversedTrsf, theMgr);
    mystored.Add (anOwner, aCriterion);
  }
}

//=======================================================================
// function: computeFrustum
// purpose : Internal function that checks if a current selecting frustum
//           needs to be scaled and transformed for the entity and performs
//           necessary calculations
//=======================================================================
void SelectMgr_ViewerSelector::computeFrustum (const Handle(Select3D_SensitiveEntity)& theEnt,
                                               const SelectMgr_SelectingVolumeManager&     theMgr,
                                               const gp_GTrsf&                             theInvTrsf,
                                               SelectMgr_FrustumCache&                     theCachedMgrs,
                                               SelectMgr_SelectingVolumeManager&           theResMgr)
{
  Standard_Integer aScale = isToScaleFrustum (theEnt) ? sensitivity (theEnt) : 1;
  const gp_GTrsf aTrsfMtr = theEnt->HasInitLocation() ? theEnt->InvInitLocation() * theInvTrsf : theInvTrsf;
  const Standard_Boolean toScale = aScale != 1;
  const Standard_Boolean toTransform = aTrsfMtr.Form() != gp_Identity;
  if (toScale && toTransform)
  {
    theResMgr = theMgr.ScaleAndTransform (aScale, aTrsfMtr, NULL);
  }
  else if (toScale)
  {
    if (!theCachedMgrs.IsBound (aScale))
    {
      theCachedMgrs.Bind (aScale, theMgr.ScaleAndTransform (aScale, gp_Trsf(), NULL));
    }
    theResMgr = theCachedMgrs.Find (aScale);
  }
  else if (toTransform)
  {
    theResMgr = theMgr.ScaleAndTransform (1, aTrsfMtr, NULL);
  }
}

//=======================================================================
// function: traverseObject
// purpose : Internal function that checks if there is possible overlap
//           between some entity of selectable object theObject and
//           current selecting volume
//=======================================================================
void SelectMgr_ViewerSelector::traverseObject (const Handle(SelectMgr_SelectableObject)& theObject,
                                               const SelectMgr_SelectingVolumeManager& theMgr,
                                               const Handle(Graphic3d_Camera)& theCamera,
                                               const Graphic3d_Mat4d& theProjectionMat,
                                               const Graphic3d_Mat4d& theWorldViewMat,
                                               const Standard_Integer theViewportWidth,
                                               const Standard_Integer theViewportHeight)
{
  Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = myMapOfObjectSensitives.ChangeFind (theObject);
  if (anEntitySet->Size() == 0)
  {
    return;
  }

  const opencascade::handle<BVH_Tree<Standard_Real, 3> >& aSensitivesTree = anEntitySet->BVH();
  gp_GTrsf aInversedTrsf;
  if (theObject->HasTransformation() || !theObject->TransformPersistence().IsNull())
  {
    if (theObject->TransformPersistence().IsNull())
    {
      aInversedTrsf = theObject->InversedTransformation();
    }
    else
    {
      gp_GTrsf aTPers;
      Graphic3d_Mat4d aMat = theObject->TransformPersistence()->Compute (theCamera, theProjectionMat, theWorldViewMat, theViewportWidth, theViewportHeight);

      aTPers.SetValue (1, 1, aMat.GetValue (0, 0));
      aTPers.SetValue (1, 2, aMat.GetValue (0, 1));
      aTPers.SetValue (1, 3, aMat.GetValue (0, 2));
      aTPers.SetValue (2, 1, aMat.GetValue (1, 0));
      aTPers.SetValue (2, 2, aMat.GetValue (1, 1));
      aTPers.SetValue (2, 3, aMat.GetValue (1, 2));
      aTPers.SetValue (3, 1, aMat.GetValue (2, 0));
      aTPers.SetValue (3, 2, aMat.GetValue (2, 1));
      aTPers.SetValue (3, 3, aMat.GetValue (2, 2));
      aTPers.SetTranslationPart (gp_XYZ (aMat.GetValue (0, 3), aMat.GetValue (1, 3), aMat.GetValue (2, 3)));

      aInversedTrsf = (aTPers * gp_GTrsf (theObject->Transformation())).Inverted();
    }
  }

  SelectMgr_SelectingVolumeManager aMgr = aInversedTrsf.Form() != gp_Identity
                                        ? theMgr.ScaleAndTransform (1, aInversedTrsf, NULL)
                                        : theMgr;

  SelectMgr_FrustumCache aScaledTrnsfFrustums;

  Standard_Integer aNode = 0; // a root node
  if (!aMgr.Overlaps (aSensitivesTree->MinPoint (0),
                      aSensitivesTree->MaxPoint (0)))
  {
    return;
  }

  const Standard_Integer aFirstStored = mystored.Extent() + 1;

  Standard_Integer aStack[BVH_Constants_MaxTreeDepth];
  Standard_Integer aHead = -1;
  for (;;)
  {
    if (!aSensitivesTree->IsOuter (aNode))
    {
      const Standard_Integer aLeftChildIdx  = aSensitivesTree->Child<0> (aNode);
      const Standard_Integer aRightChildIdx = aSensitivesTree->Child<1> (aNode);
      const Standard_Boolean isLeftChildIn  =  aMgr.Overlaps (aSensitivesTree->MinPoint (aLeftChildIdx),
                                                              aSensitivesTree->MaxPoint (aLeftChildIdx));
      const Standard_Boolean isRightChildIn = aMgr.Overlaps (aSensitivesTree->MinPoint (aRightChildIdx),
                                                             aSensitivesTree->MaxPoint (aRightChildIdx));
      if (isLeftChildIn
          && isRightChildIn)
      {
        aNode = aLeftChildIdx;
        ++aHead;
        aStack[aHead] = aRightChildIdx;
      }
      else if (isLeftChildIn
        || isRightChildIn)
      {
        aNode = isLeftChildIn ? aLeftChildIdx : aRightChildIdx;
      }
      else
      {
        if (aHead < 0)
        {
          break;
        }

        aNode = aStack[aHead];
        --aHead;
      }
    }
    else
    {
      Standard_Integer aStartIdx = aSensitivesTree->BegPrimitive (aNode);
      Standard_Integer anEndIdx = aSensitivesTree->EndPrimitive (aNode);
      for (Standard_Integer anIdx = aStartIdx; anIdx <= anEndIdx; ++anIdx)
      {
        const Handle(SelectMgr_SensitiveEntity)& aSensitive = anEntitySet->GetSensitiveById (anIdx);
        if (aSensitive->IsActiveForSelection())
        {
          const Handle(Select3D_SensitiveEntity)& anEnt = aSensitive->BaseSensitive();
          SelectMgr_SelectingVolumeManager aTmpMgr = aMgr;
          computeFrustum (anEnt, theMgr, aInversedTrsf, aScaledTrnsfFrustums, aTmpMgr);
          checkOverlap (anEnt, aInversedTrsf, aTmpMgr);
        }
      }
      if (aHead < 0)
      {
        break;
      }

      aNode = aStack[aHead];
      --aHead;
    }
  }

  // in case of Box/Polyline selection - keep only Owners having all Entities detected
  if (mySelectingVolumeMgr.IsOverlapAllowed()
  || (theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Box
   && theMgr.GetActiveSelectionType() != SelectBasics_SelectingVolumeManager::Polyline))
  {
    return;
  }

  for (Standard_Integer aStoredIter = mystored.Extent(); aStoredIter >= aFirstStored; --aStoredIter)
  {
    const SelectMgr_SortCriterion& aCriterion = mystored.FindFromIndex (aStoredIter);
    const Handle(SelectMgr_EntityOwner)& anOwner = aCriterion.Entity->OwnerId();
    Standard_Integer aNbOwnerEntities = 0;
    for (SelectMgr_IndexedMapOfHSensitive::Iterator aSensIter (anEntitySet->Sensitives()); aSensIter.More(); aSensIter.Next())
    {
      if (aSensIter.Value()->BaseSensitive()->OwnerId() == anOwner)
      {
        if (++aNbOwnerEntities > aCriterion.NbOwnerMatches)
        {
          // Remove from index map.
          // Considering NCollection_IndexedDataMap implementation, the values for lower indexes will not be modified.
          // Hence, just keep iterating in backward direction.
          mystored.RemoveFromIndex (aStoredIter);
          break;
        }
      }
    }
  }
}

//=======================================================================
// function: TraverseSensitives
// purpose : Traverses BVH containing all added selectable objects and
//           finds candidates for further search of overlap
//=======================================================================
void SelectMgr_ViewerSelector::TraverseSensitives()
{
  mystored.Clear();

  Standard_Integer aWidth;
  Standard_Integer aHeight;
  mySelectingVolumeMgr.WindowSize (aWidth, aHeight);
  mySelectableObjects.UpdateBVH (mySelectingVolumeMgr.Camera(),
                                 mySelectingVolumeMgr.ProjectionMatrix(),
                                 mySelectingVolumeMgr.WorldViewMatrix(),
                                 mySelectingVolumeMgr.WorldViewProjState(),
                                 aWidth, aHeight);
  const Handle(Graphic3d_Camera)& aCamera = mySelectingVolumeMgr.Camera();
  if (!aCamera.IsNull())
  {
    myCameraEye = aCamera->Eye().XYZ();
    myCameraDir = aCamera->Direction().XYZ();
    myCameraScale = aCamera->IsOrthographic()
                  ? aCamera->Scale()
                  : 2.0 * Tan (aCamera->FOVy() * M_PI / 360.0);
    const double aPixelSize = Max (1.0 / aWidth, 1.0 / aHeight);
    myCameraScale *= aPixelSize;
  }

  for (Standard_Integer aBVHSetIt = 0; aBVHSetIt < SelectMgr_SelectableObjectSet::BVHSubsetNb; ++aBVHSetIt)
  {
    SelectMgr_SelectableObjectSet::BVHSubset aBVHSubset =
      static_cast<SelectMgr_SelectableObjectSet::BVHSubset> (aBVHSetIt);

    if (mySelectableObjects.IsEmpty (aBVHSubset))
    {
      continue;
    }

    gp_GTrsf aTFrustum;

    SelectMgr_SelectingVolumeManager aMgr (Standard_False);

    // for 2D space selection transform selecting volumes to perform overap testing
    // directly in camera's eye space omitting the camera position, which is not
    // needed there at all
    if (aBVHSubset == SelectMgr_SelectableObjectSet::BVHSubset_2dPersistent)
    {
      const Graphic3d_Mat4d& aMat = mySelectingVolumeMgr.WorldViewMatrix();
      aTFrustum.SetValue (1, 1, aMat.GetValue (0, 0));
      aTFrustum.SetValue (1, 2, aMat.GetValue (0, 1));
      aTFrustum.SetValue (1, 3, aMat.GetValue (0, 2));
      aTFrustum.SetValue (2, 1, aMat.GetValue (1, 0));
      aTFrustum.SetValue (2, 2, aMat.GetValue (1, 1));
      aTFrustum.SetValue (2, 3, aMat.GetValue (1, 2));
      aTFrustum.SetValue (3, 1, aMat.GetValue (2, 0));
      aTFrustum.SetValue (3, 2, aMat.GetValue (2, 1));
      aTFrustum.SetValue (3, 3, aMat.GetValue (2, 2));
      aTFrustum.SetTranslationPart (gp_XYZ (aMat.GetValue (0, 3), aMat.GetValue (1, 3), aMat.GetValue (2, 3)));

      // define corresponding frustum builder parameters
      Handle(SelectMgr_FrustumBuilder) aBuilder = new SelectMgr_FrustumBuilder();
      aBuilder->SetProjectionMatrix (mySelectingVolumeMgr.ProjectionMatrix());
      aBuilder->SetWorldViewMatrix (SelectMgr_ViewerSelector_THE_IDENTITY_MAT);
      aBuilder->SetWindowSize (aWidth, aHeight);
      aMgr = mySelectingVolumeMgr.ScaleAndTransform (1, aTFrustum, aBuilder);
    }
    else
    {
      aMgr = mySelectingVolumeMgr;
    }

    const Graphic3d_Mat4d& aProjectionMat   = mySelectingVolumeMgr.ProjectionMatrix();
    const Graphic3d_Mat4d& aWorldViewMat    = aBVHSubset != SelectMgr_SelectableObjectSet::BVHSubset_2dPersistent
                                            ? mySelectingVolumeMgr.WorldViewMatrix()
                                            : SelectMgr_ViewerSelector_THE_IDENTITY_MAT;

    const opencascade::handle<BVH_Tree<Standard_Real, 3> >& aBVHTree = mySelectableObjects.BVH (aBVHSubset);

    Standard_Integer aNode = 0;
    if (!aMgr.Overlaps (aBVHTree->MinPoint (0), aBVHTree->MaxPoint (0)))
    {
      continue;
    }

    Standard_Integer aStack[BVH_Constants_MaxTreeDepth];
    Standard_Integer aHead = -1;
    for (;;)
    {
      if (!aBVHTree->IsOuter (aNode))
      {
        const Standard_Integer aLeftChildIdx  = aBVHTree->Child<0> (aNode);
        const Standard_Integer aRightChildIdx = aBVHTree->Child<1> (aNode);
        const Standard_Boolean isLeftChildIn  =
          aMgr.Overlaps (aBVHTree->MinPoint (aLeftChildIdx), aBVHTree->MaxPoint (aLeftChildIdx));
        const Standard_Boolean isRightChildIn =
          aMgr.Overlaps (aBVHTree->MinPoint (aRightChildIdx), aBVHTree->MaxPoint (aRightChildIdx));
        if (isLeftChildIn
          && isRightChildIn)
        {
          aNode = aLeftChildIdx;
          ++aHead;
          aStack[aHead] = aRightChildIdx;
        }
        else if (isLeftChildIn
          || isRightChildIn)
        {
          aNode = isLeftChildIn ? aLeftChildIdx : aRightChildIdx;
        }
        else
        {
          if (aHead < 0)
          {
            break;
          }

          aNode = aStack[aHead];
          --aHead;
        }
      }
      else
      {
        Standard_Integer aStartIdx = aBVHTree->BegPrimitive (aNode);
        Standard_Integer anEndIdx  = aBVHTree->EndPrimitive (aNode);
        for (Standard_Integer anIdx = aStartIdx; anIdx <= anEndIdx; ++anIdx)
        {
          const Handle(SelectMgr_SelectableObject)& aSelectableObject =
            mySelectableObjects.GetObjectById (aBVHSubset, anIdx);

          traverseObject (aSelectableObject, aMgr, aCamera, aProjectionMat, aWorldViewMat, aWidth, aHeight);
        }
        if (aHead < 0)
        {
          break;
        }

        aNode = aStack[aHead];
        --aHead;
      }
    }
  }

  SortResult();
}

//==================================================
// Function: ClearPicked
// Purpose :
//==================================================
void SelectMgr_ViewerSelector::ClearPicked()
{
  mystored.Clear();
}

//==================================================
// Function: Picked
// Purpose :
//==================================================
Handle(SelectMgr_EntityOwner) SelectMgr_ViewerSelector::Picked() const
{
  const Standard_Integer aRankInMap = myIndexes->Value (myCurRank);
  const Handle(SelectMgr_EntityOwner)& anOwner = mystored.FindKey (aRankInMap);
  return anOwner;
}

//=======================================================================
//function : Picked
//purpose  :
//=======================================================================
Handle(SelectMgr_EntityOwner) SelectMgr_ViewerSelector::Picked (const Standard_Integer theRank) const
{
  if (theRank < 1 || theRank > NbPicked())
  {
    return Handle(SelectMgr_EntityOwner)();
  }

  const Standard_Integer anOwnerIdx = myIndexes->Value (theRank);
  const Handle(SelectMgr_EntityOwner)& aStoredOwner = mystored.FindKey (anOwnerIdx);
  return aStoredOwner;
}

//=======================================================================
//function : PickedData
//purpose  :
//=======================================================================
const SelectMgr_SortCriterion& SelectMgr_ViewerSelector::PickedData(const Standard_Integer theRank) const
{
  Standard_OutOfRange_Raise_if (theRank < 1 || theRank > NbPicked(), "SelectMgr_ViewerSelector::PickedData() out of range index");
  const Standard_Integer anOwnerIdx = myIndexes->Value (theRank);
  return mystored.FindFromIndex (anOwnerIdx);
}

//===================================================
//
//       INTERNAL METHODS ....
//
//==================================================

//==================================================
// Function: SetEntitySetBuilder
// Purpose :
//==================================================
void SelectMgr_ViewerSelector::SetEntitySetBuilder (const Handle(Select3D_BVHBuilder3d)& theBuilder)
{
  myEntitySetBuilder = theBuilder;
  for (SelectMgr_MapOfObjectSensitives::Iterator aSetIter (myMapOfObjectSensitives); aSetIter.More(); aSetIter.Next())
  {
    aSetIter.ChangeValue()->SetBuilder (myEntitySetBuilder);
  }
}

//==================================================
// Function: Contains
// Purpose :
//==================================================
Standard_Boolean SelectMgr_ViewerSelector::Contains (const Handle(SelectMgr_SelectableObject)& theObject) const
{
  return mySelectableObjects.Contains (theObject);
}

//==================================================
// Function: ActiveModes
// Purpose : return all the  modes with a given state for an object
//==================================================
Standard_Boolean SelectMgr_ViewerSelector::Modes (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
                                                  TColStd_ListOfInteger& theModeList,
                                                  const SelectMgr_StateOfSelection theWantedState) const
{
  Standard_Boolean hasActivatedStates = Contains (theSelectableObject);
  for (SelectMgr_SequenceOfSelection::Iterator aSelIter (theSelectableObject->Selections()); aSelIter.More(); aSelIter.Next())
  {
    if (theWantedState == SelectMgr_SOS_Any)
    {
      theModeList.Append (aSelIter.Value()->Mode());
    }
    else if (theWantedState == aSelIter.Value()->GetSelectionState())
    {
      theModeList.Append (aSelIter.Value()->Mode());
    }
  }

  return hasActivatedStates;
}

//==================================================
// Function: IsActive
// Purpose :
//==================================================
Standard_Boolean SelectMgr_ViewerSelector::IsActive (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
                                                     const Standard_Integer theMode) const
{
  if (!Contains (theSelectableObject))
    return Standard_False;

  const Handle(SelectMgr_Selection)& aSel = theSelectableObject->Selection (theMode);
  return !aSel.IsNull()
       && aSel->GetSelectionState() == SelectMgr_SOS_Activated;
}

//==================================================
// Function: IsInside
// Purpose :
//==================================================
Standard_Boolean SelectMgr_ViewerSelector::IsInside (const Handle(SelectMgr_SelectableObject)& theSelectableObject,
                                                     const Standard_Integer theMode) const
{
  if (!Contains (theSelectableObject))
    return Standard_False;

  const Handle(SelectMgr_Selection)& aSel = theSelectableObject->Selection (theMode);
  return !aSel.IsNull()
       && aSel->GetSelectionState() != SelectMgr_SOS_Unknown;
}


//=======================================================================
//function : Status
//purpose  :
//=======================================================================

SelectMgr_StateOfSelection SelectMgr_ViewerSelector::Status (const Handle(SelectMgr_Selection)& theSelection) const
{
  return theSelection->GetSelectionState();
}

//==================================================
// Function: Status
// Purpose : gives Information about selectors
//==================================================

TCollection_AsciiString SelectMgr_ViewerSelector::Status (const Handle(SelectMgr_SelectableObject)& theSelectableObject) const
{
  TCollection_AsciiString aStatus ("Status Object :\n\t");
  for (SelectMgr_SequenceOfSelection::Iterator aSelIter (theSelectableObject->Selections()); aSelIter.More(); aSelIter.Next())
  {
    if (aSelIter.Value()->GetSelectionState() != SelectMgr_SOS_Unknown)
    {
      aStatus = aStatus + "Mode " + TCollection_AsciiString (aSelIter.Value()->Mode()) + " present - "
              + (aSelIter.Value()->GetSelectionState() == SelectMgr_SOS_Activated ? " Active \n\t" : " Inactive \n\t");
    }
  }

  if (!Contains (theSelectableObject))
  {
    aStatus = aStatus + "Not Present in the selector\n\n";
  }

  return aStatus;
}

//=======================================================================
//function : SortResult
//purpose  :  there is a certain number of entities ranged by criteria
//            (depth, size, priority, mouse distance from borders or
//            CDG of the detected primitive. Parsing :
//             maximum priorities .
//             then a reasonable compromise between depth and distance...
// finally the ranges are stored in myindexes depending on the parsing.
// so, it is possible to only read
//=======================================================================
void SelectMgr_ViewerSelector::SortResult()
{
  if(mystored.IsEmpty()) return;

  const Standard_Integer anExtent = mystored.Extent();
  if(myIndexes.IsNull() || anExtent != myIndexes->Length())
    myIndexes = new TColStd_HArray1OfInteger (1, anExtent);

  TColStd_Array1OfInteger& anIndexArray = myIndexes->ChangeArray1();
  for (Standard_Integer anIndexIter = 1; anIndexIter <= anExtent; ++anIndexIter)
  {
    anIndexArray.SetValue (anIndexIter, anIndexIter);
  }
  std::sort (anIndexArray.begin(), anIndexArray.end(), CompareResults (mystored));
}

//=======================================================================
//function : HasDepthClipping
//purpose  : Stub
//=======================================================================
Standard_Boolean SelectMgr_ViewerSelector::HasDepthClipping (const Handle(SelectMgr_EntityOwner)& /*theOwner*/) const
{
  return Standard_False;
}

//=======================================================================
// function : AddSelectableObject
// purpose  : Adds new object to the map of selectable objects
//=======================================================================
void SelectMgr_ViewerSelector::AddSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
{
  if (!myMapOfObjectSensitives.IsBound (theObject))
  {
    mySelectableObjects.Append (theObject);
    Handle(SelectMgr_SensitiveEntitySet) anEntitySet = new SelectMgr_SensitiveEntitySet (myEntitySetBuilder);
    myMapOfObjectSensitives.Bind (theObject, anEntitySet);
  }
}

//=======================================================================
// function : AddSelectionToObject
// purpose  : Adds new selection to the object and builds its BVH tree
//=======================================================================
void SelectMgr_ViewerSelector::AddSelectionToObject (const Handle(SelectMgr_SelectableObject)& theObject,
                                                     const Handle(SelectMgr_Selection)& theSelection)
{
  if (Handle(SelectMgr_SensitiveEntitySet)* anEntitySet = myMapOfObjectSensitives.ChangeSeek (theObject))
  {
    (*anEntitySet)->Append (theSelection);
    (*anEntitySet)->BVH();
  }
  else
  {
    AddSelectableObject (theObject);
    AddSelectionToObject (theObject, theSelection);
  }
}

//=======================================================================
// function : MoveSelectableObject
// purpose  :
//=======================================================================
void SelectMgr_ViewerSelector::MoveSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
{
  mySelectableObjects.ChangeSubset (theObject);
}

//=======================================================================
// function : RemoveSelectableObject
// purpose  : Removes selectable object from map of selectable ones
//=======================================================================
void SelectMgr_ViewerSelector::RemoveSelectableObject (const Handle(SelectMgr_SelectableObject)& theObject)
{
  Handle(SelectMgr_SelectableObject) anObj = theObject;
  if (myMapOfObjectSensitives.UnBind (theObject))
  {
    mySelectableObjects.Remove (theObject);
  }
}

//=======================================================================
// function : RemoveSelectionOfObject
// purpose  : Removes selection of the object and marks its BVH tree
//            for rebuild
//=======================================================================
void SelectMgr_ViewerSelector::RemoveSelectionOfObject (const Handle(SelectMgr_SelectableObject)& theObject,
                                                        const Handle(SelectMgr_Selection)& theSelection)
{
  if (Handle(SelectMgr_SensitiveEntitySet)* anEntitySet = myMapOfObjectSensitives.ChangeSeek (theObject))
  {
    (*anEntitySet)->Remove (theSelection);
  }
}

//=======================================================================
// function : RebuildObjectsTree
// purpose  : Marks BVH of selectable objects for rebuild
//=======================================================================
void SelectMgr_ViewerSelector::RebuildObjectsTree (const Standard_Boolean theIsForce)
{
  mySelectableObjects.MarkDirty();

  if (theIsForce)
  {
    Standard_Integer aViewportWidth, aViewportHeight;
    mySelectingVolumeMgr.WindowSize (aViewportWidth, aViewportHeight);

    Standard_Integer aWidth;
    Standard_Integer aHeight;
    mySelectingVolumeMgr.WindowSize (aWidth, aHeight);
    mySelectableObjects.UpdateBVH (mySelectingVolumeMgr.Camera(),
                                   mySelectingVolumeMgr.ProjectionMatrix(),
                                   mySelectingVolumeMgr.WorldViewMatrix(),
                                   mySelectingVolumeMgr.WorldViewProjState(),
                                   aWidth, aHeight);
  }
}

//=======================================================================
// function : RebuildSensitivesTree
// purpose  : Marks BVH of sensitive entities of particular selectable
//            object for rebuild
//=======================================================================
void SelectMgr_ViewerSelector::RebuildSensitivesTree (const Handle(SelectMgr_SelectableObject)& theObject,
                                                      const Standard_Boolean theIsForce)
{
  if (!Contains (theObject))
    return;

  Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = myMapOfObjectSensitives.ChangeFind (theObject);
  anEntitySet->MarkDirty();

  if (theIsForce)
  {
    anEntitySet->BVH();
  }
}

//=======================================================================
// function : resetSelectionActivationStatus
// purpose  : Marks all added sensitive entities of all objects as
//            non-selectable
//=======================================================================
void SelectMgr_ViewerSelector::ResetSelectionActivationStatus()
{
  for (SelectMgr_MapOfObjectSensitivesIterator aSensitivesIter (myMapOfObjectSensitives); aSensitivesIter.More(); aSensitivesIter.Next())
  {
    Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = aSensitivesIter.ChangeValue();
    const Standard_Integer anEntitiesNb = anEntitySet->Size();
    for (Standard_Integer anIdx = 0; anIdx < anEntitiesNb; ++anIdx)
    {
      anEntitySet->GetSensitiveById (anIdx)->ResetSelectionActiveStatus();
    }
  }
}

//=======================================================================
// function : DetectedEntity
// purpose  : Returns sensitive entity that was detected during the
//            previous run of selection algorithm
//=======================================================================
const Handle(Select3D_SensitiveEntity)& SelectMgr_ViewerSelector::DetectedEntity() const
{
  const Standard_Integer aRankInMap = myIndexes->Value(myCurRank);
  return mystored.FindFromIndex (aRankInMap).Entity;
}

//=======================================================================
// function : ActiveOwners
// purpose  : Returns the list of active entity owners
//=======================================================================
void SelectMgr_ViewerSelector::ActiveOwners (NCollection_List<Handle(SelectMgr_EntityOwner)>& theOwners) const
{
  for (SelectMgr_MapOfObjectSensitivesIterator anIter (myMapOfObjectSensitives); anIter.More(); anIter.Next())
  {
    const Handle(SelectMgr_SensitiveEntitySet)& anEntitySet = anIter.Value();
    const Standard_Integer anEntitiesNb = anEntitySet->Size();
    for (Standard_Integer anIdx = 0; anIdx < anEntitiesNb; ++anIdx)
    {
      const Handle(SelectMgr_SensitiveEntity)& aSensitive = anEntitySet->GetSensitiveById (anIdx);
      if (aSensitive->IsActiveForSelection())
      {
        theOwners.Append (aSensitive->BaseSensitive()->OwnerId());
      }
    }
  }
}

//=======================================================================
//function : AllowOverlapDetection
//purpose  : Sets the detection type: if theIsToAllow is false,
//           only fully included sensitives will be detected, otherwise
//           the algorithm will mark both included and overlapped entities
//           as matched
//=======================================================================
void SelectMgr_ViewerSelector::AllowOverlapDetection (const Standard_Boolean theIsToAllow)
{
  mySelectingVolumeMgr.AllowOverlapDetection (theIsToAllow);
}