Re: Undefined qsort behavior

[Steve Baker <sjbaker1@airmail.net>]

Miguel A. Osorio wrote:

> 	It's a fact that we can increase performance in OpenGL by reducing
> state changes, like for example, grouping primitives by material, or
> texture, for example. I'd like to use the C standard lib function qsort
> to do this kind of sorting for me, but it's obvious that I'll have
> repeated entries in my array (more than one primitive with the same
> material/texture). But the qsort man page says: "If  two  members
> compare as equal, their order in the sorted array is undefined". So my
> question is this: this "undefined order" still groups equal elements
> together, or is the undefined *really* undefined ? For instance, if I
> have an array: 4 2 3 1 2 4, do I *always* get: 1 2 2 3 4 4 ?
What it means is that if you have two sets of polygons: 'A' and 'B',
both with the same OpenGL state, then sometimes A could come out before
B and other times B will appear before A.  That *could* matter - it might
result in additional Z flickering or something...but I don't think
it's really serious.  If it is, you could include the address of the polygons
data structure into your sort criteria and then they can never be equal
so they'll always come out it the same order.

HOWEVER:  Your entire question supposed that QSort is appropriate here -
and it certainly isn't.

Qsort is a *really* poor solution for rendering.

You can know up-front what OpenGL state setups you need - it's a small set -
typically one for each texture map or so.  That suggests that a 'bucket sort'
(which is a strictly O(n) solution) would be appropriate - and I can
assure you it is in practice.

Separate out your data structures into 'Geometry Sets' (GeoSet's for short)
which contain your polygons and 'State sets' (GeoStates) which contain
contains the texture handle, the shininess, etc, etc.  Each GeoSet has
a pointer to whichever a GeoState it wants to be rendered with.

In general, there will be far fewer GeoState's than there are GeoSet's.

Associate each GeoState with a 'bucket' - an array of pointers-to-GeoSet.

As you do your field of view cull, toss a pointer to each GeoSet
into the 'bucket' of it's GeoState.  This is a fast operation - and
since you are walking your scene graph anyway, it'll add hardly any
extra time.

Finally, loop through the GeoStates setting up the OpenGL state and
then rendering the GeoSet's polygons pointed to by the pointers in th
bucket.  As you loop through, remember to zero out the bucket after
you've rendered it so it'll be ready for next time around.

No sorting (of the Qsort variety) required...much faster than anything
else you could possibly imagine...only adds a dozen lines of code to
a reasonably well structured application.

For a final spin - PRE-SORT the order of the buckets so that the
ones that are most similar come consecutively...eg if two OpenGL
state sets are identical except for the texture map (ie same
material colours, same shininess, etc) then put them next to
each other in the bucket ordering.  Your sort mechanism for
ensuring this may be kinda complicated - but you only have to
do it once (at the start of each level of the game maybe) - so
it doesn't have to be very efficient.

The data structure for the 'bucket' should be something fast like
a fixed length array - not a linked list or anything complicated.
I've used fixed length arrays - and if the array overflows, I allocate
a new one twice as big, copy all the pointers over into it and delete
the original array.  Very rapidly, all the arrays get to be an appropriate
size and rarely (if ever) resize after that.

If you find there are a lot of empty buckets in your 'typical' scene,
then you might want to make a linked list of non-empty buckets so you
can skip over them quickly - but that's rarely a useful optimisation
because of the additional per-GeoSet testing...remember that there
are usually vastly more GeoSets than GeoStates.

Notice also that sorting translucent surfaces so that they render
after all the opaque ones now becomes a trivial matter of placing
all the translucent GeoStates at the end of the bucket chain.

---------------------------- Steve Baker -------------------------
HomeEmail: <sjbaker1@airmail.net>    WorkEmail: <sjbaker@link.com>
HomePage : http://web2.airmail.net/sjbaker1
Projects : http://plib.sf.net    http://tuxaqfh.sf.net
           http://tuxkart.sf.net http://prettypoly.sf.net