   The Intrinsics of Entity Sorting in 3D Engines
  If we define entities as being 3D meshes that have certain caracteristics, like textures, shaders, etc, what is the correct order in which to sort them?I''m guessing, we first sort by texture. Each mesh usually has a texture assigned, so we sort the entities by texture first (or lack of texture).Certain entities none the less, have a secondary mesh, for multi-texturing purposes, so our 2nd sort can be the 2nd texture.So we can define that we first sort by t(n), where "t" equals texture, and "n" defines the logical number of the texture.Other possible sorting parameter that comes to mind is the alpha of the entity, its transparency.Other parameters for sorting might be vertex shader used, pixel shader used...So, our sort parameters could be:t(n) - texture elements (or lack of them)a - alpha value of the entityvs - vertex shaderps - pixel shaderYou use any other parameters on your engine?Also, from the research i''ve done, developers seem to prefer radix sorting (RS), correct? Is RS''s speed linear in relation to the number of elements it has to sort? Does it have any cons one should be aware, for example, being slower than other possible sorting algos in low-entity environments?What other sorting algorithms might be apropriate for entiry sorting in a 3D engine?What are your thoughts on this?   [Hugo Ferreira][Positronic Dreams][Colibri 3D Engine][Entropy HL2 MOD][My DevDiary][Yann  L.][Enginuity]  [Penny Arcade]  [MSDN][VS  RoadMap][Humus][BSPs][UGP][NeHe] Prozak - The GameDever formally known as pentium3id 
  Basically the order you search is dependant upon the cost of changing the corresponding state in your engine. In other words during development make the order of the sorting parameters customisable, and provide debug info on number of texture/vp/fp changes per frame and the numbers of each used per frame, this gives you some idea as to what changes are happening. Then experiment e.g. if you have a lot of vertex program changes, try sorting by that first - you mnay find that you get a increase/decrease in frame rate, then experiment with different orders. Of course the optimal order will depend upon the distributions of the use of each parameter in the scene e.g. in some scenes you may have a lot of different fragment programs, sorting by them first in this case could be beneficial.You probably actually want to divide the entities with transparency into a seperate list since these need to be drawn after all your solid geometry to get the correct blending effects.James ;  There's a fair amount of information on what you need to sort by in various presentations available on the nVIDIA and ATI websites. In most cases you'll want to sort by shader first and texture second since changing shaders is usually more expensive than changing textures. Other things to sort by include render target (one of the most expensive changes so probably want to sort by render target first), vertex buffer, vertex and pixel shader constants and render state.Drawing your objects in rough front to back order is also a performance win on most new hardware as early z-reject can save quite a bit of work on more distant objects that are obscured by nearer objects.In order to render alpha blended objects correctly you have no choice but to draw them in back to front order so you should draw all opaque objects sorted by shader, texture, etc. first and then draw all your transparent objects from back to front.As James says, the best thing to do is make it easy to change your sorting criteria and test in your particular game as the best strategy will depend on the specifics of your situation.   [edited by - mattnewport on April 2, 2004 5:23:35 PM];  You dont generally use a Radix sort, but more of a bucket sort.  For example, if I want to sort by texture, then I make a list (bucket) for each texture, and loop through the objects adding them to the respective list.  This takes O(n) time, so it''s faster than like quicksort or something that puts them in exact order.  We dont care about the order within a bucket, just that they are drawn together so we dont have to change the texture.Also, there are times where sorting by more than one parameter is best, but many times the sorting out weights the cost of the state change.  So you HAVE to benchmark everything if you want to get the best performance possible.  Dont just assume that sorting front to back will speed it up because of early z regection because many times the sorting will be worse than the overdraw.-Brandon ;  Are you doing extensive lighting w/ shadows?  If so, it''s sort of decided for you - you end up sorting by light first.  Then you can sort by shader or texture.Sorting by shader may be cheaper on ati hw ( not on nv ).  Sorting by texture saves CPU work ( more state associated w/ textures than shaders for the driver to validate ).I recommend by texture first, b/c most games are CPU bound at reasonable rez. ;  w/ shaders b/c it''s cheaper c/2 texture changes.OK, I this post really didn''t have any point, but it isn''t very clever to use those idiotic abbreviations. 