Skip to content

modernize depth sorting code

Burlen Loring requested to merge bloring/vtk:depth_sort_updates into master

modernize depth sorting code

The following improvements were made to vtkDepthSortPolyData:

  • transfrom GetCell to GetCellPoints. Building the cells one by one is expensive and we only need points to determine the depth. We can also then access the points in place.
  • transform qsort to std::sort. Comparisons in std::sort get inlined so std::sort is much faster. I also reduced the overhead of swaps by using a functor so that only cell id is swapped.
  • use templates to deal with point types instead of going through virtual GetValue API that converts them to double.
  • restructure depth computations so that they can be vectorized by the compiler.
  • I added a Cxx test to improve test coverage of the various sorting modes supported by this class.

The following improvements were made to vtkPolyData and vtkCellTypes:

  • move the non-virtual impementations of GetCellPoints to the header to improve compiler optimization.
  • add non-virtual GetCell method and also make it inline
  • fix an issue in cell types where the MaxId is not set correctly when you pass in pre-built arrays

In tests the improved depth sort is ~ 3 x faster when sorting by first point and cell bounds, and ~ 2 x faster when sorting by parametric center. The tests made use of a ~ 8.1M cell iso-surface computed from a cosmology simulation, and gcc 4.9.2 compiled with -Wall -Wextra -DNDEBUG -Ofast -march=native -mavx -ffast-math

depth_sort_speedup

code point bounds param
old 2.58 sec 3.05 sec 3.19 sec
new 0.82 sec 1.02 sec 1.65 sec
speed up 3.14 x 2.98 x 1.93 x

Merge request reports