マインクラフト的なゲームのメッシュ生成

MagicaVoxel から，OBJ を介さずに UE4 に，VOX ファイルをそのままインポート出来る VOX4U というプラグインでのメッシュ生成を行うときに最適化を行ったのでそれのメモ．

本当は，昔作ったのだけれど誰も使ってないよねと放置状態だったのを，イシューとプルリクエストが連続で来て慌ててマージと機能追加を行ったのが本当のところ．

元ネタおよび，参考にしたソースはMeshing in a Minecraft Game (Part 2) | 0 FPS．パート１ではそのまま描画，カリングする，隣接するセルを結合して四角形ポリゴンを作って描画するというところまで．

四角形ポリゴンから三角形ポリゴン

多角形の三角形分割 - Wikipediaでもあるように，色々あるのだけれど単調多角形による三角形分割をしてから，あとはまあ普通に三角形に分割しようね．そして，単調多角形に分割するアルゴリズムは O(n log n) ¹ になるんだけれど，真面目にするとボクセルの数ってのは頂点数なんかより遙かに多いわけで，これはボクセルのスライスした面を走査することで O(n) ² で単調多角形を作ることでそれをカバーできるねというお話．

モノトーン化する

アルゴリズムはざっくりと

垂直方向分
- 水平方向にスキャンして，面を探す
  - 上のポリゴンがあるか，スキャンした面がある間
    - スキャンした面が上のポリゴンとくっついてる
      - 面を上のポリゴンとくっつける
      - 次の上のポリゴンにする
      - 上のポリゴンと，面を進める
    - 面が上のポリゴンより進んでる
      - 上のポリゴンは閉じる
      - 上のポリゴンを進める
    - 上のポリゴンが面より進んでる
      - 面をポリゴンにして，次の上のポリゴンにする
      - 面を進める
  - 上のポリゴンの残りを閉じる
  - 面をポリゴンにして，次の上のポリゴンにする
  - 上のポリゴンは次の上のポリゴン
上のポリゴンを閉じる

シンプルで実際に書いてみるとミスする場所もなくすっきり仕上がる感じ．

三角形ポリゴンに分割する

教科書通り．めっちゃでかい字で書いてあってめっちゃわかりやすい．

リスト = 最初の２頂点
モノトーンポリゴンの左右がある間
- P = 左右の垂直方向が小さい方
- 同一周り
  - リストが１より大きい間
    - 三角形作成リスト，リスト＋１，P
    - リストの先頭を削除
- 逆回り
  - リストが１より大きい間
    - リストの最後，リストの最後の前，P が凹
      - 終了
    - リストの最後，リストの最後の前，P が凸
      - リストの最後，リストの最後の前，P がまっすぐじゃない
        
        三角形作成リストの最後，リストの最後の前，P
      - リストの最後を削除
- P をリストに追加

階段状になっている箇所があるので，そこをスキップするところを追加って感じになる．

雑感

JavaScriptの変数のスコープってどうなっとるんじゃ？
もう２年も放置していたのか．
昔作ってたプラグインなので TSet がプロパティに出来ないため TArray 使ってたのだけれど，分割のスピード云々よりも，面のルックアップが遅すぎてそれどころの話じゃなかった．
GitHub みてたら，全く同じことを Unity でしてはった．ray-cast/UnityVOXFileImport: 🌈 A tool to import a .vox file for Unity's GameObject and Prefab

頂点の数をnとして↩
ボクセルのスライスした面の数をnとして↩