Axis Aligned Rectangle Intersection and Projection Technique(1)

先日のエントリではマンハッタン幾何を紹介し、総当たりによる実装を行いました。その際、水平と垂直の線分を縮退した矩形とみなし、交差判定を行いました。

今回のエントリでは、矩形の交差判定アルゴリズムを考えるための用語の解説を行います。また、次回以降のエントリにて射影(Projection)という技法を紹介します。


さて、矩形は4つの角が全て等しい四角形となります。次回以降のエントリでは、特に4つの辺がxもしくはy軸に対して平行である矩形を用います。このような条件を持った矩形を、Axis Aligned Rectangleと呼びます。4辺が軸と平行である制限を持った矩形は、その扱いの容易さからカルテシアン座標系、すなわち直行座標系*1での交差判定に多用されます。これを三次元に拡張し、各面が軸と直行している条件を持った直方体も共に多用されます。

マンハッタン幾何で扱う線分は単純なものですが、実際のデータの交差判定を行うには大変な計算量を必要とします。交差判定の計算量を減らすために、データを包括する近似データを用いて粗く交差判定を行い、絞り込みを行うのが一般的です。通常、データの近似には凸包を用います。先に挙げた矩形や直方体は、それぞれ直行した4辺で構成された四角形であり、隣接する全ての辺が直行する六面体です。ある特定の条件を満たす凸包として考えることが出来ます。

以下は、Axis Aligned Rectangleを使った凸包の一例です。

このような特殊な凸包を、矩形の場合はMinimum Bounding Rectangle、直方体の場合はMinimum Bounding Boxと呼びます。しかし、何れの場合でも単にBounding Boxと呼ばれることが多いようです。

また、英語の文献ではAABB、すなわちAxis Aligned Bounding Boxとして表記されることが多いです。AABBは計算幾何を考える上で覚えておいて損のない用語です。元々は特殊な凸包の意を込められたAABBですが、より一般的に、Minimum Bounding RectangleやMinimum Bounding Boxを表す用語としても用いられることが多いようです*2

また、AABBと明確に区別するために、以下のように辺が軸に対して平行とは限定しないMinimum Bounding RectangleやMinimum Bounding BoxをOBB、すなわちOriented Bounding Box(有向境界ボックス、有向バウンディングボックス)と呼ぶことがあります。

文献によっては同じ用語を異なる意味合いで用いている場合がありますので、注意が必要です。


さて、次回のエントリでは射影(Projection)と呼ばれる技法を用いた矩形の交差判定について記載したいと思っています。

追記(2010/3/28)

Oriented Bounding Box using Covariance MatrixにてGoogle Gadgetsを用いた動的なOBBのデモを掲載しました。是非ご覧ください。

*1:デカルト座標系としても知られています

*2:Axis Aligned Boxとはあまり言いません