Re: [AD] Remove the P3D code please!

[tom st denis <tomstdenis@xxxxxxxxxx>]

--- Nick Kochakian <nickk@xxxxxxxxxx> wrote:
> > > Um, well, actually it would seem to me that most of the routines
> are
> quite
> > > slow. I was just saying that the face sort could be much faster
> (from
> > > experience.) For example, I implemented something of a face sort
> using
> the
> > > regular allegro 3D routines and got at least 50% more speed than
> I would
> > > have if I had used the P3D routines. There's obvously something
> in there
> > > that's causing the whole thing to slow down. I don't think the
> z-buffering
> > > stuff should be messed with, because that's slow to begin with :)
> (In
> > > software, anyway) The z-buffer routines, for software ones, are
> actually
> > > quite nice, but I was just _really_ surprised that the face sort
> was so
> > > slow! Perhaps doing something like a radix sort would make it
> better? (I
> > > hear that's one of the fastest :)
> >
> > but could you please give me a little more info on *what* to have a
> quick
> > glance at ? (not that i think i'll make it faster anyway, but who
> knows)...
> 
> 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.

Tom

__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail - only $35 
a year!  http://personal.mail.yahoo.com/