當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

八叉树 ( 1 )

發布時間：2024/5/15 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了八叉树 ( 1 ) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1、對Octree的描述

Octree的定義是：若不為空樹的話，樹中任一節點的子節點恰好只會有八個，或零個，也就是子節點不會有0與8以外的數目。那么，這要用來做什么？想象一個立方體，我們最少可以切成多少個相同等分的小立方體？答案就是8個。再想象我們有一個房間，房間里某個角落藏著一枚金幣，我們想很快的把金幣找出來，聰明的你會怎么做？我們可以把房間當成一個立方體，先切成八個小立方體，然后排除掉沒有放任何東西的小立方體，再把有可能藏金幣的小立方體繼續切八等份….如此下去，平均在Log8(房間內的所有物品數)的時間內就可找到金幣。因此，Octree就是用在3D空間中的場景管理，可以很快地知道物體在3D場景中的位置，或偵測與其它物體是否有碰撞以及是否在可視范圍內。

2、實現Octree的原理

(1). 設定最大遞歸深度

(2). 找出場景的最大尺寸，并以此尺寸建立第一個立方體

(3). 依序將單位元元素丟入能被包含且沒有子節點的立方體

(4). 若沒有達到最大遞歸深度，就進行細分八等份，再將該立方體所裝的單位元元素全部分擔給八個子立方體

(5). 若發現子立方體所分配到的單位元元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎么切數目還是一樣，會造成無窮切割的情形。

(6). 重復3，直到達到最大遞歸深度。

3、Octree的存貯結構

本例中Octree的存貯結構用一個有（若干+八）個字段的記錄來表示樹中的每個結點。其中若干字段用來描述該結點的特性(本例中的特性為：節點的值和節點坐標)，其余的八個字段用來作為存放指向其八個子結點的指針。此外，還有線性存儲和1托8式存儲。

4、BSP Tree和Octree對比

a) BSP Tree將場景分割為1個面，而Octree分割為3個面。

b) BSP Tree每個節點最多有2個子結點，而Octree最多有8個子結點

因此BSP Tree可以用在不論幾唯的場景中，而Octree則常用于三維場景

5、本例實現Octree的若干關鍵技術及截圖

A、主界面：

Main函數中使用while(true)產生類似Trinigy引擎中的渲染循環效果，等待用戶輸入操作。通過IF判斷用戶的輸入并進行相應的操作。

[Copy to clipboard] [-] View CodeCPP
1234567891011	cin>>choiced; while(true){ if(choiced == 0) return 0; else if(choiced == 1) {………… } …………}

B、創建八叉樹界面，需要用戶輸入遞歸次數和外包盒在三維場景中的坐標

本例使用3層深度，外包盒坐標為（1,100,1,100,1,100）

[Copy to clipboard] [-] View CodeCPP

12345678910111213

template<class T>struct OctreeNode{T data; //節點數據 T xmin,xmax; //節點坐標，即六面體個頂點的坐標 T ymin,ymax; T zmin,zmax; OctreeNode <T> *top_left_front,*top_left_back; //該節點的8個子結點,即個子六面體 OctreeNode <T> *top_right_front,*top_right_back; OctreeNode <T> *bottom_left_front,*bottom_left_back;OctreeNode <T> *bottom_right_front,*bottom_right_back;…………};

樹的結構圖：

C、創建成功后先序遍歷此八叉樹。

[Copy to clipboard] [-] View CodeCPP

12345678910111213141516171819

void createOctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax){ maxdepth=maxdepth-1; //每遞歸一次就將最大遞歸深度-1 if(maxdepth>=0) { root=new OctreeNode<T>(); root->xmin=xmin; //為節點坐標賦值 root->xmax=xmax;……………… double xm=(xmax-xmin)/2; double ym=(ymax-ymin)/2; double zm=(ymax-ymin)/2; //計算節點3個維度上的半邊長 //遞歸創建子樹，根據每一個節點所處（是幾號節點）的位置決定其子結點的坐標。 createOctree(root->top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax); createOctree(root->top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax); ……………… //8個子結點 }}

共產生了73個節點，由于比較多，沒有截出全部結果。

D、查看此樹的深度

即查找1號節點的個數。

[Copy to clipboard] [-] View CodeCPP
1234567891011121314	int i=1;template <class T>void preOrder( OctreeNode<T> * & p){ if(p) { cout<<i<<".當前節點的值為："<<p->data<<"/n坐標為："; cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;………… i+=1; preOrder(p->top_left_front); preOrder(p->top_left_back);……………… }}

E、查找點，需要用戶輸入坐標，本例使用坐標（80，80，80）

如果用戶輸入的點在場景外，則提示沒有找到。如（200，2，200）

根據用戶定義的最大遞歸深度和場景的坐標，計算一下該場景被分割后的最小6面體各邊的邊長，然后判斷用戶輸入的坐標是在當前節點的哪一個子結點中并循環搜索，直到達到葉子節點。（代碼較多，詳情請見下面的源代碼）

6、源代碼

八叉樹節點類的定義：

[Copy to clipboard] [-] View CodeCPP
12345678	template<class T>int depth(OctreeNode<T> *& p){ if(p == NULL) return -1; int h = depth(p->top_left_front); return h+1;}

創建節點的函數：

總結

以上是生活随笔為你收集整理的八叉树 ( 1 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

八叉树

上一篇：关于项目奖
下一篇： jqprint实现浏览器打印功能