5. 境界ボリュームの構築

レンダリングの時のカリングや衝突判定に使う。ここでは、点列を標準的な3次元オブジェクトでフィッティングさせる(ぴったり含むようにする)ことを考えてみる。

たとえば、キャラクターを表すポリゴンの頂点すべてを含む球を求める。そうすれば、キャラクターの当たり判定は、それぞれの頂点を考える代わりにこの球で行なえば良いからである。

このような領域は、境界ボリューム(boundary volume)と呼ばれる。

キャラクターの当たり判定を実装するための境界ボリュームとしてあまり複雑な図形を採用しても仕方ないと思われるかも知れないが、そうでもない。境界ヴォリュームは事前に計算できるので、フィッティングにかかる作業時間は0と考えて良いし、交差判定は（接触判定ならば）1フレーム構築する間に、ほんの数回しか行なわない（ものによるが）ので、無視できるからである。

ここでは点列(点の集合) $\left\{\vec{V}_{i}\right\}_{i=0}^{n-1}$ で構成される幾何学オブジェクトを内包する球(a bounding sphere)を計算する方法を考える。

なお、フィッティングにガウス分布(いわゆる正規分布)を利用するとスマートに解決できる。

$A exp\left(\frac{(\vec{X}-\vec{C})(\vec{X}-\vec{C})^{T}}{M}\right)$ , $A$ はスケーリングファクタ, $\vec{C}$ は分布の平均値(the mean of the distribution) , $M$ は共分散(covariance)と呼ばれる。

$\displaystyle \vec{C}=\frac{1}{n}\sum_{j=0}^{n-1}\vec{V}_{j}$

基本的な考えかたとしては、点列の散らばっている方向に軸をとる、ということである。

ボックスの軸は次の共分散行列の単位長の固有ベクトルを選ぶ。(unit−length eigenvectors of the covariance matrix)

$M=\displaystyle \frac{1}{n}\sum_{j=0}^{n-1}(\vec{V}_{j}-\vec{C})(\vec{V}_{j}-\vec{C})^{T}$

この行列が決まれば、 $V_{j}$ をこの行列の単位長の固有ベクトル(ボックスの軸方向)に投影して、ボックスの範囲を決定すれば良い。（その後、本当のボックス中心が決定する）

(補足)

言うまでもなく、ここで出てくる $(\vec{V}_{j}-\vec{C})(\vec{V}_{j}-\vec{C})^{T}$ という表記は、次のように計算する。

ベクトル $\vec{W}=\{x,y,z\}$ に対して $\vec{W}\vec{W}^{T}$ は、

テンソル $Tensor(\vec{W},\vec{W})=\left\{\begin{array}{l}xx xy xz\\yx yy yz\\zx zy zz\end{array}\right\}$ である。これは6つの独立成分を持つ対称行列である。

ここで出てきた共分散行列は、x,y,z座標の各組の間の相関を表している。0の成分は、互いに相関がないことを意味する。すなわち、

$\left\{\begin{array}{l}xx xy xz\\yx yy yz\\zx zy zz\end{array}\right\}=\left\{\begin{array}{l}a 0 0\\0 b 0\\0 0 c\end{array}\right\}$ (対角行列)

となるとき、3つの座標は完全に無相関である。すなわち、角軸に点が均等に分布している。

このようにするため、点列を変換したときに共分散行列が対角行列になるような変換 $\vec{A}$ を考える。

対角行列 $M^{\prime}=\displaystyle \frac{1}{n}\sum_{j=0}^{n-1}(A\vec{V}_{j}-A\vec{C})(A\vec{V}_{j}-A\vec{C})^{T}$

$=\displaystyle \frac{1}{n}\sum_{j=0}^{n-1}A(\vec{V}_{j}-\vec{C})(\vec{V}_{j}-\vec{C})^{T}A^{T}=AMA^{T}$

すなわち、 $M$ に対して $AMA^{T}$ が対角化行列となるような直交変換行列Aが必要である。

ここで必要となる $A^{T}$ はいわゆる対角化行列である。

$M$ が対称行列であることから、 $M$ の固有ベクトルは互いに直交する。よって $M$ の固有ベクトルを行とする行列は、ここで必要としている対角化行列となる。

※　このように、点列の自然な軸を求める問題は、共分散行列の固有ベクトルを求める問題に帰着される。

行列 $M$ の3つの固有値 $\lambda_{i}$ (i=0,1,2) $,\left|\lambda_{0}\right|\geq\left|\lambda_{1}\right|\geq\left|\lambda_{2}\right|$ とすれば、この $\lambda_{0}$ に対応する固有ベクトル軸を主軸 $L_{0}$ 軸、 $\lambda_{1}$ に対応するのを2番目の軸 $L_{1}$ 軸、 $\lambda_{2}$ に対応するのを3番目の軸 $L_{2}$ 軸とする。
点列は $L_{0}$ 軸方向に一番偏って存在していると言える。以下、 $\vec{L}_{0},\vec{L}_{1},\vec{L}_{2}$ と書けば角軸をの単位ベクトルを意味するものとする。

5.1 球(spheres)

球の中心 $\vec{C}$ 。半径 $r$ 。 $\left|\vec{X}-\vec{C}\right|^{2}=r^{2}$

軸と平行な辺を持つボックスを含む球(sphere containing axis−aligned box)

まず、最小のAABB(axis−aligned bounding box:軸と平行な辺を持つ範囲ボックス)を考えて、こいつを内包する球を計算することを考える。

単純に考えれば、AABBの中心を球の中心として、AABBの対角線の長さの半分を半径とすれば良い。

点列の重心を中心とする球(sphere centered at average of points)

$\left\{\vec{V}_{i}\right\}_{i=0}^{n-1}$ の平均(重心)を、球の中心としたら、どうか。場合によっては、こっちのほうがうまくfitする。

最小体積の球(minimum−volume sphere)

これが一番多用されるはず。最適なものを求めるのはかなり難しい。

近似で良ければいくつか方法がある。

１．ガウス分布を用いて、主軸 $L_{0}$ を計算し、点列のこの軸方向での最小値と最大値を求め、この中心を球の中心とする。そこから球を膨らませていく。膨らませ方は次の方法をとる。

もし現在の球に点Pが含まれていないなら、

　現在の球の中心Qと、直線PQと球の交点のうち、Pから遠いほうの交点Gとして、

新しいQ =GとPの中点　，　半径=|P−新しいQ|

という作業をすべての点に対して行なう。

ところが、これは作業する点の順番により結果の精度にばらつきが出ることがある。そこで次の方法と併用すると良いかも知れない。

２．Emo Welzl(1991)の論文が詳しいが、概略だけ説明すると、 $\left\{\vec{V}_{i}\right\}_{i=0}^{n-1}$ をまずシャッフリングして、

while (i<N) {

if ( p[i] not in support )

if ( p[i] not in sphere )

p[i]をsupport集合に加えて可能ならば不要な点をsupport集合から除去。

現在のsupport集合からsphereをupdate。

i=0; continue;

}

++i;

}

※　updateというのは、さきほどの「新しいQ =GとPの中点　，　半径=|P−新しいQ|」を用いると良いだろう。

5.2. 方位性を持ったボックス(oriented boxes)

方位性を持ったボックスのほうが球でオブジェクトにフィットさせるよりはいい結果になることが多い。

ボックスの辺の方向を表す正規直交行列 $R=\left[\vec{L}_{0}\vec{L}_{1}\vec{L}_{2}\right]$ によって、

$\vec{X}=\vec{C}+R\vec{Y} , \vec{Y}=(y_{0},y_{1},y_{2}) ,$ すべての $i$ に対して $\left|y_{i}\right| \leq e_{i}$

のように表現することが出来る。

軸と平行な辺を持つボックス(axis−aligned boxes)

AABBを求めるところでも出てきたように、 $\left\{\vec{V}_{i}\right\}_{i=0}^{n-1}$ の最小 $\vec{p}_{min}=(x_{min},y_{min},z_{min}) , \vec{p}_{max}=(x_{max},y_{max},z_{max})$ を求めて、それを頂点とするボックス。

ガウスの分布による点列のフィッティング(fitting points with Gaussian distribution)

重心 $\vec{C}$ を求め、軸 $L_{i}$ に角点を投影して、その最大、最小を $min_{i}+max_{i}$ とすれば

$\displaystyle \vec{C}^{\prime}=\vec{C}+\sum_{i=0}^{2}\frac{min_{i}+max_{i}}{2}\vec{L}_{i}$

最小体積のボックス(minimum−volume box)

ボックスによる最適なフィッティングは点列を含むボックスが最小体積になる時だと思われる。この計算には時間を要するが、この計算をオフラインで行なえるならば、なかなか有力な方法である。

$\vec{A}_{i}$ ( $i=0,1,2$ )を初期座標軸として、軸上に各点を投影したものを考える。 $\rho_{ij}=\vec{A}\text{・}(\vec{V}_{j}-\vec{V}_{0})$ , $\alpha_{i}=min_{j}(\rho_{ij})$ , $\beta_{i}=max_{j}(\rho_{ij}) , \gamma_{i}=(\alpha_{i}+\beta_{i})/2$ として、

$\displaystyle \vec{C}=\vec{V}_{0}+\sum_{i=0}^{2}\gamma_{i}\vec{A}_{i}$ , ボックスの範囲は $a_{i}=(\beta_{i}-\alpha_{i})/2$

このとき、体積は $\displaystyle \nu=\prod_{i=0}^{2}(\beta_{i}-\alpha_{i})$ 　

これを各 $L_{i}$ 軸で回して最小にならないかと言うもの。詳しいことは割愛。

ガウス分布による三角形のフィッティング(fitting triangles with a gaussian distribution)

3角形メッシュの頂点集合を方位性を持ったボックスでフィッティングさせようとする時、頂点集合は偏在してるからガウス分布を仮定できない。

そこで、3角形の面積で重み付けしてやればいいんじゃないかって話。

論文→Gottschalk,Lin,Manocha(1996) , SIGGRAPH 1996,pp.171−180

5.3. カプセル(capsules)

カプセルは円筒の両端に半球をくっつけた形状である。これは、線分から一定距離r以内にある集合として定義できる。球が「点から一定距離r以内にある集合」と定義できたことから考えるに、これは球の等距離(equidistance)に基づく自然な拡張である。

最小二乗法によるフィット(least−squares fit)

カプセルは線分から一定距離r以内になる集合なので、まずは線分でフィッティングさせることを考える。点列の重心を $\vec{A}$ として、

線分: $\text{　}\vec{A}+t\vec{L}_{0}$

$R=\left[\vec{L}_{1}\vec{L}_{2}\vec{L}_{0}\right]$ は正規直交行列。この座標系で点列の座標を考える。

$\vec{X}_{i}=\vec{A}+R\vec{Y}_{i} , \vec{Y}_{i}=(u_{i},v_{i},w_{i})$

そのあと、すべての点列が含まれるように半球 $u^{2}+v^{2}+(w-\xi_{0})^{2}=r^{2}$ , $w\leq\xi_{0}$ の $\xi_{0}$ を求める。

$\displaystyle \xi_{0}=\min_{i}\left\{w_{i}+\sqrt{r^{2}-(u_{i}^{2}+v_{i}^{2})}\right\}$

同様に $u^{2}+v^{2}+(w-\xi_{1})^{2}=r^{2}$ , $w\geq\xi_{1}$ なる $\xi_{1}$ を求める。

$\displaystyle \xi_{1}=\max_{i}\left\{w_{i}-\sqrt{r^{2}-(u_{i}^{2}+v_{i}^{2})}\right\}$

そしたら、 $\vec{P}_{j}=\vec{A}+\xi_{j}\vec{W} , j=0,1$ を両端とする線分から距離r以内のカプセルが求めるカプセルである。

最小面積の投影された円の極小(minimum of minimum−area projected circles)

$\vec{X}_{i}=\vec{A}+R\vec{Y}_{i} , \vec{Y}_{i}=(u_{i},v_{i},w_{i})$ 　なので、この軸方向 $\vec{L}_{0}$ を法線とする平面 $\vec{L}_{0}\text{・}\vec{X}=0$ への投影は $(u_{i},v_{i})$ 球のフィッティングでやった手法と同じく、これの最小化を考えて、そのrを使えばいい。

5.4. 菱形(lozenges)

菱形は、4辺の長さが等しい4角形。この菱形から距離r以内の集合を考える。これは球からカプセルに拡張した時同様、距離に関する自然な球の拡張だと言える。ここでは、この図形でフィッティングすることを考える。

ガウス分布によるフィット(fit with a gaussian distribution)

$\vec{X}_{i}=\vec{A}+u_{i}\vec{L}_{0}+v_{i}\vec{L}_{1}+w_{i}\vec{L}_{2}$

$w_{i}$ の最小、最大を $w_{min}$ , $w_{max}$ とおくと、平面 $\vec{W}\text{・}\left(\vec{X}-\vec{A}\right)=w_{min}$ と $\vec{W}\text{・}\left(\vec{X}-\vec{A}\right)=w_{max}$ で点列はすべて挟まれていることになるので、あとはこれをカプセルの時と同様の考えかたで縮めていけば良い。

5.5. 円柱(cylinders)

無限円柱は、直線 $\vec{P}+t\vec{D}$ （ $t\in \mathbb{R},\vec{D}$ は単位長ベクトル）から一定距離r以内の点の集合である。有限な円柱は、この無限集合の部分集合である。ここでは「有限な円柱」を単に「円柱」と書くことにする。

最小二乗法による軸を含む線分(least−squares line contains axis)

例によって $\vec{X}_{i}=\vec{A}+R\vec{Y}_{i} , \vec{Y}_{i}=(u_{i},v_{i},w_{i})$ とすれば、

円柱の半径 $r =max_{i}\left\{\sqrt{u_{i}^{2}+v_{i}^{2}}\right\}$ , 円柱の高さ $h = w_{max}-w_{min}$

最小二乗法で最小面積となる中心に移動させた線分(least−squares line moved to minimum−area center)

上の方法で求めたあと、カプセルの時と同じく軸を移動させたほうが良い。

5.6. 楕円体(ellipsoids)

軸に沿った楕円体は $\displaystyle \frac{x^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}+\frac{z^{2}}{c^{2}}=1$ で表される。

中心は(0,0,0)で a>0,b>0,c>0。楕円の軸の方向は(1,0,0),(0,1,0)と(0,0,1)である。

中心 $\vec{C}$ ,正規直交行列 $R$ を直交座標軸として与えた座標系において、楕円体は

$(\vec{X}-\vec{C})^{T}R^{T}DR(\vec{X}-\vec{C})=1$ , $D=diag\{1/d_{0}^{2},1/d_{1}^{2},1/d_{2}^{2}\}$

で表現される。

・軸沿いの楕円体(axis−aligned ellipsoid)

いままでの議論と同じなので省略。

・ガウス分布による点列のフィッティング(fitting points with a gaussian distribution)

いままでの議論と同じなので省略。

・最小体積の楕円体(minimum−volume ellipsoid)

これは難しいからやめたほうがいいそうな。

参考文献

1.『3DGame EngineDesign』 , David H.Eberly , MORGANKAUFMANNPUBLISHERS ,ISBN1−55860−593−2.

2.『Mathematics for 3d Game Programming and Computer Graphics (Game Development Series)』 , Eric Lengyel , Charles River Media , ISBN 1−58450−277−0 .