メッシュ表面のランダムな座標を計算する　前編

Unityでメッシュ上にあるランダムな点を取得する方法をメモメモ…

※このページの内容の動作確認にはUnity2018.2を使用しています。

たとえば「あるメッシュの表面に沿って別のオブジェクトをランダムに配置したい！」という場合にどうやってその座標を取得するか、という話です。手っ取り早く実装するなら「メッシュの外側から中心方向に向かってランダムに Ray を発射し、メッシュコライダーと衝突した地点を取得する」という方法が楽で便利だと思います(参考: Unity 地表に沿ってオブジェクトを配置する)。ただ、その方法だと Ray の当て方やメッシュの形状によっては均等に取得できないので、今回はもう少し厳密に計算して求める方法を考えます。

アプローチとしてはこんなかんじ↓

メッシュを構成する三角形のうち1つをランダムに選ぶ
選んだ三角形の内側にある点をランダムに算出する

注意しないといけないのは 1. の三角形の選び方です。すべての三角形を同じ確率で選んじゃうと偏ってしまうので、面積に応じて選ばれる確率を変えないといけません。つまり、広い面ほど確率が高く、逆に小さい面ほど確率を低くする「重み付き」のランダムにする必要があります。

重み付きランダム抽選

まずはその「各要素の重みに応じて抽選をする」機能をつけましょう。すぐに思いつくのはこういう方法。

int WeightedRandomIndex(params float[] weights)
{
 float total = weights.Sum();
 float value = Random.Range(0, total);
 for (int i = 0; i < weights.Length; i++)
 {
  value -= weights[i];
  if (value <= 0) return i;
 }
 return -1;
}

ループ処理で「重み」を順に足していく(あるいは引いていく)やり方です。

通常はこの方法で大丈夫なのですが、今回のようにメッシュの三角面が対象になる場合、要素数が数千とか数万の単位になることが予想されます。そうなると抽選のたびに毎回ループ処理を行うのは非効率ですよね。

そこで、今回は Walker's Alias Method という手法を使ってランダム抽選を実装してみたいと思います。 Walker's Alias Method についての詳しい説明はこちらのページが(タイトルどおり)すごくわかりやすかったので、ぜひご一読ください。

Qiita - Walker's Alias Methodの箱の作り方のわかりやすい説明

めちゃめちゃ簡単に言ってしまうと「あらかじめ重みの大きい要素の一部と重みの小さい要素をセットにしておくことで、値を取り出すときにループ処理を使わなくてもいいようにする手法」です。このアルゴリズムを使えば、多少の前処理が必要になるものの、実際の抽選はO(1)、つまり要素数が10個であろうが10000個であろうが毎回一定の計算時間で済むようになります。というわけで Walker's Alias Method を使った重み付きランダムをUnityで使えるよう、上記のページのコードを参考にC#で書いてみました。

using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// Walker's Alias Method を利用した重み付きランダム抽選用クラス
/// </summary>
public class WeightedRandom
{
 float[] weights;
 float totalWeight = 0;

 float[] thresholds;
 int[] aliases;

 /// <summary>
 /// 重み付きランダム用オブジェクトを作成する
 /// </summary>
 /// <param name="weights">各要素がどれだけの重みを持っているかのリスト</param>
 public WeightedRandom(float[] weights)
 {
  ResetWeights(weights);
 }

 /// <summary>
 /// 重み付けを設定しなおす
 /// </summary>
 /// <param name="weights">各要素がどれだけの重みを持っているかのリスト</param>
 public void ResetWeights(float[] weights)
 {
  int length = (weights != null) ? weights.Length : 0;
  this.weights = new float[length];
  if(length != 0) System.Array.Copy(weights, this.weights, length);

  CreateAliasList();
 }
 
 // 抽選用の内部リストを構築する
 // 各要素を1ブロックとして扱う 各ブロックの重みは1になるように調整(正規化)する
 void CreateAliasList()
 {
  int length = weights.Length;
  
  thresholds = new float[length];
  aliases = new int[length];
  totalWeight = 0;
  
  // 重みの合計を算出
  for (int i = 0; i < length; ++i)
  {
   // 重みがマイナスだった場合は 0 にしておく
   weights[i] = Mathf.Max(weights[i], 0);
   totalWeight += weights[i];
  }

  // あとで重みの正規化を行うため割合を計算しておく
  float normalizeRatio = (totalWeight != 0) ? length / totalWeight : 0;
  
  Stack<int> small = new Stack<int>();
  Stack<int> large = new Stack<int>();
  for (int i = 0; i < length; i++)
  {
   // エイリアス初期化
   aliases[i] = i;

   // 重みを要素数で正規化
   float weight = weights[i];
   weight *= normalizeRatio;
   
   thresholds[i] = weight;
   
   // 重みがブロック内に収まるものとはみ出るものとで振り分けていく
   if (weight < 1f)
   {
    small.Push(i);
   }
   else
   {
    large.Push(i);
   }
  }
  
  // 重みの小さい要素に重みの大きい要素のはみ出た部分を移動させてブロックを埋めていく
  while (small.Count > 0 && large.Count > 0)
  {
   int s = small.Pop();
   int l = large.Peek();

   aliases[s] = l;
   thresholds[l] = thresholds[l] - (1f - thresholds[s]);
   
   if (thresholds[l] < 1f)
   {
    small.Push(l);
    large.Pop();
   }
  }
 }
 
 /// <summary>
 /// 各要素の重みを考慮しながらインデックスを1つ抽出する
 /// </summary>
 public int GetRandomIndex()
 {
  int length = weights.Length;

  float random = Random.value * length;  
  int index = (int)random;
  if (index == length) index = length - 1; // Random.value = 1.0 だった場合
  float weight = random - index;
  
  // ランダムな値の小数部分(weight)がブロック内で設定された重みの基準値(thresholds)
  // を超えたらエイリアスを返す
  if (weight < thresholds[index])
  {
   return index;
  }
  return aliases[index];
 }
}

長っ！

とりあえずこれを WeightedRandom という名前のスクリプトにコピペすれば使えるようになります。

メッシュから三角形を1つ取り出す

では、さっそくこの重み付きランダム抽選用クラスを使って三角形を取得してみましょう。

// meshには対象のメッシュデータ(Mesh)が入っているとする
Vector3[] vertices = mesh.vertices;
int[] triangles = mesh.triangles;
int trisNum = triangles.Length / 3;

// すべての三角形の面積を計算
float[] areas = new float[trisNum];
Vector3 p1, p2, p3;
for (int i = 0; i < trisNum; i++)
{
 p1 = vertices[triangles[i*3]];
 p2 = vertices[triangles[i*3+1]];
 p3 = vertices[triangles[i*3+2]];
 areas[i] = Vector3.Cross(p1 - p2, p1 - p3).magnitude * 0.5f;
}

// ランダム抽選用オブジェクトを準備
WeightedRandom weightedRandom = new WeightedRandom(areas);

// 各三角形の面積を考慮しつつランダムなインデックスを取得
int randomIndex = weightedRandom.GetRandomIndex();

ポイントは三角形の面積の求め方です。…といってもこれは簡単で、三角形の頂点の座標(p1, p2, p3)さえわかっていれば、あとは14行目のように1行で計算できます。

「2つのベクトルの外積(Vector3.Cross)の大きさ(magnitude)は、そのベクトルが構成する平行四辺形の面積に等しい」ので、三角形の面積を求めたい場合はそれをさらに半分(*0.5f)にすればいいというわけです。ただ、今回の場合は厳密に面積を求める必要はなく、それぞれの三角形の面積比さえわかれば重み付けができるので、実は最後の *0.5f は別になくても構いません。むしろパフォーマンス的にはないほうがいいです…。

あとはさっき作成した WeightedRandom クラスに三角形の面積のリストを渡して、重み付きのランダムなインデックスを返してもらうという流れです。

ためしに抽選を何度も繰り返して、選ばれた三角形の頂点を少しずつ赤く塗っていくとこんな感じになります。赤くなっている面ほど高い確率で選ばれているということなので、面積の大きい三角形は赤くなっているはずで…　いや、気持ち悪っ！「学校の怪談」に出てくる人体模型みたいでめちゃめちゃ怖い！結果もよくわからん！

というわけでサイズの違う三角形を綺麗に並べたモデルで再確認。はい、たしかに面積が大きい三角形ほど赤くなっていて、高確率で選ばれていることがわかりますね。一応ちゃんと機能しているようで一安心です。

…とか書いてるうちにちょっと記事が長くなってしまったので、前編・後編に分けることにします。続きの「選んだ三角形の内側にある点をランダムに算出する方法」については後編で！

メッシュ表面のランダムな座標を計算する　後編

おねむゲーマーの備忘録

2019年1月4日