depth sorting (bug 989156)

[James W. W. <os...@jw...>]

I've been doing some experimentation on ways of doing depth sorting of 
transparent triangles.  The choice of algorithms comes down to one of 
those classic tradeoffs: do you want the job done right or do you want 
it done right now?  But it seems clear that we can do better than what 
we have now.

Those with access to Mac OS X can see some of my experiments in this 
program: <ftp://ftp.jwwalker.com/TransTest.dmg>.  This program offers 
choices of 3 comparison methods (the current Quesa method, and what I 
call the centroid and barycentric methods) and 3 sorting methods 
(qsort, selection sort, and qsort with centroid comparison followed by 
selection sort by the specified comparison).  Obviously that produces 9 
possible combinations, but I would like to direct your attention to 3 
of them:

1. current Quesa comparison method, qsort
2. centroid comparison, qsort
3. barycentric comparison, selection sort after centroid qsort

Method 1 (which Quesa currently uses) displays constant ugly flashing.
Method 2 has much less flashing, though it is not hard to see sorting 
errors much of the time.  This is of similar speed to method 1.
Method 3 has only occasional errors, but is quite a bit slower.

In case you wonder why one would want to use qsort for centroid 
comparison but not barycentric comparison:  The qsort algorithm is 
intended for sorting totally ordered data, and the centroid comparison 
comes close to providing a linear order on triangles (it orders them by 
z coordinate of the centroid).  The barycentric method, on the other 
hand, defines only a partial order on triangles, so qsort does not work 
well on it.  The problem of finding a linear order consistent with a 
partial order is called topological sorting, and my selection sort 
algorithm is a kind of topological sort.   There are other topological 
sorting algorithms that are probably faster than mine, but use 
additional storage as a quadratic function of the number of triangles.

Comments?
--
<http://www.jwwalker.com/>