読者です 読者をやめる 読者になる 読者になる

CGとCVの日記

Computer GraphicsとComputer Visionについて

メッシュから3Dプリント可能なワイヤフレームを作る

ボリュームワイヤモデル

太さをもったワイヤフレームモデルをボリュームワイヤと呼びます(勝手に読んでます.
Shapewaysという3Dプリントされたものを購入することができるwebサイトでもアート作品としてボリュームワイヤモデルが売られています.
f:id:daiki_yamanaka:20130815002539p:plain:right

アートとしてだけでなく実用的な応用もあります.安価な機器が登場したり3Dプリンタは一般にも普及してきましたが,材料費や造形時間などのコストはまだまだ3Dプリンタの解決すべき問題です.
ボリュームワイヤを使えば少ないコスト(時間,材料)で物体の形状を表現することができます.
プロトタイプの造形のような物体の形状を素早く見たいときに適しているかもしれません.

SIGGRAPH ASIA 2013にも"Cost-effective Printing of 3D Objects with Skin-Truss"というタイトルの論文が発表されています.タイトルから察するにサーフェス上のTruss(ワイヤ)を使って時間や材料などのコストを考慮した3Dプリンティングのためのモデリング技術の研究だと思います.
このような3Dプリンタの問題をモデリング技術でソフトウェア的にうまく解決する研究はとてもおもしろいと思います.

ボリュームワイヤの作り方

入力メッシュ
f:id:daiki_yamanaka:20130815003119p:plain:w300
ボリュームワイヤモデル
f:id:daiki_yamanaka:20130815003129p:plain:w300
3Dプリンタで作成したモデル
f:id:daiki_yamanaka:20130815003223p:plain:w300


このようにメッシュモデルを3Dプリンタで造形可能なボリュームワイヤモデルに変換します.
ボリュームワイヤを作る方法はいろいろと考えられれますが,陰関数を使いました.
入力メッシュのエッジ一本一本を独立した陰関数で表現し,それを合わせることで全体のモデルを作成します.
実装にはCGALを使いました.
ソースコードこちらです.
ある点の関数値を評価するのにすべてのエッジをチェックしてるので遅いです.
Kd-treeなどで空間的にソートしてあげると高速化できると思います.

Poisson Disk Sampling による Image Stippling

Poisson disk samplingによるimage stipplingを実装してみました.

Stipplingとは


Stipplingとは点のパターンで画像を表現することです.
アートの世界では点刻と呼ばれているようです.
このような画像をコンピュータで生成するには
画像の輝度値のような与えられた値にたいして点の密度を変えることが必要となります.
ここでPoisson Disk Samplingが登場します.

Poisson Disk Sampling とは

ランダムかつ点同士がある距離以上離れているようなサンプリングをPoisson Disk Samplingと呼びます.
blue noise property
もともとは画像をレンダリングする際のantialiasingのための技術で,
CGの分野では"Stochastic sampling in computer graphics"で初めて登場しました.
この中で著者はpoisson disk samplingを周波数的に解析し(ローパスフィルタを打ち消すような周波数特性になっている),
なぜantialiasingとして有効なのかを議論しています.
猿の目のphotoreceptorの配置も規則的ではなくblue noise samplingのような配置になっているそうです.

antialiasing以外にもimage stipplingやtexture synthesisなど様々な応用があります.
Poisson disk samplingの周波数はblue noiseというカテゴリに属し,
Poisson disk samplingを含んだblue noiseの生成方法の研究はComputer Graphicsの分野でホットなトピック
となっています.

実現方法

Poisson disk samplingを実現する手法として大きく2つに分けられます.

Dart throwing

これはその名の通りダーツを投げるようにある領域に対しランダムに点を発生させ,その点を中心とする円の内部に点が存在しない場合,その点を採用するという手順を繰り返すことで分布を発生させます.

  • Fast Poisson Disk Sampling in Arbitrary Dimensions

任意の次元で高速にサンプリングする方法を提案しています.

Voronoi graph

とても多いので最新のものを幾つか挙げておきます.

  • Variational blue noise sampling

Centroidal Voronoi tessellationのエネルギー + Capacity Constrained Voronoi tessellationのエネルギーを目的関数とするCapacity-constrained-centroidal voronoi tessellationを提案

  • Blue noise through optimal transport

Capacity Constrained Voronoi tessellationを連続関数の最小化問題として再定義,

実装

今回は"Fast Poisson Disk Sampling in Arbitrary Dimensions"を参考に実装しました.
半径が一定の場合の結果がこちらです.


画像の輝度値に応じて半径を変えることでstipplingをすることができます.

3Dプリンタを造形方式別に比較してみた

最近よく話題になっている3Dプリンタには様々な造形方法が存在します.
それらを比較してみたいと思います.

f:id:daiki_yamanaka:20130313150737j:plain:w350

比較するプリンタは
・Cube
・uPrint SE Plus
・ZPrinter 250
・ProJet 1500
です.
Cubeが1299$と一番安く.それ以外は数百万円ほどです.
個人向けではない3Dプリンタの中では安い価格帯のものだと思います.


造形モデルとしてはこちらのモデルを使います.f:id:daiki_yamanaka:20130313152154p:plain:w250:right
鋭い特徴(Sharp features)と曲率(緩やかなところから勾配が急なところまである)の観点からこれを選びました.
このモデルはAim@Shape Project - Shape Repositoryから入手可能です.

熱溶解積層法

まずは熱溶解積層法です.
その名の通り熱で溶かした材料を積層していきます.
仕組みが簡単なのでとても安価なモデルが登場しています.最近話題の個人向けの3Dプリンタもほとんどこの方式を採用しています.
今回比較する3DプリンタではCubeとuPrint SE Plusがこの方式のモデルになります.

まずこちらが1299$のCube で造形したモデルです.
f:id:daiki_yamanaka:20130313145338j:plain:w400
このCubeはサポート材として造形物と同じ材料を使うためサポート材を取り除くときにどうしても後が残ってしまいます.
積層ピッチは0.25mmですので見た目が結構ギザギザしています.
f:id:daiki_yamanaka:20130313150905j:plain:w400

次はuPrint SE Plusです.
これは水溶性のサポート材を使っているので痕などは残っていません.
f:id:daiki_yamanaka:20130313144851j:plain:w400
この3Dプリンタも積層ピッチはCubeと同じ0.25mmなのでギザギザが目立ちます.
f:id:daiki_yamanaka:20130313144901j:plain:w400
細くて造形できないような部分はドライバソフトが太らせるそうです.
f:id:daiki_yamanaka:20130313144857j:plain:w400

積層ピッチは同じでも制御系などが違うため造形されるモデルにもかなり違いがあります.
f:id:daiki_yamanaka:20130313145455j:plain:w400f:id:daiki_yamanaka:20130313145504j:plain:w400
例えばこのフタ付きの入れ物では,入力モデルはフタと本体の間に0.1mm程度の隙間があるのですが,Cubeで出力したモデルは閉まりません.
やはり値段が高いほうが制御系も高精度ですので精度が高いものが造形できます.

今回比較した3Dプリンタの中で熱溶解積層方式は同じ価格帯で比較すると他の方式よりも積層ピッチが粗いです.
しかし,材料がABS樹脂ですので粘りがあり強度は一番高いでしょう.
フィギュア等ではなく負荷のかかるパーツなどに向いているような気がします.

紫外線硬化方式

次は紫外線硬化方式です.
紫外線硬化樹脂の液面に紫外線レーザーをあてて造形していきます.
後処理として2次硬化,その後洗浄する必要があります.
なので3Dプリンタ本体,2次硬化用の機器,洗浄機が必要となり場所と手間を食います.

造形したモデルに関しては,積層ピッチが0.1mmと他の機種と比べると小さいため,見た目は一番きれいだと思います.
f:id:daiki_yamanaka:20130319222947p:plain:w400
表面がなめらかで触り心地もなかなか良いです.
f:id:daiki_yamanaka:20130313144717j:plain:w400
先端付近もよく表現できていると思います.
f:id:daiki_yamanaka:20130313145559j:plain:w400
サポート材は同じ材質です.さらにサポート付近がすこし盛り上がってしまいます.
f:id:daiki_yamanaka:20130313145725j:plain:w400
これは表面張力が原因だと思います.きれいに剃るには後処理が必要ですね.
材料はアクリルなのでABS樹脂とまではいかないまでもそこそこ粘りはあります.熱溶解積層方式と同様負荷がかかるパーツにも適している
と思います.

しかし,寸法は期待できないと思います.
フタ付きの入れ物はフタを閉めることができませんでした.
f:id:daiki_yamanaka:20130313145749j:plain:w400f:id:daiki_yamanaka:20130313145807j:plain:w400
精度について問い合わせてみたのですが公表していないということでした.
紫外線硬化方式で精度を必要とするなら数千万クラスのものを購入してくれとのことでした.

粉末固着方式

接着材が含まれたインクを吹きつけて粉を固めて造形していきます.
カラーのインクを使うとカラフルなモデルが作れます.
このZPrinter 250 では64色が表現可能です.
他の方式では色を付ける場合材料自体を変える必要があるので,かなり楽です.

造形物は少し粉っぽいというかざらざらしていますが積層ピッチが0.1mmということもあり見た目もとてもきれいです.
f:id:daiki_yamanaka:20130313144748j:plain:w400
f:id:daiki_yamanaka:20130313144805j:plain:w400

積層ピッチ0.1mmに対して最小造形サイズが0.4mmとのことなので細かい部分は表現しづらいようです.
f:id:daiki_yamanaka:20130313144751j:plain:w400

フタ付きの入れ物は問題なく閉まりました.寸法にかんして上の2機種が大きめに出るのに対して小さめに出る傾向がある気がします.
f:id:daiki_yamanaka:20130313145949j:plain:w400f:id:daiki_yamanaka:20130313150012j:plain:w400
石膏ベースの材料なので負荷には弱いです.力をかけるとすぐ壊れそうです.

まとめ

造形方式によって様々な特徴があるので用途によって選ぶ必要がある.
値段が高ければ高いほど性能がよい.

Chopper: Partitioning Models into 3D-Printable Parts

論文

Siggraph Asia 2012 の論文です.

 

3Dプリンタで出力できない大きなモデルを複数のパーツに分割します.

分割の表現にはBSPを使っています.

分割面の探索範囲は正10面体を3回subdivisionして各頂点と中心を結ぶ129方向で,

BSPの探索にビームサーチ(Beam Search)を使っています.

ビームサーチとは幅が決まった幅優先探索みたいなものです.

  

探索範囲とアルゴリズムが決まったので,次は目的関数です.

この論文では幾つかの目的関数の重み付き和をグローバルな目的関数にしています.

・パーツの数

    任意のオブジェクトをカバーするboxを求めるのはNP困難

    最小のパーツの数を求めるのではなく,アルゴリズムの終了を優先

    パーツの大きさが小さくなることがあるので正則化も考える

 

・コネクタのfeasibility

     パーツには組み上げた時に落ちないように一個以上のコネクタをつける

     コネクタの質が最大になるようなcutを選びたい

     コネクタの凸包を考え,cross-sectionと凸包の面積の比を目的関数に使う

     

・Structural Soundness(応力が集中するような分割は避ける)

     ○structure

     まず,regular gridにvoxelize -> 1 voxel あたり6つの四面体を作る

     四面体の頂点の5%を固定

     ユーザが指定したモジュールと密度の外力(方向もユーザ指定)を与える.

     結局,目的関数は応力(せん断,垂直)

 

     ○fragility

    構造解析だけだと計算時間がかかるのでヒューリスティクスを追加.

     薄い"fin"や"bridge"は避けたい.

     一つでも好ましくないcutがあると∞になるような目的関数

 

・分割の美しさ

     ○ seam unobstrussiveness

     パーツの継ぎ目は見えないほうがいい

     継ぎ目はself-occlusionのある部分や,テクスチャのエッジがないところが好ましい

     もしくはユーザが大事な部分を指定,そこを避けるようにseamを配置

     ○ symmetry

     symmetryを見つけるために,まず,ある面(500個)に対し反射したモデルと入力モデルのHausdorff distanceを計算(uniformly sampled 10000 points)

     距離の合計を対称性項の目的関数とする

 

各目的関数がもとまり,これらの重み付き和が最終的な目的関数となります.

その重みは実験的にうまくいったもの(例えばα_symmetry = 0.25)を使う.

 

結果としてman-madeのカクカクしたものから自由曲面を持ったモデルまでいろんな入力で分割して実際に3Dプリンタで出力して組み立てていた.

ユーザテストとして,ユーザが行った分割と比較して,Chopperのほうがパーツの数が少ないし,目的関数の値も小さい(当たり前だと思うけど)と主張していた.

 

 

読んでみた印象として,マジックナンバーが多い気がする(129方向とか各目的関数の重みとか).

まぁ分割できてるからいいんだろうけど.

teaserの椅子を作って実際に座っている図が印象的でした.

 

 

 

 

 

Support Vector Machines for 3D Shape Processing

SIGGRAPH 2012 に"Object-Space Multiphase Implicit Functions"

という複数材質の陰関数を求める論文がありました.

これはラベル付けされたvolumeを入力としていて,Octreeのノードなどの小領域一つに

SVMにより最適化した陰関数をあてはめます.

SVMで陰関数をfittingしてSurface Reconstructionをするというのが面白かったので,

おそらく陰関数のfittingを使ったSurface ReconstructionにSVMを初めて使ってであろう

”Support Vector Machines for 3D Shape Processing”という論文を読んでみました.

Eurographcis 2005年の論文です.

  • Introduction

この論文以前は点群からの陰関数のフィティングにはparametricな方法が使われるのが一般的でした.

例えば点一つ一つにRBFを当てはめる手法や,Octreeのノードにcompact support な関数を当てはめる手法(MPU)等.

それを当時流行っていたKernel法を使ってnon-parametricに点群に陰関数を当てはめる

というのがこの論文の目的です.

さらに,この手法を使って,2つの陰関数に対して,surface上の点だけでなく周りの点のdeformation fieldを計算しています(要するにvolume間のマッピング).                                                      

 

  • Algorithm

まずはsurfaceのモデル化です.kernel法を使うので,陰関数f(x)は3次元から任意のヒルベルト空間Hへの射影Φ(x)とヒルベルト空間のベクトルwとの内積で表すことができます.

曲面上の点はf(x)=0, 曲面内の点はf(x) < 0, 曲面外の点はf(x) > 0を満たすような関数fを求めたいわけです.

fを計算するにはヒルベルト空間での内積を計算する必要があるのですが,このΦと内積計算を組み合わせた関数k(x, y)を定義するこで計算量を抑えることができます.

この論文でもfをカーネル関数k(x, y)を用いて

f(x) = \sum^{m}_{i=0}\alpha_{i}k(x_i,x)+b

このように定義しています.

あとは通常のSVMと同じようにwの正則化項とペナルティを最小化する目的関数とし,上の式のαを求めます.

 

次に3D deformation fieldの計算です.すでに2つの陰関数f1とf2がわかっているとし,この変換をτとおきます.このτもfと同じようにヒルベルト空間のベクトルwdと射影Φとの内積で表されます.

さらに2つの陰関数の特徴的な点(xi, zi)のcorrespondanceもわかっているとします.

すると目的関数はwのノルム最小化とcorrespondenceの誤差の最小化とτで変換後の関数値の誤差の最小化となります.

 

あとはMultiscale でやってDenoisingやHole fillingができるとか計算速度の話とかいろいろ書いてありました.

 

これは陰関数のfittingの話だけど,multi materialのsegmentationに使えないか考え中です.

VASE: Volume-Aware Surface Evolution for Surface Reconstruction from Incomplete Point Clouds

論文

Eurographics Symposium on Geometry Processing(SGP) 2011の論文.

点群からの Surface Reconstructionの話.
著者の研究グループはSIGGRAPH ASIA 2010に"Cone Carving for Surface Reconstruction"という不完全な点群からvisibilityを考慮して
Surface Reconstructionをするという論文を出していて,これに関係しています.

深く凹んでいたり穴が開いていたりする物体は光学式の点群スキャナを使っても完全に点群が取れない場合があります.
この点群をつかって従来の手法(RBF使うやつ, Poisson Surface Reconstruction)でSurface Reconstructionを行うと
元の物体とは違ったSurfaceが得られるという結果になってしまいます.

そこでこの研究では最適化の式にdata fittingとsmoothnessの項だけでなくVolumeの項を追加しています.
fittingの前には先ほど紹介したvisibilityを使う手法で大まかにSurfaceを出しておいて,体積を考慮してSurfaceを
きれいにします.

具体的には体積をMedial AxisとMedial Axis上の点を中心とした球と考え,その球の半径Rのラプラシアン積分
を最小化します.

点群からSurfaceをReconstrucitonする研究は2000年代前半がとても盛んで,
Surfaceを表す陰関数をRBFで近似する方法"Reconstruction and Representation of 3D Objects with Radial Basis Functions" [2002, SIGGRAPH]や
SurfaceのGradiantがなめらかになるようにSurface Reconstructionする "Poisson Surface Reconstruction"[2006, SGP]が有名です.

最近はこの論文のように不完全は点群からの再構成や,ワイヤ状のものや,木とか計測しにくいものを対象とした論文も増えています.
また,Reconstructionするだけでなくそのあと(EditできるようにTopologyもきちんとReconstructionする)に注目した論文もあったりします.


話は変わってPCLのSurface Reconstructionの動画

陰関数のfittingしてMarching Cubesで面はってる感じがする.
そしてRenderingのときにSmoothingしてるかんじ?
この動画みるとまだやることあるなーって感じる.

Surface Reconstructionに体積を考えるってすごくおもしろいよなー.こんな研究したい.

Lp Centroidal Voronoi Tessellation and its Applications

論文

INRIAの研究者 Bruno LevySIGGRAPH 2010の論文です.

Mesh Processing がよくまとまっているこの本の著者の一人です.

Polygon Mesh Processing

Polygon Mesh Processing


ここにスライド等もあります.
http://www.pmp-book.org/


通常のCVTではボロノイ点から各点のL2ノルムを最小化します.
有名な方法はLloyd’s algorithmで,ボロノイ領域の点をボロノイ領域の重心に移動させることで均等にボロノイ点を配置することができます,
これを収束するまで繰り返すとボロノイ領域が綺麗にtessellationされます.
応用としてはリメッシングがあります.
CVTで拡張点を移動させて元のメッシュにプロジェクションしてあげるとクオリティの高いメッシュにリメッシングすることができます.


この論文ではそのCVTのL2ノルムだけでなくLpノルムの最小化を考えるように一般化しています.
Lpノルムを考えるとなにがいいかというと,L2ノルムの場合では,等距離の領域が円状になりますが,
L∞ノルムの場合では正方形に限りなく近くなります.正方形の領域だと四角形の領域にきれいに並べることができます.
この論文ではさらにノルムに対して変換行列Mを考えてあげることによりanisotropic な領域で距離を等しくすることができます.

Applicationとして.Anisotropic Remeshing や,Fully Automatic Feature-Sensitive Remeshing(これはFeatureにタグ付けしているし,もとのSurfaceがわかっている状態)
Variational な quad meshing(L8でだいたい正方形っぽくなって,Voronoi領域の四角形が綺麗にならぶので隣接するVoronoi点を結んであげるとquad meshになる), Hex meshing などが紹介されている.

Supplymental Material の気合の入り方もすごい.