如何將八叉樹轉換爲具有緩存的線性數組？

Question

我有一個3D網格（稀疏的八叉樹），每個葉子（最深的節點）存儲一個3d點的顏色。我想將整個八叉樹轉換爲一個3d點的線性數組（頂點緩衝區），可以直接上傳到OpenGL。

以一種令人反感的方式，我可以迭代八叉樹的所有節點並填充線性數組。

現在，我面臨的問題是，當我向稀疏八叉樹中添加新的3d點並想更新頂點緩衝區時，我必須遍歷完整的八叉樹才能將數據導入OpenGL。

有沒有人有一個想法如何避免只有幾點更新/添加完整的迭代？

我能想到的唯一方法是記住八叉樹中的哪些元素已被添加並直接將它們追加到頂點緩衝區數組中。這會更好，但從八叉樹中刪除元素時不起作用。

我使用C++。

Answer 1

也許你可以在樣本中保留一個索引（它在頂點緩衝區中的位置）。這將允許您從陣列中移除樣本時從陣列中移除樣本。

所以整個算法將進行如下：

vertex_array

• 插入（點，樣品）

  • sample.idx = vertex_array.push（點）
  • InsertToOctree（點，樣本）

• 刪除（樣品）

  • RemoveFromOctree（樣品）
  • vertex_array.remove（sample.idx）