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の椅子を作って実際に座っている図が印象的でした.