稀疏八叉樹的高效存儲？

任何人都可以提出一個快速，用於存儲和訪問稀疏八叉樹有效的方法？稀疏八叉樹的高效存儲？

最好是可以在HLSL中輕鬆實現的東西。（我正在一個光線投射/體素的應用程序）

在這種情況下，樹可以預先計算，所以我主要關心的是大小和搜索時間。

更新

對於任何要做到這一點，一種更有效的解決方案可以是節點存儲爲具有Z階曲線/莫頓樹產生的線性八叉樹。這樣做消除了內部節點的存儲，但可能需要使用包含關於單個體素的信息的第二個「數據紋理」來交叉引用線性樹數組。

來源

2011-05-22 David Lively

當你說稀疏，你的意思是有廣闊的三維空間中，只有極少數，小件物品？ – 2011-05-22 05:55:23

@凱文是的。假設，一個立方體大小爲（2^10）^ 3（1GB）的元素，可能大約爲20％。 – 2011-05-22 15:13:44

與普通八叉樹不同嗎？對不起，我熟悉quad和octrees，但是稀疏的八叉樹聽起來像是我的新東西。 – 2011-05-22 16:12:27

我不是很在HLSL經歷過，所以我不知道這將滿足您的需求，這裏有我的想法。讓我知道這裏的東西是否不符合你的需求 - 我想討論一下，或許我可以自己學習一些東西。

八叉樹中的每個節點都可以作爲vector3存在，其中（x，y，z）分量表示節點的中心點。 w組件可以用作標誌字段。 a。 w-flags字段可以表示哪個八分體子節點跟隨當前節點。這將需要8位數值。
存儲在你的八叉樹的每個實體可以被存儲爲一個邊界框，其中R，G，B可以是邊界框的尺寸和w可用於任何。
定義一個特殊的向量表示對象列表如下。例如，如果（w + z）是一些魔法值。例如，一些func（x，y）可以是後面的對象的數量。或者，無論什麼作品。 a。每個節點後面都可能跟着這個特殊的向量，表明這個節點中存有對象。接下來的X向量都只是對象標識符或類似的東西。 b。或者，您可以讓一個節點指定一個內存中的對象列表。再次，不確定你在這裏需要什麼或者如何訪問對象的限制。

因此，首先，建立八叉樹和東西它與你的對象。然後，走八叉樹，輸出矢量到內存緩衝區。

我在想，一個512x512的紋理可以容納座無虛席八叉5級深（32,768節點），各包含8個目標。或者，一個完整打包的4級八叉樹，每個八叉樹有64個對象。

來源

2011-05-24 16:37:51

不錯的做法，明確的解釋。 +1 – 2011-05-27 14:10:25

通過假設一個作爲單位立方體的根節點，使用.a來指示內部，葉子或空，並將偏移量存儲到第一個子項中。r爲內部節點，我可以將其降至每個八叉樹節點1個像素。這讓我可以在DX9中通過4K 2D紋理尺寸在最大4K上放置一些相當深的樹。以特定順序保留子節點並利用隱含的邊界框確實有所幫助。 – 2012-08-17 15:46:16

有關於稀疏八叉樹集中在GPU上一大篇：Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation

來源

2011-05-25 20:35:33 thalador

稀疏八叉樹的高效存儲？

回答

相關問題