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