MastaLlama Member Posts: 671 From: Houston, TX USA Registered: 08-10-2005 |
Check out the article I just posted!!!! http://www.christiancoders.com/cgi-bin/articles/show_article.pl?f=mastallama06262007151042.html Later, |
GUMP Member Posts: 1335 From: Melbourne, FL USA Registered: 11-09-2002 |
Sorting is actually a topic that hasn't been discussed too much in relation to game engines. Usually all the data for rendering is sorted before the draw call is made. Typically the data is sorted with a O(n) algorithm such as Flashsort, RadixSort, quicksort (which is a comparison sort, which in worst cases does O(n^2) ), or bucketsort. Reality Engine uses RadixSort for example. With a sort function the CPU is the bottleneck. The problem is this: once the complexity of the data set reaches a certain threshold sometimes drawing the scene UNSORTED is actually faster! For example, I've read that with id software's Tech4 engine used with Enemy Territory that they don't sort level geometry at all (not sure about other types of data). In developing EW: Nightmares I ran into this same situation, which I semi-resolved by running tests on a highly complex scene. I set a max sort size which checked against the array size each frame. If the array went over the max the sort function wasn't run. By running multiple trials where I changed the max sort size and the scene (data set) I was able to find the threshold where the CPU via the sort function became the largest bottleneck. From then on highly complex scenes were rendered much fast (sometimes 5-10x so!) yet less complex scenes, which might still have a lot of shader effects, would still benefit from sorting. Now on a console, with its static hardware setup, that solution for EWN would have been fine. Problem is, there are many, many configurations for PCs and the max sort size is a static number. But the threshold for when the sort function becomes the bottleneck depends on the CPU. Until I started writing this I didn't even consider this problem but I imagine I should be able to resolve it by writing a function that keeps track of the max sort size and the framerate and then tries to adjust the max sort size on the fly. |
|
MastaLlama Member Posts: 671 From: Houston, TX USA Registered: 08-10-2005 |
Yeah, in MOST cases you'd have everything sorted before the data is presented (in the case of a webpage the SQL Query should tell the database what order to put the stuff in) but in my particular case I had data coming from 2 sources and needed to be viewed in 1. In actuality my 2 arrays were dates and they had corrisponding arrays with a message subject and message body in them. What slows things down with the bubble sort is if there are small numbers at the bottom. It will take more passes to get them to the top but with a larger number at the top it will take less passes. Example: The 10 will make it to the bottom on the 1st pass but the 1 will take 5 passes to "float" (like a bubble) to the top. The merge sort is quick depending on the length of your 2 source arrays. I looked into the other types of sorts but since my data was only going to deal with around 8 - 12 items in an array this worked out fine. I wouldn't want to do a bubble sort on an array with 100,000 indexes. [This message has been edited by mastallama (edited June 27, 2007).] |