#2604 Failure of depth sort among overlapping surfaces (environment dependent)

[Hiroki Motoyoshi]

Depending on the compiled environment, the depth sort in splot may fail for overlapping surfaces. This is likely due to the fact that the qsort function used for depth sort behaves differently depending on the C language library. Especially, the behavior depends on whether the implementation of the qsort function is stable sort or unstable sort, which does or does not preserve the order of elements of the same value.

I discovered this phenomenon on MacOS environment. According to 'man', qsort function in the C library of the MacOS system is not stable,

The algorithms implemented by qsort(), qsort_r(), and heapsort() are not stable; that is,
if two members compare as equal, their order in the sorted array is undefined. The
mergesort() algorithm is stable.

As a test, I simply replaced the 'qsort' function with the 'mergesort' function which has the same API as 'qsort' and was able to draw without problems even on MacOS.

On the other hand, I had no problem on Rockey Linux. It is said that glibc uses a kind of merge sort as 'qsort', but I could not find an exact description.

I have not checked the situation in other environments (other BSDs, Windows ...)

I suppose that this has never been a problem because there is no need to draw multiple surfaces that fully or partially overlap in the normal case.

Here is a test script:

set term pngcairo

f(x,y) = 5*exp(-((x+y)**2+((x-y)/2)**2))

set xrange [-3:3]
set yrange [-3:3]
set samples 30
set isosamples 30
set xyplane 0
unset colorbox

set output "case_pm3d.png"
set pm3d border lt -1 lw .1
set pm3d depthorder
set style fill solid 0.3
splot f(x,y) with pm3d fc "red" notitle, \
      f(x,y) with pm3d fc "green" notitle

set output "case_hidden3d.png"
set hidden3d
splot f(x,y) with lines notitle, \
      f(x,y) with lines notitle

Attached are the results of the above test scripts for the qsort and mergesort cases respectively on MacOS.

[Tatsuro MATSUOKA]

On windows (MinGW w64),

[Tatsuro MATSUOKA]

Cygwin

[Tatsuro MATSUOKA]

Ubuntu 22.04

[Hans-Bernhard Broeker]

Frankly, any expectations for that test case would be wrong. There is no sane way to even define what a "correct" result would look like for these cases. The whole question which of two identical surfaces should be hidden by the other makes no sense.

I might even go so far as to claim that the mottled output from MacOS's qsort is slightly better in this case, because it more clearly exposes the underlying silliness.

[Hiroki Motoyoshi]

Thank you for your comment. It made me realize that this ticket should have been raised for “Feature Request” category, not “Bugs” category.
It is as follows

"In depth order, for overlapping surfaces, give priority to the surface given later in the splot command."

Mathematically you are correct, but I think that it would be better to have the above ordering as a plotting tool.

In 2D plotting, overlays take priority over later given surfaces. Even in the case of depth order, I would expect this priority to be given to overlapping surfaces as well. I believe that this would increase the usefulness as a plotting tool.

The phenomenon discussed here was encountered during testing of Feature Request 553. Feature Request 553 includes use cases of overlays for overlapping surfaces in 3D view.

[Hiroki Motoyoshi]

One way to deal with this phenomenon, besides replacing 'qsort' with a stable sort implementation, would be to include the surface order in the comparison in the compare function. In that case, if 'qsort' is implemented with stable sort, it would just be a waste of time, and there might be a disadvantage in speed and memory efficiency.

[Ethan Merritt]

Yes that is possible to provide an alternative sort in gnuplot that preserves the original order of equal elements. In fact the code is already there, but it is only used by the "zsort" filter operation and only if conditional code protected by #ifdef EXTRA_COORDINATE is included in the compilation. See discussion attached to Bug #2446.

However I agree with Hans-Bernhard that it makes no sense in this case. If you want to guarantee that the 2nd surface occludes the identical 1st surface, simply replace set pm3d depth with set pm3d scansauto and that is exactly what you will get. I think a more realistic problem case is needed before any cost/benefit discussion is possible.

[Hiroki Motoyoshi]

I think a more realistic problem case is needed before any cost/benefit discussion is possible.

First is the case where only a partial area is colored for surface. The use case in Feature Request 553 includes something similar.

[Hiroki Motoyoshi]

I think a more realistic problem case is needed before any cost/benefit discussion is possible.

Second case is modified version of 'boxes3d.dem'.
This one may be a little harder to notice, but in the qsort version, the color of the border between the boxes randomly switches between the front and back colors during the rotation. In addition, scansauto does not draw with the correct depth relationship.

I think this is clearly unintended behavior.

[Ethan Merritt]

OK. I'm still busy working to automate filled contours following the model of your previous request. That is, as expected, kind of messy. Give me another day or so and I will attach a patchset to use for testing a configuration option that forces a stricter sort implementation for pm3d depthorder sorting. I'll rely on you to test that since the visual glitching doesn't happen on my linux machines.

[Hiroki Motoyoshi]

The third example seems to be related to hidden3d, which is "splot with points" to overlay different point types. If hidden3d is not specified, the depth relation of the points is broken partially . The option pm3d depthorder does not seem to have anything to do with this depth relationship.

[Hiroki Motoyoshi]

The fourth example is the case of projecting multiple surfaces or multivalued functions onto the bottom surface (at base) in pm3d plot.

Looking at the attached 'pm3d_at_base_2_mergesort_MacOS.png', the bottom image is strange even with mergesort employed, and probably seen on Linux as well. This may be another issue unrelated to this ticket, so I guess it's something that can't be fixed by addressing it here.

[Hiroki Motoyoshi]

That is, as expected, kind of messy.

I imagine it would be.

Give me another day or so and I will attach a patchset to use for testing a configuration option that forces a stricter sort implementation for pm3d depthorder sorting.

Thank you. I have a private patch that just replaces qsort with mergesort, so you are in no hurry.

I'll rely on you to test that since the visual glitching doesn't happen on my linux machines.

OK, I'll test with it on MacOS.

[Tatsuro MATSUOKA]

On Windows gcc (both mingw and Cygwin ) seems to have some bad effect by the qsort. (I do not know about Microsoft Compiler.). I will also test on MinGW ans Cygwin (WIndows).

[Ethan Merritt]

Here you go, a patchset for testing.
The code itself is pretty straightforward. I may have messed up something while modifying the configure file because I'm terrible at that. But if I didn't mess it up, you should be able to;
1) apply to patch
2) ./prepare
3) ./configure --enable-stable-sort
4) make

Surprisingly, I do find a difference in one output plot from the full demo set run with or without enabling the new option under linux. It's the final plot in "param.dem". I am guessing that is because the parametric description of a sphere is degenerate at the poles and many quadrangles overlap there. But at the pole the size of the quadrangles goes to zero, so even though the output order is different there is no visible change in the resulting plot. I only know there is a difference because I dumped the PostScript output to compare line by line.

I expect this option to have negligible effect on both the code size and the run time. The downside is a constant 5% increase in memory use for all pm3d calculations. Not horrible, but certainly under linux I see no reason anyone would want to take a 5% hit for no visible gain. Anyhow, give it a try and let me know if it solves the issue.

[Hiroki Motoyoshi]

Thank you for the patch set.

I agree with introducing it with the configure option. I think we can use this option to create a binary that fits the environment at the discretion of the maintainer.

In testing on MacOS (build with libraries installed via homebrew),
the source with the patchset applied could be compiled without problems.

The following examples that depend on pm3d depthorder give the expected results.

• masked_surface.gp (OK!)
• from_boxes3d.gp (OK!)
• pm3d_at_base.gp (OK!)

On the other hand, the following examples that depend on hidden3d don't give the expected result, as the previous behavior still remain.

• case_hidden3d.gp [Attached] (NG)
• points_overlaps.gp (NG)

This behavior comes from the ‘qsort’ function in “hidden3d.c”.

[Ethan Merritt]

I don't think the hidden3d case is fixable in the same way.

Linetype properties are the only thing I see available as a secondary sort criterion.
So it might be possible to modify the sort comparison such that it consistently put, say, red lines in front of green lines. But that would not correspond to whether the red surface was before or after the green one in the plot command. I suppose in extrema you could make the lines of each successive plot incrementally thinner and then select thick lines over thin lines. Ugh.

I am far less familiar with the hidden3d code than the pm3d code, so I might be overlooking an opportunity for some other approach.

Fortunately, all the examples so far can be solved without changing gnuplot at all. For any pair of well-behaved (i.e. single-valued with respect to z) identical surfaces like the ones in these toy examples you can solve the problem by displacing one of them by a small delta-z. I am not seeing a real need to address this issue by changing sort algorithms.

[Hiroki Motoyoshi]

I really appreciate your efforts on this issue.

I understand that the problem with this issue is that the standard C library specification does not include a stable sort function, and that portable stable sort functions are not available in gnuplot, which is expected to be used in a variety of environments.

Fortunately, all the examples so far can be solved without changing gnuplot at all. For any pair of well-behaved (i.e. single-valued with respect to z) identical surfaces like the ones in these toy examples you can solve the problem by displacing one of them by a small delta-z. I am not seeing a real need to address this issue by changing sort algorithms.

Thank you for detailed explanation about hidden3d situation and difficulty of implementation.

Now that I understand the cause of this phenomenon, I will not be surprised if I encounter the same situation in the future. As you said, the example with hidden3d can be avoidable with workaround. And, as long as I build myself on MacOS, I can make and use a private patch that simply replaces 'qsort' in hidden3d.c with 'mergesort'.

[Tatsuro MATSUOKA]

I have tested Hiroki Motoyohshi scripts on the MinGW and the Cygwin without and with the Ethan's patch. The results are the same as those on the macOS.

• masked_surface.gp (OK!)
• from_boxes3d.gp (OK!)
• pm3d_at_base.gp (OK!)
• case_hidden3d.gp (NG)
• points_overlaps.gp (NG)

[Hiroki Motoyoshi]

Thank you for testing on Windows (Cygwin and MinGW).

Because hidden3d cases can be avoidable with workaround that Ethan mentioned, I will not require a fix to hidden3d for this issue.

As for Hans-Bernhard's point about which surface should have priority in overlapping surfaces, I don't think there is a correct answer either. If we start thinking about how the surface should be displayed from the front side and from the back side, we will have to consider modifications to the depth sort algorithm itself.

I would like to be satisfied that with this fix we now have the same pm3d output as the glibc environment (no glitch).

[Ethan Merritt]

Is the API to the mergesort implementation on macOS identical to qsort? If so, then one option is to add a configuration option that looks for mergesort and, if found, places a redefinition in syscfg.h

#ifdef WITH_MERGESORT
#define qsort(base, n, size, compare) mergesort(base, n, size, compare)
#endif

Can you help with adding the correct tests to configure.ac?
It should be something like the section below (but I am terrible at using these macros so I may have it wrong). Also it should be wrapped in a test for the configuration option --with-mergesort but that can be added after this part is working.

AC_SEARCH_LIBS( [mergesort], [somelibname],
   [AC_DEFINE(WITH_MERGESORT,1,[ Define to replace qsort with mergesort ])]
)

[Hans-Bernhard Broeker]

The canonical methods would rather be AC_CHECK_FUNC or AC_CHECK_FUNCS, which will define HAVE_MERGESORT if the function is found and usable.

But bluntly #defineing over the top of qsort() is pretty certainly going to fail. This calls for one of those gp_ prefixed wrapper functions or GP_ prefixed macros instead. Something along the lines of

#if HAVE_MERGESORT
# define GP_STABLE_SORT mergesort
#else
# define GP_STABLE_SORT qsort
#endif

[Hiroki Motoyoshi]

The qsort manual page on MacOS can also be found at the following URL (although it is called an iOS page, it is (almost) identical to 'man qsort' on MacOS).
https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/qsort.3.html

The header has the following line, which appears to be a BSD-derived function.

QSORT(3) BSD Library Functions Manual

FreeBSD seems to have the same functions (just an observation).
https://man.freebsd.org/cgi/man.cgi?qsort(3)

The 'mergesort' function is included in 'stdlib.h' as well as the 'qsort' function. I think we need to verify the existence of the 'mergesort' functions included in the standard c library. In that case, would the following macro AC_SEARCH_LIB be sufficient?

AC_SEARCH_LIBS( [mergesort], [c],
[AC_DEFINE(WITH_MERGESORT,1,[ Define to replace qsort with mergesort ])]
)

returns

checking for mergesort in -lc... yes

Or is it AC_CHECK_FUNC?

AC_CHECK_FUNC(mergesort,
[AC_DEFINE(WITH_MERGESORT,1,[ Define to replace qsort with mergesort ])]
)

returns

checking for mergesort... yes

[Hans-Bernhard Broeker]

The function may have come from BSD to MacOS at some point, but qsort() is a completely standard library function. It's been in the ANSI/ISO C language since day one.

[Hiroki Motoyoshi]

I know. It simply means that the mergesort function should be looked for in libc.