kd木

1975年にジョン・ベントレーが考案した。根では点をx軸方向に分け、次の階層ではy、その次はzというように軸を巡回させる。中央値の点で分割すれば、バランスの取れた木になる。これにより、最近傍探索や範囲検索が線形時間から対数時間になる。

kd木は点群、フォトンマッピング、静的シーンのレイトレーシングにおける高速化構造として使われる。動き回るゲーム世界では、毎フレームの再構築が高くつくためBVHのほうが好まれる。