Render Sort Algorithms
One significant problem with Computer Graphics is in sorting algorithms. For images to be rendered correctly, the geometry must be sorted somewhere before they are rendered to the user. If not properly sorted, then distant geometry can appear in front of near geometry, creating completely wrong imagery.
Algorithms
While an active field of research, there are three main types of sorting algorithms.
Sort-First
In a sort-first approach, the raw input geometry is sorted within 3-D space. Sorting in 3-D space can be very beneficial as you can eliminate large portions of geometry before they are rendered, putting less load on later stages of the rendering pipeline.
Benefits:
- Completely dependent on size of input dataset
- Not related to output image size or display medium
- Can significantly reduce data bandwidth by removing large amounts of occluded geometry early
Sort-Last
In a sort-last approach, the final images are sorted by their depth buffers to determine what is in front. This is a very trivial operation, a single comparison of Z-buffers, but does require the entire geometry to be rendered.
Benefits:
- Completely dependent on image resolution
- Regardless of input data size
- Well suited for parallel rendering, where each node renders a separate piece of the dataset
Sort-Middle
In a sort-middle approach, some hybrid of sort-first and sort-last is used. Typically the input geometry is transformed into screen space, and from there some combination of 3-D sorting and 2-D Depth Buffer comparisons can eliminate geometry.
Overview
In recent years, sort-last has emerged as the most commonly used render-sorting algorithm. The simplicity to implement and independence of input datasize have made it especially popular. Sort-last also seems to be the best suited algorithm to the increasing gap between data sizes and screen resolutions. As dataset sizes continue to increase exponentially, the fact that the sort-last algorithm is completely dependent on the framebuffer size, which is largely unchanging, makes it a very scalable and parallel-friendly solution.
Recent developments in the GPU market have started to make sort-middle algorithms more appealing tho. With the ability of video cards to perform significant amounts of per-vertex and per-fragment computation in hardware, algorithms like Hardware Assisted Visibility Sort (HAVS) have brought sort-middle back into appeal. While still lacking the simplicity and pure performance of a sort-last approach, some sort-middle algorithms can offer significant advantages much earlier in the rendering process. This is helpful for computations that may not need the full imagery rendered to the user, but merely need it for collision detection or intersection testing.