[OpenGL] Depth sort particles stored as a linked list

[motionblur]

Hi all, I need to depth-sort around 5000 alpha-blended particles stored inside a linked list (not the std one); blending is not additive, glAlphaFunc() is not a option obviously and depth buffer tricks help a bit but don't work in many situations.

I've spent hours looking on the web for informations about this topic but I couldn't find any clear explanation or tutorial about depth sorting techniques or what is the best technique to do this.

Any help will be really appreciated.

Thanks a lot,

Michele

[sicarie]

I'm going to go ahead and move this over to the C/C++ Forum (instead of the Articles section), where you're more likely to get a response.

[weaknessforcats]

I have never used a depth sort, but I found this.

I don't know if it's a help or not.

If not, post again with more info.

[motionblur]

sicarie: Thanks for moving it, sorry I placed it in the wrong section by mistake.

weaknessforcats : That's what I'm looking for, basically all I need is to figure out "Step 1:Sort objects from near to far (smallest to largest z coordinate)."

What's the easier and most efficient in terms of complexity (linear time? logaritmic complexity?) way to sort a list of objects based on the square distance from the camera.

I've been suggested a couple of techniques at gamedev, like radix sort, quicksort, std::sort, etc.

[RRick]

Sorting ints or doubles from smallest to largest has been done a lot. Each of the specific sorts, have their average time (typically n*log(n)) but can degrade depending on the order of the elements. 5000 is not a lot, so I would't worry too much about the specific types of sorts.

Your problem is that the container is a linked list. Many of the sort algorithms depend on random access within the container. You don't have that with a linked list. The STL does supply a linked list sorter but will probably not work with your linked list. You might find it easiest to create an array of z-depth values and pointers to data. Most sorts can handle that type of container.

[motionblur]

Yep sounds like a good idea. Thanks a lot!

[weaknessforcats]

You might find it easiest to create an array of z-depth values and pointers to data. Most sorts can handle that type of container.

That could be done using a vector since vector is an array. The sort would be the std::sort().