リアルタイム3DCGにおける 位相変化を考慮した弾性体の挙動表現

修士論文
平成 20 年度 (2008)
リアルタイム 3DCG における
位相変化を考慮した弾性体の挙動表現に関する研究
東京工科大学大学院
バイオ・情報メディア研究科メディアサイエンス専攻
海上 一徳
修士論文
平成 20 年度 (2008)
リアルタイム 3DCG における
位相変化を考慮した弾性体の挙動表現に関する研究
指導教員
渡辺 大地 講師
東京工科大学大学院
バイオ・情報メディア研究科メディアサイエンス専攻
海上 一徳
論文の要旨
論文題目
執筆者氏名
指導教員
キーワード
リアルタイム 3DCG における
位相変化を考慮した弾性体の挙動表現に関する研究
海上 一徳
渡辺 大地 講師
リアルタイム、 3DCG、 弾性体、位相変化、
アニメーション、幾何学、シェイプマッチング
[要旨]
近年リアルタイム 3DCG では、様々な物体の挙動を高速かつリアルに表現する技術が
必要になっている。ゲームやバーチャルリアリティ等のリアルタイム 3DCG においては、
物体のリアルな挙動をインタラクティブに表現することが、臨場感の面で大きな役割を果
たす。そのため、ゲームなどでは様々な物理現象・自然現象による表現を積極的に取り入
れているが、ハードウェアの処理能力の限界等により、実現していない表現も数多い。本
研究では、その中でも外力が加わることにより形状が変化し、外力がなくなれば自立的に
元の状態に戻る弾性体表現に注目した。現実世界における弾性体物体では、物体そのもの
の形状が破壊されることで断裂を伴う変形が起こる。そのような変形挙動は、ゲームやア
ニメーションの分野ではフラクチャリングと呼ばれ、弾性体表現の幅を広げる重要な要素
となっている。
コンピュータグラフィックスにおいて弾性体のシミュレーションには数多くのアプロー
チが存在するが、厳密な物理計算を行った場合は計算処理的に非常に高価なものとなる。
また、弾性体シミュレーションにおける研究の中では、物体の断裂や破壊を伴うような変
形操作に関する研究もなされているが、弾性体の物理特性を考慮したポリゴンモデルでの
位相変化表現をリアルタイムで処理する手法は、まだ確立していない。
本研究では、リアルタイムでの位相変化に対応した弾性体の位相変形を考慮した、変
形シミュレーションを行うことを目的とし、弾性体物体における位相変化表現をリアル
タイムで行う方法を提案する。弾性体のシミュレーションには幾何学ベースの手法であ
るシェイプマッチング法を用いた。それに加えて、高速な位相変化を伴う変形が可能な、
Half-Edge 構造を提案モデルに採用することで、弾性体の位相変化表現をリアルタイムで
実現した。
Abstract
Title
Author
Advisor
Key Words
Tolopogy Operation of Meshes
with Elastic Object in real-time 3DCG
Kazunori Unakami
Lecturer Taichi Watanabe
Realtime 3DCG, Elasticity, Topplogy Operation,
Animation, Geometric, Shape Matching
[summary]
In recent years, The technology which is expressed to high speed and substance was
needed operation of various objects in the real time 3DCG. In the real time 3DCG of the
game and virtual reality etc, By the fact that behavior of the object is expressed to interactive, the appearance impression is produced. Because of that, physical phenomenon
and natural phenomenon is adopted positively in the game. But, By the capacity of the
hardware, the expression which is not implemented it is many. In this research, attention
to elastic body expression that form changes with external force and returns to original
shape when no external force.
In CG elastic body simulation are many approaches. But when strict physical calculation it does, to compute it is very slow. In additon, in research of elastic body simulation,
Also tge reseach regarding the fracture of the object and the deformation operation of accompanying destruction has done, but there is no technique which processes the topology
operation expression with the polygon model which considers. The deformation which
accompanies fracture by the fact that form of the object is destroyed with also the actually elastic. That kind of deformation behavior has become the important with the game
and animation at the time of elastic body expressing.
This reseach designates that the deformation simulation which considers the topology
deformation of the elastic body which corresponds to the topology operation at real-time
is done as purpose, and the technique which does the topology operation expression of
the elastic body in realtime is proposed. Shape Matching of Geometric base was used to
elastic body simulation. Furthermore, high speed by the fact Half-Edge whose topology
operation is possible used for the elastic body model, topology operation of the elastic
body was implemented in real time.
目次
第 1 章 はじめに
1.1 研究背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 論文構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第2章
2.1
2.2
2.3
1
2
8
弾性体モデルにおける位相変化表現
9
3 次元モデルにおける位相変化 . . . . . . . . . . . . . . . . . . . . . 10
既存研究おける弾性体モデルの位相変化表現 . . . . . . . . . . . . . 11
本研究の位置づけと研究方針 . . . . . . . . . . . . . . . . . . . . . 13
第 3 章 提案手法
3.1 幾何学的手法による弾性体挙動 . . . . . . . .
3.1.1 シェイプマッチング法 . . . . . . . . .
3.1.2 数値積分 . . . . . . . . . . . . . . . . .
3.1.3 変形アルゴリズム . . . . . . . . . . . .
3.2 提案モデルの位相変化手法 . . . . . . . . . . .
3.2.1 動的なクラスタ化による位相状態管理
3.2.2 位相変化手順 . . . . . . . . . . . . . .
3.2.3 位相変化操作の概要 . . . . . . . . . .
3.3 計算手順 . . . . . . . . . . . . . . . . . . . . .
第 4 章 評価と検証
4.1 実行結果 . . . . . . . . . . . . . . . .
4.1.1 提案モデルによる弾性体挙動
4.1.2 提案モデルによる位相変化 . .
4.2 実行速度検証 . . . . . . . . . . . . .
4.3 現状の問題点 . . . . . . . . . . . . .
第 5 章 おわりに
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
16
18
20
22
23
23
24
24
26
.
.
.
.
.
28
29
29
32
35
35
37
謝辞
39
参考文献
41
図目次
1.1
1.2
格子法と粒子法の違い . . . . . . . . . . . . . . . . . . . . . . . . .
質点バネモデルの構成要素 . . . . . . . . . . . . . . . . . . . . . . .
2.1
バネモデルによる位相変化のモデル . . . . . . . . . . . . . . . . . . 11
3.1
3.2
3.3
3.4
3.5
陽的積分による線形バネに働く力 . . . .
陽的積分による線形バネの移動距離 . . .
シェイプマッチング法を用いた形状変形
本位相変化操作の概要 . . . . . . . . . .
計算のながれ . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16
17
19
25
26
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
ブロックモデルでの弾性体挙動表現 . . . . . . . . .
スフィアモデルでの弾性体挙動表現 . . . . . . . . .
キャラクターモデルでの弾性体挙動表現 . . . . . .
スタンフォード・バニーモデルでの弾性体挙動表現
ブロックモデルでの位相変化 . . . . . . . . . . . .
スフィアモデルでの位相変化 . . . . . . . . . . . .
キャラクターモデルでの位相変化 . . . . . . . . . .
スタンフォード・バニーモデルでの位相変化 . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
31
31
32
33
33
34
34
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
7
表目次
2.1
既存弾性体シミュレーションの特徴 . . . . . . . . . . . . . . . . . . 13
4.1
提案モデル 処理速度の測定 . . . . . . . . . . . . . . . . . . . . . . 35
第1章
はじめに
1.1
研究背景
近年リアルタイム 3DCG において、様々な物体の挙動を高速かつリアルに表現
する技術が必要とされている。ゲームやバーチャルリアリティ等のリアルタイム
3DCG においては、物体のリアルな挙動をインタラクティブに表現することが、臨
場感の面で大きな役割を果たす。そのため、様々な物理現象・自然現象による表現
が積極的に取り入れられているが、ハードウェアの処理能力の限界等により、実
現されていない表現も数多い。
本研究では、その中でも弾性体表現に注目した。ゴムやゲルなど自然界におけ
る弾性体は、外力が加わることにより形状が変化し、外力がなくなれば自立的に
元の状態に戻る。また、過度の外力が加わる場合には、外力がなくなったとして
も元の状態に戻らなくなったり、物体そのものの形状が破壊され分断されるといっ
た変形が起こる。そのような弾性体の変形では、変形をひずみで表し、元に戻ろ
うとする力である復元力を圧力と同じ単位を持つ応力で表す。ひずみとは、伸縮
により生じた元の状態との変位比の値である。また、このとき応力はひずみに比
例する。これをフックの法則と呼ぶ。弾性変形とはフックの法則の範囲内で起こ
る変形のことであり、ここから応力がある限界を超えると弾性の性質から元に戻
らない塑性変形を引き起す。弾性体の材質により、ある力が加わったときどの程
度変形するのか、或いはある変形を生じさせるのに必要な力はどの程度の大きさ
が必要なのかが異なる。この材質固有力学的特性を数学的に表現したものが応力
とひずみの関係である。弾性体においてはこれを式によって定式化し、これを支
配方程式と呼ぶ。変形があまり大きくない場合で等方性、つまり弾性体の性質が
方向によらず一定である弾性変形では、体積変化をもとに戻そうとする力と伸縮
変形をもとに戻そうとする力の 2 種類の復元力が働くことになる [1]。弾性体の支
配方程式は、ひずみが非常に大きくなる場合や異方性、つまり弾性体の性質が方
向により異なる場合には適用できない。
本研究では、弾性体の位相変化を伴う変形についてリアルタイムでの処理が可
2
能な手法を実現することを目的とした。したがって、より高速な弾性体モデルで
ある必要がある。そこで本研究では以下の 3 つの条件を満たすことを想定した。
• 効率：インタラクティブアプリケーションで使用可能な処理速度を持つこと
• 安定性：シミュレーションにおけるあらゆる状況下で計算が安定すること
• 制御性：物体の制御に必要なパラメータを極力無くし、柔軟な制御性を持つ
こと
本論文では、これらの想定を満たす、リアルタイムにおける位相変化を伴う変形
可能な弾性体挙動シミュレーション手法について述べる。
3DCG における弾性体シミュレーションでは、物理ベースによる方法と幾何学
ベースによる方法がある。物理的な法則に則った物理ベースによる方法には、大き
く分けて格子法と粒子法の 2 種類がある。格子法には、差分法、有限体積法（Finite
Volume Method,FVM）、有限要素法（Finite Element Method ,FEM）などがあ
り、空間や物体を格子で覆い、連続体の物理法則を格子点上の変数の関係式に変
換することでシミュレーションを行う。格子法による弾性体シミュレーションで
は、特に有限要素法を用いる場合が多い。
有限要素法を用いて弾性要素の変形に応じた物体の再構築に関する研究につい
ては、有限要素法における変形が大きい部分の要素を小さい要素に分解する方法
[2] がある。有限要素法とは数値解析手法の 1 つで、一般に粘弾性解析、クリープ
解析、といった構造力学分野で広く利用されている手法 [3] である。有限要素法で
は、計算対象を有限の範囲にモデル化し、その内部を小さな要素で区切り、各々の
要素内で成り立つ連立 1 次方程式を作成する。次に、各要素における方程式を全
解析領域分足し合わせることで大きな連立 1 次方程式を作成し、近似解を求める
方法である。有限要素法は、実物体の持つヤング率やポアソン比などの物理特性
3
を直接記述できるため、物体を精度良く表現することが可能であるが、膨大な計
算量を必要とするため、リアルタイムでの処理には不向きとされる。
有限要素法では、対象物体全体の変形と外力の関係を、式 (1.1) に示す剛性方程
式によって表現する。
[
F=
]
K
δ
(1.1)
ここで、F は物体に与えられる外力であり、δ はその結果生じる物体の歪（変位）
である。[K] は物体の柔らかさを決定するための剛性行列である。外力が与えられ
たときの物体の歪を求めるには、剛性行列 [K] の逆行列を求める必要があるが、不
定であるため、それを求めることに膨大な計算量が必要となる。このことが、リ
アルタイム処理を行う際の問題点になる。この問題に対して、物体の位相が変化
しない状況下、すなわち物体の変形状態によって剛性行列が変化しない場合には、
その逆行列を予め計算しておくことで、リアルタイムでの弾性変形を可能とした
手法がある [4]。また、前処理において、予め変形操作に対する物体の変位を計算
しておき、その計算結果をファイルに格納しておくことで、リアルタイムに弾性
変形を実現した手法がある [5]。また、有限要素法における変形を質点バネモデル
に応用した研究が報告されている [6]。このモデルは大変形部分のみ要素解像度を
高められるため処理効率の良いモデルとして評価できるが、変形が大きくなるに
つれて処理速度が低下するため、リアルタイム処理には不向きである。
一方、粒子法には、越塚ら [7] が開発した、非圧縮性流体を半陰的なアルゴリズ
ムで解く粒子法である MPS(Moving Particle Semi-implicit) 法や、Lucy[8] によっ
て、宇宙物理学のために開発された圧縮性流体を陽的なアルゴリズムによって解
く粒子法に SPH(Smoothed Particle Hydrodynamics) 法などがある。どちらの方法
も、もともとは水などの流体をシミュレーションするために開発されたが、現在
では、弾性体シミュレーションにも応用されている [9]。粒子法では、物体を粒子
4
の集合とみなして表し、物理法則を各粒子に適応することで物理ベースのシミュ
レーションを行う。粒子法にみられる特徴として、弾性体等における支配方程式
を、計算格子を考慮することなく粒子の運動方程式として離散化可能である。粒
子法を用いて弾性体を表現する場合、まず、同じ大きさの粒子を物体の形状に合
わせて生成する。各粒子にはそれぞれ位置ベクトルと回転角の自由度を持たせる。
粒子の回転を考慮することで、モデルに生じるひずみを精度よく計算できる。格
子法と粒子法の違いは、格子点 (あるいは粒子) 間の繋がりを持たせるか否かにあ
る。図 1.1 は格子法と粒子法の違いを示した図である。格子法では各格子点におい
て繋がりのある他の格子点との間に関係式を立てるのに対し、粒子法では、粒子
間の繋がりは与えず、各粒子から一定の距離にある近傍粒子との間で関係式を作
る。したがって、物体が断裂するなどの大変形が起こるシミュレーションを考え
た場合、格子法では格子の変形が著しくなり、計算が破綻するが、粒子法では容
易に計算できる。しかしながら、粒子法によるアプローチは格子法同様、計算的
に高価でインタラクティブなアプリケーションの使用には適さない。
図 1.1: 格子法と粒子法の違い
弾性体に働く弾性力を、他の力学モデルに置き換えて物理ベースのシミュレー
5
ションを行う方法に、質点バネモデルによる方法がある。質点バネモデルは、質点
同士の力学特性を基にしたシミュレーション手法である。物体を離散的な有限個
の質点の集合として構成し、質点間に作用する力をバネのネットワークを用いて
弾性体特有の弾性を表現する。そして、一般に差分法による数値解析により、離
散時間における質点の位置を、逐次的に計算することで弾性体の挙動を表現する。
しかし、質点バネモデルの表現では、実物体の物理特性を直接記述することがで
きないため、実物体の持つ物理特性を反映させた柔らかさを決定しなければなら
ない。また、質点バネモデルは、変形の過渡特性に問題があるとされる [10]。変形
の過渡特性の問題とは、バネに外力が与えられた場合、そのバネに接続している
隣接質点にしか力の伝播を行わないため、過度に外力が加わると、質点バネモデ
ルの構造が局所的に破壊されてしまうのである。この問題を解決するために、質
点バネモデルの粘性率を高めるか、または、剛性の変形モデルを加味することに
よって過度の力の発生を防ぐという方法がある [11]。計算の安定性の問題とは、数
値計算における誤差がその解に大きく影響する問題であり、具体的には差分法に
おける離散時間間隔を大きくとり過ぎると、質点バネモデルが振動・発散してし
まうのである。そのため、バネモデルが振動・発散しない上限値以下の離散時間
間隔を経験的に決定する必要がある。また、質点バネモデルを用いて複雑な挙動
を表現するためには、多くの質点およびバネのネットワークを用いて弾性体を表
現する必要がある。しかし、それらの増加に比例して質点バネモデルの 1 サイク
ルあたりの計算量が増加してしまうという問題もある。
質点バネモデルでは、四面体格子や立方体格子の構成要素を組み合わせること
によって物体を表現する。立方体格子では、表現する物体に合わせて、面上や格子
内の対角線上にも、バネのネットワークを張る。また、バネのネットワークにダ
ンパを加えることにより、変形挙動に粘性を与える。また、格子を構成する稜線
上のバネの長さを変更することによって、様々な形状に対応することが可能であ
る。計算の簡略化のために、物体が均質で等方性の変形挙動を仮定した場合、一
般に、質点バネモデルの構成要素は図 1.2 に示すように、立方体格子を利用し、そ
6
の格子上の質点すべての組み合わせで張る 28 本のバネのネットワークを用いて表
現する。ただし、格子の稜線上および面上のバネは隣接する格子と共有している。
また、格子は一様の質量を持つとして各質点に等価な質量を与える。
図 1.2: 質点バネモデルの構成要素
物理ベースのシミュレーションとは異なり、弾性体の支配方程式を解くのでは
なく、アニメーションを作成することを主目的とした手法に、シェイプマッチング
法と呼ばれる手法を用いて構築したモデルがある。シェイプマッチング法は、物
理シミュレーションではあるが、連続体の式を正確に解くのではなく、アニメー
ションを作成することを目的とした手法である。Müller らは、シェイプマッチン
グ法を用いて、メッシュレスな形状変形シミュレーションを実現している [12]。こ
の方法では、まず物体の形状を構成する頂点に質点を配置し、これらの質点に外
力や外部の物体との干渉などだけを考慮した変形処理を行う。その結果から、各
タイムステップにおいて物体の形状が、もとの物体の形状を回転と平行移動だけ
で変換したものにできるだけ近づけるようにバネの力を用いて引き付ける処理を
行う。シェイプマッチング法による方法は、支配方程式を解くような物理的に動機
づけられた方法ではないが、前計算を必要とせず、データ構造に依存しないため、
リアルタイムでの弾性変形シミュレーションが可能である。しかしながら、Müller
らの手法では位相変化を前提としていない。
一般に、リアルタイム性を要求されるアプリケーションの中では、シミュレー
7
ションモデルとして剛体を用いる事が主である。剛体を用いたモデルでの、断裂な
どの形状が破壊されるような表現に関する研究は数多くある。しかしながら、弾
塑性を考慮に入れた変形可能な 3 次元物体を、安定で効率的な方法でシミュレート
することを許容する実用的な解法はない。現実世界における弾性体物体でも、物
体そのものの形状が破壊されることで、断裂を伴う変形が起こる。そのような変
形挙動は、ゲームやアニメーションの分野ではフラクチャリングと呼ばれ、弾性体
表現の幅を広げる重要な要素となっている。よって、本研究では基本的弾性体の性
質は、前述したシェイプマッチング法を用いて表現し、データ構造には Half-Edge
構造を用いることにより、前述した３つの条件を満たし、かつ位相変化が可能な
モデルの提案をする。ここで位相変化とは、3 次元モデルが持つ形状に断裂や破壊
が生じることであり、詳細については 2 章で述べる。また、具体的なデータ構造
およびシミュレーション方法については 4 章で述べる。
1.2
論文構成
本論文の構成は以下の通りである。第 2 章では、3DCG における 3 次元モデル
に対する位相変化について説明し、3DCG における既存の弾性体シミュレーショ
ンにおける位相変化表現についてレビューするとともに、とともに、本研究で実
現する位相変化表現について明確化する第 3 章では、本研究で提案する位相変化
を考慮した弾性体の挙動表現手法について述べる。第 4 章では、本研究で開発し
た位相変化可能な弾性体モデルのプログラムより、その結果の検証と考察を行う。
第 5 章では、本研究の成果と意義をまとめ、今後の展望について述べる。
8
第2章
弾性体モデルにおける位相変化表現
本章では、3DCG における 3 次元モデルに対する位相変化について説明し、既
存の弾性体モデルにおける位相変化手法についてレビューするとともに、本研究
で実現する位相変化表現について明確化する。2.1 節では 3 次元モデルにおける位
相変化について、2.2 節では既存研究における弾性体モデルの位相変化表現につい
て、2.3 節では本研究の位置づけと研究方針について述べる。
2.1
3 次元モデルにおける位相変化
3DCG において物体を描画する方法は 、ポリゴンを用いて描画する方法と粒子
を用いて描画する方法がある。そのため、描画方法により 3 次元モデルの位相の
捉え方が異なる。ポリゴンモデルにおける位相変化とは、モデルを構成する頂点
や面の接続状態が変わることをいう。ポリゴンとは、元々は多角形という意味で
あり、3DCG では主に、3 角形または 4 角形の組み合わせで物体を表現する。3 角
形ポリゴンでは、面の法線方向を一意に決定できることに対し、4 角形ポリゴンで
は、面を構成する頂点座標の位置関係によっては法線方向を一意に決定できない
ため、ポリゴンに捩れが発生してしまう。そのため、現在の 3DCG によるコンテ
ンツでは、ほとんどの場合 3 角形ポリゴンを用いることが多い。一方、粒子法を用
いる方法はパーティクルシステムと呼ばれ、動きが不規則な煙や炎などを表現す
る場合や、毛髪や植物など、ポリゴンで表現することが困難なものを表現する際
に用いられる。そのため、粒子法では描画する物体の位相状態を考慮しない。粒
子法による描画では、粒子を球と見なし描画することができるが、レンダリング
するためにはポリゴン化を行う必要がある。ポリゴン化を行うには陰関数曲面を
構築し、マーチング・キューブス法を用いて表面となるポリゴンを抽出する。つ
まり、ポリゴンの位相状態を考慮せず、粒子の動きに応じてポリゴンを再構築す
るため、ポリゴンの位相に対して直接操作をするものではない。 10
2.2
既存研究おける弾性体モデルの位相変化表現
ポリゴンモデルに対する位相変化表現には、有限要素法およびバネモデルを用
いたモデルそれぞれにおいて研究されている。有限要素法を用いたモデルでの位
相変化を実現するためには、断裂した物体をモデル化する必要がある。そういった
位相変化のアニメーションを実現した方法 [13] では、位相変化の発生する場所や
その方向を、物体の変形に伴って生じる応力を解析することによって決定し、これ
に基づいて物体を再構成することで物体の断裂表現を実現している。また、有限
要素法を用いたモデルでは、オブジェクトを描画するために、マーチング・キュー
ブス法等によりポリゴンを生成しなければならない。これは、計算的に高価で、リ
アルタイム処理の妨げになる可能性がある。一方、ポリゴン生成を必要としない
計算手法として、移動最少自乗法近似を用いて関数近似を行い Galerkin 法を適用
して積分形の方程式に変換する EFG（Element Free Galerkin）法 [14] がある。し
かしながら、やはり計算が高価である。また、この方法では制約条件や前処理の
域を超えるため、リアルタイムでの実現はなされていない。一方、バネモデルで
は、計算 1 サイクルあたりの計算量が比較的少ないことから、リアルタイムでの
位相変化を伴う変形を実現している [11]。ここで、バネモデルを用いて位相変化を
実現した既存研究について述べる。 図 2.1: バネモデルによる位相変化のモデル
11
図 2.1(a) に示すように、バネモデルに外力が加わり変形操作が行われバネモデ
ルが極度に変形し、図 2.1(b) に示すようにバネが閾値以上伸びた場合、そのバネを
含む格子を構成するバネを切断する手法 [15][16] や、図 2.1(c) では 質点に閾値以上
の力が加えられた場合に、その質点を分裂させ、新しくバネのネットワークを生
成する手法 [11][16] がある。前者の手法は、閾値を越えたバネを単に削除すること
によって位相変化が実現できることから、変形に要する計算量が少なく、質点と
バネに関するデータ構造が簡単化できる。しかし、位相変化によって体積を失う
ことから写実性に問題がある。この問題に対して、格子数を増やすことによって
解決することも可能であるが、同時にバネモデルの計算量も増加してしまうこと
が難点である。後者の手法は、体積が保持できることから、前者の写実性の問題
を解決することができる。しかし、質点の分離や新しいバネのネットワークの生
成のために計算量が増加する問題がある。また、位相幾何的に位相変形を行う手
法に、拘束付きドロネー三角形化アルゴリズムを用いた再分割曲面（Subdivision
Surfaces）による方法があるが、干渉領域の抽出処理や境界接続アルゴリズム等に
多くの計算コストが掛ってしまう。
Rivers[17] らは、FastLSM(Fast Lattice Shape Matching) と呼ばれる、シェイプ
マッチング法を用いた弾性表現に、有限要素法的な手法を施すことで位相変化を
実現している。3 次元モデルを立方体格子で表現し形状変形を実現する。個々の頂
点をまず独立に物理法則にしたがって動かし、次に近傍立方体格子群毎に形を復
元する力をかける。シェイプマッチングを行う際に極分解を行う必要があるが、各
立方格子に同じ計算が何度もでてくるのでそれらを無駄なく行うことで高速な計
算を実現する。また、大変形に伴い Müller ら [18] の手法を使用し、立方体格子間
を切断することで、3 次元モデルの破壊表現を行っている。しかしながら、ハード
ウェアレンダリングを行っているため、ポリゴンモデルに対して位相変化を施す
ものではない。したがって、ポリゴンモデルの位相変化を直接操作できない。 12
2.3
本研究の位置づけと研究方針
本節に至るまで、3DCG における弾性体シミュレーションおよび、弾性体モデ
ルにおける位相変化表現の既存研究について述べた。有限要素法を用いた弾性体
表現では、実物体の持つ物理特性を直接記述できることから、物理的に正確な弾
性体表現が可能である。しかし、反面計算量が多く、前処理や制約条件を適用して
も、リアルタイムでの位相変化を実現することは困難である。一方、粒子法を用
いたモデルでは、物体の位相構造にとらわれることなく計算可能なことから、体
変形や破壊といった表現が容易に行えるが、レンダリングを行うために計算コス
トの増加を招く可能性がある。また、バネモデルでは、物理特性を反映する従来
法を用いて弾性体を表現することが可能であり、質点やバネの本数に依存するが、
その変形挙動はリアルタイムでの弾性変形および位相変化に応じて変形すること
が可能である。しかし、複雑な変形を実現するために質点やバネの本数が増加し
た場合には、変形挙動が遅く感じられる問題がある。更には、陽的オイラー積分を
用いて数値積分を行った場合、強健性に欠けてしまう。また、FastLSM では物理
的なシミュレーションを行わずに高速な弾性体の断裂表現を実現しているが、有
限要素法的な手法による断裂表現を行っているため、ポリゴンモデルを直接操作
するものではない。
表 2.1 は既存研究における弾性体シミュレーションの特徴をまとめた表である。
表 2.1: 既存弾性体シミュレーションの特徴
物理的
実行速度 安定性 位相変化 容易さ
正確性
陽的方法
(バネモデル)
陰的方法
(FEM)
粒子法
シェイプ
マッチング法
FastLSM
ポリゴン
モデル
◦
×
◦
◦
◦
◦
×
◦
◦
×
◦
×
×
◦
◦
×
◦
×
◦
◦
×
◦
×
◦
◦
◦
◦
◦
×
×
13
本研究で手法を考案する上で重要なことは、リアルタイムシミュレーションが
可能であり、かつ強健性を失わないことである。そこで本研究では、実物体の持
つ物理的特性を擬似的に表現し、実世界に存在する弾性体らしい挙動表現をする
ことが可能な、計算量の少ない幾何学的なモデル表現に主眼を置く。また、位相
変化表現については、物体の位相構造を直接扱えるようなデータ構造を持たせる
ことで、ポリゴンモデルの位相に対して直接操作が可能な弾性体のモデル化を行
い、提案手法の妥当性を検証する。
14
第3章
提案手法
本章では、本研究で提案する位相変化を考慮した弾性体の挙動表現手法につい
て述べる。3.1 節では弾性体挙動のシミュレーション手法について、3.2 節では位相
変化を伴う変形手法について、3.3 節に提案手法全体の計算手順について述べる。
3.1
幾何学的手法による弾性体挙動
本手法では弾性体モデルをインタラクティブなアプリケーションで使用すると
いう側面から、幾何学ベースモデルとして構築していく。
質点バネモデルでは、加速度および速度を微少時間によって離散化し、値積分
を行うことで物体の位置を求める。コンピュータシミュレーションにおける数値
積分には、陰的解法と陽的解法による方法があり、陰的解法では、時間ステップ
に依存しない安定性を保証するが、離散化した式の解が必要となる為計算コスト
的に高価になる。これはリアルタイム性の妨げとなる。一方で陽的解法では、代
入操作だけで計算が可能な為、計算コスト的に安価である。しかしながら、数値
安定性に問題が出ててくる。線形でダンピングしない質点バネモデルに対し、陽
的積分を行った場合がその顕著な例である [19]。
図 3.1 および図 3.2 は、自然長 l0 でバネ定数 k の線形バネである。片方のバネの
質点 A は原点に固定されている。もう片方の質点 B は質量 m で、x(t) にある。こ
のとき、図 3.1 のように質点 B は f の力で平衡状態 l0 に引っ張られる。図 3.2 は、
そのときの移動距離を表している。
図 3.1: 陽的積分による線形バネに働く力
16
図 3.2: 陽的積分による線形バネの移動距離
このとき、質点 B の位置 x(t+∆t) は、陽的オイラー法により算出した速度 v(t+∆t)
を用いて、式 (3.1) にあるように陰的オイラー積分する。
{
v(t + ∆t) = v(t) + ∆t − k(x(t) − l0 )/m
x(t + ∆t) = x(t) + ∆tv(t + ∆t)
(3.1)
連立方程式 (3.1) より、式 (3.2) のように行列方程式として書くことができる。
[
]
v(t + ∆t)
x(t + ∆t)
[
=
1
−k∆t/m
∆t 1 − ∆t2 k/m
][
]
v(t)
x(t)
(3.2)
式 (3.2) から、
[
A=
1
−k∆t/m
∆t 1 − ∆t2 k/m
]
(3.3)
とおくと、式 (3.3) から、式 (3.4,3.5) に示すような固有値を得る。
e0 = 1 −
√
1
(∆t2 k − −4m∆t2 k + ∆t4 k 2 ) 2m
(3.4)
e1 = 1 −
√
1
(∆t2 k + −4m∆t2 k + ∆t4 k 2 ) 2m
(3.5)
17
式 (3.2) は各行が１つの離散式を表しているので、行列 A も離散的な式である。数
値安定性を保証するには、行列 A のスペクトル半径が 1 よりも小さいことが必要
である。すなわち、固有値 e0 , e1 は１より大きくあってはならなず、固有値 e0 の大
√
きさは ∆t2 k → ∞ のとき |e0 | < 1 で 1 に収束し、固有値 e1 の大きさは ∆t が 2 m
k
より小さい場合のみ 1 より小さくなる。もし ∆t を大きく取りすぎてしまうと、行
列 A は不安定になってしまう。
0)
線形バネの場合、質点 B を ∆x = ∆t2 k(x(t)−l
だけ動かしたとき、微小時間分
m
∆t, バネ定数 k が大きすぎるか、或いは質量 m が小さすぎると、質点 B は平衡位
置 l0 を大きく超過してしまう。また、バネの復元力が変形毎に大きくなるため、バ
ネの変形が減衰振動をしなくなる。復元力は常に質点を平衡状態に進めるが、陽
的積分では盲目的に変位を計算するため、このような問題が起こる。
本研究では Müller らの手法 [12] を用いることで、安定で高速な弾性体挙動表現
を実現する。以下、3.1.1 節 ∼3.1.3 節でその手法について述べる。 3.1.1
シェイプマッチング法
シェイプマッチング法を用いた形状変形の概要を図 3.3 に示す。まず、元の形状
の質点群 x0i と変形後の形状の質点群 xi から、最小の変化量となる回転行列 R と
平行移動ベクトル t を求め、その位置座標を gi とする。次に、変形後の質点 xi を
最小の変形位置座標 gi に引っぱる。このとき、引き付ける速度と位置を、求めた
位置座標 gi から連立式を立て、オイラー積分を行うことにより、物理法則を考慮
に入れた弾性変形を行うことができる。
18
図 3.3: シェイプマッチング法を用いた形状変形
シェイプマッチング法では、2 つの点群が与えられた場合、ある点群からもう一方
の点群間における最小の変化量を、最小自乗法を使用して求める。式 (3.6) では、
初期形状の点群を x0i 、変形後の形状の点群を xi としたとき、回転行列 R と移動
ベクトル t を最小にする t0 を算出する。
∑
mi (R(x0i − t0 ) + t − xi )2
(3.6)
i
ここで、mi は質点の質量である。2 点群間における最少の移動ベクトルは、式 (3.8)
にあるように、初期形状点群 x0i の重心と変形後点群 xi の重心から求める。
∑
mi x0i
0
t0 = xcm = ∑i
(3.7)
i mi
∑
mi xi
t = xcm = ∑i
(3.8)
i mi
最小の回転行列 R は質点と重心の相対位置である式 (3.9,3.10) を定義し、式 (3.11)
を最小にする行列 A より求める。
qi = x0i − x0cm
(3.9)
pi = xi − xcm
(3.10)
∑
mi (Aqi − pi )2
i
19
(3.11)
式 (3.11) の導関数が 0 となるような A は式 (3.12) となる。
A=(
∑
i
∑
qi qTi )−1 = Apq Aqq
mi pi qTi )(
(3.12)
i
式 (3.12) の第 2 項 Aqq は、ベクトルの内積定義より対称行列である。対称行列は
幾何学的に見ると直行するベクトル方向に拡大・縮小させる変換行列である。し
たがって、回転変換を含まない平行移動のみの変換行列である。これにより、式
(3.12) の第 1 項 Apq における回転成分が最小の回転行列 R となる。Apq は実正則
行列であるから、ATpq Apq は正値対称行列である。このとき ATpq Apq = U2 となる
正値対称行列 U が存在する。ここで、R = AU−1 とおくと、R は直行行列である
から、Apq は直行行列と正値対称行列を用いて式 (3.13) と一意的に表せる。これ
を極分解と呼ぶ。
Apq = RU
(3.13)
したがって、回転行列 R は式 (3.14) により得られる。
R = Apq U−1
√
また、U =
(3.14)
ATpq Apq であるから、計算するためには固有値と固有ベクトルを求
めて対角化を行う必要があり、Jacobi 法を用いることで計算可能である。以上に
より、最適な位置座標は式 (3.8,3.14) から、式 (3.15) によって得られる。
gi = R(x0i − x0cm ) + xcm
3.1.2
(3.15)
数値積分
質点バネモデルを考えた場合、平衡状態からの変位は、物体を平衡状態に戻す
ために加速する力を引き起こす。物体の位置を計算するために、加速度と速度は
微小時間毎に数値的に積分する。用いられる数値積分には、陰的積分と陽的積分
があり、陰的積分は選んだタイムステップに依存しない安定性を保証する。しか
しながら、計算的に高価でインタラクティブアプリケーションの妨げとなる可能
20
性がある。対照的に、陽的積分は計算が高速であるが、安定性を保証するには制
約条件が必要になる。顕著な例は陽的オイラー積分であり、これは線形でダンピ
ングしない質点バネモデルに適用されると無条件に不安定である。また、線形で
ダンピングされない質点バネモデルでの弾性力は、弾性エネルギーの反対方向に
生じる。したがって、弾性力は常に平衡状態に進めるが、陽的積分では盲目的に質
点の変位を計算することになる。つまり、質点バネモデルに陽的積分を用いると、
安定性のために要求される変形量や系のエネルギー維持や減少の変わりに、それ
らが増えることで変位は平衡状態から大きく超過してしまう現象が起きる。この
問題を解決する方法は、質点が平衡状態を飛びすぎないように変位を決定するこ
とである。そこで、シェイプマッチング法では、式 (3.15) より得られた gi を用い
て、式 (3.16,3.17) のようにオイラー積分式を構築する。ここで、α は弾性力を表
すパラメータである。
fext(t)
gi (t) − xi (t)
+ ∆t
∆t
mi
(3.16)
xi (t + ∆t) = xi (t) + ∆tvi (t + ∆t) (3.17)
vi (t + ∆t) = vi (t) + α
式 (3.16,3.17) は、行列方程式 (3.18) のように書くことができる。
[
]
v(t + ∆t)
x(t + ∆t)
[
=
α
1 − ∆t
∆t 1 − α
][
]
v(t)
x(t)
式 (3.18) の最初の項における固有値は 1 − α2 ) ± i
√
[
+
4α−α2
2
gi
α ∆t
αgi
]
(3.18)
であり、スペクトル半径
は、パラメータ α および微小時間分 ∆t に依存せず、独立して１である。すなわち、
式 (3.16, 3.17) による数値積分は無条件で安定であり、ダンピングを引き起こさな
いことを意味する。また、外力がない場合にも安定である。
シェイプマッチング法による方法は、支配方程式を解くような物理的に動機づ
けられた方法ではない。しかしながら、前計算を必要とせず、データ構造に依存し
ないため、リアルタイムでの弾性変形シミュレーションが可能である。また、計
21
算に必要なのは形状を構成する頂点の位置情報のみである。つまり、位相的な繋
がりのある質点群を 1 つのクラスタとして解釈することが可能であり、各クラス
タごとにシェイプマッチング法を適用することできる。各クラスタはそれぞれ別
の質点群から成り立っているので、独立した形状変形が行える。そこで、本手法
では後述する位相変化操作に対応するために、形状を構成する同位相の頂点群を
1 つクラスタとしてグループ化する。 3.1.3
変形アルゴリズム
本節では、シェイプマッチング法を拡張した、剪断変形、伸縮変形、およびひ
ねり変形アルゴリズムについて述べる。
前述のシェイプマッチング法では、剛体に近い変形しかできない。そこで、式
(3.12) によって計算された行列 A を用いて、形状変形中に変形変換を施す。行列
A は最小自乗法を用いて、初期の形状から変形後の形状にもっとも近づくような
線形変形を行う行列である。式 (3.15) において、回転行列 R を用いる代わりに式
(3.19) を使用する。
βA + (1 − β)R
(3.19)
式 (3.19) 中の β は、線形変形の度合を調整するパラメータである。これにより、剪
断変形および伸縮変形が表現できる。
∑
式 (3.9) を用いて q̃ = [qx , qy , qz , qx2 , qy2 , qz2 , qx qy , qy qz , qz qx ]T ∈ R9 とおき、 i mi (Ãq̃i −
p̃i )2 を最小化する行列 Ã を式 (3.20) によって求める。
à = (
∑
∑
q̃i q̃Ti )−1 = Ãpq Ãqq
mi pi q̃Ti )(
i
i
このとき Ãqq ∈ R
9×9
(3.20)
の行列、Ãpq ∈ R
3×9
の行列である。したがって、剪断変形、
伸縮変形、およびひねり変形を考慮した最適な移動位置 gi は式 (3.21) となる。こ
こで、R̃ は式 (3.14) によって算出された回転行列 R を用いて、R̃ = [R 0 0] ∈ R3×9
である。
gi = β Ã + (1 − β)R̃
22
(3.21)
3.2
提案モデルの位相変化手法
位相変化が可能な弾性体モデルでは、形状操作により変化していく 3 次元モデ
ルの状態を正確に把握する必要がある。
コンピュータグラフィクスおけるポリゴンモデルでは、一般的に Index Face Set(以
下、IFS) と呼ばれるデータ構造を用いる。IFS は、頂点座標データの集合と、頂
点番号による多角形データの集合の配列によりデータ構造を構成する。IFS は、メ
モリ効率に優れ高速な処理が行えるが、形状の状態を取得したり、位相変化を伴
うような変形には不向きである。
本研究では、3 次元形状データ構造として、Half-Edge 構造 [20][21] のモデルを
用いる。Half-Edge 構造は Weiler,Mäntylä が提案した、データ分析、形状変形に適
したソリッドモデル用データ構造であり、
「頂点（Vertex）」
「稜線（Edge）」
「半稜
線（Half-Edge）」「ループ（Loop）」の 4 種類の位相要素の集合によって形状を定
義する。IFS よりも多くの位相用データを保持するため、メモリ効率が悪い。しか
しながら、Half-Edge 構造の各要素が保持するデータ構造から弾性体モデルの形状
状態を把握し、位相変化を伴う変形が可能である。
Half-Edge 構造の特徴は、任意位相要素に対する高速な検索が可能であるため、
位相変化を伴う変形を高速に行えることである。IFS により構築したモデルでは、
任意位相要素を取得するためには、モデルを構成する全位相要素に対して検索を
行わなければならない。これは、位相変化を伴う変形においては、処理速度的な
ボトルネックとなる。
3.2.1
動的なクラスタ化による位相状態管理
本研究で用いる弾性体モデルは、Half-Edge 構造により構成されたポリゴンモデ
ルを用いて位相情報を管理している。3.1 節で示した幾何的な変形アルゴリズムで
は、すべての質点において互いに独立した計算を行うことができる。すなわち、変
形過程において位相変化が起こった場合でも、各質点同士の繋がりを考慮する必
23
要なく積分計算を行うことが可能である。弾性体の挙動表現手法で用いた変形ア
ルゴリズムにおいて、各質点の速度および位置座標を算出するのに必要なのは点
群の位置情報である。本手法では、同位相の質点群を 1 つのクラスタとして管理
し、位相変化によって質点同士の接続に変更があった場合、再度クラスタ化を行
うことで位相変化に伴う断裂変形を実現する。そのために、本提案モデルでは各
頂点に対して Half-Edge 構造がもつデータに加え、どのクラスタに属しているか
を管理するため、クラスタ固有の ID を付加する。また、提案モデルはすべて 3 角
形ポリゴンにより構成する。これは、モデルの位相状態の把握を管理し易くする
ためである。
3.2.2
位相変化手順
提案モデルにおいて、位相変化が生じた場合は上記に示したルールに従って変
形操作を行う。位相変化が起こる条件として、各稜線が初期の状態から一定距離
伸びた場合に行うものとする。提案する位相変形操作の大まかな流れは以下の通
りである。
1. 位相変化が起こる部分の位相要素を抽出する。
2. 抽出した位相要素を用いて、変形後の形状を再構成する。
3. 再構成した形状ごとにクラスタ分けを行い、各頂点に属するクラスタの ID
を付ける。
4. 再構成した形状ごとにシェイプマッチングを行う。
3.2.3
位相変化操作の概要
本位相変形操作の概要を述べる。本手法は弾性体モデルを構成する 3 角形メッ
シュに対して操作を行う。はじめに、位相変化が起こる前の形状では、同位相の
状態にある全ての頂点は 1 つのクラスタに属している (図 3.4(a))。次に、位相変化
24
が起こる位相要素の検出を行い、その位相要素を抽出する (図 3.4(b))。さらに、抽
出した位相要素から、位相変形後の形状となる位相要素の再構築を行う。このと
き、Half-Edge 構造が持つ機能を用いて、各位相要素の消去および生成を行う (図
3.4(c))。最後に、位相変化操作によって分離したそれぞれの形状ごとに、頂点に
対してクラスタ番号を付加する (図 3.4(d))。
図 3.4: 本位相変化操作の概要
また、位相変化操作によって分離した形状では、分離面に対して面を張る必要
がある。これには、位相変化操作によって生成した頂点の重心となる頂点を新た
に生成し、これらの頂点を用いて 3 角形メッシュを生成する。
25
3.3
計算手順
本提案手法の全体の計算手順を図 3.5 に示す。
図 3.5: 計算のながれ
まず、形状に対して位相変化が起こっているかどうかを検出する。位相変化が
起こる場合には、3.3 節で述べた手法により、形状の位相状態を更新し、位相変化
が起きた頂点のクラスタ分割を行う。次に、3.1 節で述べた手法を用いて、頂点の
適切な変位をシェイプマッチング法により求め、頂点の移動速度および位置座標
26
を更新する。以上の手順で 1 タイムステップの計算が終了する。
27
第4章
評価と検証
本章では、本研究で提案した弾性体モデルに沿って実装したプログラムを使用
し、その有用性を検証する。本研究で試作したプログラムは、グラフィクス API の
OpenGL[22] をベースとした 3 次元グラフィックスツールキットである「FK Kernel
Tool Kit System」[23][24] を用いて実装した。
4.1
実行結果
本提案モデルの実行結果を以下に示す。
実装した位相変化が可能な弾性体モデルのプログラムでは、位相変化が起こる
条件として、外力が加わった頂点に対して接続関係にある稜線が、変形前の状態
の長さから 3 倍の長さになったときに位相変化が起こるものとした。
4.1.1
提案モデルによる弾性体挙動
本提案モデルを用いた弾性体挙動表現の結果を示す。
29
図 4.1: ブロックモデルでの弾性体挙動表現
図 4.1 はシェイプマッチング法による弾性体の挙動を示したものである。加わっ
た外力に応じて変形し、外力がなくなれば元の状態に戻る様子が確認できた。
30
図 4.2: スフィアモデルでの弾性体挙動表現
図 4.3: キャラクターモデルでの弾性体挙動表現
31
図 4.4: スタンフォード・バニーモデルでの弾性体挙動表現
図 4.2、図 4.3、図 4.4 は、それぞれスフィアモデルとキャラクターモデルおよび、
スタンフォード・バニーモデルでの弾性体挙動を示した図である。いずれも図 4.1
と同様に弾性変形の様子が確認できた。
4.1.2
提案モデルによる位相変化
本手法の提案モデルによる位相変化は、形状が同位相のものならどのような形状
にでも適用できる。以下に複数のモデルにおいての動作検証を行った様子を示す。
32
図 4.5: ブロックモデルでの位相変化
図 4.5 はブロックモデルでの位相変化を行った画像である。図 4.5(a) は位相変化
前の形状、図 4.5(b) は位相変化が起こる途中の形状、図 4.5(c) は位相変化後の形
状である。
図 4.6: スフィアモデルでの位相変化
図 4.6 はスフィアモデルでの位相変化を行った画像である。図 4.6(a) は位相変化
前の形状、図 4.5(b) は位相変化が起こる途中の形状、図 4.6(c) は位相変化後の形
状である。
33
図 4.7: キャラクターモデルでの位相変化
図 4.7 はキャラクターモデルでの位相変化を行った画像である。図 4.7(a) は位相
変化前の形状、図 4.5(b) は位相変化が起こる途中の形状、図 4.7(c) は位相変化後
の形状である。
図 4.8: スタンフォード・バニーモデルでの位相変化
図 4.7 はスタンフォード・バニーモデルでの位相変化を行った画像である。図
4.8(a) は位相変化前の形状、図 4.8(b) は位相変化が起こる途中の形状、図 4.8(c) は
位相変化後の形状である。
図 4.5、図 4.6、図 4.7、図 4.8 において、それぞれ形状のことなるモデルでも、
弾性変形過程で位相変化を伴う様子が確認できた。
34
4.2
実行速度検証
本手法で提案した弾性体モデルを実装したプログラムの処理速度を検証した。
処理速度の測定に用いた PC の構成は CPU ：Core2Duo E8400、ビデオカード：
GeForce9600 GT、RAM：3GB である。提案モデルでは、処理速度はモデルの形
状を構成する頂点数に依存するため、頂点数のことなるブロックモデルを複数用
意し、クラスタ分割を行わない場合と、50 回のクラスタ分割を行った場合での処
理速度の検証を行った。処理速度の単位は FPS(Frame Per Second) であり、1 秒
間に可能なタイムステップの回数を表す。表 4.1 にその結果を示す。
頂点数
表 4.1: 提案モデル 処理速度の測定
クラスタ分割無し クラスタ分割数 50
602
1352
2402
3752
140 FPS
65 FPS
40 FPS
20 FPS
92
42
23
12
FPS
FPS
FPS
FPS
表 4.1 より、頂点数が 2 倍になるクラスタ分割無しとクラスタ分割数 50 ともに
処理速度が半減することがわかった。しかしながら、位相変化が起こる瞬間の形
状の再構成には、ほとんど速度の低下は見られないため、処理速度はほぼ頂点数
に依存していると言える。従って、本提案モデルではリアルタイム性を実現でき、
リアルタイムでの実用性を有すると考える。
4.3
現状の問題点
現状の問題点として、第１に外力が加わった頂点に接続する全ての稜線が位相
変化が起こる条件を満たしたときのみ、位相変化を伴う変形を行っているため、亀
裂を伴うようなクラック表現ができないという問題が挙げられる。この問題は、亀
裂が起こる箇所に対して、位相要素を上手く構築するアルゴリズムを考案するこ
とで対処可能であると考える。
35
第 2 に頂点数に応じて処理速度が低下してしまうという問題がある。これはシェ
イプマッチング法による処理が、ボトルネックになっている部分が大きい。この
問題は、シェイプマッチング法による処理を GPU により並列計算することで、高
速な処理速度の実現が可能であると考える。
36
第5章
おわりに
本研究では、位相変化を考慮した弾性体の挙動表現をリアルタイムで実現する
手法の研究に取り組んだ。その結果として、従来の手法ではできなかったメッシュ
構造で表現された弾性体物体に対して、リアルタイムでの位相変化を実現できた。
本手法で提案したモデルを用いることで、インタラクティブゲームやアニメーショ
ンなどのインタラクティブコンテンツで弾性体を用いる際、弾性体を用いた表現
の幅を広げるという目的において、大いに役立つだろう。
今後の展望として、5.3 節で挙げた亀裂を伴う位相変化表現の実装や、弾性体同
士の融合表現を実現する手法の考案が挙げられる。また、処理の高速化のための
GPU による並列処理の実装では、NVIDIA が提供する GPU 向けの統合開発環境
である CUDA を用いることで、高速化を実現できるだろう。
38
謝辞
本研究を締めくくるにあたり、学部時代から引き続きまして終始温かいご指導
ならびに適切な助言を下さいました、本校メディア学部 渡辺大地講師に心からの
感謝の意を表します。また、副査を引き受けて下さいました、近藤邦雄教授、三
上浩司講師に深く感謝致します。
最後に、共に歩んできた院生の諸氏に感謝の意を致します。
40
参考文献
[1] 恒藤敏彦, 「弾性体と流体」, 岩波書店, 1982.
[2] O. Zienkiewicz, J. Zhu, “Adaptivity and Mesh Generation”, International
Joumal for Numerical Method in Engineering, 34, pp.783-810, 1991.
[3] 三好俊郎, 「有限要素法入門」, 培風館, 1994.
[4] 広田光一, 金子豊久, “柔らかい仮想物体の力覚表現”, 情報処理学会論文誌,
Vol.39, No.12, pp.3261-3268, 1998.
[5] S. Cotin, H. Dlingette and N. Ayache, “Real-Time Elastic Deformations of
Soft Tissues for Surgery Simulation”, IEEE Trans, Visualization and Computer Graphics, Vol. 5, No. 1, pp.62-72, 1999.
[6] 河合裕文, 松宮雅俊, 佐藤哲, 山澤一誠, 竹村治雄, 横矢直和, “弾性体のバネ
モデルの疎密表現による計算量削減手法”, 日本 VR 学会第 5 回大会論文集,
pp.229-232, 2000.
[7] S. Koshizuka, H. Tamako, and Y. Oka, “A particle method for incompressible
viscous flow with fluid fragmentation”, Comput. Fluid Dynamics J., Vol. 4,
pp. 29-46, 1995.
[8] L.B. Lucy, “Numeriacal approach to testing the fission hypothesis”, Astronomical Journal, Vol. 82, pp. 1013-1024, 1977.
[9] 越塚誠一, 「粒子法シミュレーション」, 倍風館, 2008.
[10] 広田光一, 金子豊久, “仮想物体の弾性モデルに関する検討”, 計測自動車制御
学会論文誌, Vol.34, No.8, pp.232-238, 1998.
[11] S. Miyazaki, J. Ueno, T. Yasuda, S. Yokoi and J. Toriwaki, “A Study of
Virtual Manipulation of Elastic Objects with Destruction”, Proc. IEEE Int.
Workshop on Robot and Human Communication, pp.26-31, 1995.
42
[12] M. Müller, B. Heidelberger, M. Teschner, and M. Gross, “Meshless deformations based on shape matching”, ACM Trans. on Graphics 24, 3 (Aug.),
471-478, 2005.
[13] J. F. O’Brien and J. K. Hodgins, “Graphical Modeling and Animation of
Brittle Fracture”, Proc. ACM SIGGRAPH ’99, pp.137-146, 1999.
[14] T.Belytschko, Y.Y.LU, and L. Gu, “Element-free Galerkin methods”, Int.
J.Numer. Meth. Engng., Vol. 37, pp. 3-47, 1996.
[15] A. Norton, G. Turk, B. Bacon, J. Gert and P. Sweeney, “Animation of Fracture by Physical Modeling”, Visual Computer, Vol.7, pp.210-219, 1991.
[16] M. Holton and S. Alexander, “Soft Cellular Modeling: A Technique for Simulation of Non-rigid Materials”, R. Earnshaw and J. Vince(Eds.), Computer
Graphics: Developmentes in Virtual Environments, Academin Press, pp.449460, 1995.
[17] A.R. Rivers, D.L. James, “FastLSM:fast lattice shape matching for robust
real-time deformation”, ACM Trans. on Graphics 26, 3(July), 2007.
[18] M. Müller, M. Tescohner, and M. Gross, “Physically based simulation of
objects represented by surface meshes”, In Proc. of Computer Graphics International (CGI), 26-33, 2004.
[19] Eberly, D.H, 「Game Physics」, Morgan Kaufmann, 2003.
[20] WEILER, K.J., “ Edge-based data structures for solid modeling in curvedsurfaceenvironments ”, IEEE Computer Graphics and Applications， 1985.
[21] MÄNTYLÄ, M., “An Introduction to Solid Modeling ”, Computer Science
Press, MaryLand, 1988.
43
[22] OpenGL.org, OpenGL, <http://www.opengl.org/>.
[23] 渡辺大地, “リアルタイムグラフィックスのためのツールキットに関する研究”,
慶應義塾大学大学院政策・メディア研究科修士論文, 1996.
[24] 渡辺大地, FK Tool Kit System, <http://www.media.teu.ac.jp/~earth/FK/>.
[25] M. Wicke, P. Hatt, M. Pauly and M. Müller, and M. Gross, “Versatiole virtual
materials using implicit connectivity”, Eurographics Symposium on PointBased Graphics, 2006.
発表論文
海上一徳, 渡辺大地, “リアルタイム 3DCG プログラミングにおける、位相変化を
考慮した弾性体の挙動表現に関する研究”, 情報処理学会 第 71 回全国大会, 2008.
44