Re: surface elements for transparent_solids.dem

[Daniel J S. <dan...@ie...>]

Hans-Bernhard Bröker wrote:
> 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)".

Right.


> 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.

Those, for the time being, aren't a concern.  Two reasons.  They are rare (if those start occurring at too high a percentage in one's plot, s/he has not selected the sampling interval large enough or your function has some kind of singularity problem, e.g., 1/sin(x)).  The plotting of the quadrangle which doesn't have convex points is not unique, so you get what you get.

Barring that class of nasty quadrangles, one can sort but can't use the transitive property.  Hence, almost anything below O(N^2) algorithm is out for a good approximation.


> 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)).

Well, gnuplot is doing depth sorting.  There may be a subtle difference I'm not aware of.

Dan