オクトリーの紹介

octreeとは何ですか？ この概念をまったく知らない場合は、 ウィキペディアの記事を読むことをお勧めします （これには約5分かかります）。 それは十分なアイデアを与えますが、それらがなぜ使用され、どのようにそれらを実装するのかを理解するのに十分ではありません。



この記事では、概念、図、およびコードを説明する例を使用して、octreeツリーのデータ構造を作成するために必要なすべての手順について説明します。 また、各段階で下した決定についても説明します。 この記事がオクターブの実装に関する唯一の真のガイドになるとは思わないが、それはあなたに良い基礎を与えるはずであり、参照のために使用することができる。

必要な知識

この記事を書くとき、読者は次のことを前提としています。

1. Cスタイルの構文を持つ言語のプログラミングに精通している（XNAでC＃を使用する）。
2. バイナリ検索ツリー などのデータ構造のような 、ある種のツリーはすでにプログラミングされており、再帰、その長所と短所に精通しています。
3. 境界長方形、球体、および角錐台で衝突認識がどのように実現されるかを知っています。
4. 彼は標準のデータ構造（配列、リストなど）を理解し、 大きな「O」が何であるかを理解しています（ このGDnetの記事で読むことができる大きな「O」 について ）。
5. 彼は、衝突をチェックする必要がある機能があるプロジェクトに取り組んでいます。

シーンの準備

非常に大規模なゲームを作成し、さまざまな種類、形状、サイズの何千もの物理オブジェクトを含めることができ、それらのいくつかは互いに衝突する必要があるとします。 各フレームで、どのオブジェクトが互いに交差するかを判断し、これらの交差を何らかの方法で処理する必要があります。 ゲームの速度が落ちないようにこれを行う方法は？

単純なブルートフォースによる衝突検出

最も簡単な解決策は、各オブジェクトを世界のすべてのオブジェクトと比較することです。 これは通常、2つのforループで実行できます。 コードは次のようになります。

foreach(gameObject myObject in ObjList) { foreach(gameObject otherObject in ObjList) { if(myObject == otherObject) continue; //       if(myObject.CollidesWith(otherObject)) { //   } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

グラフィカルには、次のように表すことができます。







赤い線はそれぞれ、CPUの交差点のコストの高いチェックです。



当然、そのようなコードはO（N ² ）回実行されるため、恐ろしいはずです。 10,000個のオブジェクトがある場合、1億個の衝突チェック（1億個）を実行する必要があります。 プロセッサの速度や数学コードをどれだけ改善したかは関係ありません。そのようなプログラムはコンピュータの速度を低下させます。 ゲームが毎秒60フレームで動作する場合、毎秒60 * 1億の計算が実行されます！ これは完全な狂気です。



これを回避できる場合は、少なくとも大規模なオブジェクトのセットについては、これを行わないでください。 これは、たとえば、チェックが10個のオブジェクト（100個のチェック）に対してのみ実行される場合にのみ受け入れられます。 ゲーム内にオブジェクト（たとえば小惑星）がほとんどないことを事前に知っている場合は、単純な枯渇が適切であり、八分木を完全に放棄することができます。 フレームごとの衝突チェックが多すぎるためにパフォーマンスの問題に気付き始めた場合、非常に簡単な最適化を使用できます。



1.衝突計算手順にはいくつの計算が必要ですか？ たぶんその中のどこかに平方根の計算が隠されているかもしれません（たとえば、距離をチェックするとき）？ 詳細な衝突チェック（ピクセル、三角形などの交差）を実行していますか？ 標準的な手法があります。最初に衝突の大まかなチェックを実行してから、より詳細なものに進みます。 長方形または球形の境界線を記述するオブジェクトを追加し、境界線の交差を確認してから、より多くの数学的計算とリソースを必要とする詳細なチェックを実行できます。

オブジェクト間の距離を比較するには、オブジェクト間の平方平方距離を使用して、平方根の計算を避けます。 平方根を計算するには、通常ニュートン近似が使用され、非常に高価になる可能性があります。

2.より少ない衝突チェックを計算することで取得できますか？ ゲームが毎秒60フレームで実行される場合、いくつかのフレームをスキップできますか？ 一部のオブジェクトの動作が決定的である場合、それらの衝突は事前に計算できます（たとえば、ビリヤードボールとテーブルの側面の間）。 スキャンされるオブジェクトの数を減らすことは可能ですか？ オブジェクトを異なるリストに分割してみてください。 1つのリストには、「静止」オブジェクトを含めることができます。 互いの競合をチェックすることはできません。 別のリストには、「移動する」オブジェクトが含まれる場合があります。このオブジェクトについては、他のすべての移動オブジェクトおよびすべての静止オブジェクトとの衝突をチェックする必要があります。 これにより、必要な衝突チェックの数を許容可能なパフォーマンスレベルまで減らすことができます。



3.パフォーマンスの問題がある場合、一部のオブジェクトの衝突のチェックを拒否することは可能ですか？ たとえば、煙の粒子は表面オブジェクトと相互作用し、その輪郭をたどって美しい効果を生み出すことができますが、これはゲームプレイを妨げるべきではありません。 チェックの数が特定の制限を超えた場合、煙粒子の衝突の計算を停止できます。 ただし、 重要なゲームオブジェクトの動きを無視すると、ゲームプレイも破壊されます（たとえば、プレイヤーの弾丸がモンスターと相互作用しなくなります）。 つまり、衝突の優先度チェックのリストを保持しておくと便利です。 まず、優先度の高いコリジョンが処理され、制限を超えない場合、優先度の低いコリジョンが処理されます。 制限に達すると、ゲームは優先順位リストに残っているすべての要素を破棄するか、将来の検証を遅らせる必要があります。



4.実行時にO（N ² ）を取り除くために、衝突を検出するためのより高速でありながら簡単な方法を使用することは可能ですか？ 衝突がすでにチェックされているオブジェクトを削除すると、ランタイムはO（N（N + 1）/ 2）に短縮されます。これははるかに高速ですが、実装は非常に簡単です（技術的には、これはまだO（N ² ）です） ） ソフトウェア開発の観点から見ると、結果として、貧弱なアルゴリズムと不正確なデータ構造の改善によるパフォーマンス低下を抑えるためにかかる費用よりも多くの時間を費やすことができます。 費用便益比は益々不採算になりつつあり、衝突認識の処理により適切なデータ構造を選択する時が来ました。



実行時の衝突の認識の問題の解決策として、スペースを分割するアルゴリズムが積極的に使用されています。 速度の一部を事前に選択しますが、対数的に衝突チェックの回数を減らします。 開発時間とCPUの初期費用は、スケーラビリティと高速化の利点によって簡単に相殺されます。

スペースブレイクのコンセプト

一歩後退して、八分木に移る前に、一般に空間と木を分割する考えを考えてみましょう。 この概念を理解していない場合、コードで実装することはできません。



上記の単純な検索の実装では、ゲーム内の各オブジェクトを取得し、その位置を他のすべてのオブジェクトの位置と比較して、関連するかどうかを確認しました。 これらのオブジェクトはすべて、ゲームの世界に空間的に配置されています。 ゲームの世界を制限する図を作成し、この図に含まれるオブジェクトを見つけると、そこに含まれるオブジェクトのリストを含むスペース領域ができます。 この場合、ゲームのすべてのオブジェクトが含まれます。



1つのオブジェクトが世界の一端にあり、もう1つのオブジェクトが反対側にあることがわかります。したがって、各フレームでオブジェクト間の衝突チェックを計算する必要はありません。 これは貴重なプロセッサ時間の無駄になります。 おもしろいことをしよう！ 世界を正確に半分に分割すると、オブジェクトの3つの個別のリストを作成できます。



最初のリスト、リストAには、ワールドの左側にあるすべてのオブジェクトが含まれます。



2番目のリストList Bには、世界の右側にオブジェクトが含まれています。



一部のオブジェクトは、パーツ間の境界線、つまりその両側にある境界線に触れる場合があります。 そのようなオブジェクトに対して、3番目のリスト、リストCを作成します。







各区分で、世界を半分に空間的に縮小し、結果の半分にあるオブジェクトのリストを収集することに気付くかもしれません。 これらのリストを保存するために、バイナリ検索ツリーを作成できます。 このようなツリーの概念は次のようになります。







擬似コードのツリーのデータ構造は次のようになります。

 public class BinaryTree { //   ,      private List m_objectList; //         private BinaryTree m_left, m_right; //     (   ). private BinaryTree m_parent; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リストAのすべてのオブジェクトがリストBのオブジェクトと交差することはないため、衝突チェックのほぼ半分を放棄できます。 リストCには、リストAおよびBのオブジェクトに触れることができるオブジェクトが残っているため、リストA、B、Cのすべてのオブジェクトとの衝突がないか、リストCのすべてのオブジェクトを確認する必要があります



世界をますます小さな部分に分割し続けるなら、毎回半分ずつチェックの数を減らし続けます。 これが、スペースを分割する主なアイデアです。 世界をツリーのようなデータ構造に分割する方法は多数あります（ バイナリスペースパーティション（BSP） 、 四分木 、 K次元木 、八分木など）。



ここで、デフォルトでは、すべてのオブジェクトが世界全体にほぼ均一に分布していると考えているため、最良の分割は真ん中のちょうど半分の分割であると単純に仮定します。 これは良い仮定ですが、一部のパーティションアルゴリズムでは、各半分に等しい数のオブジェクトが存在するようにパーティションが実行され（重み付けパーティション）、結果のツリーのバランスがより良くなります。 しかし、これらすべてのオブジェクトが動き始めるとどうなりますか？ ほぼ均等な分割を維持するには、割線面を移動するか、各フレームでツリーを完全に再構築する必要があります。 これはかなり複雑で複雑です。



したがって、スペースパーティションツリーを実装するために、毎回それを半分に分割することにしました。 その結果、一部のツリーはよりまばらになりますが、これは正常であり、大きなコストにはつながりません。

共有するか共有しないか？ それが問題です。

ほんの数個のオブジェクトだけでかなりまばらな領域があるとします。 最後のオブジェクトの可能な限り小さい境界スペースが見つかるまで、パーティションの実行を続行できます。 しかし、それは必要ですか？ ツリーを作成する理由は 、各フレームで実行される衝突チェックの回数の減少であり、すべてのオブジェクトを理想的に区切る空間領域の作成ではないことを思い出してください。 分割するかどうかを決定するために選択したルールは次のとおりです。

• オブジェクトが1つしかない分離を作成する場合、スペースをさらに分割できるという事実にもかかわらず、分割を停止します。 このルールは、octreeで「リーフノード」を定義する基準の重要な部分になります。
• もう1つの重要な基準は、領域の最小サイズを設定することです。 サイズが数ナノメートルの非常に小さなオブジェクトがある場合（またはコードにバグがあり、オブジェクトのサイズを初期化するのを忘れた場合！）、分離が続行され、呼び出しスタックがオーバーフローする可能性があります。 私の実装では、最小面積である1x1x1サイズのキューブを選択しました。 このキューブ内のすべてのオブジェクトについて、単純な列挙（O（N ² ））による衝突チェックを実行する必要があります（これ以上オブジェクトを期待しない！）。
• 領域にオブジェクトが含まれていない場合、ツリーに追加しません。

半分に分割し、世界の2次元空間を四分円に分割することで、もう1つの手順を実行できます。 ロジックは基本的に同じですが、2つの長方形ではなく、4つの正方形間の衝突をチェックします。 完了条件が満たされるまでパーティションを継続できます。 世界の空間と象限木に対応するデータ構造は次のようになります。







クアドラントツリーへの分割とデータ構造が論理的に見える場合、octreeも明確になります。 3番目の次元を追加し、正方形ではなく境界キューブを使用します。つまり、4つの子ノードではなく、8つの子ノードがあります。 ゲームワールドのサイズが200x300x400などの非立方体の場合、どうなるのか疑問に思われるかもしれません。 とにかく、立方体の寸法を持つ八分木を使用することができます-いくつかの子ノードは、世界の空間に何もない場合、単に空になります。 明らかに、octreeの次元は、少なくともゲームワールドの次元の大きい方に等しいことが必要です。

オクトリーの作成

したがって、すでにお読みいただいたように、octreeは特別なタイプの分割ツリーであり、通常は3次元空間（または3次元のオブジェクト）で使用されます。 境界領域は3次元の長方形（ボックス）（通常は立方体）です。 次に、上記のロジックを適用し、境界領域を8つの小さな平行六面体に分割します。 ゲームオブジェクトがこれらのサブディビジョンの1つに完全に配置されている場合、ツリーを下ってエリアを含むノードまで下げます。 次に、完了条件の1つが満たされるまで、結果の各領域を再帰的に分離し続けます。 その結果、美しいツリーのようなデータ構造を取得する必要があります。

私のoctreeの実装では、境界球および/または境界ボックスを持つオブジェクトが含まれます。 使用する境界形状を決定するために大量のコードを使用することがわかります。

Octreeクラスのデータ構造では、各ツリーに次のルールを選択しました。

• 各ノードには、その領域を定義する境界領域があります
• 各ノードには親ノードへのリンクがあります
• 8つの子ノードの配列が含まれます（配列はコードの簡素化とキャッシュ速度のために使用されます）
• 現在の領域のオブジェクトをリストします。
• バイトサイズのビットマスクを使用して、どの子ノードがアクティブに使用されているかを判断します （ 複雑さが増すという最適化の利点はかなり重要なポイントです ）
• いくつかの静的変数を使用して、ツリーの状態を示しました

次に、 Octreeクラスのアウトラインコードを示します。

 public class OctTree { BoundingBox m_region; List m_objects; /// ///  ,       . ///        ,      .      . /// static Queue m_pendingInsertion = new Queue(); /// ///        . /// OctTree[] m_childNode = new OctTree[8]; /// ///   , ,     . ///    ,   ,        . /// byte m_activeNodes = 0; /// ///     -  1x1x1. /// const int MIN_SIZE = 1; /// ///  ,       . ,    .     ///     ,   ""     (64) /// int m_maxLifespan = 8; // int m_curLife = -1; //    ,     /// ///    .      . /// OctTree _parent; static bool m_treeReady = false; //     ,   ,      static bool m_treeBuilt = false; //      }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

境界の初期化

octreeを作成する最初のステップは、ツリー全体の境界領域を定義することです。 これは、ツリーのルートノードのバウンディングボックスになり、最初はゲームワールド内のすべてのオブジェクトが含まれます。 境界ボリュームを初期化する前に、設計に関する決定を行う必要があります。



1.ルートノードの境界ボリュームを超えてオブジェクトが移動するとどうなりますか？ すべてのオブジェクトが制限されるようにツリー全体のサイズを変更しますか？ その場合は、octreeを最初から完全に再構築する必要があります。 そうでない場合は、境界外のオブジェクトを処理する方法を見つけるか、オブジェクトが決して境界を越えないようにする必要があります。



2. octreeの境界ボックスをどのように作成しますか？ たとえば、平行六面体の200x400x200（X、Y、Z）などの所定のサイズを使用しますか？ または、立方体の次元を使用します。 2のべき乗ですか？ 最小許容境界領域を分割できない場合はどうなりますか？ 私は、全世界を完全に制限するのに十分な大きさの2の累乗に等しい次元を持つ立方体の境界領域を使用することにしました。 最小の許容領域は1x1x1ユニットキューブです。 これにより、世界を明確に分割し、整数を取得します（ Vector3には浮動小数点形式があります）。 また、境界領域が全世界を制限することを決定したため、オブジェクトがこの領域を離れると破壊されます。 最小限のオクタントでは、単純な列挙で衝突チェックを実行します。 ただし、このような小さな領域を同時に占有するオブジェクトは3つまでであるため、O（N ² ）のパフォーマンスコストは絶対に許容できます。 リージョンのサイズとツリーに挿入されたオブジェクトのリストを取得するコンストラクターを使用して、octreeを標準的に初期化します。 コードのこの部分は基本的なものであるため、表示するべきではないように思えましたが、完全を期すために追加しました。



私のコンストラクタは次のとおりです。

 /*:        ,        .*/ /// ///  ,         . /// ///   . ///  ,     private OctTree(BoundingBox region, List objList) { m_region = region; m_objects = objList; m_curLife = -1; } public OctTree() { m_objects = new List(); m_region = new BoundingBox(Vector3.Zero, Vector3.Zero); m_curLife = -1; } /// ///    ,     . /// ///    . /// :       ,     . public OctTree(BoundingBox region) { m_region = region; m_objects = new List(); m_curLife = -1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

元のoctreeの作成

私は初期化の遅延が大好きです。 絶対に必要になるまで、メモリの割り当てと作業を避けようとします。 octreeの場合、可能な限りデータ構造を作成しないようにします。 データ構造にオブジェクトを挿入するというユーザーのリクエストを受け取りますが、実際には、誰かがそのキューを開始するまでツリーを作成する必要はありません。



これにより何が得られますか？ さて、ツリーの作成とトラバースのプロセスは、かなりのリソースを消費すると考えてください。 ユーザーがツリーに1000個のオブジェクトを挿入したい場合、後続の各バウンディングエリアを1,000回カウントするのは理にかなっていますか？または、時間を節約して一括処理できますか？



要素の「待機」キューと、ツリーの構築状態を示すいくつかのフラグを作成しました。挿入されたすべての要素は保留中のキューに移動し、キューの準備が完了すると、これらの保留中の要求はすべて転送されてツリーに挿入されます。これはゲームをロードするときに特に便利です。何千ものオブジェクトを同時に挿入する可能性が高いためです。ゲームワールドを読み込んだ後、ツリーに挿入されたオブジェクトの数は、桁違いに小さくなります。遅延初期化ルーチンは、UpdateTree（）メソッドに含まれています。ツリーが構築されているかどうかを確認し、データ構造が存在せず保留中のオブジェクトがある場合は構築します。

 /// ///        . /// ///     ? private void UpdateTree() //    { if (!m_treeBuilt) { while (m_pendingInsertion.Count != 0) m_objects.Add(m_pendingInsertion.Dequeue()); BuildTree(); } else { while (m_pendingInsertion.Count != 0) Insert(m_pendingInsertion.Dequeue()); } m_treeReady = true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ツリー自体を構築するには、それを再帰的に使用できます。



つまり、再帰反復ごとに、境界領域に含まれるオブジェクトのリストから始めます。完了条件が満たされているかどうかを確認し、そうでない場合は、境界領域に完全に収まる8つの分割された境界空間を作成します。次に、指定されたリスト内の各オブジェクトを調べて、それがオクタントの1つに完全に収まるかどうかを確認します。収まる場合は、このオクタントの対応するリストに挿入します。最後に、対応するオクタントのリストで数量を確認し、新しいオクターブを作成して現在のノードにアタッチし、アクティブに使用されている子オクタントをビットマスクでマークします。



残りのすべてのオブジェクトは親ノードから渡されますが、子ノードのいずれかに単純に下げることはできません。したがって、これは、このオブジェクトに含めることができる最小のオクタントであることが論理的です。

 /// ///     . /// private void BuildTree() //   { // ,       if (m_objects.Count <= 1) return; Vector3 dimensions = m_region.Max - m_region.Min; if (dimensions == Vector3.Zero) { FindEnclosingCube(); dimensions = m_region.Max - m_region.Min; } //,       if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE) { return; } Vector3 half = dimensions / 2.0f; Vector3 center = m_region.Min + half; //      BoundingBox[] octant = new BoundingBox[8]; octant[0] = new BoundingBox(m_region.Min, center); octant[1] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z)); octant[2] = new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z)); octant[3] = new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z)); octant[4] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z)); octant[5] = new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z)); octant[6] = new BoundingBox(center, m_region.Max); octant[7] = new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z)); //     ,       . List[] octList = new List[8]; for (int i = 0; i < 8; i++) octList = new List(); //     ,    .       . List delist = new List(); foreach (Physical obj in m_objects) { if (obj.BoundingBox.Min != obj.BoundingBox.Max) { for (int a = 0; a < 8; a++) { if (octant[a].Contains(obj.BoundingBox) == ContainmentType.Contains) { octList[a].Add(obj); delist.Add(obj); break; } } } else if (obj.BoundingSphere.Radius != 0) { for (int a = 0; a < 8; a++) { if (octant[a].Contains(obj.BoundingSphere) == ContainmentType.Contains) { octList[a].Add(obj); delist.Add(obj); break; } } } } //        . foreach (Physical obj in delist) m_objects.Remove(obj); //  ,    ,     for (int a = 0; a < 8; a++) { if (octList[a].Count != 0) { m_childNode[a] = CreateNode(octant[a], octList[a]); m_activeNodes |= (byte)(1 << a); m_childNode[a].BuildTree(); } } m_treeBuilt = true; m_treeReady = true; } private OctTree CreateNode(BoundingBox region, List objList) //   { if (objList.Count == 0) return null; OctTree ret = new OctTree(region, objList); ret._parent = this; return ret; } private OctTree CreateNode(BoundingBox region, Physical Item) { List objList = new List(1); //         objList.Add(Item); OctTree ret = new OctTree(region, objList); ret._parent = this; return ret; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ツリー更新

私たちの木には多くの動く物体があると想像してください。オブジェクトが移動した場合、そのオブジェクトを囲むオクタントの境界を超えた可能性が高くなります。ツリー構造の整合性を維持しながら、オブジェクトの位置の変更を処理する方法は？



テクニック1：非常に単純に、すべてを削除して再構築します。



octreeツリーの一部の実装では、各フレームに新しいツリーが作成され、古いツリーが削除されます。これは非常に単純で、この手法は機能します。自分に合っている場合は、選択する必要があります。一般に、各フレームでツリーを再構築するためにプロセッサに費やされる予備時間は、単純な網羅的検索による衝突チェックを実行するよりもはるかに安価であり、プログラマの時間はオプションの最適化に費やすには貴重すぎると考えられています。困難や合併症を愛する私たちにとって、「除去と再構築」技術は小さな問題を引き起こします。

1. ツリーを再構築するたびに、常にメモリを割り当てて解放します。新しいメモリを割り当てるには少しのリソースが必要です。可能な限り、既存のメモリを再利用して、割り当てられたメモリと解放されたメモリの量を最小限に抑えようとします。
2. ツリーのほとんどは変更されないため、同じブランチを継続的に再構築することは、プロセッサ時間の無駄です。

テクニック2：既存のツリーを保存し、変更されたブランチを更新します。



ツリーのほとんどのブランチには更新が必要ないことに気付きました。静止したオブジェクトのみが含まれます。



各フレームでツリー全体を再構築する代わりに、更新が必要なツリーの部分を更新するだけでいいのではないでしょうか？この手法は、既存のツリーを保存し、移動オブジェクトを含むブランチのみを更新します。その実装はもう少し難しいですが、より興味深いので、これを完了させましょう！



最初の実験で、子ノードのオブジェクトはツリーの1つの遷移のみを上下させることができると誤って信じていました。これは真実ではありません。子ノードのオブジェクトがノードの端に到達し、この端が境界の親ノードの端でもある場合、オブジェクトはその親の上に、場合によってはそれ以上に挿入する必要があります。つまり、結果として、オブジェクトがツリー内でどれだけ高くなるかはわかりません。さらに、オブジェクトは子ノードまたは子ノードの子ノードに都合よく収まることができます。私たちは、どこまで知りませんダウン、それは木を下ることができます。



幸いなことに、各ノードの親への参照を保持しているため、最小限の計算を使用した再帰によってこの問題を簡単に解決できます。



更新アルゴリズムの主なアイデアは、ツリー内のすべてのオブジェクトが最初に自分自身を更新できるようにすることです。それらの一部は移動またはサイズ変更されます。移動されたすべてのオブジェクトのリストを取得して、オブジェクト更新メソッドが、オブジェクトの境界を変更するかどうかを決定するブール値を返すようにします。



すべてのオブジェクトが動くのリストを受け取った後、私たちは現在のサイトで開始し、ツリーを取得しようとするまで、我々は完全に動くオブジェクトを（ほとんどの場合、オブジェクトがまだ現在のノードになります）を収容、ノードを見つけるまで。オブジェクトが現在のノードに完全に存在しない場合、次の親ノードに移動し続けます。最悪の場合、オブジェクトはルートノードにあることが保証されます。



ツリー内でオブジェクトをできるだけ高く移動した後、ツリー内でオブジェクトをできるだけ低くしようとします。ほとんどの場合、オブジェクトを上に移動できた場合、オブジェクトを下げることはできません。しかし、現在のノードの子ノードがオブジェクトを含むことができるようにオブジェクトが移動した場合、ツリーの下にそれを下げる機会があります。ツリー内でオブジェクトを上下に移動できることが重要です。そうしないと、すべての移動オブジェクトが徐々に上に移動し、衝突認識手順の速度に問題が生じます。



ブランチの削除



場合によっては、オブジェクトがノードから移動でき、このノードにはすべての子孫のようにオブジェクトが含まれなくなります。この場合、空のブランチが形成されます。。次に、マークを付けて、この枯れた枝を木から切り取ります。



ここで興味深い疑問が生じます。いつ枯れた枝を木から切り落とす必要があるのでしょうか？新しいメモリの割り当てには時間がかかるので、同じ領域を数サイクルにわたって再利用する場合、すぐに削除するのはなぜですか？デッドブランチを維持するのに費用がかかるまで、どれくらいの期間保存できますか？



ブランチが停止したときにアクティブになるカウントダウンタイマーを各ノードに与えることにしました。デスタイマーがアクティブなときにオブジェクトがこのノードのオクタントに移動した場合、寿命を2倍にしてタイマーをリセットします。これにより、頻繁に使用されるオクタントがアクティブのままになり、削除されなくなります。また、使用頻度の低いノードは、ストレージが高くなりすぎる前に削除されます。



この技術の有用性は、機関銃が弾丸の流れを発射する実際の例から明らかです。これらの弾丸は互いに非常に近くに飛んでいるので、最初の弾丸が飛び出した直後にノードを削除し、2番目の弾丸がヒットした瞬間にノードを回復するのは不便です。箇条書きがたくさんあるので、これらのオクタントをしばらく保持する方が良いでしょう。子ブランチが空で、長期間使用されていない場合、ツリーから簡単に切り離すことができます。



このすべての魔法を実行するコードを見てみましょう。



まず、Update（）メソッドがあります。すべての子ツリーは、その中で再帰的に呼び出されます。すべてのオブジェクトを移動し、データ構造の順序を復元してから、シフトされた各オブジェクトを対応するノード（親または子）に移動します。

 public void Update(GameTime gameTime) { if (m_treeBuilt == true) { //        ,      . //   ,   .       ,    . //               if (m_objects.Count == 0) { if (HasChildren == false) { if (m_curLife == -1) m_curLife = m_maxLifespan; else if (m_curLife > 0) { m_curLife--; } } } else { if (m_curLife != -1) { if(m_maxLifespan <= 64) m_maxLifespan *= 2; m_curLife = -1; } } List movedObjects = new List(m_objects.Count); //         foreach (Physical gameObj in m_objects) { //  ,   ,        . if (gameObj.Update(gameTime)) { movedObjects.Add(gameObj); } } //     . int listSize = m_objects.Count; for (int a = 0; a < listSize; a++) { if (!m_objects[a].Alive) { if (movedObjects.Contains(m_objects[a])) movedObjects.Remove(m_objects[a]); m_objects.RemoveAt(a--); listSize--; } } //    . for( int flags = m_activeNodes, index = 0; flags > 0; flags >>=1, index++) if ((flags & 1) == 1) m_childNode[index].Update(gameTime); //  ,       ,        . //,       ,          . foreach (Physical movedObj in movedObjects) { OctTree current = this; //,       ,     //      //      ,      if (movedObj.BoundingBox.Max != movedObj.BoundingBox.Min) { while (current.m_region.Contains(movedObj.BoundingBox) != ContainmentType.Contains) if (current._parent != null) current = current._parent; else break; //  ,        } else { while (current.m_region.Contains(movedObj.BoundingSphere) != ContainmentType.Contains)//,     ,     . if (current._parent != null) current = current._parent; else break; } //           . m_objects.Remove(movedObj); current.Insert(movedObj); //        ,  . } //     for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++) if ((flags & 1) == 1 && m_childNode[index].m_curLife == 0) { m_childNode[index] = null; m_activeNodes ^= (byte)(1 << index); //       } //,          ,   . if (IsRoot == true) { //       . //               . //:  ,        . // 2:     ,    .         . List irList = GetIntersection(new List()); foreach (IntersectionRecord ir in irList) { if (ir.PhysicalObject != null) ir.PhysicalObject.HandleIntersection(ir); if (ir.OtherPhysicalObject != null) ir.OtherPhysicalObject.HandleIntersection(ir); } } } else { } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

移動したオブジェクトに対して、Insert（）メソッドを呼び出していることに注意してください。ツリーへのオブジェクトの挿入は、元のツリーを作成するために使用される方法に非常に似ています。Insert（）は、オブジェクトをツリーのできるだけ下に下げようとします。また、子ノードで既存のスペースを使用できる場合は、新しい境界スペースを作成しないようにします。

 /// ///   ,       ,     /// ///   ///       private void Insert(T Item) where T : Physical { /*,     ,   -       ,   .*/ if (m_objects.Count <= 1 && m_activeNodes == 0) { m_objects.Add(Item); return; } Vector3 dimensions = m_region.Max - m_region.Min; //,       if (dimensions.X <= MIN_SIZE && dimensions.Y <= MIN_SIZE && dimensions.Z <= MIN_SIZE) { m_objects.Add(Item); return; } Vector3 half = dimensions / 2.0f; Vector3 center = m_region.Min + half; //           BoundingBox[] childOctant = new BoundingBox[8]; childOctant[0] = (m_childNode[0] != null) ? m_childNode[0].m_region : new BoundingBox(m_region.Min, center); childOctant[1] = (m_childNode[1] != null) ? m_childNode[1].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, m_region.Min.Z), new Vector3(m_region.Max.X, center.Y, center.Z)); childOctant[2] = (m_childNode[2] != null) ? m_childNode[2].m_region : new BoundingBox(new Vector3(center.X, m_region.Min.Y, center.Z), new Vector3(m_region.Max.X, center.Y, m_region.Max.Z)); childOctant[3] = (m_childNode[3] != null) ? m_childNode[3].m_region : new BoundingBox(new Vector3(m_region.Min.X, m_region.Min.Y, center.Z), new Vector3(center.X, center.Y, m_region.Max.Z)); childOctant[4] = (m_childNode[4] != null) ? m_childNode[4].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, m_region.Min.Z), new Vector3(center.X, m_region.Max.Y, center.Z)); childOctant[5] = (m_childNode[5] != null) ? m_childNode[5].m_region : new BoundingBox(new Vector3(center.X, center.Y, m_region.Min.Z), new Vector3(m_region.Max.X, m_region.Max.Y, center.Z)); childOctant[6] = (m_childNode[6] != null) ? m_childNode[6].m_region : new BoundingBox(center, m_region.Max); childOctant[7] = (m_childNode[7] != null) ? m_childNode[7].m_region : new BoundingBox(new Vector3(m_region.Min.X, center.Y, center.Z), new Vector3(center.X, m_region.Max.Y, m_region.Max.Z)); //-,        ? // 2:       .       ,     /. // .           .     . // :       256x256x256.    . if (Item.BoundingBox.Max != Item.BoundingBox.Min && m_region.Contains(Item.BoundingBox) == ContainmentType.Contains) { bool found = false; //     .       ,        . for(int a=0;a<8;a++) { //     ? if (childOctant[a].Contains(Item.BoundingBox) == ContainmentType.Contains) { if (m_childNode[a] != null) m_childNode[a].Insert(Item); //          ,     else { m_childNode[a] = CreateNode(childOctant[a], Item); //      m_activeNodes |= (byte)(1 << a); } found = true; } } if(!found) m_objects.Add(Item); } else if (Item.BoundingSphere.Radius != 0 && m_region.Contains(Item.BoundingSphere) == ContainmentType.Contains) { bool found = false; //     .       ,        . for (int a = 0; a < 8; a++) { //     ? if (childOctant[a].Contains(Item.BoundingSphere) == ContainmentType.Contains) { if (m_childNode[a] != null) m_childNode[a].Insert(Item); //A          ,     else { m_childNode[a] = CreateNode(childOctant[a], Item); //      m_activeNodes |= (byte)(1 << a); } found = true; } } if (!found) m_objects.Add(Item); } else { //      ,   .     ,    // ,      //BoundingBox enclosingArea = FindBox(); BuildTree(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

衝突認識

最後に、octreeを構築し、必要なすべての設備が整っています。衝突認識の実行方法は？始めるために、衝突を認識したいさまざまな方法をリストしましょう：

1. . , . , . , .
2. . , , , (, ). . , , .
3. . , . «» (, ..).
4. . , . , .

octreeの再帰衝突認識処理の主なアイデアは、ルート/現在のノードから開始し、このノード内のすべてのオブジェクトと交差する図形との交差をチェックすることです。



次に、交差する形状を持つすべてのアクティブな子ノードに対して、境界ボックスを使用した交差チェックが実行されます。子ノードの交差チェックに失敗した場合、この子ノードの残りのツリーは完全に無視されます。子ノードが交差のチェックに合格した場合、ツリーを再帰的にたどってプロセスを繰り返します。各ノードは、呼び出し元のプロシージャにリストを渡す必要があります。交差点レコード。このプロシージャは、これらの交差点を独自の交差点リストに添付します。再帰が完了すると、元の呼び出しプロシージャは、指定された交差図形のすべての交差点のリストを取得します。



このアプローチの利点は、実装に必要なコードが非常に少なく、パフォーマンスが非常に高いことです。これらの衝突の多くでは、多くの結果が得られる可能性があります。また、衝突するオブジェクトに応じて、各衝突に対応する何らかの方法が必要です。たとえば、プレイヤーのキャラクターは空中にぶら下がっているボーナスを獲得する必要があります（4倍のダメージ！）。しかし、ロケットはこのボーナスに当たると爆発しません。



各交差点に関する情報を格納する新しいクラスを作成しました。このクラスには、交差するオブジェクト、交差点、交差点での法線などへの参照が含まれます。このような交差レコードは、オブジェクトに渡して処理するときに非常に役立ちます。



完全性と明確性のために、交差点エントリコードを以下に示しました。

 public class IntersectionRecord { Vector3 m_position; /// ///    3D-,    . /// public Vector3 Position { get { return m_position; } } Vector3 m_normal; /// ///       /// public Vector3 Normal { get { return m_normal; } } Ray m_ray; /// ///  ,    /// public Ray Ray { get { return m_ray; } } Physical m_intersectedObject1; /// ///  ,    /// public Physical PhysicalObject { get { return m_intersectedObject1; } set { m_intersectedObject1 = value; } } Physical m_intersectedObject2; /// ///     (   null, ,    -) /// public Physical OtherPhysicalObject { get { return m_intersectedObject2; } set { m_intersectedObject2 = value; } } /// ///       ,    .      ///           .   -       , ///        ,      . /// OctTree m_treeNode; /// ///       .      ,     . /// /// ,     /// ,   -      ,    . public override bool Equals(object otherRecord) { IntersectionRecord o = (IntersectionRecord)otherRecord; // // (m_intersectedObject1 != null && m_intersectedObject2 != null && m_intersectedObject1.ID == m_intersectedObject2.ID); if (otherRecord == null) return false; if (o.m_intersectedObject1.ID == m_intersectedObject1.ID && o.m_intersectedObject2.ID == m_intersectedObject2.ID) return true; if (o.m_intersectedObject1.ID == m_intersectedObject2.ID && o.m_intersectedObject2.ID == m_intersectedObject1.ID) return true; return false; } double m_distance; /// ///       . ///     ,      . /// public double Distance { get { return m_distance; } } private bool m_hasHit = false; public bool HasHit { get { return m_hasHit; } } public IntersectionRecord() { m_position = Vector3.Zero; m_normal = Vector3.Zero; m_ray = new Ray(); m_distance = float.MaxValue; m_intersectedObject1 = null; } public IntersectionRecord(Vector3 hitPos, Vector3 hitNormal, Ray ray, double distance) { m_position = hitPos; m_normal = hitNormal; m_ray = ray; m_distance = distance; // m_hitObject = hitGeom; m_hasHit = true; } /// ///    ,   ,   ,      . /// /// : ,    .   null. public IntersectionRecord(Physical hitObject = null) { m_hasHit = hitObject != null; m_intersectedObject1 = hitObject; m_position = Vector3.Zero; m_normal = Vector3.Zero; m_ray = new Ray(); m_distance = 0.0f; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

境界を切り取ったピラミッドとの交差点

 /// ///     ,          /// ///      /  ///      private List GetIntersection(BoundingFrustum frustum, Physical.PhysicalType type = Physical.PhysicalType.ALL) { if (m_objects.Count == 0 && HasChildren == false) //   return null; List ret = new List(); //       foreach (Physical obj in m_objects) { //  ,     if ((int)((int)type & (int)obj.Type) == 0) continue; //   IntersectionRecord ir = obj.Intersects(frustum); if (ir != null) ret.Add(ir); } //       for (int a = 0; a < 8; a++) { if (m_childNode[a] != null && (frustum.Contains(m_childNode[a].m_region) == ContainmentType.Intersects || frustum.Contains(m_childNode[a].m_region) == ContainmentType.Contains)) { List hitList = m_childNode[a].GetIntersection(frustum); if (hitList != null) { foreach (IntersectionRecord ir in hitList) ret.Add(ir); } } } return ret; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

境界の切り捨てられたピラミッドの交点のリストを使用して、現在のカメラの可視領域に表示されるオブジェクトをレンダリングできます。シーンデータベースを使用して、ゲームワールド内のすべてのオブジェクトをレンダリングする方法を見つけます。これは、アクティブカメラの境界の切り捨てられたピラミッドを使用したレンダリング関数のコードスニペットです。

 /// ///         /// /// public int Render() { int triangles = 0; //    ,       //       foreach (IntersectionRecord ir in m_octTree.AllIntersections(m_cameras[m_activeCamera].Frustum)) { ir.PhysicalObject.SetDirectionalLight(m_globalLight[0].Direction, m_globalLight[0].Color); ir.PhysicalObject.View = m_cameras[m_activeCamera].View; ir.PhysicalObject.Projection = m_cameras[m_activeCamera].Projection; ir.PhysicalObject.UpdateLOD(m_cameras[m_activeCamera]); triangles += ir.PhysicalObject.Render(m_cameras[m_activeCamera]); } return triangles; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ビーム交差点

 /// ///       ,     /// /// ,     ///    private List GetIntersection(Ray intersectRay, Physical.PhysicalType type = Physical.PhysicalType.ALL) { if (m_objects.Count == 0 && HasChildren == false) //   return null; List ret = new List(); //    ,              . //        foreach (Physical obj in m_objects) { //   ,     if ((int)((int)type & (int)obj.Type) == 0) continue; if (obj.BoundingBox.Intersects(intersectRay) != null) { IntersectionRecord ir = obj.Intersects(intersectRay); if (ir.HasHit) ret.Add(ir); } } //       for (int a = 0; a < 8; a++) { if (m_childNode[a] != null && m_childNode[a].m_region.Intersects(intersectRay) != null) { List hits = m_childNode[a].GetIntersection(intersectRay, type); if (hits != null) { foreach (IntersectionRecord ir in hits) ret.Add(ir); } } } return ret; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オブジェクトのリストとの交差点

これは、現在のノードのオブジェクトのリストとすべての子ノードのオブジェクトの共通部分を決定するための特に便利な再帰的方法です（アプリケーションのUpdate（）メソッドを参照）。このメソッドは最も頻繁に呼び出されるので、正確で効率的な方法にするとよいでしょう。



ツリーのルートノードから始めましょう。現在のノードのすべてのオブジェクトと現在のノードの他のすべてのオブジェクトとの衝突を比較します。すべての衝突を交差点の記録として修正し、それらをリストに挿入します。次に、スキャンしたオブジェクトのリストを子ノードに渡します。子ノードは、オブジェクトとそれらの交点をチェックし、次に渡したオブジェクトとの交点をチェックします。子ノードはすべての衝突をリストに保存し、このリストを親に渡します。次に、親は子ノードから取得した衝突のリストを取得し、それを独自の衝突のリストに追加し、呼び出し元のプロシージャに渡します。











図で衝突チェックの回数を数えると、29の衝突の可能性がチェックされ、4が見つかったことがわかります[11 * 11 = 121]衝突チェックよりもはるかに優れています。

 private List GetIntersection(List parentObjs, Physical.PhysicalType type = Physical.PhysicalType.ALL) { List intersections = new List(); // ,          . //            foreach (Physical pObj in parentObjs) { foreach (Physical lObj in m_objects) { //    .   ,      . //   ,   . IntersectionRecord ir = pObj.Intersects(lObj); if (ir != null) { intersections.Add(ir); } } } //         if (m_objects.Count > 1) { #region self-congratulation /* *     .      foreach,  : * foreach(Physical lObj1 in m_objects) * { * foreach(Physical lObj2 in m_objects) * { * //    * } * } * *   ,    O(N*N)    ,      . * ,        : {1,2,3,4} *    {1}  {1,2,3,4} *   {2}  {1,2,3,4}, *     {1}  {2},    {2}  {1}    .     ,  {1}? *     4+3+2+1  ,    O(N(N+1)/2).  N = 10,       . *           for,       foreach,    *  for(int i=0;i tmp = new List(m_objects.Count); tmp.AddRange(m_objects); while (tmp.Count > 0) { foreach (Physical lObj2 in tmp) { if (tmp[tmp.Count - 1] == lObj2 || (tmp[tmp.Count - 1].IsStatic && lObj2.IsStatic)) continue; IntersectionRecord ir = tmp[tmp.Count - 1].Intersects(lObj2); if (ir != null) intersections.Add(ir); } //      ,    O(N(N+1)/2)   O(N*N) tmp.RemoveAt(tmp.Count-1); } } //         ,        . foreach (Physical lObj in m_objects) if (lObj.IsStatic == false) parentObjs.Add(lObj); //parentObjs.AddRange(m_objects); //       ,        . for (int flags = m_activeNodes, index = 0; flags > 0; flags >>= 1, index++) if ((flags & 1) == 1) intersections.AddRange(m_childNode[index].GetIntersection(parentObjs, type)); return intersections; } ;i++)>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

デモのスクリーンショット

, .





, . , .