📄 polysorting.htm
字号:
<HTML> <HEAD> <TITLE>Poly Sorting Algorithms</TITLE> </HEAD> <BODY bgcolor="#FFFFFF" TEXT="#000000" LINK="#666699" ALINK="#000000" VLINK="#666699"> <table bgcolor="#666699" BORDER=0 CELLPADDING=5 CELLSPACING=0 WIDTH=640> <TR> <TD align="left" bgcolor="#666699" width="90%"> <font face="arial" color="#FFFFFF"><b>Poly Sorting Algorithms</b></font> </TD> <TD bgcolor = "#000000" align="right"> <a href="math.htm"><font color="#FFFFFF" face="arial"><b>Back</b></a></font></TD> </TR> </table> <center><br> <center> <table border="0" cellpadding="10" cellspacing="0"> <tr> <td> <br><br><pre> OTMSORT.TXT - Sorting algorithms for 3d graphics released 2-20-95 by Voltaire/OTM [Zach Mortensen] email - mortens1@nersc.govINTRODUCTION During the past month, I have received many inquiries concerning sorting algorithms used in 3d engines, which are the fastest, etc. I figured I could save myself some IRC and email writing time by compiling a text on the matter that would explain everything in a concise manner. In this text, I will describe various sorting algorithms, and the pros and cons of each. This primarily covers variations of the radix sort, which I have found to be the fastest algorithm. A fast sort is critical to a fast 3d engine, perhaps even more critical than a fast poly fill. In the first version of my 3d engine, I implemented a linear sort (quite a misnomer actually). When I began optimizing, I found that the sort was a huge bottleneck. After I switched to a z-buffered drawing scheme which eliminated the sorting algorithm, my code ran about 7 times faster than it had before. I quickly discovered that z-buffering was not the fastest method either. It requires an enormous amount of memory accesses per polygon, which can be very very slow on a machine without a fast bus and writeback cache. I needed to find an algorithm that would allow me to sort my polygons with the fewest number of memory accesses. The radix sort was the answer I had been looking for. The radix sort is adventageous over all other sorting algorithms because its sorting time as a function of the number of data to be sorted is linear. The sorting time as a function of number of data in most commonly used sorts is exponential, which causes a tremendous slowdown when a large number of polygons are being sorted.THE BUBBLE SORT Here is an example of a bubble sort for (count = 0; count < numData; count++) for (index = 0; index = numData; index++) if (data[count] > data[index]) swap(data[count], data[index]); This is by far the simplest sorting algorithm known to man. It is also the most inefficient sorting algorithm that could possibly be used, literally. In the bubble sort, each element of the set is compared with all other elements, yeilding a total of numData * numData iterations through the sorting loops. As you can see, this is a quadratic function. By doubling the number of data to be sorted with a bubble sort, the sorting time increases FOUR TIMES. The bubble sort is a definite no no if you are remotely interested in speed.THE "LINEAR" SORT The linear sort was taught to me in my High School pascal class. It was a much faster sort than the bubble sort in our examples which required us to sort a set of not more than 20 numbers, so it was the first sort I implemented in my 3d code. However, a closer look shows that it is nothing more than a slight variation of the bubble sort algorithm, with a slight increase in the performance. for (count = 0; count < numData; count++) { x = count; for (index = count + 1; index < numData; index++) if (data[index] > data[x]) x = index; if (x > count) swap(data[x], data[count]); } This algorithm yeilds numData iterations through the outer loop, with an average of (numData / 2) iterations through the inner loop per outer loop iteration. Therefore, the total number of iterations through the inner loop is (numData * numData) / 2. This total is half the total of the bubble sort, but it is still a quadratic relationship. By doubling the number of data, the sort time is doubled. This seems to be a linear increase (hence the name linear sort), but it is not. If the size of the data is increased by a factor of 4, the sort time is increased by a factor of 8 (4 * 4 / 2). An increase by a factor of 8 in the size of the data will result in the sort time increasing by a factor of 32 (8 * 8 / 2). So, this sort is nearly as bad as the bubble sort when sorting VERY large data sets.THE RADIX SORT If you have never heard of the radix sort, you are not alone. If you learned about the radix sort in a programming class and thought it was totally useless, you are like I was. The way the radix sort is usually taught in classes is efficeint for everything but computers. This is because the textbooks usually use base 10 (decimal), which is extremely foreign and difficult to implement in a computer. The idea behind a radix sorting algorithm is to sort the data by each radix, starting with the least significant and moving to the most significant. This is best illustrated by an example. First off, it helps to define radix. A radix is a 'place' in a number. The base 10 radices have common names (1s place, 10s place, 100s place, etc), but the concept can be extended to numbers of any base. Consider the base 10 number 32768. The value of the first (least significant) radix is 8, the second is 6, the third is 7, the fourth is 2, and the fifth is 3. Now consider the base 16 (hexadecimal) number 3f8. The value of the first radix is 8, the second is f, the third is 3. Now the following example will make a bit more sense. base 10 radix sort example data |first |second set |pass |pass ---------------+---------------+--------------- | | 12 |09 |83 65 |38 |73 44 |37 |65 37 |65 |44 03 |44 |38 38 |03 |37 83 |83 |12 09 |73 |09 73 |12 |03 The first pass through a radix sorting algorithm deals ONLY with the least significant radix (in base 10, the least significant radix is the one's place). The data is sorted from greatest to least (or least to greatest depending on the application) based on the least significant radix. After the first pass, the data with the least significant radix of greatest value is at the top of the list. The second pass is similar to the first, with the exception that the resultant data from the first pass is sorted (NOT the original data), and the data is sorted based on the second radix. It is extremely important to preserve the order of the previous pass, so make sure to traverse the list the same way the original data was traversed in the first pass (in this case, top to bottom). Any additional passes to sort additional radices are performed in the same manner, by sorting the data from the previous pass with respect to the radix in question. The radix sort has an advantage over the other sorts presented here, because its sort time as a function of number of data is linear. The number of iterations needed in a radix sort is given by (numData * numRadices) where numRadices is constant for the entire data set.THE BIT SORT (BASE 2 RADIX SORT) Now that we have an algorithm that gives a linear increase in the number of iterations needed to sort larger sets of data, we need to find a way to make each iteration as fast as possible. This can be accomplished by changing the base in which the data to be sorted is interpreted. In base 10, we have to go through each element of the set looking for a 9 in a given radix, then look for an 8, etc. This is quite slow, and fairly difficult to implement on a computer. A better approach than using base 10 is to use base 2, where there are a total of 2 possible values for each radix (0 or 1). It is very easy to test whether or not a binary number contains a 1 in a given place, this can be accomplished by an AND or TEST instruction. Since there are only two possible values for a radix of base 2, it is also extremely easy to sort from greatest to least based on a given radix. Simply put all the '1' radices at the top and all the '0's at the bottom. Here is some example code for the bit sort applied to 16 bit data: // this requires two temporary arrays of [numData] elements, // one for 1s and one for 0s short data[]; // 16 bit data in this example short oneArray[numData]; short zeroArray[numData]; int numOnes; int numZeros; int mask = 1; for (count = 0; count < 16; count++) { numOnes = 0; numZeros = 0; for (index = 0; index < numData; index++) { if (data[index] & mask) { oneArray[numOnes] = data[index]; numOnes++; } else { zeroArray[numZeros] = data[index]; numZeros++;⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -