この記事は Blender Advent Calendar 2020 6日目の記事です。

この記事ではメッシュを構成する四角ポリゴンやNゴンを平坦化する Make Planar Faces という機能と、その実装について説明します。
ソースコードは Blender 2.90.1 のものを参照しています。

Make Planar Faces の機能の概要

4つ以上の頂点から構成される面¹（四角ポリゴンやNゴン）では、すべての頂点が同一平面¹上に存在するとは限りません。
たとえば、以下のような面では、すべての頂点を含むような平面は見つかりません。

Make Planar Faces は、このような歪んだ面を平坦な面に近づけます。²
下図の灰色の面は黒い面に Factor=0.5 として Make Planar Faces を適用したもので、白色の面は黒い面に Factor=1.0 として Make Planar Faces を適用したものです。
図を見るとわかるように、Factor=0.5 の面の各頂点は元の面と Factor=1.0 の面の対応する頂点のちょうど中間にあります。

Factor で1回の操作で各頂点をその移動先へどの程度近づけるのかを指定し、Iteration でこの操作を何回繰り返すかを指定します。

Make Planar Faces の機能の実装

機能の概要では「移動先に近づける」といった抽象的な表現を使いましたが、この節ではそれらの操作が具体的にどのような処理で実現されているのか説明します。

Make Planar Faces に直接対応する関数は source/blender/editors/mesh/editmesh_tools.c の edbm_face_make_planar_exec() に実装され、source/blender/editors/mesh/mesh_ops.c でメッシュに対する操作として登録されています。

edbm_face_make_planar_exec() では、複数のオブジェクトから³それぞれのメッシュを取得して、それぞれのメッシュに対して、メッシュ内のそれぞれの面を平坦化する処理を行います。
メッシュ内のそれぞれの面を平坦化する処理は blender/bmesh/operators/bmo_planar_faces.c の bmo_planar_faces_exec() に実装されています。

`bmo_planar_faces_exec()` の実装

Make Planar Faces の実際の処理にあたる bmo_planar_faces_exec()について説明します。

最初にメッシュ内の面を3頂点の面とそれ以外の面に分け、3頂点でない面に含まれる頂点の合計を計算します。
3頂点の面はもともと平坦なので、3頂点でない面と頂点を共有していない限り、3頂点の面に含まれる頂点は処理する必要がありません。

その他にいくつかの初期化処理が実行された後、面を平坦にする処理が始まります。
この処理は Iteration で指定された回数だけ繰り返されます。
面を平坦にする処理は以下のようなものです。

処理する必要がない3頂点の面をスキップして、メッシュ中の各面に対して以下の処理をする
1. 処理中の面と法線が同じで、処理中の面の幾何重心を含む平面を計算する⁴
2. 処理中の面の各頂点について以下の処理をする
処理する必要がある面に含まれる各頂点に対して以下の処理をする
1. 移動元の頂点から移動先の頂点への距離がεを超えていた場合
  1. この頂点を処理対象に再度追加する
  2. 移動元$v_1$と移動先$v_2$と Factor $k$ に対して結果 $v = (1-k)v_1 + kv_2$ を計算する⁷
2. 処理中の頂点を含む面すべてを処理対象に再度追加する
2の1で移動元から移動先への距離がεを超えた頂点がひとつも無かった場合、Iteration で指定された回数を繰り返す前に終了する
頂点の移動元と移動先の関連付けを初期化する

繰り返しが終了すると、メモリを開放して終了します。

まとめ

実装を調べた時に書いたメモを整形して記事にしたら、何が書きたかったのかよく分からない記事になってしましました…

Make Planar Faces の実装やベクトル計算の実装を振り返ると、全体的に処理速度を意識した実装になっていたように思います。
重複した計算を避けたり、時間のかかる計算を避けたりするように実装されていました。
Blenderの起動や処理が速い背景には、こういった地道な高速化もあるようですね。

「面」と「平面」を区別して書いています。面は3つ以上の頂点と、それらを循環するようにつなぐ辺と、法線を持ちます。 ↩
Make Planar Faces は、すべての頂点が正確に単一の平面に含まれるように変形するわけではなく、少しずつ平坦に近づけていきます。 ↩
Blender 2.80 よりも古いバージョンでは選択中の単一のメッシュに対してしか適用できなかったようです。 ↩
平面は4つの浮動小数点数で表現されます。法線ベクトルのx, y, z要素と、原点から平面への距離に法線ベクトルの長さをかけた値が格納されています。 ↩
法線ベクトルに沿って頂点を移動させ、平面に最も近い点を計算します。平面がうまく表現されているので、簡単に計算できます。 ↩
他の面で同じ頂点が処理されていた場合、移動先の頂点が複数あることになります。メモリに保存される値はこれらの幾何重心を取るように計算されます。 ↩
結果として、$|v_1-v| : |v_2-v| = k : 1-k$ になります。 ↩