modernize depth sorting code
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
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 |