   Sorting by shader, texture etc.
  Hi. I’m working on a module for a graphics engine that sorts objects to be rendered by state changes. I.e. minimising potentially expensive changes like shader and texture changes. This is what graphics card manufacturers advise.My idea is for another part of the engine to traverse a scene graph and add the objects to the sorting module and then render the scene after all the objects have been added. This seems to make sense as the graphics card can draw the images to the screen while the game engine moves on and prepares the next frame.My questions: 1.Does this make sense, or have I got the wrong idea completely.2.How do I sort the objects without spending too much time doing it, there are likely to be a lot of small objects, esp. as any object with more than one material will have to be broken up. Using a scene graph, with just material state changes( i.e. excluding transformation state changes, which are relatively cheap) seems sensible, but I can’t think of an efficient way of sorting it. A binary tree might be another way, with each material given a value according to its type and sorted that way. But that doesn’t necessarily mean that expensive state changes are correctly ordered. Any advice?3.Will this defeat the point of vertex buffers as objects will be rendered in a completely different order to when they where created.I know there are a lot of questions here, many thanks for your time.  
quote:Original post by kohonen  My questions: 1.Does this make sense, or have I got the wrong idea completely.2.How do I sort the objects without spending too much time doing it3.Will this defeat the point of vertex buffers as objects will be rendered in a completely different order to when they where created.1.  Yes.  It''s what I do.2.  I use mergesort on a linked list of nodes.  I use Amiga Style lists, and modified  this sort to work with my lists.  My sort is non-optimal in that it calls a compare function, rather than comparing inline, and the compare function checks a half dozen things (transparency, distance, textures, other material properties).  According to the profiler, it''s taking roughly 1% of CPU time.  Just remember to sort after you frustum cull and it''s not a big deal.3.  No.  The point of vertex buffers is to have the data stored on the graphics card.  You could arrange your vertex data such that vertices used in one material comes before vertices of another material.  This would stop you from jumping around the VB as much, which is a minor speed gain.  Sorting by materials is a MAJOR speed gain.;  Drivers already queue up to 3 frames - you are likely duplicating effort. The only time they cannot queue up is when you do something which stalls the pipeline (e.g. Read from the backbuffer). You can use Async query events get some information back from the driver without stalling however.In general, sorting is helpful only at a very course level. STate changes are primarly CPU limited (driver work), not GPU limited - so spending alot of CPU cycles to minimize the amount of work the driver does can easly be self defeating if your overhead is greater then the overhead that you are actually saveing the driver.The characteristics for Batch performance are very different depending on your hardware and drivers. Some drivers and hardware, the amount of state changes you make have almost no impact on performances - its purely the raw number of batches. The best thing to do is try a bunch of different things and measure the performance - and do not spend alot of app CPU cycles sorting. The calculation of determing weather you should set a state is often greater then just setting it.quote:Original post by kohonen  Hi. I’m working on a module for a graphics engine that sorts objects to be rendered by state changes. I.e. minimising potentially expensive changes like shader and texture changes. This is what graphics card manufacturers advise.My idea is for another part of the engine to traverse a scene graph and add the objects to the sorting module and then render the scene after all the objects have been added. This seems to make sense as the graphics card can draw the images to the screen while the game engine moves on and prepares the next frame.My questions: 1.Does this make sense, or have I got the wrong idea completely.2.How do I sort the objects without spending too much time doing it, there are likely to be a lot of small objects, esp. as any object with more than one material will have to be broken up. Using a scene graph, with just material state changes( i.e. excluding transformation state changes, which are relatively cheap) seems sensible, but I can’t think of an efficient way of sorting it. A binary tree might be another way, with each material given a value according to its type and sorted that way. But that doesn’t necessarily mean that expensive state changes are correctly ordered. Any advice?3.Will this defeat the point of vertex buffers as objects will be rendered in a completely different order to when they where created.I know there are a lot of questions here, many thanks for your time.  ;  Drivers can queue upto 3 frames, that doesn''t mean they will.  It also doesn''t mean you can waste CPU and GPU time swapping textures and render states.  Time wasted is time wasted, whether you pay for it at the time you call a function, or at the time the GPU gets around to the command in it''s queue.Texture changes and some state changes take quite a bit of time for the GPU.  Is it a duplicated waste of effort to sort?  As I said, my sort takes 1% of the CPU (on XBox, so 733MHz processor).  A sorted frame takes 20% less time to render than not sorting.Sorting seems to be a win.  Also transparent objects require sorting to occur in order to draw in the correct back to front order after all solid objects.  If you''re already sorting, and you can get 20% better performance with one extra compare to sort solid objects by material, then why would you not do it?;  Personally, I have found that sorting by textures gives a very significant performance benefit. Not sure what should take precedence in terms of shaders,textures,vb''s etc, but basically, the less state changes the better. Its definatly worthwhile.As for what algorithm I use, lets put it this way: I''ve never bothered implementing some special sorting method, and I''ve almost always obtained significant performance benefits for sorting. Basically, I dont think its going to matter much what type of sort you use.  ;  Sorting per material/shader can be very important. In my engine I got form 20-150% FPS increase when I added shader sorting & lasy evaluation. And the sorting doesn''t even show up in profiler (takes <0.5% of time) even with std::sort().   You should never let your fears become the boundaries of your dreams. ;  Thanx for all the reply. Very helpfull.I think I will use Namethatnobodyelsetook''s linked list suggestion, its must simpler than trying to use some sort of tree. (If the number of objects get too large then I will consider a tree) Thanks for the link. 