在八叉樹/四叉樹中定位體素的性能

Question

這是我過去幾個小時一直在想的事情。這是一個精神鍛鍊。

所以我今天學到了八分之一！很有意思！我一直在思考如何實現一個解析爲體素的八叉樹。

我現在最大的問題是我無法包裹頭部，引用了八叉樹中的一個位置。

聲明：首先，我將在二維平面中使用四叉樹來可視化我的問題。其次，我不明白這裏的正確術語，我將假定在八叉樹中的任何細分是一個「分支」，並且任何只是一個孩子的細分（在這種情況下，它解析爲一個體素）是一片樹葉」。第三，我要在四叉樹的分支號每個空間由左到右頂部至底部{1,2,3,4}

比方說，我有一個定義了一個16×16的四叉樹單位空間。在位置[16,16]我有一個體素存儲。

4->4->4->4 

現在說我們添加一個體素到位置[4,4]。 （請注意，我們從零開始）

1->4->1->1 
4->4->4->4 

現在讓我們假設我要檢查[16.8]，看是否有體素存儲。使用前面的方法，我們在技術上遍歷這些分支：

4->1->1->1 

然而4-> 1尚未分配的任何數據，因此它是空的。 （它沒有細分，因爲它沒有被使用）。

我的問題變成這樣，我怎麼能快速遍歷四叉樹找到體素？

我的第一個也是最簡單的方法是以我上面使用的格式沿分支行進。

// Pseudo-code 
Class Quadtree { 
Quadtree Parent; 
Quadtree c[4]; // children 
}; 

Quadtree test1; 
test1.c[4].c[4].c[4].c[4]; 
Quadtree test2; 
test2.c[1].c[4].c[1].c[1]; 

這裏的問題是，voxelArray [16] [16]，voxelArray [4] [4]，或voxelArray [16] [8]的速度要快得多。使用更大的四叉樹（256x256）會增加深度（從4到8）。嵌套數組仍然是2個內存操作。 （注意，對於四叉樹，實際上我們將使用某種訪問器並檢查以確保孩子是否存在條件邏輯）

我的第二個想法是將四叉樹存儲爲體素本身。例如，假設我們有一個2x2的陣列，清空看起來像

{0, 0, 0, 0} 

在位置[1,1]，我們將增加一個體素，它會成爲

{0, 0, 0, 1} 

如果我們存儲四叉樹它會是這個樣子

{1/*q*/, 0, 0, 0, 1} 

把這個交給4x4和

{0/*q*/, 0, 0, 0, 
0/*q*/, 0, 0, 0, 
0/*q*/, 0, 0, 0, 
1/*q*/, 0, 0, 1} 

雖然現在你可以直接訪問數據，你已經失去了四叉樹的內存緊湊，但您仍執行許多邏輯運算。國際海事組織這隻會工作得很好，如果你有大面積的0和1的小組。

通過四叉樹/八叉樹存儲體素，您可以通過他們全部循環時提高性能，但失去效能時，直接訪問它們。

Answer 1

可以計算quadkey然後散列每個像素。這個想法是減少尺寸複雜性。您可以查找哈密爾頓路徑或z曲線或希爾伯特曲線的示例。這條道路完全穿過飛機，但在技術上仍然是一條曲線。

Answer 2

這比一個答案延長評論。儘管如此，它可能對您有所幫助。或者它可能不會。你的例子：

{0, 0, 0, 0} 

沒有示出一個空的四叉樹，它示出了四叉樹，其中所有4個象限具有在第一（也是唯一的）電平值0。這：

{} 

說明一個空的四叉樹。這個：

{0, 0, 0, {1,0,1,0}} 

說明了一個四叉樹，其中3個象限都是0，第四個是棋盤（儘管是一個小棋盤）。這：

{{1,{1,0,0,0},0,{1,1,1,{0,0,0,1}}}, 0, 0, {1,0,1,0}} 

開始變得棘手，但你現在得到我的漂移。

在某些語言（如Lisp，Matlab，Mathematica）中，這些插圖可以直接實現和操作。在許多語言中，您可以將四叉樹實現爲指針和/或值的集合。