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