如何在C++中構造八叉樹

我正在C++中實現八叉樹，後者應該包含用於渲染的網格。但目前我正在爲八叉樹的建設而努力。更確切地說，它是導致問題的addNode（）函數。我認爲類似於一二進制樹的遞歸實現的： Binary Tree implementation C++如何在C++中構造八叉樹

然而，在一個八叉樹的每個節點具有8個兒子和不僅2。此外，所以不能用一個簡單的開關（左/右），如二叉樹決定在哪裏添加節點。我需要檢查8個兒子中的一個是否爲空（指針爲NULL），如果沒有指針爲空，我需要用其中一個兒子作爲參數調用add函數。然而，這將導致一個八叉樹，總是第一個兒子將包含所有後續子八分音符。這個添加函數是如何實現的，並避免了這個問題？

來源

2014-03-03 00Jan00

在我讀[Octree的維基]（http://en.wikipedia.org/wiki/Octree）之前，我從來沒有聽說過他們（不是3D傢伙，Sry）。就像Phpnda的答案那樣簡單（並且被公認是隱晦的），它與所需要的東西並沒有太大的區別。每個孩子代表整個父母的空間立體感。「中心」（或起源）是父母，3D座標指示哪個可移動到該過程重複的地方。網上有很多例子。感謝大腦的食物！ – WhozCraig

您需要檢查對象的x，y，z尺寸，並且八叉樹可以保存有限數量的對象。

來源

2014-03-03 20:53:07 Bytemain

你有正確的想法，你只需要將概念擴展到三個維度。您不必確定孩子是應該插入左側還是右側（x尺寸），您還必須選擇上方或下方（y尺寸）以及前方或後方（z尺寸）。你可以使用一個三維數組是這樣的：

Node* children[2][2][2];

而且你的內部節點（那些分支機構）應該有一個3-d中心和大小。當決定在哪裏值應插入八叉樹，你需要比較的位置被插入或搜索到當前八分中心：

children[position.x > center.x][position.y > center.y][position.z > center.z]

這給在那裏你會插入指針。如果在這個位置有節點，那麼如果它是另一個分支，則需要遞歸;如果節點爲空，則創建一個新節點;如果節點是葉節點，則創建分支並重新插入。

在遍歷子元素時，可能會發現三維數組很麻煩。相反，可以使用一維陣列和索引，就像它具有三個維度：

Node* children[8]; 

int index = (position.x > center.x) << 2 | 
      (position.y > center.y) << 1 | 
      (position.z > center.z);

這生成索引[0-7]通過根據其中位置是相對於八分圓的中心設置位。

來源

2017-11-30 16:27:23

如何在C++中構造八叉樹

回答

相關問題