タブレットインターフェイスを用いたラティス構造のモデリング

タブレットインターフェイスを用いた
ラティス構造のモデリング
Modeling Lattice
with Tablet Interface
2002 年 1 月 15 日
武部
佳文
Yoshifumi Takebe
慶應義塾大学大学院 政策・メディア研究科
Graduate School of Media and Governance
KEIO UNIVERSITY
修士論文要旨
2001
年度 (平成 13 年度)
タブレットインターフェイスを用いた
ラティス構造のモデリング
現在、Web3D と呼ばれる、インターネット上で 3 次元コンピュータグラフィ
クスを表示する技術が注目されている。Web3D を用いることにより、ブラウザ上で
3 次元形状を自由な視点で閲覧することが可能である。Web3D は娯楽のみならず、
Web 上での商取引、教材用コンテンツなどにも利用されている。
3 次元 CG を表現するために、通常 3 角形ポリゴンメッシュが使われる。3 角形
ポリゴンメッシュはデータが単純であるために扱いやすく、レンダリングも高速に
行うことが可能である。しかし、精密な 3 次元形状を表現する場合、多数の 3 角形
ポリゴンが必要となるためデータサイズが大きくなるという欠点がある。そのため、
Web3D で利用する際には多重解像度表現やラティス構造などの自由曲面表現へ変換
するのが一般的である。これらの変換手法の多くは自動的にパラメータ化を行うた
め、ユーザの意図した位相を生成することが困難である。そのため、アニメーショ
ンやテクスチャマッピングのように、領域間の輪郭線が操作に大きく関係する処理
においては、これらのモデルを直接利用することができないのが現状である。
そこで、本論文ではタブレットインターフェイスを用いたラティス構造のモデリ
ング手法を提案する。本手法ではタブレットインターフェイスを用いて 3 角形ポリ
ゴンメッシュに特徴を入力し、その結果を反映したラティス構造をモデリングする。
これにより、ユーザは目的に応じたパッチネットワークと制御格子の構築が可能に
なる。本研究では以上の操作を計算機上に実装し、その有効性を検討した。
キーワード
1. タブレットインターフェイス 2. 特徴入力
3. Web3D
4. 自由曲面
5. ラティス構造
慶應義塾大学 大学院 政策・メディア研究科
武部 佳文
Abstract of Master's Thesis
Academic Year 2001
Modeling Lattice
with Tablet Interface
Now, the technology which is called Web3D and which displays 3-dimensional computer graphics on the Internet attracts attention. By using Web3D, it is possible to
peruse 3-dimensional model with a free viewpoint on a browser. Web3D is used not only
for amusement but for the commercial transaction on Web, the contents for teaching
materials, etc.
In order to express 3-dimensional CG, triangle polygon mesh is usually used. It is possible to be easy to treat since triangle polygon mesh has simple data, and to also perform
a rendering at high speed. However, when expressing precise 3-dimensional model, since
many triangle polygons are needed, there is a fault that data size becomes large. Therefore, in case it uses by Web3D, it is common to change into multi-resolution representation
or free form surface of lattice structure etc. Since many of these conversion techniques to
perform parameterization automatically, it is dicult to generate the topology which the
user meant. Therefore, the outline between domains cannot use these models directly in
processing important for operation.
This paper presents method of Modeling Lattice with tablet interface. By this technique, the feature is inputted into triangle polygon mesh with tablet interface. And the
modeling of the lattice reecting the result is carried out. Thereby, users can build the
patch network and control lattice according to the purpose. We implement this operation
on computer and discuss its availability.
Key Words
1. Tablet Interface 2. Input Character
3. Web3D
4. Free Form Surface
5. Lattice Structure
Keio University Graduate School of Media and Governance
Yoshifumi Takebe
目次
1.
2.
はじめに
1
1.1 Web3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2 3 次元形状の自由曲面化と問題点 . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3 タブレットインターフェイスを用いたラティス構造のモデリング . . . . . . .
3
1.4 論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
関連研究
5
2.1 ラティス構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.1.1
輪郭線 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.1.2
双 3 次 Gregory パッチの内挿 . . . . . . . . . . . . . . . . . . . . . .
8
2.2 3 角形ポリゴンメッシュのラティス化 . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1
稜線除去 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2
QEM に基づくモデルの簡略化 . . . . . . . . . . . . . . . . . . . . . . 10
2.2.3
QEM に基づく曲面フィッティング手法 . . . . . . . . . . . . . . . . . 11
2.3 曲面上の局所変形 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.
特徴入力とラティス構造の生成手法
15
3.1 特徴線決定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.1
取得した面に属する稜線列 . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.2
入力線列の近傍の稜線列 . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.3
近傍の稜線列を利用した特徴線決定 . . . . . . . . . . . . . . . . . . . 18
3.1.4
特徴領域を元に面分割して生成された稜線列 . . . . . . . . . . . . . . 20
3.2 特徴線によるモデルの切断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 ラティス化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.
3.3.1
特徴線の指定による重み付き QEM . . . . . . . . . . . . . . . . . . . 25
3.3.2
4 角形化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.3
特徴線を保存した 4 角形化 . . . . . . . . . . . . . . . . . . . . . . . . 30
評価と考察
31
4.1 編集を考慮したラティス化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 医用モデルのラティス化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.1
頭部モデルのラティス化 . . . . . . . . . . . . . . . . . . . . . . . . . 34
i
4.2.2
5.
下顎骨モデルのラティス化と切断 . . . . . . . . . . . . . . . . . . . . 37
結論と今後の展望
42
5.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2 今後の展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
ii
図目次
2.1 Doo と Sabin の細分割操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
7
P
0 の求め方の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 輪郭線の制御線の求め方の例 . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4 双 3 次 Gregory パッチの内挿 . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5 稜線除去 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 頂点 V 近傍の参照点の抽出 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.7 オリジナルモデル (上) と生成された曲面モデル (下) . . . . . . . . . . . . . . 13
2.8 局所的に変形した曲面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1 稜線列の移動 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 稜線列の移動 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 接続されていない頂点同士の連結 . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 面分割よる特徴線生成と面分割 . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 面分割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.6 モデルの切断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.7 特徴線指定による重み付き QEM . . . . . . . . . . . . . . . . . . . . . . . . 26
3.8 3 角形面の内挿と 4 角形面の内挿 . . . . . . . . . . . . . . . . . . . . . . . . 27
3.9 3 角形同士のペアリング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.10 1 つの評価関数だけでは検知できない 3 角形のペア . . . . . . . . . . . . . . . 29
3.11 特徴線を保存した 4 角形化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 オリジナルモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 特徴線生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 ラティスの特徴線編集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4 CT データを元に生成した頭部モデル . . . . . . . . . . . . . . . . . . . . . . 35
4.5 特徴入力をせずにラティス化したモデル . . . . . . . . . . . . . . . . . . . . 35
4.6 特徴入力をしてラティス化したモデル (非 4 角形化) . . . . . . . . . . . . . . 36
4.7 特徴入力をしてラティス化したモデル (4 角形化) . . . . . . . . . . . . . . . . 36
4.8 下顎骨切断 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.9 オリジナルの下顎骨モデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.10 切断せずにラティス化した下顎骨モデル . . . . . . . . . . . . . . . . . . . . 38
4.11 ラティス化後に切断した下顎骨モデル (非四角形化) . . . . . . . . . . . . . . 39
4.12 ラティス化後に切断した下顎骨モデル (四角形化) . . . . . . . . . . . . . . . 39
iii
第 1章
はじめに
1.1
Web3D
1960 年代に登場した 3 次元コンピュータグラフィックス (3 次元 CG) を扱う技術は、ハー
ドウェア、ソフトウェアの急激な進歩とともに大きな発展を見せている。3 次元 CG は娯楽、
工業、医療、教育など様々な分野で活用されている。また、高速な PC が一般に普及し、ブ
ロードバンドの時代を目前とした現在、インターネット上で 3 次元 CG を扱う技術である
Web3D が注目されている。 1995 年に登場した VRML(Virtual Reality Modeling Language)
は、表示品質の低さ、膨大なデータサイズなどにより普及しなかった。しかし、近年のイン
タラクティブグラフィックスの技術革新により、形状表現やレンダリングの品質が格段に向
上した [39]。このような流れを受け、Web3D の標準化団体である Web3DConsortium[30] は
次世代の Web3D 標準言語として X3D(eXtensible 3D) の仕様決定を進めている。
Web3D は、人々の関心を集めるメディアとしての大きな可能性を持っており、多くの
企業がその技術の利用を検討している。既に Web3D 技術を用いた E コマースを行っている
企業もあり、自社製品を 3 次元 CG によって実写のように表現したり、あるいはインタラク
ティブに変化させるなど、積極的に広告活動に利用している。また、多くの研究者が Web3D
の技術開発を行っている [5][11][25][31]。既に高い完成度を持ち、実際に使われている技術
や、研究段階だが魅力あるアイディアで将来性を期待される技術など様々有り、今後どの技
術、規格が生き残っていくか注目されている。
医療分野でも Web3D 技術を用いたコンテンツが多く公開されるようになった。これま
でも Web 上での医療コンテンツは存在したが、膨大なデータを用いたコンテンツは公開が
困難であった。CT や MRI のデータから生成された人体の 3 次元モデル [10][22] は、精密
な形状を 3 角形ポリゴンメッシュによって表現するため、莫大なデータ量を必要としたこと
などが原因である。しかし、データの圧縮技術やブロードバンドの普及などにより、膨大な
データサイズの医療コンテンツの Web 上で利用可能になった。その結果、精密な人体の 3
次元モデルなども Web 上での公開が可能となり、医学の教育分野でも実測データを元に作
成された 3 次元モデルの利用が容易になった。また、医療コンテンツ作成のための研究も多
く発表されている [29][24][34][37]。
1.2
3 次元形状の自由曲面化と問題点
通常 3 次元 CG を表現するために、3 角形ポリゴンメッシュが使われる。3 角形ポリゴ
ンメッシュはデータが単純であるために扱いやすく、レンダリングも高速に行うことが可
能である。しかし、精密な 3 次元形状を表現する場合、多数の 3 角形ポリゴンが必要とな
るためデータサイズが大きくなるという欠点がある。3 角形ポリゴンメッシュ表現に基づ
2
く形状データを Web3D で利用する際は、データサイズを削減するために多重解像度表現
[2][6][14][19][21][23] や自由曲面表現 [1][3][13][36] へ変換するのが一般的である [7][26][37]。精
密な 3 次元形状を小さいデータサイズで表現するために、ラティス構造 [28][38] などの自由
曲面を用いる形式が提案されている。自由曲面は少ないパラメータで滑らかな曲面形状を表
現することが可能である。また、クライアント側のマシンのスペックに合わせて解像度を変
更することも容易である。ラティス構造では精度の粗いポリゴンモデルから滑らかな曲面形
状を表現することが可能である。そのため、小さいデータサイズで精度の高いモデルを表現
することが可能である。
3 角形ポリゴンで構成されたモデルをラティス構造に変換するための手法を林ら [37] が
提案している。林らは元の 3 角形ポリゴンメッシュを QEM[9] により簡略化する。その際、
定義される曲面形状を元のモデルに近似するために、最適な頂点座標を計算する。また、バ
ウンディングボックスを用いた領域指定により、局所的に精度を調整することも可能である。
しかし、簡略化後のモデルの面は全て 3 角形となるため、Gregory パッチを内挿する際に全
ての面を 4 角形に分割する必要がある。そのため余分な曲面化計算が必要になるという問題
がある。また、簡略化後の制御格子の形状の予想が困難なため、生成されるモデルに対する
形状編集に適さない。
また、領域指定の方法にも問題がある。林らは領域指定にバウンディングボックスを用
いるため、細かい領域指定が困難である。一方、Krishnamurthy ら [17] は 3 次元モデル上
に領域指定をして自由曲面に変換する手法を提案した。しかし、この手法では自由曲面の 1
つ 1 つをピックして形状を定義する必要があり、モデルを完成させるまでのユーザの負担が
大きくなる。
これらの理由により、モデルに対して容易に特徴を入力し、ユーザの期待する位相構造
を持つモデルを生成する技術が重要となる。また、特徴を入力した部位の精度を調整するこ
とにより、重要な特徴を保持しながら無駄なデータを削減する手法が重要となる。
1.3
タブレットインターフェイスを用いたラティス構造のモデリング
そこで本論文ではタブレットインターフェイスを用いて局所的に精度を調整したラティ
ス構造を生成する手法を提案する。
本手法の手順は以下の通りである。まず、タブレットインターフェイスを用いてモデル
上に特徴として高い精度を保ちたい部位を指定する。次に入力された情報を元に簡略化に
よって消失させたくない稜線を指定する。この稜線を本論文では特徴線と呼ぶ。次に林らの
手法を用い、3 角形ポリゴンモデルをラティス構造に変換する。本論文では、3 角形ポリゴ
3
ンメッシュからラティス構造への変換をラティス化と呼ぶ。この際、特徴線として指定され
た稜線に高い制約をかけてラティス化を行うことにより、ユーザの意図した特徴を保持した
ままラティス化が可能となる。最後に高い精度を必要としない 3 角形同士をペアリングして
4 角形面を生成する。
本手法により、ユーザが意図したラティス構造のモデリングが可能となる。これにより
ユーザは対話的に 3 角形ポリゴンメッシュに特徴を入力し、その特徴を損なわずに形状の簡
略化が可能となる。また、3 角形同士を結合して 4 角形にすることにより曲面化による計算
負荷が軽減される。本論文で提案する手法を計算機上に実装し、その有効性を確認した。
1.4
論文の構成
本論分の構成は以下のとおりである。第 2 章では本研究の元となる研究背景について述
べる。第 3 章ではタブレットインターフェイスを用いた特徴入力と、特徴に基づいたラティ
ス構造の生成手法について述べる。第 4 章では実行例を示しながら本手法を考察し評価す
る。最後に、第 5 章では結論と今後の展望について述べる。
4
第 2章
関連研究
本章では、本研究の主要な関連研究として、ラティス構造、3 角形ポリゴンメッシュの
ラティス化、曲面形状の局所変形の解説を行う。
2.1
ラティス構造
本節ではラティス構造による曲面形状の生成手法について解説する。
ラティス構造では、曲面形状はラティスと呼ばれる制御格子によって定義される。曲面
形状の表現には千代倉らが提案した Gregory パッチを用いる。ラティスに自由曲面を内挿す
るために、まず、全ての曲面の輪郭線を抽出する。次に隣り合う曲面同士が滑らかに接続す
るように Gregory パッチのパラメータを決定する。
以下にそれぞれの手順について詳細を述べる。
2.1.1
輪郭線
まず、Doo と Sabin[6] の手法により 3 次元形状の面を 1 回細分割する。図 2.1 に細分割
操作の例を示す。
図
2.1:
Doo と Sabin の細分割操作
6
次に生成された立体を元に自由曲面を生成するための輪郭線を 3 次の Bezier 曲線 [1] と
して抽出する。抽出される輪郭線は元の 3 次元形状の稜線と 1 対 1 の対応関係を持つ。元の
モデルの稜線の端点
P
に対応する輪郭線の端点
P
0=
X
は
P
Vi
は式 (2.1) の通りである。
(2.1)
M eshes
に接続する面を示す。Vi は
うち、P に最も近い頂点である。ki は
0
ki Vi
2
i
M eshes
P
P
に接続する、ある面上に生成された頂点の
の属する面の面積と M eshes の面積の総和との比
0 の求め方の例を示す。元のモデルの稜線の両端をそれぞれ P0 、 P3
とし、対応する輪郭線の両端をそれぞれ P 0 、 P 0 とする。 P0 を含み対象となる稜線を含
率を示す。図 2.2 に
P
0
3
む 2 つの面の中心点同士を結んだ稜線の中点を
の面の中心点同士を結んだ稜線の中点を
R
Q
、
P3
を含み対象となる稜線を含む 2 つ
とする。輪郭線となる自由曲線の制御点
は式 (2.2) の通りである。図 2.3 に輪郭線の制御線の求め方の例を示す。
図
2.2:
P 0 の求め方の例
7
0
0
P1 ; P2
P’1
P’2
Q
R
P’
P’0
図
2.3:
3
輪郭線の制御線の求め方の例
0 = 4Q 0 P 0; P 0 = 4R 0 P 0
0
2
3
P1
3
0
0
0
0
輪郭線を P0 ; P1 ; P2 ; P3 を制御点とする 3 次 B
ezier 曲線 [1] とする
2.1.2
3
(2.2)
双 3 次 Gregory パッチの内挿
次に、抽出された輪郭線を基礎パッチ法 [35] を用いて自由曲面を内挿する。自由曲面に
ezier 曲面、NURBS[13] など様々なものが研究されている。いずれの自由曲面も、少数
は B
の制御ベクトルにより広域的かつなめらかな形状を表現することができる。しかし、これら
の曲面は曲面間で G1 連続性を保つのが困難である。そこで、曲面間の連続性を容易に確保
するために双 3 次 Gregory パッチを用いる。Gregory パッチは輪郭曲線ごとに流れベクトル
関数 (Cross Boundary Derivertive) を定義できるので、曲面間の連続性を容易に保つことが
できる。双 3 次 Gregory パッチは図 2.4 に示すように、20 個の制御点 Pij k (i = 0; : : : ; 3;
0; : : : ; 3;
k
j
=
= 0; 1) により表現される。
双 3 次 Gregory パッチの曲面表現式は次のようになる。
(
S u; v
)=
XX
3
3
3
Bi
(u)B 3 (v )Q (u; v )
ij
j
(0 u 1; 0 v 1)
(2.3)
i=0 j =0
ここで Bi3 (u) と Bj3 (v) は Bernstein 基底関数である。また、制御点 Pij k (i = 0; : : : ; 3;
0; : : : ; 3;
k
= 0; 1) と Q (i = 0; : : : ; 3;
ij
j
= 0; : : : ; 3) には次のような関係がある。
8
j
=
P 130
P 230
P 030
P 020
P 220
P 120
P 121
P 330
P 221
P 111
P 010
P 320
P 211
P 110
P 210
P 100
P 310
P 200
P 000
P 300
図
i
2.4:
双 3 次 Gregory パッチの内挿
6= 1 2 または 6= 1 2 の時
;
j
;
(
Qij u; v
i
)=P
(2.4)
ij 0
= 1; 2 または j = 1; 2 の時
(
Q11 u; v
(
Q21 u; v
ただし 0
)=
)=
+ vP111
;
u+ v
uP110
(1 0 u)P210 + v P211
;
(1 0 u) + v
(
Q12 u; v
(
Q22 u; v
1 0 1 である。
u
;
v
9
)=
)=
+ (1 0 v )P121
;
u + (1 0 v )
uP120
(1 0 u)P220 + (1 0 v)P221
(1 0 u) + (1 0 v )
(2.5)
2.2
3 角形ポリゴンメッシュのラティス化
本節では、3 角形ポリゴンメッシュをラティス化する手法について解説する。この手法
は、林ら [37] の拡張した QEM(Quadric Error Metrics) に基づいた簡略化手法によって稜線
を除去する。QEM とは高密度な 3 角形ポリゴンメッシュと、稜線除去により簡略化した 3
角形ポリゴンメッシュとの形状の誤差に関するエネルギー最小問題を 2 次の評価関数を用い
て高速に解く手法である。QEM を用いることにより、形状の精度を保ちながらデータサイ
ズを小さくすることができる。
以下にそれぞれの手順について詳細を述べる。
稜線除去
2.2.1
一般にモデルの簡略化は稜線の除去の繰り返しを基本としている。図 2.5 に稜線除去の
例を示す。任意の稜線
動し、
稜線を
v2
v2
f
の除去する際、稜線の両端の頂点
v1 ; v2
に繋がっていた稜線と面を全て v1 に接続する。頂点
v1 ; v 2
、稜線
e
f
g 、頂点
g、f
v2 ; v3
v1 ; v 2 ; v 3
v2 ; v4
囲まれる面を
g 、面 f
v1 ; v 2 ; v 3
f
g、f
v1 ; v2 ; v3
e
e
v 1 ; v2 ; v4
v1
v2
v4
図
QEM
によって構成される
v3
v4
2.2.2
v1 ; v 2
g と表す。稜線 の除去で頂点
g は除去される。
v3
v1
を新しい頂点の位置に移
2.5:
稜線除去
に基づくモデルの簡略化
モデルの簡略化は稜線の除去の繰り返しを基本としている。最適なモデルの簡略化を行
うためには、除去しても全体への影響の少ない稜線を選んで稜線除去を行っていく必要が
ある。任意の稜線 e を除去した場合のモデルに与える影響をコストという。Garland ら [9]
は QEM と呼ばれる評価値を定め、稜線のコストを算出している。頂点 v の持つ QEM は式
(2.6) のように求められる。v が属する面を f (j = 1:::k)、面 f の面積を area(f )、面 f の法
j
10
線ベクトルを n と表す。
( )=
F v
X
k
( ) 1 (n
area fj
j =1
=v
A
は3
2 3 の対称行列、
b
T
Av
T
v
+ d)2
+ 2bv + c
(2.6)
T
は列ベクトル、c はスカラーである。これら 3 つの変数を構成
する 10 個の浮動小数点が頂点 v の QEM である。稜線 e に対し、稜線除去を行った後の頂
点 v 0 の最適な座標を求める。最適な頂点座標 v min は、e の両端点 v1 ,v2 のコストの和を最
小にする座標である。この v min を式 (2.6) に代入した F (v min ) が e のコストとなる。各頂
点のコストを計算し、コストの小さいものから順に稜線除去を実行する。稜線除去を実行し
た後は、除去される頂点の QEM は残る頂点の QEM に足し、v0 に隣接する頂点のコストを
随時更新する。
2.2.3
QEM
に基づく曲面フィッティング手法
竹内ら [26] は QEM に基づいた簡略化手法を拡張した。竹内らの手法では、簡略化後の
形状がサブディビジョンサーフィスの制御格子になる。制御格子の収束曲面はオリジナル
メッシュを高い精度で近似する。そのため、最適な頂点座標を求めるための評価関数を、オ
リジナルメッシュの頂点ではなく、オリジナルメッシュを細分割した後の頂点を評価するよ
うに定義する。また、金井 [32] による拡張では最適な頂点座標を求めるために、稜線にも
QEM を持たせて近傍の頂点も評価し、得られる形状の精度を高めている。
林らは竹内らの手法を拡張したものである。林らは、簡略化後の形状がラティスになる。
また、任意の領域に対する簡略化後の精度の調節が可能である。林らは、最適な頂点座標
を計算するための評価関数を、稜線除去後のメッシュに対して丸め操作を行った後の曲面上
の点を評価するように定義する。評価には、丸め操作後の頂点と曲面の輪郭線となる 3 次
Bezier 曲線の中点を用いる。ここで後の議論のために、稜線除去後に新しく生成される頂
点 V の近傍頂点と、丸め操作後の曲面上の頂点の ID 付けについて図 2.6 を用いて説明す
る。頂点 Vj (1:::k ) はオリジナルメッシュにおいて V に隣接する頂点である。頂点 vj (1:::k ),
pj
(1:::k ) はそれぞれ、元のメッシュに対して Doo と Sabin らの手法を用いて 1 回細分割し
た時の頂点 V ,
V0
に対応する頂点である。qj(1:::k) は
V
と
Vj
に接続する 3 次 Bezier 曲線の
中点である。V 0 , V00 はそれぞれ、V , V0 に対応する丸め操作後の曲線上の頂点である。t0 , t1
は V 0 ; V 0 に接続する 3 次 B
ezier 曲線の第 2、第 3 制御点である。
0
11
p0
q1
V1
p1
V2
p4
q0
v2
p2
V
p2
p3
v4
q3
p3
v3
v4
v2
p4
V0'
t1
t0
V'
V0
v0
v1
v0
v1
q2
p0
p1
q4
t0
t1
v3
V'
V3
q0
V0'
V4
図
2.6:
頂点 V 近傍の参照点の抽出
林らの手法で定義される評価関数は式 (2.7) のような形式で表現される。
( ) = F (V 0 ) +
F V
X
k
( )
F qj
(2.7)
j =1
式 2.7 の右辺の第 1 項は、頂点 V 付近の形状を評価したものであり、V の持つ QEM が
使用される。また第 2 項は
V
つ QEM が使用される。 V 0 ,
に隣接する稜線付近の形状を評価したものであり、稜線の持
qj
は以下の式 (2.8)、(2.9) のように表すことができるため、こ
れらを用いて式 (2.7) を展開し整理すると式 (2.10) のようにまとめることができる。
V
qj
=
0=
3
V
8
7
V
12
X
k
(2.8)
vj
j =1
+ 18 V 01 + 83 V + 18 V
( )=V
F V
5
+ 12
1
j
T
j +1
j
AV
+ 2bV + c
T
(2.9)
(2.10)
これは V に関数する 2 次関数となる。F (V ) を最小にする頂点の座標 V min は F (V ) = 0
を解くことで得られる。本手法では任意の領域に対する簡略化後の精度の調整が可能であ
る。これは簡略化開始時に、任意領域内の QEM に適当な制約をかけることで実現する。制
約の値を
U
とした時、任意の稜線 e の QEM の値
12
e
G
は式 (2.11) で表される。
G
e
+G
e
1
U
図 2.7 に林らの手法によって生成された曲面モデルとオリジナルモデルを示す。
図
2.7:
オリジナルモデル (上) と生成された曲面モデル (下)
13
(2.11)
2.3
曲面上の局所変形
本節では、曲面上に入力した線分を元に局所変形を行う手法について解説する。Kho-
dakovsky ら [16] は、Loop[21] の細分割曲面手法によって表現される曲面を、入力した線分
により再構築する手法を提案した。以下に手順について説明する。
まず、モデルの表面に線分を入力し、稜線との交点を求める。次に、入力した線分と求
めた交点により、２次のスプライン曲線を定義する。最後に、定義したスプライン曲線から
の距離や変形部位の形状を決定するパラメータをコントロールすることにより、局所的に曲
面形状を変形することが可能となる。図 2.8 に Khodakovsky らの手法によって局所的に変
形した曲面の例を示す。
この手法は曲面を自由曲線によって局所変形するため、変形部位が滑らかな形状を保つ
ことが可能である。しかし、線によって定義される形状以外の変形が困難である。また、変
形対象のモデルや生成されるモデルが 3 角形ポリゴンメッシュのみに限られる。
一方、本手法では面単位、稜線単位で特徴を指定できる。また、高い精度を必要としな
い 3 角形同士を結合して 4 角形化することにより、曲面を表示するために必要なポリゴン数
を削減する。その結果、計算負荷の軽減が可能となる。
図
2.8:
局所的に変形した曲面
14
第 3章
特徴入力とラティス構造の生成手法
本章では本手法によるラティス構造のモデリング手法について説明する。本手法では、
まずタブレットインターフェイスを用いて特徴領域を入力する。次に、入力された特徴を保
持しながら形状の簡略化を行う。簡略化の際に頂点位置を補正してラティスを生成する。最
後に高い精度を必要としない 3 角形同士をペアリングする。
以下にそれぞれの手順について詳細を述べる。
3.1
特徴線決定
本手法では、3 角形ポリゴンメッシュからラティスを生成する際に高い精度を保ちたい
部位の稜線を確保する。タブレットインターフェイスを用いて入力した点のウィンドウ座標
を 3 次元に変換した点と視点を結ぶ直線と、交わる面を取得する。その中から最も視点に近
い面との交点を取得する。取得した面や交点同士を接続した線分などの入力情報を元に、そ
れを元に特徴線を決定する。
本論文で提案する手法では、以下の稜線列を特徴線とする。
1. 取得した面に属する稜線列
2. 入力線列の近傍の稜線列
3. 入力線列にフィットさせた近傍の稜線列
4. 入力線列を元に面分割して生成された稜線列
これらの手法を用途に合わせて使い分ける。以下にそれぞれのの手法について説明する。
3.1.1
取得した面に属する稜線列
この手法では、ペンで塗りつぶすように領域を選択し、領域に含まれる全ての面を構成
する稜線を特徴線として取得する。以下にその手順について述べる。
まず、タブレットインターフェイスによって入力した 2 次元の点列のウィンドウ座標と
重なる位置にある面の中で、最も手前にあるものを取得する。次に、該当する全ての面に属
する全ての稜線を取得する。最後に重複した稜線は削除し、残りの稜線を特徴線とする。
16
3.1.2
入力線列の近傍の稜線列
この手法では、接続し合う稜線列を特徴線として取得する。図 3.1 に入力線列の近傍の
稜線列の取得の例を示す。
まず、タブレットインターフェイスによって入力した 2 次元の点列のウィンドウ座標を
スクリーン座標に変換する。次に、視点からスクリーン座標へ伸びる半直線とモデルの交点
を求める。その中で最も視点に近い交点を連結し、入力した 2 次元の点列を 3 次元に変換す
る (図 3.1a)。次に、連続する 2 つの点の属する面が異なる場合、境界となる稜線上に 2 つ
の点からの距離の和が最小となる座標値を求める。それらの座標値と、最初と最後に入力し
た点の座標値を新しい入力点列とする。次に、それぞれの入力点列に一番近い頂点を求める
(図 3.1b)。最後に求めた頂点列を順番に接続する稜線列を特徴線とする (図 3.1c)。連続する
頂点同士が隣接していない場合は、接続可能になるまで隣接する頂点から接続ルートを追跡
する。Lanthier[18]、金井ら [15] などのメッシュ上の 2 点間の最短経路を求める手法がある
が、本手法では対象となる 2 点はすぐそばにある場合に限定されるため、計算を簡略化して
接続ルートを決定する。追跡中に特徴線が自己干渉を起こす場合は、追跡中に選択した稜線
を特徴線から除き追跡を終了する。
a
b
c
図
3.1:
稜線列の移動
17
3.1.3
近傍の稜線列を利用した特徴線決定
入力線列近傍の稜線列を移動させて、それを特徴線とする手法について説明する。この
手法は元のモデルのグラフ構造を変えずに、既存の稜線列を入力線列に近似させる。図 3.2
に入力線列に近傍の稜線列を近似させる過程を示す。
まず、タブレットインターフェイスによって入力された点列を 3 次元座標値に変換する。
(3.2a)。次に、連続する 2 つの点の属する面が異なる場合、境界となる稜線上に 2 つの点か
らの距離の和が最小となる座標値を求める。これらの座標値と最初と最後に入力した座標値
を新しい入力点列とする (3.2b)。次に、それぞれの入力点に最も近い頂点を移動させる。こ
の時、1 つの頂点に対して移動先の候補となる座標値が複数ある場合は、その平均値を移動
先の座標値とする。最後に移動した頂点列を順番に接続する稜線列を特徴線とする (3.2c)。
a
b
c
図
3.2:
稜線列の移動
18
接続すべき頂点同士が隣接しない場合は、接続可能になるまで隣接する頂点を移動させ
ながら接続ルートを追跡する (図 3.3)。
pm
pi
pj
ed0
p'm
pi
ed0
pn
pn
図
頂点
pi
と 頂点
pj
頂点のうち、最も線分
ち、線分 pi
ed
pj
3.3:
接続されていない頂点同士の連結
を補間する頂点を、pi に隣接する頂点から選ぶ。まず、候補となる
pi pj
に近い 頂点
pm
を求める。また、
pm
を含む 2 つの稜線のう
に近い方の稜線 ed0 と稜線を構成するもう一方の頂点 pn を求める。最後に
0 上で最も p に近い座標値 p0 を求め、p をその座標値に移動させる。p0 の座標値は
j
m
m
m
式 3.12 のように求まる。
! 00!
m pn 1pm pj
0 = p000
00!
8 k0pmpj k2
>< 0(t < 0)
0
0
t =
>: t1(1(0 < tt0) 1)
0 = p + tp000
!
p
m pn
t
m
m
19
(3.12)
3.1.4
特徴領域を元に面分割して生成された稜線列
入力した線分を元に新しく生成された稜線を特徴線とする手法の説明をする。図 3.4 に
稜線生成のための位相操作の例を示す。
まず、タブレットインターフェイスによって入力された点列を 3 次元座標値に変換する。
(図 3.4a)。次に、連続する 2 つの点の属する面が異なる場合、境界となる稜線上に 2 つの点
からの距離の和が最小となる座標値に新たな頂点を生成する (図 3.4b)。次に入力点列の最初
と最後の点によって、属する面を分割する。分割は入力点と面に属する全ての頂点の接続に
よって行う (図 3.4c)。次に生成された頂点を順に接続するように稜線を生成する (図 3.4d)。
ただし、接続すべき頂点同士が同一の面を持たない場合は後で処理を行う。次に生成された
頂点や稜線によって生じた 3 角形以外の面を全て 3 角形になるように分割する (図 3.4e)。次
に接続できなかった頂点同士を繋ぐ稜線列を生成し、もう 1 度全ての面を 3 角形に分割する
(図 3.4f)。最後に該当する頂点列を順番に接続する稜線列を特徴線とする (図 3.4g)。
20
a
b
c
d
e
f
g
図
3.4:
面分割よる特徴線生成と面分割
21
隣り合わない 2 点の接続の接続例を図 3.5 に示す。以下に隣接していない頂点
pi
,p を
j
接続する手順について詳細を述べる。
pi
に隣接する全ての頂点同士で構成されている全ての稜線の中から最も
を選択する (図 3.5a)。図 3.5b のように頂点
離
disti
si
に近い稜線
, e で構成される稜線 ed と頂点 p との距
i
i
の求め方について説明する。edi 上にある点
足である。hi の座標値と
pj
hi
は、
pj
j
から edi におろした垂線の
は以下のように求める。
disti
0!
s!
i ei 1si pj
0=0
0
!
8 0ksieik2
>< 0(t < 0)
0
0
t =
>: t1(1(0 < tt0) 1)
t
(3.13)
= s + t0
s!
i ei
0
0
!
dist = khi pj k
hi
i
i
次に
pj
に最も近い稜線
0 上に新しく頂点 p0 を生成する。p0 の座標値は式 3.13 で求
ed
めた垂線の足の座標値を用いる (図 3.5c)。最後に、
p
0 生成の際に生じた 3 角形以外の面を
3 角形に分割する (図 3.5c)。p0 と p が隣接していない場合、上記の操作を繰り返す。
j
22
p
dist i
pm
si
pi
hi
ed0
ed i
pj
pn
ei
a
b
pm
pi
ed1
p'
p'
ed0
pn
pj
d
c
図
3.5:
面分割
23
3.2
特徴線によるモデルの切断
閉じた状態の特徴線によって切断されたラティスの生成手法について説明する。まず、3
角形ポリゴンメッシュの切断したい部位の境界線を特徴線として指定する。次にその特徴線
の形状を保存しながら簡略化してラティスを生成する。最後に境界線によってラティスを切
断する。以下に、閉じた状態の特徴線によってモデルを切断する手法について説明する (図
3.6)。
まず、分断する領域の境界線として、閉じた特徴線を入力する (図 3.6a)。次に、入力し
た特徴線を構成する全ての頂点から 1 つの頂点と稜線を生成する (図 3.6b1)。この時生成さ
れる稜線は実際には長さを持たず、また、生成された頂点は元の頂点と同じ座標値を持つ。
次に、生成された頂点同士を接続し、境界となる特徴線と同じ座標値を持つ稜線列を生成す
る (図 3.6b2)。最後に、分断する領域同士を接続している全ての稜線を削除する (図 3.6b3)。
以上の手順によりモデルを特徴線によって切断する (図 3.6c)。
a
b2
b1
c
図
3.6:
モデルの切断
24
b3
3.3
3.3.1
ラティス化
特徴線の指定による重み付き QEM
QEM に基づく簡略化 [9] においては、稜線に付加されたコストが大きいほど、その稜線
が削除された際の形状の変化が大きい。このことは、コストが大きい稜線はモデルの特徴的
領域に位置していることを示している。我々はこの特徴に注目し、QEM の値を故意に変化
させることで、ユーザが特徴領域だと意図する部位をコントロールすることを可能にしてい
る。具体的には、タブレットにより特徴線として入力された稜線集合の各稜線が保持してい
る
(
QE M G
e
) に制約値 k を掛け合わせる。
e
G
=k1G
e
(3.14)
この際の制約値 k は実数であり、値が大きいほど特徴線が高い精度で保存される。重み
付けを行った後、評価式 (3.14) に基づいてメッシュ削減を行うことで、ラティス格子が作
成される。制約付けを行った稜線には最も高い QEM が割り当てられているため、メッシュ
削減後にも削除されることなく保存される。結果として、入力した特徴線がラティスの稜線
として残ることになり、パッチの輪郭に反映されることになる。大幅なメッシュ数の削減を
行った場合は、制約付けがされている稜線が削除の対象になりうるため、入力した特長を位
相として保存することはできない。しかし、大幅なメッシュ削減を行った場合は、元の入力
メッシュを高い精度で近似すること自体ができなくなるために、この場合を考慮する必要は
ない。また、特徴稜線として扱う稜線集合をメッシュ削減の QEM ヒープから除外すること
で、入力した特徴線の完全な保存が可能になる。
25
重み付き QEM による簡略化を行う際、特徴として残したい稜線のほかに、その稜線に
隣接する稜線に対しても高い制約値を指定する必要がある。図 3.7 に、3 種類の制約値の設
定を用いた簡略化の例を示す。
オリジナルのモデルに対し、図 3.7a のように特徴を指定する。図 3.7b は制約値の変更
を一切行わずに簡略化したモデルである。図 3.7c は特徴として残したい稜線にのみ高い制
約値を設定して簡略化したモデルである。図 3.7d は特徴として残したい稜線とそれに隣接
する稜線に対して高い制約値を設定して簡略化したモデルである。b のモデルは特徴となる
稜線がまったく残っていない。c のモデルは特徴となる稜線は削除されないが、周囲の稜線
が削除される時の頂点移動によって特徴を損なう。d のモデルは特徴を残したまま簡略化さ
れていることがわかる。
a
b
c
d
図
3.7:
特徴線指定による重み付き QEM
26
3.3.2
4
角形化
拡張 QEM に基づくメッシュ削減後に、不要領域の 4 角形化を行う。4 角形化は以下の
理由により行われる。ラティスの 3 角形面のは 3 つの Gregory パッチにより内挿されるた
め、形状の表示に必要なポリゴンの数が多くなる（図 3.8 右）。それに対して 4 角形面は 1
つの Gregory パッチにより内挿されるため少ないポリゴン数で形状を表示するため計算コ
ストが軽減される（図 3.8 左）。曲面モデルのパッチ数を少なくし計算負荷を軽減するため
には、精度が不要な領域の 4 角形化が有効である。
図
3.8:
3 角形面の内挿と 4 角形面の内挿
27
図 3.9 に 4 角形化の例を示す。任意の稜線
0 について、その両端の 3 角形面がそれぞ
ed
れ頂点 p0; p1; p2 と、p0; p2; p3 により構成されているとする。2 つの 3 角形面が以下の 2 つ
の条件を満たす場合、ed0 が削除されて 4 角形面になる。
1. 生成される 4 角形は正方形に近い
2. 対角稜線の削除が形状に与える変化が小さい
p1
p0
ed0
p2
p3
図
3.9:
3 角形同士のペアリング
条件 1 は、鋭角部を保持する 4 角形面に滑らかな Gregory パッチを内挿するのが困難で
あることに起因する。内挿対象となる 4 角形面が正方形に近ければ、均整の取れたパッチ
ネットワークが構築される。また、その後の編集操作も容易になる。条件 1 を満たすために、
以下の評価関数を適用する。
28
k
( 0 1 2)k + kF (p0; p2; p3)k < S1
F p ;p ;p
k
( 0 1 2) + F (p0; p2; p3)k 0 kF (p1; p0; p2) + F (p0; p3; p2)k < S2
F p ;p ;p
(3.15)
(3.16)
ただし
(
F pi ; p j ; p k
式 3.16 は
)=
0
0
k 0 k1k 0 k
pi
pk
pj
pk
pi
pk
pj
pk
(3.17)
0 と対角稜線として向かい合う 2 つの角について、それぞれの角度が直角に
ed
近いものになることを保証する。S1 は実数であり 0 に近づくほど精度が高くなる。式 3.17
は
0 の両端において、それぞれの端点に接続する角度の和を求め、それらの差が最小にな
ed
ることを保証する。式 3.16 を満たすだけでは図 3.10 に示すように、ed0 に対して向き合う
角度はほぼ直角であるが鋭角部が残る可能性が残る。この状態を回避するために式 3.17 が
必要である。S1 は実数であり 0 に近づくほど精度が高くなり、長方形に近い形の 4 角形面
が生成される。
p1
ed0
p2
p0
p3
図
3.10:
1 つの評価関数だけでは検知できない 3 角形のペア
29
3.3.3
特徴線を保存した 4 角形化
図 3.11 に特徴線を保存した 4 角形化の例を示す。
特徴線以外の稜線集合 En について、それぞれの QEM のヒープを構築し、コストがもっ
とも小さい稜線の両端に接続する 3 角形同士をペアリングする。この際にペアリングされた
2 つの 3 角形に属する稜線をヒープから除外し、残りの稜線について同様の処理を行う。
図
3.11:
特徴線を保存した 4 角形化
30
第 4章
評価と考察
本章では、まず本論文で提案する手法の適用例を示す。また、それぞれの実行例を評価
し考察を行う。
4.1
編集を考慮したラティス化
図 4.1、4.2、4.3 に編集作業を考慮したラティス化の例を示す。オリジナルモデルの図
4.1 に対し図 4.2 のように特徴線となる稜線を生成し、ラティスを生成する。図 4.3 は生成さ
れたラティスを、特徴線を元に編集したモデルである。
図
4.1:
図
オリジナルモデル
4.2:
特徴線生成
32
図
4.3:
ラティスの特徴線編集
33
4.2
医用モデルのラティス化
本節では、医用目的のために生成された 3 角形ポリゴンメッシュをラティス化した例を
示す。
形成外科では患部の形状を可視化する目的から、患部の三次元モデルを作成する研究が
盛んに行われている。3 角形ポリゴンメッシュによって患部の曲面形状を表現する場合、デー
タサイズが膨大になるという問題がある。そのため、小さいデータサイズで患部の形状を表
現する手法が重要となる。
本節では 3 角形ポリゴンメッシュによって表現される患部モデルと、患部モデルから生
成したラティス曲面を比較する。比較対象はは、最大誤差、平均誤差、平均二乗誤差とする。
誤差はバウンディングボックスの対角線の長さとの比率 (%) で表す。
オリジナルの 3 角形ポリゴンメッシュとラティス曲面との比較は MetroT M を用いて行
う。Metro とは Cignoni ら [8] の手法を元に作られた、2 つの 3 角形ポリゴンメッシュの形
状の誤差を計算するアプリケーションである。Metro によってオリジナルモデルと比較され
るラティス曲面は、誤差が小さい部位ほど青く、誤差が大きいほど赤く表示される。
4.2.1
頭部モデルのラティス化
図 4.4 は CT データを元に生成した頭部モデルである。このモデルを特徴線を指定せず
にラティス化したモデルと、特徴線を指定してラティス化したモデルを比較する。オリジナ
ルのモデルの頂点数は 6001、ラティスの頂点数はいずれも 2000 である。
図 4.5 は特徴線を指定せずにラティス化したモデルである。図 4.6 は特徴線を指定して
ラティス化したモデルである。図 4.6 のモデルは形状の複雑な目、鼻、口、耳の精度を保ち
ながらラティス化したモデルである。図 4.7 は図 4.6 のモデルの、精度を必要としない部位
の稜線を削除して 4 角形化したモデルである。
34
図
図
4.4:
4.5:
CT データを元に生成した頭部モデル
特徴入力をせずにラティス化したモデル
35
図
4.6:
図
特徴入力をしてラティス化したモデル (非 4 角形化)
4.7:
特徴入力をしてラティス化したモデル (4 角形化)
36
4.2.2
下顎骨モデルのラティス化と切断
左右対称でない下顎骨の一部を切断し、適正な位置に移動する形成外科手術がある。こ
の手術では下顎骨の一部を切り離し、適正な位置に移動させて固定する。これにより正常な
運動が可能となる。この手術は、神経を傷付けないように複雑な切断作業が必要となる。そ
のため事前に切断個所を十分に検討する必要がある。そこで本手法により下顎骨の実測デー
タをラティス化し、それを切断することにより手術計画を支援を試みる。図 4.8 のように切
断した下顎骨モデルを従来手法と本手法でラティス化して比較する。
図
4.8:
下顎骨切断
図 4.9 は下顎骨の実測データを元に生成した 3 角形ポリゴンメッシュである。図 4.10 の
切断操作をせずに生成したラティスと、切断操作を行った図 4.11、図 4.12 のモデルを比較
する。これらのラティス化した下顎骨モデルは、慶應義塾大学看護医療学部教授の小林正弘
助教授の協力を得て作成した。
37
図
図
4.10:
4.9:
オリジナルの下顎骨モデル
切断せずにラティス化した下顎骨モデル
38
図
4.11:
図
ラティス化後に切断した下顎骨モデル (非四角形化)
4.12:
ラティス化後に切断した下顎骨モデル (四角形化)
39
考察
牛モデル
通常、3 角形ポリゴンメッシュを簡略化すると、生成される制御格子は不規則になるた
め形状の編集が困難である。しかし図 4.2 のように新しい位相構造を生成することにより、
図 4.3 のような編集が容易になる。
頭部モデル
頭部モデルは、形状の目、鼻、口、耳などの複雑な部位と、頭頂部、後頭部などの単純
な部位がある。しかし、全ての部位を同じように簡略化すると、複雑な形状の部位の情報を
多く失う。一方、複雑な部位を特徴線としてラティス曲面を生成すると、顔の特徴を高い精
度で表すことが可能となる。
表 1 にそれぞれの手法によって生成した、同じ頂点数のラティスに内挿される曲面の誤
差を示す。特徴線を指定してラティス化したモデルは、特徴として指定した部位以外の部分
で多くの稜線が削減される。しかし、稜線を削減される個所は単純な形状をしているため、
少ない稜線でも近似が可能である。その結果、形状の複雑な部位の精度を高く保ちながら全
体の精度も損なわずに曲面化できることがわかる。
表
1:
ラティス曲面化された頭部モデルの誤差の比較
ラティス化の種類
特徴線無し
特徴線有り (4 角形化無し)
特徴線有り (4 角形化有り)
Maximal
Mean
Mean
表示ポリゴン数
Error
Error
Square Error
1.0197% 0.05239%
0.07024%
24200
1.8905% 0.04825%
0.07776%
24226
1.8906% 0.04809%
0.07859%
23460
40
下顎骨モデル
1 つのモデルから、2 つの分離したラティスを生成した場合の切断部位の誤差を比較す
る。切断操作をせずにラティス化した図 4.10 のモデルと切断操作を行った図 4.11、図 4.12
を比較すると、切断部分の精度を高く保ちながら切断されていることがわかる。また、表 2
の誤差が示すように、モデル全体の精度も通常のラティス化とほとんど変わらないことがわ
かる。
表
2:
ラティス曲面化された下顎骨モデルの誤差の比較
ラティス化の種類
切断無し
切断有り (4 角形化無し)
切断有り (4 角形化有り)
Maximal
Mean
Mean
表示ポリゴン数
Error
Error
Square Error
0.2652% 0.05197%
0.06252%
36744
0.2824% 0.05065%
0.06222%
36778
0.3209% 0.06084%
0.07412%
30338
41
第 5章
結論と今後の展望
本章では結論と今後の展望について述べる。
5.1
結論
本論文ではタブレットインターフェイスを用いて 3 角形ポリゴンメッシュに特徴を入力
し、その結果を反映したラティス構造をモデリングする手法を提案した。
3 角形ポリゴンメッシュはデータサイズが膨大であり、自由曲面へと変換する研究が盛ん
である。従来手法は、ユーザインプットが多い、局所的に精度を調整することが困難である
などの問題があった。また、自由曲面に変換した後の制御格子が予想しにくいため、変換後
の形状編集が困難であった。本手法ではタブレットインターフェイスによる特徴入力によっ
て、局所的な精度の調整やユーザの意図した位相を持つラティスの生成が可能となった。
本手法では 3 角形ポリゴンメッシュに対する特徴入力のデバイスとしてタブレットイン
ターフェイス採用した。これにより細かい特徴指定や位相操作が容易になった。また、特徴
線を指定することにより、生成されるラティス曲面の精度を局所的に調整することが容易と
なった。
本研究では、これらの手法を実際に計算機上にアプリケーションを実装し、評価するこ
とで有用であることを確認した。
5.2
今後の展望
今後の展望として、以下の 2 点を挙げる。
第 1 点は、4 角形化した際のラティス曲面の精度が低下する点の改良である。本手法で
採用した簡略化手法は、3 角形ポリゴンをベースとしたものである。そのためラティスの頂
点補正は 4 角形化のための最適化がなされていない。この点を解決するには、3 角形以外の
ポリゴンメッシュに対する簡略化手法の研究が重要となる。
第 2 点は、均一な面のを持つラティスの生成である。3 角形ポリゴンメッシュを簡略化
すると 3 角形の形状や位相が均一性を失っていく。また、均一性を失うと 4 角形化できる 3
角形のペアが少なくなる。メッシュの均一再メッシュ化手法 [20][33] などを利用し均一な面
のを持つラティスの生成手法を検討したい。
43
謝辞
本研究を行うにあたり、様々な方の御支援を賜りました。本論文を締めくくるにあたり、
謝意を表したいと思います。
本研究の指導教授である本塾環境情報学部の千代倉弘明教授には、学部 3 年時より 4 年
間もの長きにわたり御指導を賜りました。
本塾環境情報学部の武藤佳恭教授、金井崇専任講師には、本論文の副査を快くお引き受
け頂きました。特に金井崇専任講師には大学院入学時より、研究を進める上で大変有益な御
助言を頂きました。
本塾看護医療学部の小林正弘助教授には、本研究で提案する手法を実際の医療現場で活
用するための貴重な御助言を頂きました。
本論文を執筆するにあたり、本塾政策・メディア研究科の脇田玲氏、澤田真吾氏、本塾
環境情報学部斎藤満昭氏、林隆道氏、豊島周氏には、惜しみない御助言、御助力を頂きまし
た。特に脇田氏には、本研究の理論、実装の上で幾度も議論して頂きました。ラティス・テ
クノロジー社の田中浩司氏にはプログラム実装における技術的なアドバイスを多数していた
だきました。
最後に、充実した学生生活を一緒に送ってくれたテコンドーサークル諸氏、藤柔会諸氏、
今日に至るまでの学業を支えてくれた家族に心から感謝いたします。
44
参考文献
[1] P.Bezier, Denition numerique des courbes ed surfaces, Automatisme,1966.
[2] E.Catmall, J.Clark, "Recursively Generated b-spline Surface on arbitrary Topological
meshes", Computer Aided Design, Vol.10, No.6, pp.350-355, 1978.
[3] S.Coons, "Surface for computer aided design", MIT, 1964.
[4] H.Chiyokura, F.Kimura, "Design of Solids with Free-form Surfaces", SIGGRAPH'83,
pp.289-298, 1983.
[5] CYCORE. Inc, Cult3D, http://www.cult3d.com/
[6] D.Doo, M.SABIN, "Analysis of the Behaviour of Recursive Division Surfaces near
Extraordinary Points", Computer Aided Design, pp.356-360, 1978.
[7] M. Eck, H. Hoppe. "Automatic reconstruction of B-spline surfaces of arbitrary topological type", SIGGRAPH'96, pp. 173-82, 1996.
[8] P. Cignoni, C. Montani, R. Scopigno, "Metro: measuring error on simplied surfaces",
Computer Graphics Forum, Blackwell Publishers, vol. 17(2), pp.167-174, 1998.
[9] M.Garland, P.Heckbert, "Surface Simplication Using Quadric Error Metrics", SIGGRAPH'97, pp.209-216, 1997.
[10] B.Geiger, "Three dimensional modeling of human and its application to diagnosis
and surgicalplanning", Technical Report 2150, Institut National de Rechercheen Informatique et Automatique, 1993.
[11] Cheyenne Cloud. Inc Genesis3D,http://www.gesis3d.gom/
[12] J.A.Gregory, Smooth interpolation without twist constrants,
metric Design,R.E.Barnhill
Computer Aided Geo-
and R.F.Riesenfeld, ed., Academic Press,1974.
[13] W.J.Gordon and R.F.Riesenfeld, Bernstein-Bezier methods for the computer aided
design of free-form curves and surfaces, Journal
of the ACM,1974.
[14] H.Hoppe, "Progressive Meshes", SIGGRAPH'96 Proceedings,1996., pp.99-108, 1996.
45
[15] T. Kanai and H. Suzuki. Approximate shortest path on a poly-hedral surface based
on selective renement of the discrete graph and its applications. In Proc. Geometric
Modeling and Processing 2000, pp.241-250. IEEE CS Press, Los Alamitos CA, Apr.
2000.
[16] A. Khodakovsky and P. Schroder. Fine Level Feature Editing for Subdivision Surfaces,
Proceedings of ACM Solid Modeling '99, 1999.
[17] V.Krishnamurthy, Marc Lovoy, "Fitting Smooth Surfaces to Dense polygon Meshes",
SIGGRAPH'96,1996.
[18] M.Lanthier, A.Maheshwari, J.-R. Sach. "Approximating Weighted Shortest Paths
on polyhedral Surfaces", Proceedings of 13th ACM Symposium on Computational
Geometry, pp.274-283, 1997.
[19] A.W.F.Lee, W.Sweldens, P.Schroer, L.Cowsar, D.Dobkin, "MAPS: Multiresolution
adaptive parameterization", SIGGRAPH'98, pp. 95-104, 1998.
[20] B. Levy, J.L. Mallet, "Non-distorted texture mapping for sheared triangulated
meshes", SIGGRAPH'98, pp. 343-52. 1998.
[21] C.Loop, "Smooth spline surface based on triangeles", Master's thesis, University of
Utah, Department of Mathematics, 1987.
[22] W.E.Lorensen, H.E.Cline, "Marchig Cubes: A High Resolution 3D Surface Construction Algolithm", ACM computer Graphics, 1987.
[23] J.Popovic, H.Hoppe, "Progressive simplicial complexes", SIGGRAPH'97 Proceedings, pp.217-224,1997.
[24] M.Saito, T.Hayashi, A.Wakita, H.Chiyokura, "Feature Preserving Renement of Surfaces for Web-based Surgical Simulation", Medicine Meets Virtual Reality 2002, to
appear.
[25] Shout Interactive. Inc, Shout3D, http://www.shout3d.com/
[26] S.Takeuchi, T.Kanai, Hi.Suzuki, K.Shimada, F.Kimura, "Subdivision Surface Fitting
with QEM-based Mesh Simplication and Reconstruction of Approximated B-spline
Surfaces", Pacic Graphics 2000, pp.202-212, 2000.
46
[27] D.Tanaka, M.Kobayashi, M.Chiyokura, T.Nakajima, T.Fujino, "Web-based educational tool for cleft lip repair using XVL", Medicine Meets Virtual Reality 2001,
2001.
[28] A.Wakita,M.Yajima,T.Harada, H.Toriya and H.Chiyokura, XVL : A Compapct
and Qualied 3D Representation With Lattice Mesh and Surface for the Internet,
j
Web3D VRML2000,
pp.45-51, 2000.
[29] Akira Wakita, Takamichi Hayashi, Takashi Kanai, Hiroaki Chiyokura, "Using Lattice
for Web-based Medical Applications", Web3D 2001, ACM, SIGGRAPH, Paderborn,
Germany, Feb.19-22, ACM-Press, 2001.
[30] Web3D Consortium, http://www.web3d.org/
[31] XVL Player,http://www.xvl3d.com/
[32] 金井崇,「細分割曲面の連続的多重解像度表現」, グラフィックスと CAD 研究会 (情報
処理学会研究報告, Vol.2000, No.78, 99-CG-100, pp. 19-24), 2000.
[33] 金井 崇, 鈴木 宏正, "対話的なメッシュの均一再メッシュ化手法", グラフィクスと CAD
/ Visual Computing 合同シンポジウム, 札幌，6 月, 論文集 pp.91-96, 2001.
[34] 斎藤満昭, 林隆道, 脇田玲, 千代倉弘明,「医用曲面モデル生成システムの構築」, 第 17 回
Nicograph/Multimedia 論文コンテスト,2001.
[35] 千代倉弘明,"ソリッドモデリング", 工業調査会,1985
[36] 鳥谷浩志, 千代倉弘明, "3 次元 CAD の基礎と応用", 共立出版, 1991.
[37] 林隆道, 齋藤満昭, 脇田玲, 金井崇, 千代倉弘,"CT,MRI データからのラティス構造に基
づく医用曲面モデル自動再構成",3 次元画像コンファレンス 2001,2001.
[38] 脇田 玲, 矢島 誠, 原田毅士, 鳥谷浩志, 千代倉 弘明, "ラティス構造に基づく軽量で高品
質な Web3D データ表現", 情報処理学会論文誌, 第 42 巻, 第 5 号別冊, 2001.
[39] 脇田 玲, 千代倉 弘明, "Web3D の現状と今後の動向", NICOGRAPH 論文コンテスト,
pp. 199-204, 2001.
47