複数の凸包を用いたカバー形状生成-Cover Geometry Design using Multiple Convex Hulls五十嵐 悠紀 †Yuki IGARASHI†,† 筑波大学 / 学術振興会‡ 東京大学鈴木 宏正 ‡Hiromasa SUZUKI‡

and† University of Tsukuba / JSPS Research Fellow‡ The University of Tokyo

E-mail: †yukim@acm.org, ‡suzuki@den.rcast.u-tokyo.ac.jp1

はじめにいることで実際の物体にフィットしたカバー形状を得ることができることを確認した．

実世界の物体の形状に合わせて新しい形状をデザインすることは難しい．五十嵐らは 3 次元モデルから凸包 (ConvexHull) 形状を計算することで実物体のためのカバーデザイン手法を提案した [1]．しかしこの手法では入力物体の全体2点群のクラスタリングは Computer Vision の分野においの頂点を 1 つの凸包を用いることでカバー形状を計算する
ため，入力モデルに対してカバー形状は隙間が多くできる
欠点がある．隙間が大きすぎると内部で物体が動いてしまい，物体の表面に傷がついてしまったりする．このため図1(e), (f) のような手袋やバイオリンケースのような隙間が少ないカバーがよりユーザには望まれる．て Besl らによって研究されている [2, 3]．これらは点群が格子状に並んだものをターゲットとしており，点群上での各点における曲率などの特徴量を評価し，近傍の点で特徴量が近いものをグループ化する手法である．我々の提案する点群のクラスタリング手法はランダム点群を対象とする．

3 次元メッシュを形状に着目して分割する手法はいくつ

我々は複数の凸包を用いることで入力モデルに沿ったカバー形状を生成する．提案手法は頂点群から複数の凸包を生成するための頂点クラスタリングを行う．図 1 に本手法の概要を示す．入力は 3 次元モデルの頂点と頂点同士の接続情報 (本稿ではリンクとする) とする．入力データは現実か提案されている．Lien らは凹部分を検出して領域分割することで多面体を凸包に分割することを行った [4]．Liu ら
は楕円体のプリミティブを用いて 3 次元モデルを階層的に分割することを行った [5]．
また，3 次元モデルの表面形状の領域分割手法も多々提の物体の 3 次元モデルであるため，3 次元スキャナなどを行いて得ることが多い．このため，メッシュが崩れていることも多い．頂点のリンク情報がない場合にはそれぞれの頂点に近傍の頂点をリンク情報として保持することで利用する．
システムは計算したクラスタリングを元に，複数の凸包を生成しこれらの和集合をとることでカバー形状を計算する．和集合をとった際の接合部を縫い目となる領域分割線とする．この領域分割だけでは 2 次元へ展開するのに不十関連研究案されている．Cohen-Steiner は 3 次元モデルを簡単な平面形状の集合に分割する手法を提案した [6]．Julius らは可展面に分割する手法を提案した [7]．これらの分割手法は表面形状の面の情報を使用している．これに対して我々の提案手法は面情報を使わず，頂点とリンクだけで計算することができる．スキャンデータは通常非多様体であり，面が壊れていることが多いため，提案手法が有効であると言える．

分であるため，さらにユーザが縫い目を追加・編集することができる．それぞれの領域を展開することで型紙として利用する．領域分割されたそれぞれの領域ごとにカバー用

3アルゴリズムの縮まない展開手法である shrink-free flattening [1] を利まずユーザは入力モデルを用意する (図 1a)．本提案手法

用して展開し型紙を得る．この型紙を使ってユーザは実際は頂点データと頂点同士のリンクを用いる．我々は通常のの物体のためにカバーを縫うことができる．

PC 上でインタラクティブなパフォーマンスを出すために荒本稿のコントリビューションは複数の凸包を用いた新しいメッシュ(頂点数 1000-3000) を利用した．PC は 1.4GHz

い頂点クラスタリング手法の提案である．本手法を使うことで複数の凸包の体積が最小化するようなクラスタリング

Intel Core 2 Duo CPU PC を利用した．入力モデルからカバー形状を生成するアルゴリズムは以下の 5 つのステッ結果を得ることができる．入力は 3 次元モデルの頂点と頂プから成る：

点のリンクを用いるため，複数の部品から成るようなモデルや Point-based モデルにも適用可能である．本手法を用

1) 頂点クラスタリング: 入力モデルの頂点を複数の凸包に分割するためにクラスタリングする (図 1b)．詳細

(a) 入力3次元モデル(b) 頂点クラスタリング(c) 複数Convex Hullの生成(e) 領域分割と2次元への展開(d) カバー形状の生成(f) 実際に裁縫したカバー

図 1: 本システムの概要．
は第 3.2 節に述べる．

2) 複数の凸包の生成: クラスタリング結果を用いて重なりがあるように処理を行い複数の凸包を生成する (図1(c))．詳細は第 3.3 節に述べる．
3) カバー形状の生成: 複数の凸包の集合和をとり，このメッシュをカバー形状とする (図 1d)．このカバー形状は 1 つの閉じたメッシュとなる．詳細は第 3.3 節に述べる．

4) 領域分割: (3) で生成された形状の集合和の接続線を縫い目と定義する．この縫い目だけでは不十分であるため，ユーザが手動で縫い目を追加・編集する．平
面近似を利用した領域分割手法 [6] をそれぞれの領域に適用して入力の縫い目を生かしながら領域分割を行う機能も用意した．

5) 2 次元へ展開: 領域分割されたそれぞれの領域ごとにカバー用の縮まない展開手法である shrink-free flattening [1] を利用して展開し型紙を得る．これにより3 次元メッシュ上のエッジが縮むことなく 2 次元に展開することができる．2 次元に展開した型紙をプリンタで印刷・切断し，布を裁断・裁縫することで実世界においてカバーを作成する．

3.1

前処理

システムは入力モデルから頂点と頂点のリンク情報を得る．メッシュを入力した場合にはそれぞれの頂点 vi におけるエッジで接続している頂点を近傍の頂点集合 N eigh(vi )とする．入力モデルがエッジを持たない場合には，近傍の頂点への距離を計算して近いほうから順に m 個，N eigh(vi )とする．我々は通常のメッシュのエッジから m = 6 と設定している．

3.2

頂点クラスタリング

本手法は全点群を P としたとき，その分割 {Ci }, i = 0, 1,· · · , n(∪Ci = P, i ̸= j に対して Ci ∩ Cj = ∅) を求める手法である．分割 Ci に対する凸包 CH(Ci ) は必ず決まるた
め，分割 Ci を求めれば良い．クラスタリングの分割数 nはユーザの入力とし，システムの初期設定は n = 4 とした．本稿の例ではカバーということで 2 − 6 を使用している．n = 1 としたときは凸包となり，文献 [1] のカバー形状と同様になる．
入力データに対してクラスタリングするには Lloyd [8]のアルゴリズムが有名であり，k-means クラスタリング [9]などに使われている．我々も文献 [10, 6] などと同様に頂点クラスタリングアルゴリズムに Lloyd の手法を利用する．

Lloyd [8] のアルゴリズムは，• 現状の Center を用いて Cluster を広げていく• それぞれの Cluster に対して新しい Cluster center を計算する補として得られた頂点群である．これにより入力モデルの凸となる部分を自動で選んでくることが可能になる．

• 収束するまで繰り返すというフレームワークである．我々もこれと同様に，Ge-

3.2.2

Step 1: Geometry Partitioning

ometry partitioning と Cluster fitting の 2 つを収束するま

入力頂点群を複数のクラスタに全体のエネルギーが最小で繰り返すことでエネルギー関数 E(v, Ci ) の総和を最小化になるように分割する．凸包は少なくとも 4 つの頂点を必要するような結果を得る．とするので，シードの頂点 si とこの近傍の頂点 N eigh(si )から 3 つ選んだ頂点とで初期の凸包を生成する．

3.2.1

次にシードの頂点からクラスタを広げていく．Lloyd の初期シードの決定

アルゴリズムのように，近い (エネルギーが低い) 頂点か最初に n 個のシードが必要である．クラスタリング結果ら順にクラスタに追加していく．このために，グローバルは初期のシード位置に依存する [6, 7]．そこで，我々は手に優先度付きキューを用意し，それぞれの頂点 v とクラス動入力と自動入力の両方を用意した．順に説明する．

タ Ci におけるエネルギー関数 E(v, Ci ) を計算してキュー

手動でのシードの入力はユーザがモデル上をクリックすへ入れていく．クラスタが決定した頂点はクラスタ Ci のることでシードとなる頂点の位置を指定することができる．

インデックス i をタグとして保持する．よって，同じ頂点

図 2 に初期のシード位置によってクラスタリング結果が異がキューから何度も Pop されるがすでにタグが決定していなる例を示す．

る頂点に関しては何も行わない．
クラスタを広げていく処理は優先度付きキューが空になるまで繰り返す．キューから頂点を Pop してすでにクラスタが決定していたら何も行わずに，次を Pop する．もしクラスタが決定していなかったら今着目しているクラスタと同じインデックスを付け，クラスタを決定する．さらにキューに入っている頂点のエネルギー関数の値をすべて更(a) Input model(b) Clustering result(c) Different clustering result

図 2: バナナのモデルを 2 つのクラスタに分割した例． 初期のシード位置によって結果が異なる．

新する．
本稿では CH(C) をクラスタ C の頂点を用いた凸包 と定義する．また，V ol(CHi ) を凸包 CHi の体積と定義し，エネルギー関数は体積の増加分を用いて以下のように定義する．

Ev (v, Ci ) = V ol(CH({v} ∪ Ci ) − V ol(CH(Ci ))(1)

提案手法では頂点 vi を複数の convex hull CH の中でエネルギーが最小になるようにクラスタリングする．よって，∑V ol(CH(Ci ) を最小化するようなクラスタリング結果を得ることができる．
また，計算時間を削減するために，頂点 v から凸包 CHまでのユークリッド距離を d(v, CH) としたとき，式 (1) の代わりに式 (2) を用いることができる．

Ed (v, Ci ) = d(v, CH)
図 3: 自動計算された初期のシード候補の頂点群．赤い頂点が候補点群．
次に，自動の初期のシード設定を説明する．まず入力モ
デル全体に対して 1 つの凸包 CH0 を計算し，これに含まれる頂点を初期のシード候補の頂点群としてリストに保持する．このリストの中からランダムに頂点を選び，これを初期のシードとする．図 3 での赤い頂点が初期のシード候(2)

表 1 にエネルギー関数 Ev と Ed の比較を示した．計算時間は Ed を利用した方が早いことがわかる．カバー形状の体積を計算し，入力モデルにどちらがよりフィットしているかを比較すると，Ev を用いた方がより入力モデルにフィットする形状を得ることが可能であることがわかる．

表 1: エネルギー関数 Ev と Ed の比較．分割数 6 クラスタ．

3D modelSquirrel
BunnyCamera
Teddy bear
Cap & Ball
Armadillo
Hand

3.2.3

頂点数

1,023
1,039
2,979
1,990
340
1,620612

エネルギー関数 Ev
Time
体積(ms)
804
3.054
568
1.089
3,976
1.049
2,041
0.512
155
8.180
1,020
0.248
4160.126

エネルギー関数 Ed
Time
体積(ms)
565
3.430
539
1.108
3,243
1.133
1,992
0.582
108
9.497
1,303
0.284
2400.128と定義して，CHi = CH(Ci ∪ Across(Ci )) を計算することで図 5(c), (f) のように重なりがある状態にすることができる．
生成した複数の凸包は Boundary Representation Solidである．これらに Boolean union operations[11] を適用することで 1 つの閉じたカバー形状 G を得る．

Step 2: Cluster Fitting(a) クラスタリング(b) Convex hulls
CHi (Ci )(c) Convex hulls
CHi (Ci ∪Across(Ci ))(d) クラスタリング(e) Convex hulls
CHi (Ci )(f) Convex hulls
CHi (Ci ∪Across(Ci ))新しいクラスタ C が見つかったら，それぞれのクラスタ

Ci に対して Center となるシードを更新する．本手法ではそれぞれの Cluster Ci における頂点のリンクのグラフ Giを構築し，グラフの中心となる頂点 xi を抽出する．
システムはまず Ci の境界を以下で定義する：

Bou(Ci ) = {v|v ∈ Ci , ∃vj ∈ N eigh(v), vj ∈ Cj , (∀j ̸= i)}.
この境界に含まれる頂点からの距離をダイクストラのアルゴリズムで計算し，境界からの距離が最大の頂点が中心で

図 5: クラスタリング結果と凸包の生成．上段は 2 次元，ある．

下段は 3 次元．

求まった中心 xi はクラスタ Ci の次の Center として利用する．このことでクラスタ C は全体のエネルギー関数を最小化するような結果を得ることができる．この繰り返しは図 4 に示すように 1 回で終わる．

4

結果
本提案手法はノート PC (1.4GHz Intel Core2 Duo CPU

PC (RAM 3MB)) でリアルタイムに動作する．図 6 はいく
つかのモデルに適用した結果である．クラスタリング結果，複数の凸包の結果，最終的なカバー形状を示した．図 7 にはスキャンデータでの結果を示した．これらは自動シード選択を利用し，エネルギー関数 Ev を用いた．表 2 は我々の(a) ランダムにシードを選択(b) 1 回反復後(c) 1 回反復語 (別の方向)

結果と 1 つの凸包でのカバー形状生成手法 [1] の結果を体積で比較したものである．提案手法はよりモデルにフィッ

図 4: 球を 4 つにクラスタリングした結果．

トしたカバーが生成できていることがわかり，また分割数が多いほうがよりフィットしていることがわかる．表 3 には頂点クラスタリングの時間と複数の凸包生成の時間を分

3.3

複数の凸包からのカバー形状生成割して計測時間を示した．実際のカバーを裁縫した例を図8 に示す．
まずカバーなので取り出せるようすべての頂点に対して法線方向に距離 α だけオフセットしておく．入力モデルのサイズを 1 としたとき，α = 0.05 とした．

5

今後の課題

システムは計算されたクラスタ情報を用いて複数の凸包を生成する．CHi = CH(Ci )(1 ≤ i ≤ n) と生成すると，本稿で述べた頂点クラスタリング手法は入力モデルの意

図 5(b, e) のように穴があいてしまうので，クラスタ Ci に味を理解しているわけではないので，ユーザが理想とするおける近傍 Across(Ci ) を結果を常に返すとは限らない．また, 図 9(a) のようなバナ
ナのカバーを 2 枚のパーツで作りたいとユーザが思ったと

Across(Ci ) = {v|v ∈ N eigh(vi ), vi ∈ Ci , v ∈ Cj (∀j ̸= i)},

図 6: クラスタリング，複数の凸包，カバー形状の結果．

表 2: 提案手法と文献 [1] でのカバー形状の体積の比較．

3D model

頂点数

入力モデル

Squirrel
Bunny
CameraTeddy bear
Cap & Ball
Armadillo
HandLucy
Santa

1,023
1,039
2,979
1,990
340
1,620
612
2,460
2,128

1.966
0.740
0.706
0.290
5.089
0.066
0.057
0.157
0.170

Creatinga Convex
hull
5.412
1.544
1.206
0.625
10.9680.3430.1740.890
1.111

Creating Multi-hulls(エネルギー関数 Ev )4 parts
6 parts
3.967
3.054
1.378
1.089
1.127
1.049
0.582
0.512
8.764
8.180
0.277
0.248
0.151
0.126
0.658
0.629
0.739
0.627

きに通常図 9(c) のようなカバー形状を考えるが，本手法では図 9(b) のようなカバーしかデザインできない．
また，文献 [1] で提案されたカバーデザイン手法はユー
ザが取り出し口を手動でデザインし，取り出しテストを行うことであらかじめ取り出すことが可能か否かをシステムが提示する機構を提案していた．しかし，これはカバー形状が凸包のときだけ動作し，我々のような凹を含むようなカバー形状の際は動作しないアルゴリズムであることが確認できた．我々は凹凸を含む形状でも動作する取り出しテストを今後考えたい．
さらに理論的な証明ができておらず課題として挙げられ

図 7: スキャンデータでの結果．
るのが以下の 2 点である．1 点目は提案手法の頂点クラスタリングの収束証明である．我々がテストした結果では必ず収束したがまだ証明はできていない．2 点目は生成した凸包 が他の凸包に完全に含まれるような形状にならないという証明である．もし完全に他の凸包に含まれてしまうと Lloyd [8] のアルゴリズムは使用できない．このような状態は我々がテストした範囲では起こらなかったがまだ証明できていない．

表 3: 計測時間 (RAM 3GB, 1.4GHz Intel Core 2 Duo PC.)

3D modelSquirrel
BunnyCamera
Teddy bear
Cap and Ball
Armadillo
Hand
Lucy
Santa

#vertices

1,023
1,039
2,979
1,990
340
1,620
612
2,460
2,128

Creating a
Convex hull(ms)
227
166
1,271
1,050
44282
98
543
505

Creating Multi-hulls(Energy function Ev )clustering(ms)
932
597
4,904
2,682
219
1,236
441
2,246
1,844

4 parts
Creating multihulls (ms)
114
93
476
460
21
144
50
257
286

clustering(ms)
804
568
3,976
2,041
155
1,020
416
2,227
1,673

6 parts
Creating multihulls (ms)
231
103
525
270
37
2247338
327

Computer Graphics Forum (Proceedings of PacificGraphics 2009), 28(7):1965–1973, 2009.
[2] Paul J. Besl and Ramesh Jain. Invariant surface characteristics for 3d object recognition in range images. Computer Vision, Graphics, and Image Processing, 33(1):33–80, 1986.
[3] Paul J. Besl and Ramesh Jain. Segmentation throughvariable-order surface ﬁtting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(2):167–192,
1988.
[4] Jyh-Ming Lien and Nancy M Amato. Approximate convex decomposition of polyhedra. In Proceedings of theACM Symposium on Solid and Physical Modeling, pages
121–131, 2007.

図 8: 実際に裁縫したカバー．

[5] Shengjun Liu, Charlie C L Wang, Kin-Chuen Hui, Xiaogang Jin, and Hanli Zhao. Ellipsoid-tree construction forsoid objects. In Proceedings of the ACM Symposium onSolid and physical modeling, pages 303–308, 2007.
[6] David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. Variational shape approximation. In SIGGRAPH’04: ACM SIGGRAPH 2004 Papers, pages 905–914, New
York, NY, USA, 2004. ACM.

(a) Input model(b) Cover geometry designed
using our system(c) Desired cover geometry

図 9: バナナのカバー形状の例．我々のシステムによる 2つのパーツのカバー (b) と，ユーザが望む形状 (c)．
本研究により素人のユーザが実世界にある物体のカバーを簡単にデザインすることができた．我々はコンピュータを用いることで実世界の物体の制約を素人が考えることなくデザインできるような手法を他の問題にも適用していき[7] Dan Julius, Vladislav Kraevoy, and Alla Sheﬀer. DCharts: quasi developable mesh segmentation. Computer
Graphics Forum (Proceedings of Eurographics 2005),
24(3):981–990, 2005.
[8] Stuart P. Lloyd. Least squares quantization in PCM.
Bell Telephone Laboratory Memorandum. reprint IEEE
Transactions on Information Theory, 28(2):129–136,
1982.
[9] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu,Christine D. Piatko, Ruth Silverman, and Angela Y. Wu.
An eﬃcient k-means clustering algorithm: Analysis andimplementation. IEEE Transactions on Pattern Analysis
and Machine Intelligence, 24(7):881–892, 2002.

たい．

[10] P. V. Sander, Z. J. Wood, S. J. Gortler, J. Snyder, andH. Hoppe. Multi-chart geometry images. In Proceedings of the Eurographics/ACM SIGGRAPH symposium
on Geometry processing, pages 146–155, 2003.

参考文献[11] Christoph M. Hoﬀmann. Geometric and solid modeling:a introduction. Morgan Kaufmann, 1989.

[1] Yuki Igarashi, Takeo Igarashi, and Hiromasa Suzuki. Interactive cover design considering physical constraints.