バイナリ空間分割

バイナリ空間分割（バイナリくうかんぶんかつ、Binary space partitioning, BSP）は、空間を超平面で凸集合に再帰的に分割していく手法である。その分割により、シーンをBSP木（BSP tree）と呼ばれる木構造で表現できるようになる。簡単に言えば、複雑な形状の多角形を凸多角形、すなわち 180°以下の角度の頂点のみで囲まれた小さい多角形に分割する。元々は、3次元コンピュータグラフィックスのレンダリングの効率を向上させる手段として提案されたものである。他にも、CADにおける図形処理、ロボット工学や3Dコンピュータゲームでの衝突判定、その他の複雑な形状を扱うコンピュータアプリケーションで応用されている。