跳至內容

八元樹

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
八元樹
類型
發明時間1980年
發明者唐納德·米格爾
大O符號表示的時間複雜度
演算法 平均 最差
左:遞迴子切分一個立方體為多個卦限。右:對應的八元樹

八元樹(英語:Octree)是一種樹形資料結構,每個內部節點都正好有八個子節點。八元樹常用於分割三維空間,將其遞迴細分為八個卦限。八元樹是四元樹在三維空間中的對應,在三維圖形、三維遊戲引擎等領域有很多應用。

表示空間

[編輯]

八元樹的每個節點都可以代表一個空間,對應的八個子節點則將這個空間細分為八個卦限。點域(point region,簡稱PR)八元樹的節點中都儲存著一個三維,即該節點對應區域的「中心」,也是八個子節點對應區域中的一個角落。矩陣(matrix based,簡稱MX)八元樹中,節點只記錄區域範圍,對應的中心點坐標需要從區域範圍推算。因此,PR八元樹的根節點可以表示無限大的空間;而MX八元樹的根節點只能表示有限空間,這樣才可以得到隱含的中心點。

歷史

[編輯]

八元樹在3D電腦圖形領域的應用可以追溯到1980年倫斯勒理工學院唐納德·馬爾(Donald Meagher)的報告《八元樹編碼:使用電腦表示、操作、顯示任意三維對象的新技術》(Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer[1]

主要用途

[編輯]

另見

[編輯]

參考資料

[編輯]
  1. ^ Meagher, Donald. Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer. Rensselaer Polytechnic Institute. October 1980, (Technical Report IPL-TR-80-111). 
  2. ^ David P. Luebke. Level of Detail for 3D Graphics. Morgan Kaufmann. 2003. ISBN 978-1-55860-838-2. 
  3. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010. (PDF). [2018-07-03]. (原始內容存檔 (PDF)於2016-03-03). 

外部連結

[編輯]