2
\$\begingroup\$

I'm using depth buffer as a layering system for my 2d render and I have to draw them from back to front to make semi-transparent quads work out. The problem is I have to sort my quads vector based on their depths whenever I add or remove one and that is time consuming. I've done this before, but I'm not sure what's the down side because in my mind I think if I sort a vector of let's say 5000 quads, then it'll really keep CPU busy if I remove one of them and sort the other 4999 items in a single frame.

I need to know if there is an alternate way for this or this is just it.

\$\endgroup\$
  • 2
    \$\begingroup\$ you could use an acceleration structure like a binary tree, quadtree, or octree. Could also store your quads as a B+ tree to deal with re-sorting smaller lists. \$\endgroup\$ – Nicolas Louis Guillemot Jun 26 '14 at 23:24
  • \$\begingroup\$ @NicolasLouisGuillemot You mean these structures will perform faster than a vector? \$\endgroup\$ – MahanGM Jun 27 '14 at 12:33
  • \$\begingroup\$ definitely, since they subdivide the problem. \$\endgroup\$ – Nicolas Louis Guillemot Jun 27 '14 at 20:36
  • \$\begingroup\$ @NicolasLouisGuillemot I'll give it a try. Thanks. \$\endgroup\$ – MahanGM Jun 27 '14 at 22:28
  • 1
    \$\begingroup\$ @davidvanbrink I mistakenly wrote sort on remove, I just sort on add and any depth change during run time. 5000 is just an example. I don't really know how many objects would be there in the scene, but it's important to know that the program can perform under stress. Currently I use std::sort(), but I'm thinking to switch over to a quad-tree. \$\endgroup\$ – MahanGM Sep 28 '14 at 13:29
3
\$\begingroup\$

A smart bubble/insertion sort is faster than quick sort when the array is already mostly sorted (reused on the next frame).

To speed up the copy of data rather than copying entire vertex values use an index buffer to sort the vertices.

When you remove quads you can quickly degenerate them (set all vertices to the same value) instead of removing them and copying over the following quads.

You can then gradually compact them over multiple frames or compact them only as needed. Inserting into a "swiss-cheese" vertex array with such holes lets you move data only up to the first hole and stop there rather than move the whole array.

Krom Stern's answer of using linked vectors (a list of shorter arrays) is excellent as you can fine tune the technique to a sweet spot between [number of draw calls] and [sort time of individual buffers], always put an extra bit of free space in each buffers.

And for the more adventurous:

If insertion speed is critical you can use the top-1 N bits of a positive float as an integer, skipping the sign bit, into an array of linked lists.

IEEE floating points of the same sign can be compared and sorted as integers, its part of the standard's design. They are one's-complements rather than two's-complements but this doesn't matter if we're only using positive z. If we need both positive and negative z then the negative z needs a set of reverse-sort functions due to being one's-complements.

#define NBITS 10    // 1024 entries
SortList *lists[1 << NBITS] = {0};
...
float z = object->z;
if(z <= 0){ // IMPORTANT this includes negative zero which is distinct from positive zero
 z = 0; // negative float number are in reverse when interpreted as integers, this would need a set of reverse functions
}
uint32_t raw_z_bits = ((uint32_t &)z);
uint32_t list_number = (raw_z_bits >> (31 - NBITS)); // 31 because we skip the sign bit
uint32_t index_within_list = raw_z_bits & ((1 << (31 - NBITS))-1);
AddToList(lists[list_number], index_within_list, object );

This is useful when you don't know the range you'll need to sort and/or are already using floating point depth values.

If you're using integer depth values using this float hack will limit you to 23 bits of depth values (0 to +8M) as 32bit floats only have 23 bits (+ 1bit sign) of precision (8bits used for the exponent).

All this gets complicated quickly so a good idea for debugging is to have an independant sanity-check using a per-frame sort-all-active-objects-and-verify function that will confirm everything is sorted properly and there are no bugs in the faster, gradual sorting system.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer, but I'm really confused with what you're saying. I'm trying to do something else with my list now, but if I didn't succeed, I'll come to take a deep look at your solution. Thank you. \$\endgroup\$ – MahanGM Dec 28 '14 at 18:08
0
\$\begingroup\$

You could use a different approach for your list.

Linked list. where each item hold a pointer to the next item in list. Insertion and removal cost is O(1). This is not cache friendly though, but you can try.

Better sorting methods, e.g. if you use a bubble-sort, you can pick a much better algo that suits your case better (single insertions/removals don't require to resort whole list).

You can combine and store your objects in linked vectors, where each vector is e.g. 32 items and those are linked into a list. When vector grows too big - split it. When too small - merge it to neighbour.

You can also look into spatial partitioning (Quad-trees).

\$\endgroup\$
  • 1
    \$\begingroup\$ I was interested in quad trees rather than anything else, but currently I'm focused on other things. I decided to sort the list at every late update in the loop, that way if an object's depth is changed during the loop it'll be sorted too. I thought to put a kind of sort flag to avoid unnecessary calls to sort so I can sort whenever there is a change. Thanks for the advice though. \$\endgroup\$ – MahanGM Aug 29 '14 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.