ポリゴンモデルの修正 - みたにっき＠はてな

u_1roh氏のブログで、STL修正ソフト MoNoGon のデモムービーが紹介されています。
http://d.hatena.ne.jp/u_1roh/20101017

ムービーがとてもわかりやすく、MoNoGonというソフトウェアはメッシュモデルを3Dプリンタで出力できるように修正するためのものであることがわかります。
なぜこのようなソフトウェアが必要になるかというと、3D形状を画面で見た限りではなんら問題ないように思えても、実際に物を作ろうとしたときには問題を生じるデータが、世の中には非常に多いためです。

特に3Dプリンタで形を出力しようとした場合には、物体の内側と外側が区別できなくてはなりません。
面に穴があって立体表面が閉じていない場合は、まず穴を埋める必要があります。
穴が無くなって、表面はすべて閉じているように見えても、データの構造上は閉じていない、ということも多々あります（幾何的には閉じていても位相的に閉じていない）。
このような問題は、ヒトの目で見て確認することが難しいので、ソフトウェアでチェック、さらに自動修正できるとありがたいです。

さて、私がどうしてこのソフトウェアに興味をもったかというと、私自身も以前に3DCGモデルからペーパークラフト用の展開図を作成するソフトウェアを開発した時に、同様の問題に直面して苦労したからです。
物づくりを前提としたCADソフトで作られる形にもいろいろ問題があるのですから、見た目よければOKの3DCGソフトで出力されるデータには、様々な問題が含まれます。閉じた立体でなくても構わないペーパークラフトでさえ、読み込んだままで展開図を作ろうとすると、いろいろなトラブルが発生します。

「昔は苦労したっけなぁ」と振り返りつつ、その時に直面したデータ上の問題を、いくつか紹介してみます。

■位相的につながっていない面
MoNoGonでも主にこの問題を扱っていますが、一見するとつながっているような2つの面が、実はデータ上はなんら接続関係にない場合が往々にしてあります。位相的につながっていないと、バラバラな展開図になってしまうので、幾何情報を見て接続していそうな面と面は事前に接続してあげる処理が必要になります。

■面の向きの不整合
面には表と裏があります。一見すると閉じた立体のようであっても、その表面を構成する多角形面の向きがバラバラなことがあります。全体で向きを統一しないと位相的につなげることができません。

■稜線や面の縮退
例えば、データ上では面を構成する頂点が4つあるはずなのに、実際には三角形にしか見えない場合があります。輪郭線上の2点が同じ頂点を参照している、または異なる2点が同一の座標値を持つ場合に、このような現象が起きます。稜線の長さに基づく計算を行う時にプログラムが破綻する場合があります。同様の理由で三角形面が線分になってしまうこともあり、この場合には面の面積に基づく計算を行う時にプログラムが破綻してしまいます。

■Non-Manifoldな接続（非多様体メッシュ）
異なる稜線がたまたま同じ場所に重なってしまったのであれば問題ないですが、異なる立体が同一の稜線を含む場合に、適切な展開図を作るのに失敗することがあります（組み立てようとすると紙の交差が発生するなど）。さらに、異なる立体が同一の面を含む（または複数の重複した頂点の参照を持つ）場合など、意図しない展開図ができてしまうことがあります。

■平坦でない四角形
データ上、四角形を構成する頂点が同一平面上に乗っていないことがしばしばあります。歪んだ四角形は平面に展開できないので、2つの三角形に分割して対応しますが、分割の仕方によって出来上がる立体の形が異なります。適当に分割すると、左右対称にデザインした形が左右対称にならない、などの問題が生じる場合があります。

■Hole（穴）または平面上の内部頂点の存在
下の図のように穴が存在する場合、面を1つずつ展開していくアプローチでは、数値誤差により最後にぴったり輪が閉じない場合があります。

特に下の図のように、平面上に内部頂点を多数含むような構造のポリゴンモデルは数値誤差の影響を受けやすいので、展開後にもこのままの形で展開図を出力するのは困難です。

ざっと書きましたが、上記のような問題へ適切に「自動で」対処するのは、とても難しいです。それだけでなく、各ファイルフォーマット固有の問題も多くあったりして（異なるソフトウェアで出力された場合、元のソフトウェアによって微妙に記載方法が異なるなど）、どのような形状データにも適切に対応することは、たとえそれが「展開図を作る」という単純なものであっても大変なことなのです。

ペーパークラフト用のソフトウェアを開発した時には、この「入力データに対する前処理」に膨大なエネルギーを費やしたことを思い出しながら、ざっとまとめてみました。