Re: Undefined qsort behavior

["Miguel A. Osorio" <maos@gbl.com.br>]

Steve Baker wrote:
> 
> 
> 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.

	Ok, I'm listening :)

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

	Got it. So I run through all geosets I'll be using, say, in a game
level, and for each new geostate I create a bucket.

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

	Sure thing.

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

	Excellent, this is indeed better than what I had in mind. It seems that
the detail I missed to get to your solution was that it's ok to group a
set of states (textures, materials, etc); even if we have tons of
textures and materials, the combinations for actual objects in the
application is still small. I was thinking in general terms, like the
problem was more of arbitrary combinations of states, which could yield
a combinatorial explosion :)

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

	Yes, I already had that in mind while reading your solution.

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

	You can't imagine how greatly this works out for me. As a matter of
fact, I already have implemented a generic dynamic array (as I call
these automatically resizeable arrays), so half the work is already done
:)

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

	Yes, it's a good optimization, but not essential.

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

	Sure, I already had that in mind, even with my original solution. I
would treat opaque objects first, then the translucent ones in another
operation. Of course, with your solution this comes out naturally, just
as you said, just put those translucent buckets at the end.

	Thank you very much for your suggestion, it really helped a lot. I
sense my time to code this next section of my engine is getting close :)
Just a few more details to work out an then get those lines of code
flowing :)





Thanks again,
Miguel A. Osorio.