I am rendering a bunch of points/lines using vertex arrays. How can I depth sort these points/lines? Is there a standard function in openGL? Is there a simple sorting routine for these vertices (maybe in a vertex shader program)?
The only way do sort these lines would be to do this on CPU. You can leave vertex array the way it is. Just create index array and use glDrawElements instead of glDrawArrays. By manipulating indices in index array yo can define the order in which lines are drawn.
GPU based solution should be possible with geometry shaders.
Originally posted by k_szczech:
The only way do sort these lines would be to do this on CPU. You can leave vertex array the way it is. Just create index array and use glDrawElements instead of glDrawArrays. By manipulating indices in index array yo can define the order in which lines are drawn.
GPU based solution should be possible with geometry shaders.
thank you very much. I’ll need to buy a directx10 card
is there a simple sorting algorithm for the CPU?
Google for these:
bucketsort - very fast, but not really precise sorting - n steps to sort n elements
heapsort - poper sorting, guaranteed n*log(n) steps to sort n elements
quicksort - proper sorting, averagely a bit more steps than heapsort, but every step has much less instructions. Beware of worst case - n*n steps.
So if you want professional sorting go for heapsort, but you could use quicksort which is usually much faster, but makes no guarantee to that.
My suggestion would be to use bucketsort first, and then perform quicksort on buckets with low number of elements and heapsort on buckets with large number of elements (more than 100?).
Hi Dylan,
I would suggest Radix sort, Google for optimized float Radix sort, its the fastest sort I’ve seen.
I’ve compared it to qsort, std::sort and optimized qsort(no recursion) it was the fastest by factor of 5.
Also try bucket sort, I use it to sort 50,000+ triangles in my meshes(for blending) with very good visual quality.
I’ve found the 1000 z slices are good enough for most cases but you could create a heuristic function based on the z depth range of your elements and their count.
If the sorting is for some kind of blending maybe a prepossess step with sorting from several different axes could be useful.
Hope it helps.
Ido
thanks for the help…but will it be use full for a set of very very much points? And to be able to view them from all different angles? pre-sorting will probably be impossible so it will only work if its done on-the-fly I think…
You can use pre-sorting from few different angles. First you choose which pre-sorted data is closest to current camera angle, and then you can additionally sort it to fix minor errors.
Quicksort will most definitely take advantage of such situation. Hell, even bubblesort would do OK with such data sets.
Radix sort seems very interesting. You could also try multikey quicksort (a.k.a. three-way radix quicksort): http://www.nist.gov/dads/HTML/multikeyQuicksort.html