Open xchiex17 opened 6 years ago
実世界で使用可能な、異なる形のタイルがパッキングされた3Dオブジェクトを作成する手法
WEIKAI CHEN, The University of Hong Kong, USC Institute for Creative Technologies YUEXIN MA, The University of Hong Kong SYLVAIN LEFEBVRE, INRIA SHIQING XIN, Shandong University JONÀS MARTÍNEZ, INRIA WENPING WANG, The University of Hong Kong
ユーザー指定のタイルを3Dオブジェクト平面に敷き詰める最適化問題(タイルパッキング)および プリンティングおよび接続可能なパッチ(タイル群)と接続部分の決定(パッチエクストラクション)
アルゴリズムの大まかな流れは、 初期化 ⇒ Attraction phase と呼ばれるタイルの引き寄せ ⇒タイルの追加 ⇒ Repulsion phase と呼ばれるタイルの重なり除去 の流れになる。
Attraction時に解く式 以下の式を最小化するように最適化する。 :タイル間距離。 重なっている部分とタイルの境界の距離。重なりがなければ大きな値に設定に設定するため、重なる部分が小さい、でも、離れない距離を維持する為の項。 :平面とタイル間の距離。 曲率が大きい面でも適切にシミュレーションするために必要。 :点がもつ潜在的なタイルの最大直径。 接続可能にするためには、大きなタイル直径を持つ部分を接続点とする必要がある。 位置と回転角の更新により、最適化し、隙間が出来たらタイルを追加するのを繰り返す。
Repulsion時に解く式 以下の式を最大化するように最適化する。 は閾値近傍以下の距離にある近傍タイル間の距離。 スケーリングと位置調整によって最適化を行う。
タイルの接続をグラフ(木)化し、グラフを最小の木(最小スパンニングツリーと呼ばれる)に分ける。 接続は、Hingeとsnap-fitと呼ばれる２種類のものがあり、他パッチ同士を接続するのがsnap-fitと呼ばれるものになる。 2つの点piとpjでTiとTjの間にヒンジを挿入する能力c（i、j）は、前項の潜在的なタイルの最大直径であらわされる。 snap-fitの方がHingeよりも大きいc（i、j）を持つように、かつ、ツリーの平坦化/展開が有効であるように最小スパンニングツリーを計算する。 たまに、Hingeとsnap-fitが重なることがあるので、適宜位置をずらして重ならないような接続場所も探す。
異なるタイルを混ぜても、どんな3Dオブジェクトでもうまくいってそう。
位置の指定や、タイルの大きさの指定、各タイルの数の指定なども可能であることが確認できる。
従来のどのタイルパッキングよりもうまくいってる。(b),(c)がグローバル最適化の従来手法で、(d),(e)が局所最適化の従来手法。
tprintだけ時間で、他は分。
in an affordable and easy way
実世界で使用可能な、異なる形のタイルがパッキングされた3Dオブジェクトを作成する手法
論文本体・著者
WEIKAI CHEN, The University of Hong Kong, USC Institute for Creative Technologies YUEXIN MA, The University of Hong Kong SYLVAIN LEFEBVRE, INRIA SHIQING XIN, Shandong University JONÀS MARTÍNEZ, INRIA WENPING WANG, The University of Hong Kong
解きたい問題
ユーザー指定のタイルを3Dオブジェクト平面に敷き詰める最適化問題(タイルパッキング)および プリンティングおよび接続可能なパッチ(タイル群)と接続部分の決定(パッチエクストラクション)
新規性
実装
タイルパッキングについて
アルゴリズムの大まかな流れは、 初期化 ⇒ Attraction phase と呼ばれるタイルの引き寄せ ⇒タイルの追加 ⇒ Repulsion phase と呼ばれるタイルの重なり除去 の流れになる。
Attraction時に解く式 以下の式を最小化するように最適化する。
:タイル間距離。
:平面とタイル間の距離。
:点がもつ潜在的なタイルの最大直径。
重なっている部分とタイルの境界の距離。重なりがなければ大きな値に設定に設定するため、重なる部分が小さい、でも、離れない距離を維持する為の項。
曲率が大きい面でも適切にシミュレーションするために必要。
接続可能にするためには、大きなタイル直径を持つ部分を接続点とする必要がある。 位置と回転角の更新により、最適化し、隙間が出来たらタイルを追加するのを繰り返す。
Repulsion時に解く式 以下の式を最大化するように最適化する。
は閾値近傍以下の距離にある近傍タイル間の距離。
スケーリングと位置調整によって最適化を行う。
パッチエクストラクションについて
タイルの接続をグラフ(木)化し、グラフを最小の木(最小スパンニングツリーと呼ばれる)に分ける。 接続は、Hingeとsnap-fitと呼ばれる２種類のものがあり、他パッチ同士を接続するのがsnap-fitと呼ばれるものになる。 2つの点piとpjでTiとTjの間にヒンジを挿入する能力c（i、j）は、前項の潜在的なタイルの最大直径であらわされる。 snap-fitの方がHingeよりも大きいc（i、j）を持つように、かつ、ツリーの平坦化/展開が有効であるように最小スパンニングツリーを計算する。 たまに、Hingeとsnap-fitが重なることがあるので、適宜位置をずらして重ならないような接続場所も探す。
実験・議論
Results
異なるタイルを混ぜても、どんな3Dオブジェクトでもうまくいってそう。
位置の指定や、タイルの大きさの指定、各タイルの数の指定なども可能であることが確認できる。
従来のどのタイルパッキングよりもうまくいってる。(b),(c)がグローバル最適化の従来手法で、(d),(e)が局所最適化の従来手法。
tprintだけ時間で、他は分。
Limitation and future work
読んだ中での不明点などの感想
in an affordable and easy wayとあったり、Fig.2からプリンティングの方法として複数のサポートがあるようなのだが、それぞれのサポートを入れるのがどれほど手間のかかることなのか3Dプリンタ使ったことないからよくわからなかった。関連論文