オクターブは、最適化だけでなく、コンピューターグラフィックスの視覚化に関連する多くの問題を解決するために使用されます。 たとえば、有名で愛されているidSoftwareは、コンピューターグラフィックステクノロジーやコンピューターゲームに関連する他のすべてのフラッグシップであり、革新的なSparse Voxel Octreeテクノロジーを搭載した新しい、そしてもちろんハイテクid Tech 6エンジンを実装しています。オクトツリーがあります。 オクターブを使用すると、DukeNukem 3Dエンジンのチーフプログラマーがかつて作成したように、完全に破壊可能なモデルジオメトリを作成できます。 最適化に関しては、この構造は物理モデリングエンジンで使用されるため、石材の作業がはるかに簡単になります。 さて、レイトレーシングなしでは実行できません。ここではオクトツリーも使用されます。

カットの下で多くのトラフィック！

オクトツリーは、ツリーのような再帰的なデータ構造であり、その各ノードには8つの子孫が含まれます。 これは、正面、水平面、プロファイル平面に平行な3つの平面で分割され、立方体の幾何学的中心を通る3次元立方体（ ボクセル ）として表すことができます。 その結果、1つのoctreeツリーノードの子孫である8つのキューブを取得します。 大きなキューブ。
以下に、octreeツリー要素を検索、バイパス、削除するための簡単なアルゴリズムを示します。

1ツリーを見つけて作成するためのアルゴリズム

ツリーを作成します。 ノードでは、ボクセルの幾何学的パラメーター、強調表示の色を入力します。 構造は次のようになります

struct octTree { mid midle; //   float lenght; //   char novusial; //  : / RGB_color color;//   octTree* up; //    octTree* t1; //  octTree* t2; octTree* t3; octTree* t4; octTree* t5; octTree* t6; octTree* t7; octTree* t8; }; struct mid //   { float x; float y; float z; }; struct RGB_color //  { float R; float G; float B; }; 

次に、構造全体を最初から作成します。 Dscr-キューブ（octreeツリー）の解像度、ツリー全体のサブボクセルの数。 Descrは8の倍数でなければなりません。midmidle-中心の座標、float len-立方体の辺の長さ、octTree * up-関数の最初の実行での親ノード、ルートアドレスを挿入* root、octTree ** el-作成されたノードを保存する場所へのポインター最初の実行では、ルートアドレス**ルートのアドレスを挿入します。

 // . dscr -    el . void OctObject::makeTr(octTree** el,int dscr,mid midle,float len,octTree* up) { mid setmidle; //        / if(*el==NULL) { (*el)=new octTree; (*el)->lenght=len; (*el)->midle=midle; (*el)->novusial=0; (*el)->color.B=(*el)->color.G=(*el)->color.R=1; // . null(*el); (*el)->up=up; if(!(dscr%8)) { (*el)->novusial=1;//    . //      //    ,   setmidle.x=(*el)->midle.x-(*el)->lenght/4; /// 1 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t1),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 2 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t2),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 3 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t3),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 4 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z+(*el)->lenght/4; this->makeTr(&((*el)->t4),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 5 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t5),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 6 -   setmidle.y=(*el)->midle.y+(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t6),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x-(*el)->lenght/4;/// 7 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t7),dscr/8,setmidle,(*el)->lenght/2,(*el)); setmidle.x=(*el)->midle.x+(*el)->lenght/4;/// 8 -   setmidle.y=(*el)->midle.y-(*el)->lenght/4; setmidle.z=(*el)->midle.z-(*el)->lenght/4; this->makeTr(&((*el)->t8),dscr/8,setmidle,(*el)->lenght/2,(*el)); } } else if(*el==root) //     { setmidle.x=root->midle.x-root->lenght/4; /// 1 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t1),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 2 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t2),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 3 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t3),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 4 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z+root->lenght/4; this->makeTr(&((*el)->t4),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 5 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t5),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 6 -   setmidle.y=root->midle.y+root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t6),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x-root->lenght/4;/// 7 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t7),dscr/8,setmidle,root->lenght/2,root); setmidle.x=root->midle.x+root->lenght/4;/// 8 -   setmidle.y=root->midle.y-root->lenght/4; setmidle.z=root->midle.z-root->lenght/4; this->makeTr(&((*el)->t8),dscr/8,setmidle,root->lenght/2,root); } return; } 

ご覧のとおり、関数は再帰的です。
カメラを回転させたときにサブボクセルを視覚的に強調表示するために、octreeの要素を検索するアルゴリズムを作成します。

ボクセルを強調表示するには、それを見つける必要があります。このため、画面の中心から直接レイトレーシングメソッドを3次元シーンの深さに適用し、見つかったレイとボクセルの交点を使用してボクセル自体を取得します。

X、y、z-現在の時間の光線ベクトルの座標。 octTree * el-交差点を探しているノード。

 //    ,   . octTree* OctObject::seach(float x, float y, float z,octTree *el) { if(el->t1==NULL) if(el->novusial!=1) //       ,    . return el; else return NULL; else { if(((el->midle.z+el->lenght/2)>=z)&&(el->midle.z<=z))//1 -   oz -  { if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1-    oy-  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t1); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t2); } else return NULL; //   } else { if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2-   oy -  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t3); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t4); } else return NULL; //   } else return NULL; //   } } else { if(((el->midle.z-el->lenght/2)<=z)&&(el->midle.z>=z))//2 -   oz -  { if(((el->midle.y+el->lenght/2)>=y)&&(el->midle.y<=y))// 1-    oy-  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t5); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t6); } else return NULL; //   } else { if(((el->midle.y-el->lenght/2)<=y)&&(el->midle.y>=y))// 2-   oy -  { if((el->midle.x-el->lenght/2<=x)&&(el->midle.x>=x))//1 -    ox-  { return seach(x,y,z,el->t7); } else if((el->midle.x+el->lenght/2>=x)&&(el->midle.x<=x))//2-    ox-  { return seach(x,y,z,el->t8); } else return NULL; //   } else return NULL; //   } } else return NULL; //  } } } 

スペースバーを押すかスクロールしてボクセルを削除することにより、キーボードとマウスのハンドラーからこの関数を呼び出します。 ここでビームをトレースします。

 //    ,         . octTree* OctObject::FindVoxeloutside(float a, float b,float c) { float x,y,z; octTree *ret; z=(fabs(x=(fabs(a)>=fabs(b) ? a : b))>=fabs(c) ? x : c);//      ,  ,,    . if(z==a) { x=a; //   do{ if(fabs(a)>=fabs(x)) { y=x/a*b; z=x/a*c;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } x+=eps*(a>0 ? -1 : 1); }else return NULL; }while(true); } else if(z==b) { y=b; //   do{ if(fabs(b)>=fabs(y)) { x=y/b*a; z=y/b*c;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } y+=eps*(b>0 ? -1 : 1); }else return NULL; }while(true); } else if(z==c) { z=c; //   do{ if(fabs(c)>=fabs(z)) { x=z/c*a; y=z/c*b;//   .        . if((ret=seach(x,y,z,root))!=NULL) { return ret; } z+=eps*(c>0 ? -1 : 1); }else return NULL; }while(true); } return NULL; } 

2ノードを削除する

私の場合、構造からノードを完全に削除することは望ましくなく、採算が取れません。 頂点をOpenGLパイプラインに送信せず、面を表示しないように、削除された要素に削除フラグを設定します。 ここで、特定のイベントの完了時または特定の時間間隔で、ツリー全体を再構築し、メモリからマークされたノードとサブノードを除外および削除する遅延再構築を行うことができます。

 //   (  6   6  ""   ). void OctObject::del(octTree *el) { if(el==NULL) { return; } else { el->novusial=1;//    (). if(el->up==NULL)//  . return; if(el->up->novusial)//  /     el, return; // novusial==1,   ,    novusial==1, ..   . del(el->up); } return;} 

さらに、「パート2」で、これらすべてをOpenGLでかき混ぜる方法を教えて示すことを願っています。

OpenGLでこのプロジェクトをスピンする残りのコードを表示し、バイナリとプロジェクト全体をここで取得できます。