c++ - Z 排序的 3d 对象列表

Question

在 C++/OpenGL 应用程序中，我有一堆排列在 3d 空间中的半透明对象。由于半透明，对象必须按从远到近的顺序绘制。 (出于“Transparency Sorting”中描述的原因。)

幸运的是，相机是固定的。因此，我计划维护一个指向 3d 对象的指针集合，按相机 Z 排序。每一帧，我将遍历该集合，绘制每个对象。

快速插入和删除很重要，因为存在的对象经常变化。

我正在考虑使用 std::list 作为容器。为了插入，我将使用 std::lower_bound 来确定新对象的去向。然后我将在 lower_bound 返回的迭代器处插入。

这听起来像是一种明智的方法吗？根据我提供的详细信息，您是否预见到我忽略的任何主要性能问题？

Answer 1

我认为 std::list 永远不是这个用例的好选择。虽然插入效率很低，但您需要遍历列表以找到插入的正确位置，这使得它的复杂度为 O(n)。

如果您想保持简单，std::set 已经比 std::list 好得多，甚至更易于应用。它是作为平衡树实现的，因此插入的复杂度为 O(log n)，只需调用容器上的 insert() 方法即可完成。迭代器按排序顺序为您提供元素。它确实有迭代期间非本地内存访问模式的缺点，这使得它对缓存不友好。

我想到了另一种方法，直觉上应该非常有效。它的基本思想类似于@ratchet_freak 已经提出的，但它不会在每次迭代时复制整个 vector :

• 包含数据主要部分的容器是 std::vector，它始终保持排序。
• 新元素被添加到“溢出”容器中，它可以是一个 std::set，或另一个保持排序的 std::vector。这只允许达到一定的大小。
• 在迭代时，同时遍历主容器和溢出容器，使用与归并排序类似的逻辑。
• 当溢出容器达到大小限制时，将其与主容器合并，产生一个新的主容器。

粗略的代码草图:

const size_t OVERFLOW_SIZE = 32;

// Ping pong between two 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();

    for (;;) {
        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;
        }
    }
}