c++ - Z-sorted list of 3d objects -

c++ - Z-sorted list of 3d objects -

in c++/opengl app, have bunch of translucent objects arranged in 3d space. because of translucency, objects must drawn in order furthest nearest. (for reasons described in "transparency sorting.")

luckily, photographic camera fixed. plan maintain collection of pointers 3d objects, sorted photographic camera z. each frame, i'll iterate on collection, drawing each object.

fast insertion , deletion important, because objects in existence alter frequently.

i'm considering using std::list container. insert, i'll utilize std::lower_bound determine new object goes. i'll insert @ iterator returned lower_bound.

does sound sane approach? given details i've provided, foresee major performance issues i've overlooked?

i don't think std::list ever selection utilize case. while insertion inefficient, need iterate through list find right place insertion, makes o(n) complexity.

if want maintain simple, std::set much better, , simpler apply std::list. it's implemented balanced tree, insertion o(log n) complexity, , done calling insert() method on container. iterator gives elements in sorted order. have downside of non-local memory access patterns during iteration, makes not cache friendly.

another approach comes mind intuitively should efficient. basic thought similar @ratchet_freak proposed, not re-create entire vector on each iteration:

the container contains main part of info std::vector, kept sorted. new elements added "overflow" container, std::set, or std::vector kept sorted. allowed reach size. while iterating, traverse main , overflow containers simultaneously, using similar logic merge sort. when overflow container reaches size limit, merge main container, resulting in new main container.

a rough sketch of code this:

const size_t overflow_size = 32; // ping pong between 2 vectors when merging. std::vector<entry> mainvecs[2]; unsigned activeidx = 0; std::vector<entry> overflowvec; overflowvec.reserve(overflow_size); void insert(const entry& entry) { std::vector<entry>::iterator pos = std::upper_bound(overflowvec.begin(), overflowvec.end(), entry); overflowvec.insert(pos, 1, entry); if (overflowvec.size() == overflow_size) { std::merge(mainvecs[activeidx].begin(), mainvecs[activeidx].end(), overflowvec.begin(), overflowvec.end(), mainvecs[1 - activeidx].begin()); mainvecs[activeidx].clear(); overflowvec.clear(); activeidx = 1 - activeidx; } } void draw() { std::vector<entry>::const_iterator mainit = mainvecs[activeidx].begin(); std::vector<entry>::const_iterator mainendit = mainvecs[activeidx].begin(); std::vector<entry>::const_iterator overflowit = overflowvec.begin(); std::vector<entry>::const_iterator overflowendit = overflowvec.end(); (;;) { if (overflowit == overflowendit) { if (mainit == mainendit) { break; } draw(*mainit); ++mainit; } else if (mainit == mainendit) { if (overflowit == overflowendit) { break; } draw(*overflowit); ++overflowit; } else if (*mainit < *overflowit) { draw(*mainit); ++mainit; } else { draw(*overflowit); ++overflowit; } } }

c++ opengl