Redesigned selection in OCCT 6.9.0

One of the most breaking changes in visualization component in OCCT 6.9.0 is complete reconsideration of selection mechanism. The new algorithm is designed to improve performance of dynamic selection of complex scenes by using effective 3D acceleration structures which are built only once and are autonomous from the camera.

Previous implementation

In earlier OCCT versions, selection structures were dependent from camera changes, e.g. each rotation or translation resulted in a complete re-projection of 2D selection primitives. Thus, for processing complex cases, such as fine-tessellated shapes or scenes with over 100K objects, re-projection turned into a significantly heavy operation. In order to eliminate this bottleneck, new efficient algorithm using 3D primitives for overlap detection was implemented.

New approach

The concept of new selection algorithm is to search for overlap with candidate sensitives through traverse of acceleration structure. The speedup structure used in new selection’s implementation is bounding volume hierarchy (BVH) - a tree on a set of geometric objects wrapped in bounding volumes. To account for the peculiarities of OCCT architecture and to minimize rebuilding of data structures, 3-level BVH tree was implemented:

Selection algorithm now starts from calculation of a frustum which will be tested for overlap or inclusion with each sensitive. For point or rectangular selection the base of the frustum is a rectangle built in conformity with pixel tolerance or sizes of user-defined area correspondingly. For polyline selection, the polygon defined by constructed line is triangulated and each triangle is used as the base for its own frustum. When frustum is created, algorithm passes to traverse of trees hierarchy starting from the 1st level BVH in SelectMgr_ViewerSelector::TraverseSensitives() method.

The main principle of BVH selection is that there is no need to update selection structure once it was built (except cases when entities and objects were recomputed, of course).
Therefore, location transformations are now applied to selecting frustums during traverse instead of direct re-projection of entities. Moreover, new selection mechanism is robust to manipulations with camera due to selecting volume is calculated in conformity with current view frustum.

Performance comparison

Regarding to performance of BVH selection in comparison to earlier versions of OCCT, several tests were run to estimate the result. The following table contains brief description of test scenes:

Improvements

Time measurements show significant advantage of BVH usage in all test cases for selection of static (e.g. selection primitives in OCCT 6.8.0 are already projected according to the current camera position) scenes. Moreover, the benefit of new selection grows stronger when the object is selected right after camera rotation.

Table 1: Comparison of selection times with ready-to-use selection structures. Selection time means average time of StdSelect_VewerSelector3d::Pick method execution. The table shows significant performance boost in all test cases when BVH selection algorithm is used. The best time in pair is marked green.
Chart 1: These charts illustrate benefit from usage of BVH selection using data from Table 1.

Table 2: Comparison of 1st selection times right after camera translation and rotation. The table shows robustness of BVH selection to camera changes, meanwhile for OCCT 6.8.0 selection algorithm it takes time to re-project sensitive entities. The best time in the pair is marked green.

Chart 2: This chart illustrate benefit from usage of BVH selection using data from Table 2. As it is clear from the graphics, BVH selection shows a great performance reserve making it applicable to much more complex 3D scenes in the future and making application-level workarounds unnecessary. For example, in test case 4 where MeshVS_Mesh object is created, selection has become much faster without any extra fixes or modifications. In addition, new algorithm works perfectly with large amounts of complex connected objects; in OCCT 6.8.0 the latency is too big.

Pending problems

The first implementation of BVH selection has some known issues that will be resolved in the frames of continuous OCCT evolution. The figures below illustrate one of the remaining problems related to increased display time in case of many objects due to ineffectiveness in 2nd level BVH construction.

Table 3: Display time comparison. The table shows slight performance downgrade of BVH selection due to ineffectiveness in 2nd level BVH construction. Cells where performance downgrade was detected are marked red, cells where performance improvement was detected are marked green.
Chart 3: These charts illustrate that in most cases, performance downgrade of current implementation of BVH selection is within the limits of a certain possible error. The data from chart is taken from
Table 3. Another problem consists in increased time of the first picking due to non-optimal choice of 1st level BVH building algorithm.

Table 4: Comparison of 1st selection time. The following sequence of calls is meant by the 1st selection: the first call of method StdSelect_ViewerSelector3d::Pick() where SelectMgr_ViewerSelector::TraverseSensitives() method is called at the first time. All test data is assumed to be displayed and computed before these calls. The performance downgrade of BVH selection is the result of inefficiencies in 1st level BVH construction. Cells where performance downgrade was detected are marked red.

Chart 4: This chart illustrates performance downgrade of 1st selection time using data from Table 4.

Further improvements

Work on correction of remaining performance problems is already in progress and issues described will be fixed within OCCT issue #26195. Please note that in case of customization of selection in user applications it will require porting as it is described in release notes. OCCT development team will be glad to receive feedback that will help in selection algorithm's improvement from the community members. Stay tuned, we will report selection development progress in this thread.

UPDATE

OCCT 6.9.1 release handles performance degradation issues in several use cases mentioned in the article's chapter "Pending problems".