在這篇論文中，我們探討兩項主題：即線性八元樹的建構與顯像（construction and
display）。
關於建構方面，我們採用的方式是：平移掃描法（translational sweep ）。我們提
出四個掃描的演算法，這些演算法是以一種演進的方式來陳述。一開始直接利用從下
往上的策略（bottom-up ），遞迴地合併兩片相鄰的一般化樹（generalized tree）
，直到最後在深度為一的兩片被合併為止。這其餘的演算法皆是由上往下（top-down
）的策略，並利用假的區間樹（pseudo-range tree ）來控制掃描的步距；這第二和
第三個演算法以一種類似樹的後序走訪（postorder traversal ）方式來走訪四元樹
的節點，並拷貝相對應的四元樹節點當成八元樹節點。這第四個演算法模擬像樹般走
訪的演算法，它是最佳的，因為它的時間複雜度（time complexity ）僅與黑色的節
點數成正比，而且，也不須要任何額外的暫存空間，也就是說，它須要０（B ）的時
間，這裡B 是黑色節點的數目。此外，每個演算法將會產生排好序且緊密的八元樹，
而且，其相對的執行時間也被列出來比較與討論，這些結果顯示：現存演算法的執行
成本己經被明顯地改進了。
另一方面，關於顯像部份，我們對於八元樹節點間因互擋而產生的可見性（visibil-
ity ）問題，亦介紹一個改進的方法。這個演算法的基本觀念是根基於求相對應的優
先權函數，這個函數將每個黑色的節點映成一個由後到前（back-to-front ）的顯像
順序，它的時間複雜度是０（B ），比現存的演算法０（nB）還要好，同樣地，一些
實驗的數據是被比較，其結果顯示：新的演算法比舊的演算法快很多，且這舊演算法
的執行成本將隨著n 的變化而線性地改變，這裡n 是解析度因子（resolution fact-
or）。
|