next »

[Doktor_Q]

I've recently been dabbling in making a 3D world with 2D graphics. The trouble I've been running into is finding and efficient way to use "depth" in the drawing- effectively, a way to ensure the sprites that are closer to the camera overlap those farther away, without the reverse happening.

The current method I use is basically an insertion sort, and I'm a bit worried that it will cause slowdown when I start using more sprites and calculations.

[flavio]

Have you evaluated the utilization of priority queues yet?

[Doktor_Q]

...I have no idea what a priority queue is right now. So the answer is no.

[John Nesky]

Insertion sort sounds pretty good to me. Is this a premature optimization? Is this your bottleneck?

[shadowdim]

Perhaps you could give a "depth number" to every element in your scene. Then, when rendering/updating the view, start with the lowest number (= farther elements) and end with the highest (= foreground).

No?

[slembcke]

Why not just actually draw them in 3D as billboarded quads and use the z-buffer? Also, insertion sort is generally the way to go to sort data that changes very little between sorts. It's nearly optimally efficient for this. It's also very easy to write.

[Doktor_Q]

Hm. I guess I was worrying too much, then.

[slembcke]

The reason why insertion sort is nearly optimal is because the sprites don't change sort ordering very much if at all. It takes linear time to verify that a list is already sorted, which is all insertion sort does when given an already sorted list. For a list that only has a few elements out of order, it still going to be very close to linear time.

[raigan]

I wonder if the assumption of coherence is valid; as long as the camera doesn't rotate then the back-to-front order should remain almost constant, but as soon as the camera is rotating there could be significant changes each frame. Well, maybe not -- if the game is running at 60hz then probably the camera will only move a degree or two per frame at most.

Either way, I think slembcke's suggestion is the way to go: the z-buffer is just sitting there, and this lets you offload the sorting to the GPU.

[slembcke]

Unless the camera is rotating very fast or the objects to be sorted are all collinear it's still going to stay pretty well sorted.

[LemonScented]

I have a 2D engine with sprites arranged in layers. Using Z ordering can work, but you still have to sort sprites by depth before rendering them anyway, so that you don't run into problems with alpha blending. Also, changing the Z values of sprites might not always be what you want, particularly if your camera isn't orthographic - you can get weird parallax issues, or z-fighting.

For my engine, I've just got a bunch of different layers (5 or 6 at the moment, I think - I don't envisage needing many more than that), and each layer has its own vertex array. Each sprite just sticks its vertex information into the array during the game update, and then when I come to render, I just render each vertex array in turn, starting with the furthest. It works perfectly fast enough for me, plus it has the nice side-effect that it's really easy for me to put code in to specifically tweak render states in between layers.

[slembcke]

True, if you are using anything beyond cutout transparency you do still need to sort, and if you often have billboards at the same depth you can end up with nasty z-fighting artifacts.

I guess I got the impression that the OP wanted something a bit more free form than parallax layers though.

[Chromanoid]

http://www.cs.brown.edu/people/bjm/painterly.pdf (via http://www.red3d.com/cwr/npr/)
maybe this helps... did you think of geometry shaders for creating the sprites on top of a 3d mesh?

[Doktor_Q]

Ah, what I was doing is re-building the sprite list each time. I guess building a consistent list and sorting that each time might work better.

[raigan]

Or, you could be lazy and just dump the whole thing through radix sort each frame
http://www.codercorner.com/RadixSortRevisited.htm
http://www.stereopsis.com/radix.html

[Impossible]

Or, you could be lazy and just dump the whole thing through radix sort each frame
http://www.codercorner.com/RadixSortRevisited.htm
http://www.stereopsis.com/radix.html

True laziness would be to use std::sort or qsort every frame .  The most efficient way (assuming hardware acceleration) is to use the hardware z-buffer as has been suggested earlier. If 1-bit alpha is used alpha blending is not an issue.

[BorisTheBrave]

I find it hard to believe that there's any problem with using std::sort. It's not like there's millions of sprites, and with the right sort there's very low time involvement for fixing a basically sorted list.

[Average Software]

I've handled this in the past by doing one pass of a bubble sort on the sprite list every frame.

It's very quick, and I've never run into a situation where the sprites changed so much that they got out of order.

[LemonScented]

If you're not going for the option of making the renderer work in discrete layers, I can vounch for Average Software's suggestion - I've done bubble sorts for sprite ordering myself before, when chucking around a few thousand sprites on a last-gen console. Worked a treat. Bubble sort gets a bad wrap for being inefficient in the general case, but in this case it has two serious advantages:

1 - It takes almost no time to run when the list is already sorted, or nearly sorted (as will be the case the vast majority of the time in this case)

2 - It takes almost no time to write. Probably less time than I've spent reading and replying to this thread.