Jump to content

  • Log In with Google      Sign In   
  • Create Account

Roof Top Pew Wee

Member Since 18 May 2001
Offline Last Active Jul 09 2010 06:06 AM

#3017154 Do I need to Z-sort my particles?

Posted by on 21 April 2005 - 05:35 AM

Consider the following:

The fastest sorting algorithms are usually logarithmic. However, there are assumptions you can take advantage of to make your sort even faster. Consider that once your particles are sorted, you know that next frame they will generally still be sorted. You may have some movement parallel to your view vector, but it's not by much. So actually, the most naive sorting algorithms like insertion sort will be the best, as your test will either reveal that the particular particle is already where it is, or that it will only need to move a few spaces.

This might not seem like it's right, but I ran some tests in my engine sorting a couple of thousand Sprites. I found that if your data is over 97% sorted with large data sets, then something like insertion sort will actually beat out quicksort. If you're going to run this sorting algorithm every frame, this 97% is a good bet.