Unstable sorting of nodes in e.g. vtkColorTransferFunction

Development
1

Hi

I am working with a vtkColorTransferFunction with AllowDuplicateScalarsOn() and noticed after building it by repeated calls to AddRGBPoint() that the order comes out unexpected. This appears to result from the call to SortAndUpdateRange() in AddRHBPoint(), which in turn calls std::sort(). Since std::sort() does not necessarily preserve the order of equal elements, the points which are equal on the “x axis”, but with different colours, sometimes come out in a different order than the intended insertion. When performing a DeepCopy on the same function, the points can again come out in a different order, since the DeepCopy performs the iterated insertion again. The same behaviour was also found vtkPiecewiseFunction and could perhaps exist in more classes.

Suggestion: replace the call to std::sort() with std::stable_sort().

The suggestion is motivated by the following points:

  1. The current behaviour seems contradictory to allowing “duplicate points” in the first place.

  2. It seems counter-intuitive that DeepCopy would result in data that differs from the original.

  3. It seems counter-intuitive that insertion of a point in some x range would potentially scramble unrelated points found within a disjoint x range.

Please do correct me if there is some misunderstanding within the statements above. My use case along with a minimal example will be posted in a reply below.

Cheers!
Jesper

2

Our current use case is to construct a piece-wise constant vtkColorTransferFunction, which I achieve by adding duplicate points for any x value where the function changes value: i.e., going from a constant green interval to a constant red interval would require the two points (x, 0, 1, 0) and (x, 1, 0, 0). If these two points then change order, I end up with a function that instead changes smoothly from green to red over the supposedly red interval, and then reverts to green again at the start of the next interval.

Perhaps this is not the optimal way to construct a piece-wise function in VTK, so we are happy also for pointers towards more suitable classes, but might have no other options due to also wanting to incorporate other types of functions into the same vtkColorTransferFunction.

Small code example (unfortunately quite a few nodes included, since the sorting changes with e.g. total number of nodes):

    auto colorFunction = vtkSmartPointer<vtkColorTransferFunction>::New();
    colorFunction->AllowDuplicateScalarsOn();

    colorFunction->AddRGBPoint(0, 0, 0, 0);
    colorFunction->AddRGBPoint(0.5, 0, 0, 0);
    colorFunction->AddRGBPoint(0.5, 0, 1, 0);
    colorFunction->AddRGBPoint(0.7, 0, 1, 0);
    colorFunction->AddRGBPoint(0.7, 0, 0, 0);
    colorFunction->AddRGBPoint(0.8, 0, 0, 0);
    colorFunction->AddRGBPoint(0.8, 1, 0, 0);
    colorFunction->AddRGBPoint(1.0, 1, 0, 0);
    colorFunction->AddRGBPoint(1.0, 0.734069, 0.171569, 0.171569);
    colorFunction->AddRGBPoint(1.1, 0.734069, 0.171569, 0.171569);
    colorFunction->AddRGBPoint(1.1, 0.392157, 0.392157, 0.392157);
    colorFunction->AddRGBPoint(1.15, 0.392157, 0.392157, 0.392157);
    colorFunction->AddRGBPoint(1.15, 0.249554, 0.249554, 0.613191);
    colorFunction->AddRGBPoint(1.2, 0.249554, 0.249554, 0.613191);
    colorFunction->AddRGBPoint(1.2, 0, 0, 1);
    colorFunction->AddRGBPoint(1.5, 0, 0, 1);
    colorFunction->AddRGBPoint(1.4, 0, 0, 0);
    colorFunction->AddRGBPoint(20, 0, 0, 0);

    colorFunction->Print(std::cout);

    auto colorFunction2 = vtkSmartPointer<vtkColorTransferFunction>::New();
    colorFunction2->AllowDuplicateScalarsOn();
    colorFunction2->DeepCopy(colorFunction);

    colorFunction2->Print(std::cout);

Gives the following output:

0 X: 0 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
1 X: 0.5 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
2 X: 0.5 R: 0 G: 1 B: 0 Sharpness: 0 Midpoint: 0.5
3 X: 0.7 R: 0 G: 1 B: 0 Sharpness: 0 Midpoint: 0.5
4 X: 0.7 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
5 X: 0.8 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
6 X: 0.8 R: 1 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
7 X: 1 R: 0.734069 G: 0.171569 B: 0.171569 Sharpness: 0 Midpoint: 0.5
8 X: 1 R: 1 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
9 X: 1.1 R: 0.734069 G: 0.171569 B: 0.171569 Sharpness: 0 Midpoint: 0.5
10 X: 1.1 R: 0.392157 G: 0.392157 B: 0.392157 Sharpness: 0 Midpoint: 0.5
11 X: 1.15 R: 0.392157 G: 0.392157 B: 0.392157 Sharpness: 0 Midpoint: 0.5
12 X: 1.15 R: 0.249554 G: 0.249554 B: 0.613191 Sharpness: 0 Midpoint: 0.5
13 X: 1.2 R: 0.249554 G: 0.249554 B: 0.613191 Sharpness: 0 Midpoint: 0.5
14 X: 1.2 R: 0 G: 0 B: 1 Sharpness: 0 Midpoint: 0.5
15 X: 1.4 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
16 X: 1.5 R: 0 G: 0 B: 1 Sharpness: 0 Midpoint: 0.5
17 X: 20 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5

0 X: 0 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
1 X: 0.5 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
2 X: 0.5 R: 0 G: 1 B: 0 Sharpness: 0 Midpoint: 0.5
3 X: 0.7 R: 0 G: 1 B: 0 Sharpness: 0 Midpoint: 0.5
4 X: 0.7 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
5 X: 0.8 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
6 X: 0.8 R: 1 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
7 X: 1 R: 1 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
8 X: 1 R: 0.734069 G: 0.171569 B: 0.171569 Sharpness: 0 Midpoint: 0.5
9 X: 1.1 R: 0.734069 G: 0.171569 B: 0.171569 Sharpness: 0 Midpoint: 0.5
10 X: 1.1 R: 0.392157 G: 0.392157 B: 0.392157 Sharpness: 0 Midpoint: 0.5
11 X: 1.15 R: 0.392157 G: 0.392157 B: 0.392157 Sharpness: 0 Midpoint: 0.5
12 X: 1.15 R: 0.249554 G: 0.249554 B: 0.613191 Sharpness: 0 Midpoint: 0.5
13 X: 1.2 R: 0.249554 G: 0.249554 B: 0.613191 Sharpness: 0 Midpoint: 0.5
14 X: 1.2 R: 0 G: 0 B: 1 Sharpness: 0 Midpoint: 0.5
15 X: 1.4 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5
16 X: 1.5 R: 0 G: 0 B: 1 Sharpness: 0 Midpoint: 0.5
17 X: 20 R: 0 G: 0 B: 0 Sharpness: 0 Midpoint: 0.5

Note how nodes 7 and 8 end up in “reversed” order upon initial insertion, but then end up permuted once more when DeepCopied.

3

Unless I’m missing something, this (i.e., using stable_sort) seems reasonable to me. Are you planning on submitting a MR ?

4

Thanks for the quick response.

I am willing to attempt an MR (hoping there are no big question marks about whether this behavior applies similarly to many other parts of code), but mainly wanted a sanity check on the usage and suggestion first. :slight_smile:

5

There are many variants of the stable_sort vs sort issue. This also shows up in insidious fashion when using threading (threads may process data in different order etc.) But for your application, I suspect that the code is fairly encapsulated, and the sorted data size is tiny and I can’t imagine any performance concerns. But one thing I’ve learned is that developing software is a humbling experience so only the tests will tell us for sure :slight_smile:

1 Like