陰関数による形状表現 (2)

陰関数による形状表現 (1) のつづき

前回は円領域を例にとって、パラメトリック表現と陰関数表現を比較しました。そこで分かった陰関数による形状表現の利点は「集合演算がメチャ簡単！」でした。

陰関数表現にはもう一つ重要な利点があるので、それを紹介していきましょう。今回は多角形領域を例にとってみます。

多角形領域を頂点列で表すと起きる問題

しばらく陰関数のことは忘れて、このような多角形領域を n 個の頂点座標で表すことを考えてみます。つまり上図の五角形の領域を、半時計回りに並んだ5つの頂点座標で表します。この多角形領域を下記のように $P(\cdots)$ という形式で表記することにします。

P\left(p_0, p_1, p_2, p_3, p_4 \right), \quad p_i=(x_i, y_i)\in R^2

重要なポイントが2つあります。

• $P(\cdots)$ は多角形の輪郭線を表しているのではなく、塗りつぶされた多角形領域を意味しているとします。
• 頂点列は反時計回りに並んでいるものとします。（もし時計回りに並んでいたら、その領域は多角形の内側ではなく外側の領域を表しているとします。あるいは、多角形の面にオモテとウラがあるとして、時計回りに並んでいるときは多角形が裏返っているとみなす流儀もあります。いずれにせよ、このようにループの向きに意味をもたせるのはよく用いられる手法です。）

この表現、一見何の問題もないように思えて、実は面倒なことが起きます。頂点列が次の図のように並んでいたらどうなるでしょう。

このように多角形に自己交差があると、ループの向きが時計回りか反時計回りか定まりませんし、領域が単純には定まらなくなってしまいます。自己交差の交点で領域が2つに分割するとか、分割して小さい方の領域は無視するとか、考えようはあるかもしれませんが、面倒な処理が増えることは間違いありません。

このような面倒事が、陰関数表現では生じないのです。

多角形領域を陰関数で表す

では陰関数で多角形領域を表現する方法を考えてみましょう。まずは簡単な例として、次のような一辺の長さが 1 の正方形を陰関数で表現してみます。

S = \{(x,y) \mid 0\le x\le 1,\ 0\le y\le 1\}

簡単に復習しておくと、陰関数による形状表現では、陰関数 $f : R² \mapsto R $ によって図形を次のように定義するのでした。

D(f) = \{ (x, y) \mid f(x, y) \le 0 \}

では次の陰関数で表現される図形（領域）は分かりますか？

f_1(x, y) = -x

答えは、$x\ge 0$ の半空間です。 同様に、次の陰関数も考えてみましょう。

f_2(x, y) = x - 1

こちらは $x \le 1$ の半空間になりますね。

では、$0\le x \le 1$ の領域はどのように表現できるでしょうか。これは $f_1$ による半空間と $f_2$ による半空間の集合演算で表されます。

D(f_1)\cap D(f_2) = D(\max(f_1, f_2))

$y$ 方向についても同様に同様に考えることが出来ます。従って、従って正方形領域 $S$ は次のように表されることになります。 次の4つの陰関数を用意すると、

\begin{array}{lll} f_1(x, y) &=& -x \\ f_2(x, y) &=& x - 1 \\ f_3(x, y) &=& -y \\ f_4(x, y) &=& y - 1 \end{array}

正方形 $S$ は次式となります。

\begin{array}{ll} S &= D(f_1) \cap D(f_2) \cap D(f_3) \cap D(f_4) \\ &= D(\max(f_1, f_2, f_3, f_4)) \end{array}

同様のアプローチで、任意の凸多角形領域が表現できることが、容易に推測できますね。

凸でない多角形領域についても、集合演算で作り出すことが出来ます。2つの重なり合う凸多角形の和集合や差集合を想像してみれば、凸でない多角形領域が作り出せることはすぐに分かるでしょう。

さて、陰関数表現のメリットの話に戻りましょう。

頂点列で多角形を表す方法では、自己交差が存在すると面倒なことになるのでした。陰関数による表現でも同様の面倒事が生じうるかどうか、考えてみてください。

そう、陰関数表現では、どんな関数を与えても図形が定義不能になってしまうことはありません。このロバストな性質は、次の2つの観点で大変好ましいものです。

• 演算誤差や近似誤差に対してロバストである。
• 3Dで物体形状を表現したとき、実体化が不可能なあり得ないデータが生じ得ない。

前者の誤差の問題は、実務者にとっては非常に重要でクリティカルな問題なのですが、どうしても地味な議論になってしまうのでここで深入りするのは控えます。

ここでは後者の、3D の形状表現への応用例を「チラ見せ」して、この記事を終えることにしましょう。

3Dへの応用例

陰関数を3Dに拡張

陰関数表現は、容易に3Dに拡張可能です。$f(x, y, z)$ という陰関数 $f:R³\mapsto R$ によって、3D形状を次のように定義します。

D(f) = \{(x, y, z)\in R^3 \mid f(x, y, z) \le 0 \}

集合演算も、今までの2Dの議論と同様の式で定義できます。

三角形メッシュ

一方、3Dにおいて「頂点列による多角形」に相当するものは、三角形メッシュです。こういうやつですね。

三角形メッシュは、「頂点列による多角形」と同様の問題（自己交差）以外にも、面倒な問題が起こり得ます。その問題とは、主に次の3つです。

• 自己交差（多角形と同様の問題）
• 穴
• 非多様体（ここでは詳細は説明しません）

これらは何が問題なのでしょう。3Dプリンタという機械をご存知でしょうか。三角形メッシュのデータから物体を造形する装置です。その3Dプリンタに、上記の問題を含むメッシュデータを入力した場合を想像してみてください。3Dプリンタは正常に動くでしょうか？意図したとおりの形状が造形されるでしょうか？答えはNoです。

もし物体の形状をメッシュではなく陰関数によって表現すれば、このような問題は決して生じません。この著しい特性の応用例として、下記に紹介する Mesh Reconstruction が挙げられます。

Mesh Reconstruction

3Dスキャナーとか3次元測定器などと呼ばれる機械があります。この機械は、物体の3次元形状を計測して、大量の測定点の集まり＝点群（Point Cloud）を出力します。こういうやつです。

この計測点群からメッシュを生成したいというニーズがあります。そのような処理を Mesh Reconstruction と呼びます。

Mesh Reconstruction のアルゴリズムには、大きく分けて2系統のアプローチが存在しています。1つは、計測点群で得られた点と点を三角形で結んで、メッシュを構築するアプローチです。当然ながら先述したような問題を含まないメッシュが生成されることが望ましいのですが、計測点群は必ず誤差やノイズを含むものですし、このアプローチでは生成されるメッシュが問題を含まないことを保証するのは本質的に難しいといえます。

2つ目のアプローチが、陰関数を利用したものです。計測点群から直接メッシュを生成するのではなく、いったん陰関数による形状表現を経由して、間接的にメッシュを生成します。陰関数を経由することによって、不正なメッシュが生成されないことを保証できるのです。

なお、蛇足ながら補足しておくと、Mesh Reconstruction の手法として必ずしも陰関数の方が優れているとは言い切れません。陰関数を経由すると、元々の計測点群に含まれている計測誤差に加えて、陰関数による近似誤差が乗ってしまいます。このため、測定の用途では陰関数による手法はあまり好まれないようです。一方、3Dスキャンの用途では陰関数が広く利用されています。

さて、次は…

次に何を書くかまでは決めてないので、どうなるかは分かりませんけども。

最後にチラッと、「陰関数を経由してメッシュを生成する」といった話題を出しました。物体形状を陰関数で定義しても、最終的にはメッシュに変換する処理が必要になることが多いのですが、このあたりに陰関数の厄介さがあります。その辺を紹介できるといいかな、と思いつつ。