三角形メッシュとオイラーの公式

前回（3次元CADを支えるオイラーの公式 - カタチづくり）の続きを書くよ。今回はオイラーの公式を三角形メッシュに当てはめてみよう。ここでいう三角形メッシュとは、次の図のようにすべての面が三角形で出来た立体のことだ。

前回書いたように、オイラーの公式とは次の式のこと。
$v-e+f=2(1-g)$
ここで $v, e, f$ はそれぞれ頂点の数、辺の数、面の数を表している。
さて、三角形メッシュというのはその名の通りすべての面が三角形なわけだ。その性質を考えると、 $v, e, f$ の間にはなんらかの関係があるんじゃないか、と予想できる。ここではその関係式を明らかにして、それをオイラーの公式に代入していく。そうして得られた式からは、三角形メッシュならではの面白い性質が明らかになるのだ。
次の2つの事実に着目しよう。

三角形メッシュに限らず、すべての辺は2つの面に挟まれている。そもそも2つの面の境界線を辺と呼んでいるのだから、これは当たり前の話。
三角形メッシュのすべての面は辺を3つ持っている。三角形なんだからこれも当然。

以上を考えると、次の式が成立する。
$e=\frac{3}{2}f$
これは次のように考えると分かりやすい。三角形は辺が3つだから、単純に考えると辺の数は三角形の3倍、つまり $e=3f$ 。しかしすべての辺は2つの三角形に共有されているのだから、上記の式が得られる。
これをオイラーの公式に代入すると、こうなる。
$v-\frac{3}{2}f+f=2(1-g)$
$\Leftrightarrow 2v-f=4(1-g)$
これが三角形メッシュにおけるオイラーの公式だ。ここで $g$ に対して $v,f$ が十分大きい場合を考えてみよう。その場合には右辺は無視できるので、次の近似式が得られる。
$f \approx 2v$
なんと、三角形メッシュの面数は頂点数のほぼ2倍なのだ！たまにメッシュデータのデータ量を把握するために面数と頂点数を両方調べようとする人がいるが、片方が分かればもう片方も分かるのである。頂点数だけ調べれば、面数は2倍するだけで把握できる。
ちなみに、すべての面が四角形のデータでは次の式が成立する。
$e=2f$
これをオイラーの公式に代入すると次式が得られる。
$v-f=2(1-g)$
つまり、右辺に対して頂点数や面数が十分大きい場合には、次の近似式となる。
$f \approx v$
四角形メッシュでは頂点数と面数はほぼ同じでなのだ。これは正方形のパネルが無限に敷き詰められた床を想像すると分かりやすい。そのような床のパネルの数は明らかに頂点数と同じだよね。
今回はこの辺で。