情報処理学会第65回全国大会

5A-3

干渉判定用多重解像度メッシュ生成に関する研究− メッシュ品質を考慮した低解像度メッシュ生成 −
伊達 宏昭
金井 理
岸浪 建史
北海道大学大学院工学研究科
1． はじめに形状モデル間の高速な干渉判定処理は，物理シミュレーションや組立シミュレーションには必要不可欠である．
本研究では，三角形メッシュモデルを対象として，効率の良い干渉判定処理の実現を目的とした多重解像度メッシ
ュに基づく干渉判定処理手法を提案してきた[1]．提案する干渉判定処理手法は，図 1 に示すように，メッシュモデルの多重解像度表現(図 1,A-1)から得られる低解像度メッシュ間で干渉判定を行い，干渉が検出された場合に，干渉個所の近傍のみを局所的に高解像度化しながら，段階的に干渉個所を絞り込んだ効率の良い干渉判定処理(図1,A-2,A-3)を実現するものである．この手法では，干渉判定処理の効率化を実現するには，干渉可能性の低い部分を含まず，且つ，干渉を過小評価しないために高解像度形状を内部に包み込むが干渉の過大評価の少ない低解像度メッシュが必要となる．そこで本報告では，干渉可能性の低い面積の小さな面分が少なく，干渉の過大評価を減少させるための形状膨張の少ない低解像度メッシュ生成手法を提案する．

M AJ AM BJ B

多重解像度
表現生成

MRRA

A-1

M0A

MRRB
本報告

M B0

MA
干渉判定精度・処理速
M B0度要求

M BjB
干渉判定
処理

M Aj A

適応的j
解像度 M BB制御
干渉A-2
検査

干渉の有無
干渉個所

A-3
面分間の干渉判定法

適応的解像度制御手法

図1

M Aj A

0

MRR生成規則

多重解像度メッシュを用いた干渉判定処理

表 1 干渉判定用多重解像度メッシュへの要求
必要条件
干渉判定処理効率化ための望ましい条件
干渉過小評価 低解像度メッシュは干渉可能
干渉過大を回避する性の低い部分を含まない
評価が少ない(1) 高解像度形 (2) 凹部分から (3) 低解像度メッ (4) 形状膨張量状の内包の低解像度化 シュの品質向上
最小化

2． 干渉判定用多重解像度メッシュ
メッシュモデルの多重解像度表現とは，与えられたメッシュモデル M J を最低解像度の近似 M 0 と，近似の際に失われた情報に階層的に分解した表現法であり，メッシュモデルの繰り返しの低解像度化により得られる．多重解像度表
現より得られる，解像度変更が可能なメッシュモデルを多重解像度メッシュと呼ぶ．多重解像度メッシュ生成は，A)
要素削除・復元方法：どのようにメッシュモデル内の要素を削除・復元するか，B) 解像度制御基準：どのような評価に従って要素の削除・復元の順序を決定するか，C) 幾
何学的関係：低解像度の形状は高解像度の形状に対しどのような幾何学的関係を持つか，の 3 項目を定義すれば良い．
干渉判定用の多重解像度メッシュへの要求を表 1 に示す．
本研究では，これまでに，表 1(1)(2)を満足するために，要素削除方法として頂点対を 1 頂点に統合する edge collapse(EC)[2]を用い，曲率評価による干渉可能性の低い凹部分を優先的に低解像度化する解像度制御基準に基づいて，干渉を過小評価しないように低解像度形状が高解像度形状を内部に包含する幾何学的関係(内包)を実現する多重解像度メッシュ生成手法を提案してきた．
本報では，表 1 内の残りの 2 項目である，干渉過評価を減少させるための形状膨張量の最小化(表 1(4))と，干渉可能性の低い面積の小さな面分の削減(メッシュ品質の向上，
表 1(3))を実現する低解像度メッシュ生成のための，解像度制御基準と幾何学的関係の定義法を述べる．
A Study of Multiresolution Mesh for Collision Detection
Hiroaki Date, Satoshi Kanai and Takeshi Kishinami, Hokkaido
University, kita-13 nishi-8, kita-ku, Sapporo, Hokkaido 060-8628, Japan

MJ

M0Mj

Mj

M0

Mà j

M0

Mà 0vol ( M 0 ) > vol ( Mà 0 )| T 0 |=| Tà0 |(vol(M): Mの体積)

3． 干渉判定処理効率化の為の多重解像度メッシュ
以降では，EC により統合される頂点を i, j ，新たに生成される頂点を k ，頂点 i の位置を p i ，頂点 i に接続する面分集合を Fi ，面分 f を構成する頂点を ( f 1, f 2, f 3) と記述する．
3.1

解像度制御基準

EC を用いたメッシュ低解像度化では，メッシュモデル内の全ての頂点対 (i, j ) をある観点で評価し，その評価値 ε ijの大小に従って EC を適用する頂点対を決定する必要がある．本研究では，表 1(2)-(4)の性質を満たす低解像度化を実現するために，ε ij を，曲率評価に基づく凹凸評価値 κ ij [1]と，以下で述べる面分面積評価値 aij ，形状膨張評価値 vij の重み付き和として定める(式(1))．重み (α , β , γ ) を変化させることにより，要求する性質の強度を変化させることができる．EC は， ε ij の大きな頂点対から順に適用する．

ε ij = ακ ij + βaij + γvij

(1)

3.1.1 面分面積評価値
面積の小さな面分は空間占有率が低いため，干渉可能性が低く，優先的に低解像度化によって除去されることが望ましい．EC では，図 2(a)に示すように， 2 つの面分 Fi ∩ F jが除去される．面積の小さな面分を優先的に除去するため

4−31Fi ∩ F jに，この 2 面分の面積の和 Aij の逆数を，面分面積の評価値
aij = 1/ Aij として用いる．

i

3.1.2 形状膨張評価値
内包を伴うメッシュ低解像度化は形状膨張を招く．この形状膨張が少ない部分から低解像度化することによって，干渉の過大評価の少ない低解像度メッシュが生成できる．
このために，以降で述べる，EC による体積増加量 ∆V (k ) の逆数を，形状膨張の評価値 vij = 1 / V∆ (k ) として用いる．

3.2j(a)図2

ECにより除去される面分(a)と体積変化量(b)3.2.1 高解像度形状の内包干渉過小評価回避の為の高解像度形状の内包は，図 3(a)に示すような，Fi ∪ F j 内の面分を含む平面を境界とする半空間 H f (形状の外側)の積で表される内包空間 I ij 内に，頂点位置 p k を定めることで実現される．具体的には，式(2)の不等式を満たすように p k を定めればよい．
f f pà k ≥ 0T1(p f 1 × p f 2 ) ⋅ p f 3∑
6 f ∈Fi ∪ F j ∪ Fk(3)形状膨張の最小化は， ∆V ( k ) の最小化問題に帰着する．
式(2)(3)は， p k の要素に関する線形式であるため，式(3)を目的関数，式(2)を制約式とする最適化問題を，線形計画法を用いて p k について解くことによって，上述の性質を満たす低解像度メッシュを得ることができる．

4.

適用結果とまとめ

図 4(a)に示すメッシュモデルに対し，式(1)における重み(α , β , γ ) ，及び，3.2.2 節 f B のオフセット量 l の，異なる設定において提案手法を適用した結果得られた低解像度メッシュを同図(b)-(e)に示す．また，従来法[1] により得られた低解像度メッシュを同図(f)に示す．図中括弧内の数値は(α , β , γ , l ) である．
表 2 に，
図 4 の各メッシュモデルの体積，面分面積の分散の評価結果を示す．図 4 及び表 2 より，β , lを大きくすると，面分面積分散が小さくなっていることが∆ V (k )H f2jf2
f1
Fi ∪ F j 形状内部f3(a) 内包空間

V f B1

S ijf B1V fB2
offsetoffset

ここで， pà k は p k の同次座標表現， f f は面分 f を含む平面の方程式 a f x + b f y + c f z + d f = 0 の係数列ベクトルである．

∆V ( k ) =H f3

I iji(2)3.2.2 面積の小さな面分生成の回避
面分面積評価値に基づいて面積の小さな面分を除去する一方で，更に，EC 適用後のメッシュにおける面積の小さな面分生成の回避を考え，これを実現する p k の存在可能空間 Sij を定義する．面積の小さな面分は，Fi ∪ F j の境界近くに p k を定めた場合に生じるため， Sij を，図 3(b)に示す
ように，Fi ∪ F j の境界稜線上で定義される平面 f B をオフセットした平面を境界とする半空間 V f B の積として定義する．
f B は，Fi ∪ F j の境界稜線と，それを共有する 2 面分の平均面法線方向上の 1 頂点とで張られる平面として定義する．
f B のオフセット量は任意であり，例えば，Fi ∪ F j の境界頂点の重心からの距離に対する割合 l(%)として定められる．
p k を Sij 内に定めるための制約式は，式(2)と同様の形で記述できる．
3.2.3 形状膨張量の最小化と p k の決定
内包を伴うメッシュ低解像度化による形状膨張を最小化する p k の決定を目的として，図 2(b)に示される，EC によるメッシュモデルの体積変化量 ∆V ( k ) を導出する．
∆V (k ) は，頂点 k の関数として，式(3)により求められる．

∆V (k )(b)H f1

f ∈ Fi ∪ F j ,pjpi

幾何学的関係∀Fi ∪ F j ∪ Fkpki

Fi ∪ F jfB2j

形状内部(b) メッシュ品質向上空間

図3(a) オリジナルモデル

頂点 pk の存在可能空間(b)凹凸評価値大(0.6,0.1,0.1,30)(d) 形状膨張評価値大 (e) (d)のoffset量大(0.1,0.1,0.6,30)(0.1,0.1,0.6,60)(c)面積評価値大(0.1,0.6,0.1,30)(f) 従来法

図 4 提案手法の適用結果
表 2 低解像度メッシュの評価
(f)
(e)
(d)
(c)
(b)
(a)
面分数
596
596
596
596
596
2048
体積
4178.7 4463.4 4348.8 4324.9 4330.5 4882.7
面分面積分散 125.6 1879.5 1148.1 1339.7 908.6 1243.6
平均面分面積 0.72
2.38
2.57
2.59
2.59
2.46
確認でき，このことは，低解像度メッシュにおいて面積の小さな面分の削減が実現されていると言える．また，提案法では従来法より形状膨張量が少なく， γ の値によりその効果を制御できることが確認できる．以上より，提案手法が，干渉判定処理の効率化に要求される性質を持つ低解像度メッシュ生成に有効であることが確認された．
[参考文献][1] 伊達他: 干渉判定のための多重解像度メッシュモデル生成に関する研究，FIT2002 情報科学技術フォーラム講演論文集，J-31,2002[2] H. Hoppe: Progressive Meshes, Computer Graphics (SIGGRAPH96),

4−32

pp. 98-108, 1996