メッシュの四角面化
Blenderには、三角面を四角面にする機能があります。これは、辺の長さを考慮して溶解する辺を選んでいます。
これはこれで便利なのですが、可能な限り三角面を四角面に変えたいことがあります。
ここでは、それを数理最適化で実現するアドオンを紹介します。
具体例
下記のメッシュで試してみます。
通常の「三角面を四角面に」を実行すると下記のようになります。
隅の方に三角面ができています。
一方で、今回紹介するアドオンを実行すると下記のようになります。
すべての三角面が四角面になっています。
インストール方法
PuLPのインストール
本アドオンは、PythonのPuLPモジュールを利用しています。
そのため、下記のように、コマンドラインでBlenderにPuLPをインストールする必要があります。コマンドラインからBlenderを操作する方法については、「Blenderのコマンドサンプル」も参考にしてください。
※ バージョンは適宜変えてください。
- macOSの場合
/Applications/Blender.app/Contents/Resources/3.1/python/bin/python3.10 -m pip install pulp
- Windowsの場合
"C:\Program Files\Blender Foundation\Blender 3.1\3.1\python\bin\python" -m pip install pulp
または
"C:\Program Files\Blender Foundation\Blender 3.1\3.1\python\Scripts\pip" install pulp
※ Windowsで、インストールできるのにimportでエラーになる場合は、一旦アンインストールしてから、管理者権限のコマンドプロンプトでインストールし直すとうまくいくかもしれません。
※ 実は、Python-MIPライブラリーを使いたかったのですが、Blender3.1では動かないためPuLPを用いています。
アドオンのインストール
-
GitHubのTris-Quads-Exから、下記のアドオンのZIPファイルをダウンロードしてください。ZIPファイルは解凍しないでください。
-
Blenderのプリファレンスのアドオンで「インストール…」ボタンを押し、ダウンロードしたZIPファイルを選択します。
-
テスト中を選んでください。下図のようになるので、
Mesh: Tris to Quads Exにチェックを入れてください。
使い方
- 対象のオブジェクトを選んで、編集モードに入ります。
- 対象の範囲を選択して、面メニューの「Tris to Quads Ex」を選びます。
※ 選択している辺の中でしか溶解しません。すべてを対象にする場合は、Aで全選択してください。
- 実行後、四角面以外を選択します。
最適化について
「可能な限り三角面を四角面にする」ためには、溶解する辺の数をなるべくたくさん選ぶ必要があります。
一方で、選びすぎるとNゴン（頂点が5以上の多角形）になってしまうので、できる多角形の頂点を4までに抑える必要があります。
このような問題は混合整数最適化問題になります。
混合整数最適化問題とは何かについては、「組合せ最適化を使おう」を参考にしてください。
ここでは、混合整数最適化問題を定式化し、PuLPでモデル化しCBCソルバーで解きます。
定式化
変数は以下の条件を満たす辺ごとに0-1変数を作成します。1が溶解する、0が溶解しないに対応します。
- 選択されている
- 両側の面がともに選択された三角面である
ここでは、下記の定式化を解いて、溶解する辺を求めています。
| 目的関数 | 溶解する辺の数 + 0.1×正規化した辺の長さの和 → 最大化 |
|---|---|
| 制約条件 | 三角面ごとに、溶解する辺は1本以下 |
三角面に対し2本以上を溶解するとNゴンになるため、上記の制約条件になります。
アドオンのコード（Python）
実際に辺を溶解するのは、execute()メソッドになります。
以上