Re: [AD] Remove the P3D code please!

["Elias Pschernig" <eliaspschernig@xxxxxxxxxx>]

> >
> > I'm not sure what it is specifically, but whatever controls
> > the routines for the non z-buffer rendering. I think it's
> > the scanline sort w/ the painter's algo. It's kinda slow,
> > maybe someone should add a face sort :)
> >
>
> The rasterizers from P3D are awesome (need lit transparent
> ones ,,,) but the scene functions are slow.
>
> Simply doing a "qsort" on your faces is enough.  When writting
> your qsort compare function just sum the Z components from the
> two faces. Then compare the sums (i.e for order).  This turns
> out to be much faster.
>
> The radix sort is an O(cn) time algorithm where n is the
> number of elements and "c" is the number of radix elements
> (i.e bits).  The qsort is a O(log(n)n) (I think, Knuth Vol3
> P122).  So if we have 16-bit elements we have 16n vs. log(n)
> n.  Chances are to get log(n)=16 you need n=10^16 (i.e really
> big).  So qsort is much faster.  for example... with 1000
> faces (16-bit precision for Z) we have 16*1000 vs 3*1000 or
> 16000 vs 3000.
>
> Radix sorting is over 5 times slower.

If you have a minz and maxz range for your faces, it's possible to
implement hash sort which has O(an) where a is almost 1 if the faces
aren't all at the same z. So in your example it's another 3 times
faster than q-sort :)