境界区間階層

空間分割構造を構築するには、何らかのヒューリスティックが一般的に使用されます。このために、多くの分割スキームで一般的に使用されている表面積ヒューリスティックが候補となります。もう1つのより単純なヒューリスティックは、「グローバル」ヒューリスティック^{[ 4 ]}で、プリミティブの完全なセットではなく、軸に沿った境界ボックスのみを必要とするため、高速な構築に非常に適しています。

BIHの一般的な構造設計図：

• シーンの境界ボックスを計算する
• ヒューリスティックを使用して、1つの軸と、その軸に垂直な分割平面候補を選択します。
• オブジェクトを、オブジェクトの境界ボックスに基づいて、左または右の子（排他的）にソートします（分割平面と交差するオブジェクトは、子ボリュームとの重なり具合、またはその他のヒューリスティックに基づいてソートされる場合があります）。
• その軸に関して、左側にあるすべてのオブジェクトの最大境界値と、右側にあるすべてのオブジェクトの最小境界値を計算します（一部のヒューリスティックでは、前のステップと組み合わせることができます）。
• これらの2つの値と、分割軸をエンコードする2ビットを新しいノードに格納します。
• 子供たちにはステップ2を続けてください

分割平面候補探索のための潜在的なヒューリスティック：

• 古典的な方法：最も長い軸を選択し、その軸上のノード境界ボックスの中央を選択します。
• 古典的な方法：最長軸を選択し、オブジェクトの中央を通る分割平面を作成する（ただし、結果として左向きの木構造になり、レイトレーシングには不向きな場合が多い）。
• グローバルヒューリスティック：規則的なグリッドの形式というグローバルな基準に基づいて分割面を選択する（不要な分割を回避し、ノードの体積をできるだけ立方体に保つ）。
• 表面積ヒューリスティック：可能なすべての分割平面候補のセットについて、両方の子供の表面積とオブジェクトの数を計算し、コストが最も低いものを選択します（最適であると主張されていますが、コスト関数は、現実には満たせないような、公式を証明するための異常な要求を課します。また、評価に非常に時間がかかるヒューリスティックでもあります）。

走査フェーズはkd木走査によく似ている。4つの単純なケースを区別する必要がある。

• 左の子と交差する
• ちょうど右の子供と交差する
• 両方の子供に共通する
• どちらの子とも交差しない（kdトラバーサルではあり得ない唯一のケース）

3番目のケースでは、コンポーネント（x、y、z）のレイの方向（負または正）が現在のノードの分割軸と等しいかどうかに応じて、トラバーサルはまず左（正の方向）または右（負の方向）の子で続行され、もう一方の子は遅延トラバーサルのためにスタックにプッシュされます。

葉ノードが見つかるまで走査が続きます。葉ノード内のオブジェクトとの交差が終わると、次の走査要素がスタックからポップされます。スタックが空の場合は、貫通したすべての葉ノードの最も近い交差が返されます。ポップされた要素が現在の最も近い交差を完全に超えている場合は、その走査はスキップされます。

5番目の走査ケースを追加することも可能ですが、それにはやや複雑な構築フェーズが必要です。ノードの左右の平面の意味を入れ替えることで、ノードの両側の空きスペースを切り取ることができます。これには、走査中にこの特殊なケースを検出するためにノードに格納する必要のある追加のビットが必要です。走査フェーズでのこのケースの処理は、レイが

• 現在のノードの唯一の子と交差するか、
• 何も交差しない

三角形の階層構造の構築/ソート中のすべての操作は、最小値/最大値演算と比較です。そのため、kdツリーの場合のように三角形のクリッピングを行う必要はありません。kdツリーでは、ノードとわずかに交差する三角形の場合、クリッピングが問題となることがあります。kdツリーの実装が注意深く記述されていても、数値エラーによって交差が検出されず、レイとオブジェクトの交差が見逃されることでレンダリングエラー（ジオメトリに穴が開く）が発生する可能性があります。