|
バイナリ空間分割（バイナリくうかんぶんかつ、）は、空間を超平面で凸集合に再帰的に分割していく手法である。その分割により、シーンをBSP木（BSP tree）と呼ばれる木構造で表現できるようになる。 簡単に言えば、複雑な形状の多角形を凸多角形、すなわち 180°以下の角度の頂点のみで囲まれた小さい多角形に分割する。 元々は、3次元コンピュータグラフィックスのレンダリングの効率を向上させる手段として提案されたものである。他にも、CADにおける図形処理、ロボット工学や3Dコンピュータゲームでの衝突判定、その他の複雑な形状を扱うコンピュータアプリケーションで応用されている。 == 概要 == コンピュータグラフィックスにおいては、シーンを正しくかつ素早く描画することが望ましい。シーンを正しく描画する単純な方法として画家のアルゴリズムがある。すなわち、背景から前景へと上に重ねるようにオブジェクトを描画していく方法である。しかし、この方法では後で隠れてしまう部分まで描画するなど、時間を浪費している面があり、また全てのオブジェクトが正しく描画されるわけではない。 Zバッファを使えば、画家のアルゴリズムでの描画順序決定のステップを省略してもシーンを正しく描画できるが、メモリを多く必要とするという問題がある。BSP木はオブジェクトを分割することで画家のアルゴリズムでZバッファなしでも正しく描画できるようにし、オブジェクトをソートする手間を省くことができる。すなわち、簡単な木構造の走査によって正しい描画順序が得られる。また、重ね描きを削減するための visibility list などの他のアルゴリズムの基盤としても機能する。 欠点は、事前処理に時間がかかる点で、そのためBSP木上で移動するオブジェクトを直接実装するのは困難であり、効率が悪い。その場合、BSP木とZバッファを併用し、背景となるシーン上でドアやモンスターといった動くオブジェクトをZバッファで正しくマージする。 BSP木は3Dコンピュータゲームでよく使われ、特にファーストパーソン・シューティングゲームで室内環境を描画する際に使われる。BSPデータ構造を最初に使ったゲームとして ''DOOM'' がある。他にもレイトレーシングや当たり判定に使われる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「バイナリ空間分割」の詳細全文を読む スポンサード リンク
|