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