Edit 2: It's getting reaaaallly late here, but the conclusion about the Transitivity of equivalence is the same that Jabberwocky already came to. Gosh I need to rest.
I took a
deep,
carefull look at SGI's reference (
here,
here &
here)
I think I know what's going on. The problem is in the RealEqual thing. It
potentially breaks the Transitivity of equivalence invariant. Suppose you have these three values:
X = 1.0 - 1e-6f //0.999...
Y = 1.0;
Z = 1.0 + 1e-6f //1.000001
Math::RealEqual( X, Y ) will return true.
Math::RealEqual( Y, Z ) will return true.
Math::RealEqual( X, Z ) will return false ---> Ooops. Different code path. Depending on what the other "return a.pass < b.pass;" had returned and what the current "return (adepth > bdepth);" will return, we will potentially be violating transitivity of equivalence (if X == Y && Y== Z, then X == Z, which is being violated).
With a bigger epsilon, we just translate the problem to bigger numbers.
[s]If we remove RealEqual, and use the == operator (the original problem from this thread in 2007), then we are violating Irreflexivity invariant because f( x, x ) may return true.[/s]
Edit: Using the == operator will always return false, as it should. I'm still thinking it as it doesn't feel right (and obviously it doesn't work)
Removing the whole "if( Math::RealEqual(adepth, bdepth) ) return a.pass < b.pass;" block should fix it.
However, I think that's what's causing the flickering problem, right?
Well, the flickering problem might be being caused by:
a. Floating point imprecisions. Let's make use a very big epsilon to show the behavior:
In frame 0:
particle X = 0.99
particle Y = 1.00
In frame 1:
particle X = 1.02 //Order became reversed
particle Y = 1.01
In frame 2:
particle X = 1.03 //Order became reversed again!
particle Y = 1.04
b. Equivalence! If X == Y, then the order is unaltered by sort. If at frame 0 X is submitted to the queue before Y, and at frame 1 Y is submitted before X, then we'll get flickering. In order words, it stops being sorted, and now becomes a FIFO queue for those particles with equal (actually, equivalent) depth.
Solutions:
First, remove RealEqual(). It breaks Transitivity of equivalence (on extreme cases, but it does).
[s]Second, remove "return a.pass < b.pass;". It breaks Irreflexivity.[/s]
Alternatives (not mutually exclusive):
a. Quantize values. Round them, truncate them, convert to integers (all of them potentially slow, I'm afraid). This solves flickering caused by floating point imprecisions (assuming this is actually a valid cause! I'm guessing!) If my guess is wrong, then quantization wouldn't be necessary. In other words:
Code: Select all
return Quantize(adepth) > Quantize(bdepth);
b. To avoid flickering caused by equivalence, use some sort of hashing that guarantees the order is preserved regardless of how they were submitted to the queue, and this hash should be unique for each renderable. In other words:
Code: Select all
if( adepth == bdepth ) //Or the quantize() version
{
// Must return deterministic result, but never treat two renderables as being equivalent
return a.renderable->getHash() < b.renderable->getHash();
}
else
{
//...
}
If someone thinks I'm mistaken, I would be glad to be pointed out. I really hate writing predicators.
Cheers
Dark Sylinc
