Sign in to follow this  
gtdelarosa2

scene render sorting

Recommended Posts

gtdelarosa2    121
Hello, My company makes IPhone games using a modified version of the Irrlicht engine. The function that draws all of the scene nodes in the graph does a heap sort on the solid object list, the lights, and the transparent objects like this: heap_sort( &list[0], list_size ); renderList( E_SOLID, list ); The sort is based on material. I know that doing this is a common way to minimize state changes but it seems like an inefficient approach to sort on every render loop iteration. Just curious as to people's opinions on this approach, would it not be better to have a separate list for each material type, then insertion of objects would be O(1) and no sorting would be required during rendering? Is there some advantage to sorting? I guess it might be faster if you have a low number of objects or materials but what if you have alot of both? Thanks

Share this post


Link to post
Share on other sites
ArKano22    650
Usually i have lists of objects with the same material. It is possible to sort the objects inside each list (based on distance to camera), and you can render the lists in any order you wish. For me that works quite well.

So yeah, what you say makes sense to me. I don´t know why they used that approach. Maybe we´re both missing something, but i think the same as you.

Share this post


Link to post
Share on other sites
rubicondev    296
I go for one humungous list (well, two - one for transparent, one for opaque) as frankly it's easier than maintaining lots of little lists. Arkano's method is great and will reduce sort time though.

I compromise in that whilst I only have one larger list, I sort it using pointers to items which cuts down on memory copies and that's the biggest hit of all when sorting.

My scene sort is rarely on the offenders list when I profile, and it all hangs together nicely. It might look a bit shit doing a sort like this, but if you use the pointer to item method it really doesn't hurt and you need to do /something/.

EDIT: I forgot to mention a biggie! If you have one large list of opaque objects, you can sort it quite quick from front to back and the reduction you get reducing overdraw (by early z-culling) will speed up your rendering. Not so good it you're CPU limited like most of us will be, but it means you can put more polys on the screen which is never a bad thing in my book.

EDIT2: Should mention that this front to back sort works because of course you use a single shader for ALL your materials on the depth fill pass. Don't sort solids front to back during a main pass else you'll be in shader-switch-hell forever.

Share this post


Link to post
Share on other sites
Shael    286
I use the same method as Rubicon and have a list for Opaque and a list for Transparent. Both have their own sorting routines. I haven't done much profiling yet but it seems to work well.

Share this post


Link to post
Share on other sites
Rompa    307
We use one big list because its easier - each geometry has a sort key that is constructed dependent on its type (opaque objects sort primarily by material, primitive type then front-to-back depth, non-opaque objects sort primarily by back-to-front depth, material then primitive type). We don't need any separate code for full screen passes or anything like that, it all gets sorted correctly. It also gives us one central piece of code with which to concentrate on optimizing.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this