Re: surface elements for transparent_solids.dem

[<HBB...@t-...>]

Daniel J Sebald wrote:
> Hans-Bernhard Bröker wrote:
>> Daniel J Sebald wrote:

>>> Hmm, might there be a slight alteration of this that would work
>>> "better"? 

>> No.  The whole idea of "depth sorting" is fundamentally flawed.  No 
>> slight alteration can make it work correctly.  The only real effect a 
>> slight alteration will have is to move the errors to a different 
>> region of parameter space, i.e. replace a known-bad guess by an 
>> unknown one.
> 
> Depth sorting with something like qsort() is fundamentally flawed.  

No.  It's the "sorting" itself that is based on incorrect assumptions 
--- not the choice of sort algorithm or implementation.  The "covered 
by" relation is not an ordering.

To get correct display, an algorithm has to go beyond sorting.  It has 
to be prepared to split some objects into smaller fragments to get a 
list that can be sorted.

> The assumption of equality is a problem in a sort like that.

Equality is not really a problem --- transitivity is.  For a set to be 
ordered by a relation '<', it has to be transitive, i.e. the condition

	(a < b) and (b < c)  ==> a < c

has to hold.  But doesn't hold for the relation "object obstructs (part 
of) other object from view)".

And worse yet, the ordering isn't local.  I.e. you can have two polygons 
A and B whose drawing order cannot be determined in any way looking at 
these two polygons alone (think of disjoint polygons in a plane parallel 
to the view plane).  Adding a third polygon, C, can cause them to have 
to be drawn either A before B, or B before A, depending on C.

Painters' algorithm is a different problem from sorting.  Calling it 
"depth sorting" is ultimately a lie.  It's actually harder than sorting. 
  For vector graphics output like gnuplot's terminal API it has a lower 
bound of O(N^2) output size, and thus O(N^2) time for N polygons, 
compared to sorting's O(N*log(N)).