Visualization - optimize selection algorithms

Current implementation of selection algorithms has some inefficiencies which can lead to performance degradation.

1) Select3D_SensitiveTriangulation::overlapsElement(...) performs transformation of every triangle in the set. Instead of this, it is necessary to transform frustum (only once) before processing triangles set.

2) Frustum construction is inefficient. For example, in the SelectMgr_RectangularFrustum::Build(...) method, frustum normals are computed, and after that frustum edges are computed. Therefore, edges are computed twice. It is better to compute edges and use them for computation of normals. Another point is the use of

  SelectMgr_Vec3 aDimensions[3] =
  {
    SelectMgr_Vec3 (1.0, 0.0, 0.0),
    SelectMgr_Vec3 (0.0, 1.0, 0.0),
    SelectMgr_Vec3 (0.0, 0.0, 1.0)
  };

.....

  for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
  {
    Standard_Real aProjection = DOT (aDimensions[aDim], myVertices[aVertIdx]);
    aMax = Max (aProjection, aMax);
    aMin = Min (aProjection, aMin);
  }

This code is overkilled because in this case:

  DOT (aDimensions[aDim], myVertices[aVertIdx]) == myVertices[aVertIdx][aDim]

Projecting frustum on plane normals is also inefficient:

  for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < 6; ++aPlaneIdx)
  {
    Standard_Real aMax = -DBL_MAX;
    Standard_Real aMin = DBL_MAX;
    const SelectMgr_Vec3 aPlane = myPlanes[aPlaneIdx];
    for (Standard_Integer aVertIdx = 0; aVertIdx < 8; ++aVertIdx)
    {
      Standard_Real aProjection = DOT (aPlane, myVertices[aVertIdx]);
      aMax = Max (aMax, aProjection);
      aMin = Min (aMin, aProjection);
    }
    myMaxVertsProjections[aPlaneIdx] = aMax;
    myMinVertsProjections[aPlaneIdx] = aMin;
  }

In case of ortho frustum checking all 6 normals is redundant. Moreover, instead of projecting all 8 vertices we can use only 2 vertices which lie on appropriate diagonal of the box.

3) In SelectMgr_RectangularFrustum::Build (const gp_Pnt2d &thePoint) and SelectMgr_RectangularFrustum::Build (const gp_Pnt2d& theMinPnt, const gp_Pnt2d& theMaxPnt) the code is duplicated. Please redesign it to share common build function.

4) The above remaks also applicable to SelectMgr_RectangularFrustum::Transform (const gp_Trsf& theTrsf). This method also uses redundant SelectMgr_Vec3 aDimensions[3] and computes normals before edges.

5) Another point in SelectMgr_RectangularFrustum::Transform(...) is related to normal computation. It is not necessary to re-compute them from scratch. You simply need to transform normals into new space. Please note, that normals are transformed with inversed transposed matrix. These optimization are very important because frustum transformatioans are used widely. Please check current performance of this method and its performance after optimizations (e.g., by calling this single method 1000 000 times). Please check another possible performance issues by using profiler.

6) Remove macroses like DISTANCE (...), DOT(...) and use member fucntions of SelectMgr_Vec3 class.

7) Revise a set of SelectMgr_RectangularFrustum::Overlaps(...) methods. Some of them look redundant, and some of them are not compatible. E.g.
  
  Overlaps (const SelectMgr_Vec3& theBoxMin,
            const SelectMgr_Vec3& theBoxMax,
            Standard_Boolean* theInside)

  Overlaps (const BVH_Box<Standard_Real, 3>& theBox,
            Standard_Real& theDepth)

The following method should have analog without theDepth parameter (can be used in many cases):

   Overlaps (const gp_Pnt& thePnt,
             Standard_Real& theDepth)

8) Consider the use of BVH binned builder only along main axis in Select3D_SensitiveSet. And is absolutely necessary to decrease a number of bins in both Select3D_SensitiveSet and SelectMgr_SensitiveEntitySet. Consider 4-8 bins per node. Compare performance and build times.

9) Use NCollection_IndexedMap::Swap method instead of its emulation via 3 Substitute() methods.

10) Switch from double tolerances to integer pixel tolerance and eliminate dependence from type of sensitive entity in frustum cache map in SelectMgr_ViewerSelector.