3D對象的Z排序列表

在C++/OpenGL應用程序中，我在3D空間中排列了一堆半透明對象。由於半透明性，對象必須從最遠到最近依次繪製。（由於「Transparency Sorting」中所述的原因）3D對象的Z排序列表

幸運的是，相機是固定的。所以我打算維護一個指向3D對象的指針集合，按相機Z排序。每一幀，我將遍歷集合，繪製每個對象。

快速插入和刪除很重要，因爲存在的對象經常變化。

我正在考慮使用std::list作爲容器。要插入，我將使用std::lower_bound來確定新對象的位置。然後我將插入由lower_bound返回的迭代器。

這聽起來像一個理智的方法？鑑於我提供的細節，您是否預見到我忽略的任何重大績效問題？

來源

2014-10-29 rlkw1024

如果要存儲的指針我會考慮使用'的std :: VECTOR'代替。一旦列表大小和對象大小開始變得非常大，'std :: list'只會在隨機插入時變得更好。 – sjdowling 2014-10-29 15:48:11

我不認爲std::list將永遠是這個用例的不錯選擇。雖然插入效率非常低，但您需要遍歷列表以找到插入的正確位置，這使得O（n）複雜。

如果你想保持簡單，std::set已經好多了，甚至比std::list更簡單。它以平衡樹的形式實現，所以插入的複雜度爲O（log n），只需調用容器上的insert()方法即可完成。迭代器按照排序順序爲您提供元素。它在迭代期間確實存在非本地內存訪問模式的缺點，這使得它不能緩存。

想到另一種方法，直覺上應該是非常有效的。其基本思想是類似於@ratchet_freak已經提出，但它不會複製在每次迭代整個向量：

包含數據的主要部分是一個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; 
     } 
    } 
}

來源

2014-10-30 07:16:09

std::list是一種非隨機存取容器，

複雜LOWER_BOUND的。

平均而言，第一個和最後一個之間的距離爲對數：執行大約log2（N）+1元素比較（其中N是該距離）。在非隨機訪問迭代器，迭代器的進步自己生產的N平均

額外的線性複雜性，以便它似乎不是一個好主意。

使用std::vector，您將有lower_bound正確的複雜性。

而且對於插入/刪除元素（但複雜度較低）你也可能有更好的性能。

來源

2014-10-29 15:48:19 Jarod42

「std :: vector」的緩慢插入和刪除怎麼辦？但是，正如你所說的，用'std :: lower_bound'插入'std :: list'需要O（n）操作。所以我猜這兩種方式都有一個線性時間分量？ – rlkw1024 2014-10-29 19:42:23

由於'std :: vector'是緩存友好的，即使插入/刪除，「vector」也可能比list更快。 – Jarod42 2014-10-29 19:47:12

啊，好點。另外，我認爲你是對的另一個原因。我誤讀了'lower_bound'的複雜性。我現在意識到它是O（n）*每個比較*對於一個'list'，我認爲這意味着在list上的排序插入時間是log2（n）。這可能比'vector'的插入時間差得多。（希望我的數學計算正確;我在趕上火車之前趕着打字。） – rlkw1024 2014-10-29 19:59:48

取決於列表的大小，您可以爲添加/更改最後一幀的對象和現有的大集合集保留較小的「突變集」。

然後每一幀你做了合併，而繪圖：

vector<GameObject*> newList; 
newList.reserve(mutationSet.size()+ExistingSet.size(); 
sort(mutationSet.begin(), mutationSet.end(), byZCoord);//small list -> faster sort 
auto mutationIt = mutationSet.begin(); 
for(auto it = ExistingSet.begin(); it != ExistingSet.end(); ++it){ 
    if(*it->isRemoved()){ 
     //release to pool and 
     continue; 
    } 

    while(mutationIt != mutationSet.end() && *mutationIt->getZ() < *it->getZ()){ 
     *mutationIt->render(); 
     newList.pushBack(*mutationIt); 

    } 
    *it->render(); 
    newList.pushBack(*iIt); 
} 
while(mutationIt != mutationSet.end()){ 
    *mutationIt->render(); 
    newList.pushBack(*mutationIt); 

} 

mutationSet.clear(); 
ExistingSet.clear(); 
swap(ExistingSet, newList);

你無論如何都會被做迭代和排序小的單子比追加新的名單和排序一切O(n + k + k log k)與快O((n+k)log(n+k))

來源

2014-10-29 16:18:50

3D對象的Z排序列表

回答

相關問題