三角メッシュを入力とした曲面再構成のための 四角パッチ構築方法

三角メッシュを入力とした曲面再構成のための
四角パッチ構築方法
伊藤 貴之* 山田 敦* 古畑 智武** 井上 恵介* 嶋田 憲司**
*日本アイ・ビー・エム(株) 東京基礎研究所
**カーネギーメロン大学 機械工学科
{itot, ayamada, [email protected] [email protected] [email protected]
[email protected][email protected]削減や
CAD 形状モデルとの整合性において利点がある。筆者らは、まず曲面パッチの位相が与えられたものとして、
それを入力データである点群にフィッティングする曲面再構成方法を提案している。本報告では、曲面の連続
性や滑らかさを向上することを目的とした、四角形曲面パッチの位相構築方法を提案する。本手法では細かい
三角メッシュを入力とし、それをいくつかの帯状領域に分割し、それぞれの領域を粗い四角形に分割すること
で、規則性の高い四角パッチの位相を構築する。前述の手法と本手法を組み合わせることで、曲面再構成の一
連の処理が自動的に実現される。
Rough Quadrilateralization for Surface Reconstruction
from a Fine Triangular Mesh
Takayuki Itoh* Atsushi Yamada* Tomotake Furuhata**
Keisuke Inoue* Kenji Shimada**
*IBM Research, Tokyo Research Laboratory
** Mechanical Engineering, Carnegie Mellon University
Surface reconstruction is a technique for converting fine geometric models such as triangular meshes or
unorganized points into a smaller number of curved surface patches. We have reported a component technique for
surface reconstruction that fits given surface patches into a set of points. In this paper we propose another component
technique that automatically constructs the topology of quadrilateral surface patches. Given a fine triangular mesh,
the technique first divides the mesh into several belt-like subregions, and then divides each subregion into
quadrilateral patches. Fully automated surface reconstruction can be implemented by combining the two component
techniques.
1
力として、そのメッシュ要素よりも十分粗い四角形パッ
1. はじめに
曲面再構成 (Surface Reconstruction) [Baj95] [Eck96]
チを、領域境界に沿って整列するように生成する。ま
[Kri96] は、細かい三角メッシュや点群を入力して、少
た、入力データである三角メッシュの構造を利用して、
数の曲面パッチに変換する技術である。曲面再構成
Advancing Front Method の問題点である「内側の領域
は、データ量の削減や、市販 CAD システムとの整合
におけるメッシュ要素の歪み」も同時に改善する。
性において利点がある。筆者らは、曲面再構成技術
Outer boundary
の一種として、細かい点群を入力し、あらかじめ生成さ
れた四角形パッチをフィッティングすることで、点群が
表す形状を曲面パッチで表現する手法を提案してい
Inner boundary
る [Yam99b]。
Hole
連続性や滑らかさの点で高品質な曲面形状を得る
ためには、正方形に近い四角形曲面パッチを生成す
ることが好ましいことが容易に推測できる。本報告では、
曲面再構成技術によって、十分に高品質で、かつデ
(a) 入力三角メッシュの例
ータ量の少ない形状表現を実現するために、曲面パ
Subregion (3)
ッチに対して以下の条件を仮定する。
条件 1: 曲面パッチは四角形である。また、ト
リムは用いない。
条件 2: 曲面パッチは入力した三角メッシュ要
素に比べて十分大きい。
条件 3: 四角形曲面パッチの4頂点の角度は直
角に近いことが好ましい。そのためには、滑ら
かな曲線を形成する領域境界上においては、パ
ッチ頂点は2枚のパッチに共有されることが
望ましい。また、領域内部においては、パッチ
頂点は4枚のパッチに共有されることが望ま
しい。
Subregion (2)
Subregion (1)
(b) 三角メッシュの帯状領域への分割
上記の条件 1 および条件 3 は、有限要素解析の四
角メッシュに求められる条件に類似している。そこで本
報告では、有限要素解析の分野で最も有用な手法の
ひとつである Advancing Front Method [Bla91] に類似
(c) 帯状領域のパッチへの分割
したアルゴリズムを用いて、四角形曲面パッチの位相
図 1 本手法の概要
を構築する手法を提案する。
Advancing Front Method は、与えられた領域の境界
本報告で提案する手法の概要を図 1 に示す。図
線に沿って一列にメッシュ要素(例えば四角形要素)
1(a)のような三角メッシュを与えられたとして、本手法は
を生成し、その内側に同様に一列にメッシュ要素を生
まず図 1(b)に示すように、三角メッシュを構成するメッ
成し … という処理を、領域がメッシュ要素で埋め尽くさ
シュ要素を、メッシュの領域境界に沿って、いくつかの
れるまで反復する手法である。この手法を適用するこ
帯状領域に分割する。続いて図 1(c)に示すように、そ
とで、領域境界上の多くのメッシュ頂点が2個の四角
れぞれの帯状領域を切断してパッチに分割する。この
形要素に共有され、領域内部の多くのメッシュ頂点が
手順によって、Advancing Front Method によって生成
4個の四角形要素に共有された、良好な四角メッシュ
されるメッシュのように、領域境界に整列したパッチを
を生成することができる。その反面、入力形状の最も
生成することができる。また本手法では、領域の内側
内側に歪んだ領域が残ったときに、歪んだメッシュ要
にいたるまで歪みの少ない帯状領域を生成するので、
素が生成されやすく、最悪の場合メッシュ要素の生成
Advancing Front Method の問題点である内側の要素
に失敗する、という問題点がある。
の歪みも低減することができる。
本報告で提案する手法は、細かい三角メッシュを入
2
2. 実装
2.1 三角メッシュの帯状領域への分割
本手法で生成されるノードグループおよび帯状領域の
例を図3に示す。図3(下)は、図2(下)に示したグラフを構
図 1(b) に示した通り、本手法ではまず、三角メッシュ
成するノードを、 r1 , r2 , r3 の3個のグループに分類した例
を領域境界に沿った帯状領域に分割する。
である。各々のグループを構成する三角形要素の集合が、
まず本手法では、入力三角メッシュを構成する要素
図 3(上)に示す 3 個の帯状領域となっている。
辺の中から、三角形要素1個のみに接する要素辺を
抽出する。抽出された要素辺を隣接関係にしたがって
Subregion r1
一続きに探索することで、領域境界を構成するいくつ
Subregion r2
かのループを抽出することができる。
続いて本手法では、 n 番目の境界ループから m 個
の三角形要素を隔てて位置する三角形要素に、 S m, n と
いう分類をつける。三角形要素の分類の例を図 2(上)に
示す。この図から、同じ分類をもつ三角形要素が領域境
Subregion r3
界に沿った一列の層を形成することがわかる。
続いて本手法では、図 2(下)に示すように、三角形要
r1
素層をノードとし、三角形要素層の隣接関係をアークとす
s1,1
s2,1 s3,1
s( c −1),1 sc ,1
るグラフ構造を構築する。
Boundary b1
r3
s 2,2
s3,1
s1,2
Boundary b2
r2
s1,2 s2,2 s3,2
図 3 帯状領域の生成
s2,1
s1,1
2.2 帯状領域の分割によるパッチ生成(1)
続いて本手法では、図 1(c)に示した通り、帯状領域
s1,1
s2,1 s3,1
を分割してパッチを生成する。なお、以下のアルゴリズ
s( c −1),1 sc ,1
ムの詳細は [Ito00] に説明されている。
本手法によって生成される帯状領域の多くは、1個
の穴をもつ。このような形状の帯状領域に対して、本
s1,2 s2,2 s3,2
手法では以下の手順により帯状領域を分割してパッ
チを生成する。
図 2 境界からの距離による三角形要素層の生成
1) 帯状領域を構成する三角形要素を探索し、内側
および外側の境界を構成する要素辺を抽出し、ル
続いて、このグラフを構成するノードを、以下の手順に
ープを構成する。
より数個のグループに分類する。
2) 領域外側の境界ループのメッシュ頂点を数個おき
1) 隣接ノードを 1 個だけ持つノードは、その隣接ノード
に選択し、それらを連結するパッチ辺を生成する
と同じグループに配属する。
(図 4(左)参照)。ただし、境界ループを共有する隣
2) 構成ノード数がユーザー指定値より少なく、かつグ
接帯状領域がすでにパッチに分割されているとき
は、そのパッチ辺をそのまま用いる。
ループ外の隣接ノードを1個だけ持つグループがあ
3) 2)で生成された領域外側のパッチ頂点から、領域
れば、その隣接ノードを同じグループに入れる。
内側のループに向かうパッチ辺を生成する(図
3) 1)2) の処理を終えた後に、まだグループに入ってな
4(中)参照)。
いノードがあれば、それを近隣グループに入れる。
4) 3)で生成された領域内側のパッチ頂点を連結して、
以上の手順により本手法では、ユーザー指定値に近い
パッチ辺を生成する(図 4(右)参照)。
ノード数のグループを生成する。このとき各々のグループ
以上のアルゴリズムにより、本手法では以下の 3 種類
は、ほぼ均一な太さの帯状領域を形成する。
3
のパッチを生成する。
法で帯状領域の外側の境界線と内側ループを結ぶパ
a) 外側ループの頂点 2 個と、内側ループの頂点 2 個
ッチ辺を生成し、帯状領域をパッチに分割する。
を連結してできる、四角形パッチ。ほとんどの帯状
図 6 は、このアルゴリズムで生成される骨格線およ
領域において、このパッチが最も多く生成される。
びパッチの例である。帯状領域が小さい場合には、図
b) 外側ループの頂点 3 個と、内側ループの頂点 1 個
6(左)に示すように、骨格線が 1 頂点となる場合も多い。
を連結してできる、四角形パッチ。
帯状領域が細長い場合には、図 6(右)に示すように、
c) 外側ループの頂点 2 個と、内側ループの頂点 1 個
骨格線が領域中心を表す曲線となる。
を連結して出来る、三角形パッチ。
骨格線
図 4 穴を 1 個もつ帯状領域のパッチへの分割
図 6 穴を持たない帯状領域の分割
帯状領域が複数の穴をもつ場合には、1) で複数の
内側境界ループが生成される。このような場合には、
2.4 後処理
複数の内側境界ループを接続する一つの大きなルー
以上の処理によって、入力形状である三角メッシュ
プを生成し、これを内側ループとみなしてパッチを生
は、多数の四角形パッチと少数の三角形パッチに分
成する(図 5 参照)。
割される。筆者らの実装では、以上のパッチを図 7 に
示すテンプレートで分割して四角形パッチにする。続
いて、入力形状である三角メッシュのメッシュ頂点を点
群とみなして、[Yam99b] に示す手法を用いて四角形
パッチを点群にフィッティングすることで、曲面再構成
を実現する。
図 7 三角形・四角形混合パッチの四角形パッチへ
図 5 穴を複数もつ帯状領域のパッチへの分割
の変換に用いるテンプレート
2.3 帯状領域の分割によるパッチ生成(2)
3. 従来手法
2.2 では、穴をもつ帯状領域の分割について述べた
代表的な曲面再構成技術における、四角形曲面パ
が、最も内側の帯状領域は穴を持たない場合が多い。
ッチの位相構築方法について述べる。
この場合に本手法では、まず帯状領域を構成する三
角形要素に対して細線化処理を適用して、三角形要
[Baj95] では、入力データである点群を結ぶ四面体
素辺で構成される骨格線を抽出する。続いて、この骨
メッシュを生成し、点群が表す物体の境界面にあたる
メッシュ面群を選択する。続いて、その面群に十分近く、
格線を面積ゼロの内側ループとして、2.2 と同様な手
かつ G1 連続であるパッチを、四面体との交差面の集
4
合で表す。パッチは三角形と四角形の混合になり、し
おける作業行程の短縮への貢献が期待できる。
かも点群と同等の密度で生成される。
続いて、本手法による四角形パッチの生成過程を図
[Kri96] では、曲面パッチの位相は自動生成しない
9 に示し、従来手法による四角形パッチ生成結果と比
かわりに、曲面パッチの境界線をユーザーに指定させ
較する。図 9(a)は、入力三角メッシュを2つの帯状領域
る GUI の例を提示している。
に分割し、外側の帯状領域をパッチに分割した例であ
[Eck96] では、入力データである点群を結ぶ三角メ
る。図 9(b)は、内側の帯状領域に対して細線化手法を
ッシュを単純化し、その結果としてできたラフな三角メ
適用して骨格線を生成し、それを面積ゼロの内側ル
ッシュの三角形要素をペア化して四角形パッチに変
ープとみなしてパッチを生成した例である。図 9(c)は、
換している。この方法は、点群より十分に粗く、かつ正
[Yam99b] に示す手法を用いて四角形パッチを曲面パ
方形に近い良質な形状の四角形を優先的に生成す
ッチに変換した例である。図 9(d)は、本手法を用いず
ることができる。しかし、1 章で示した「条件 3」 を満たす
に、従来手法([Eck96] に類似した手法)を用いて四角
ような位相が構築されるとは限らない。
形曲面パッチを生成した例である。この実行例から、
本手法が従来手法と比べて、良好な形状をもつ四角
4. 実行例
形曲面パッチを生成できていることが視覚的に判断で
筆者らは本手法を含む一連の曲面生成技術を、
きる。他の CAD データにおいても同様な結果を得るこ
CAD における接続面(フィレットなど)の自動生成の目
とができた。
的ですでに実装し、実用している。
(a) 本手法による四角形パッチの生成過程(1)
図 8 本手法の実用例
(b) 本手法による四角形パッチの生成過程(2)
本実装によって生成された曲面の例を図8 に示す。
図 8(左)は、10 枚の曲面を持ち、その中心部に穴を持
つ CAD データの例である。本実装ではまず、図 8(右
上)に示すように、該当領域に細かい三角メッシュを生
成し、それを [Yam99a] に示す手法で滑らかな曲面形
状に変形する。さらに、図 8(右下)に示すように、本手
(c) 本手法による四角形曲面パッチ生成結果
法を用いて細かい三角メッシュを四角形パッチに変換
し、[Yam99b] に示す手法を用いて四角形曲面パッチ
を完成する。
一般的に、図 8(左)の中心部のような込み入った形
状に対して、市販の CAD システムで曲面を作成する
には、熟練が必要である。製造業の設計現場では、こ
のような曲面の作成に非常に大きな作業行程を要して
(d) 従来手法による四角形曲面パッチ生成結果
いるのが現状である。本実装は、このような形状に対し
図 9 本手法および従来手法の実行例
て曲面を自動生成できるので、製造業の設計現場に
5
続いて、本手法および従来手法で生成した四角
・ 曲率が部位によって大きく変わるような形状に対
形曲面パッチの滑らかさを、数値的に比較する。表 1
して、適応的な大きさでパッチを生成する要求へ
は、4種類のCAD データに対して、本手法および従来
の対応。
手法で曲面を生成し、その曲率半径の最小値を測定
・ あえて接線不連続な頂点(または線)を表現した
した結果である。4 種類の CAD データすべてにおいて、
い場合への対応。
本手法で生成した曲面は、従来手法で生成した曲面
本技術に対して以上の用件を対応することは、少なく
と比較して、曲率半径の最小値が大きかった。このこと
ともアルゴリズム的には困難ではない。そこで今後の
から本手法は、従来手法と比べて滑らかな曲面を生
発展として、以上の用件を対応した上で、CG のコンテ
成していることがわかる。
ンツでよく用いられている三角ポリゴンデータに対して
曲面再構成を試みることが考えられる。
表 1 曲率半径の最小値の比較
従来手法
本手法
データ 1
4.3
4.5
データ 2
3.1
10.2
データ 3
6.7
7.6
データ 4
1.3
12.8
参考文献
[Baj95] Bajaj C. L., Bernardini F., and Xu G.,
Automatic Reconstruction of Surfaces and Scalar
Fields from 3D Scans, Proceedings of
SIGGRAPH ’95, pp. 109-118 (1995).
[Bla91] Blacker T. D., and Stephenson M. B.,
Paving: A New Approach to Automated
Quadrilateral Mesh Generation, International
Journal for Numerical Methods in Engineering,
Vol. 32, pp. 811-847 (1991).
[Eck96] Eck M., and Hoppe H., Automatic
Reconstruction of B-Spline Surfaces of Arbitrary
Topological Type, Proceedings of SIGGRAPH ’96,
pp. 325-334 (1996).
[Ito00] Itoh T., Yamada A, Furuhata T., Inoue K., and
Shimada K., Rough Quadrilateralation of Triangular
Meshes via Belt-like Subregioning for Surface
Reconstruction, IBM Japan, TRL Research Report,
RT-0354 (2000).
[Kri96] Krishnamurthy V., and Levoy M., Fitting
Smooth Surfaces to Dense Polygon Meshes,
Proceedings of SIGGRAPH ’96, pp. 313-324
(1996).
[Yam99a] 山田, 嶋田, 古畑, Hou K., 離散的なバネモ
デルを用いた滑らかな曲線、曲面生成手法, 情報処
理学会グラフィクスと CAD / Visual Computing 合同シ
ンポジウム '99, pp. 43-48 (1999).
[Yam99b] 山田, 古畑, 伊藤, 嶋田, 離散的なバネモデ
ルを用いた曲線曲面の点群へのあてはめ, 情報処理
学会グラフィクスと CAD 研究報告, 99-CG-96, pp.
31-36 (1999).
続いて、本手法で生成した曲面の連続性を、数値
的に評価する。表 2 は、本手法で生成された曲面に対
して、隣接四角形曲面パッチの共有辺上での法線方
向のブレ角の最大値(単位は degree)を求めたもので
ある。この結果から、本手法で生成された曲面は、隣
接パッチ間での G1 連続性をほぼ達成していることが
わかる。
表 2 隣接パッチ共有辺上での法線方向のブレ角
データ 1
データ 2
データ 3
データ 4
0.012
0.017
0.009
0.076
5. むすび
本報告では、細かい三角メッシュを入力して、それ
を粗い四角形パッチ群に変換する手法を提案した。
本手法は、領域境界に沿って整列した良好な位相構
造の四角形曲面パッチを生成することにより、正方形
に近い良質な四角形曲面パッチを生成することができ
た。また、本報告の実行例により、本手法が曲面再構
成技術における曲面の滑らかさや連続性を向上させ
ていることを示すことができた。
筆者らは本技術を、CAD における接続面(フィレット
など)の自動生成の目的ですでに実用している。一方、
本技術を Visualization や Rapid Prototyping などの目
的で用いるためには、以下の要求に対して考察する
必要がある。
・ 閉曲面を構成する三角メッシュへの対応。
6