本日はモデリング枠です。
先日はエッジコラスプ法のエッジを求めるアルゴリズムを実装しました。
今回は疑似的に頂点をつぶして本当にデシメートが可能なのかを見ていきます。
〇エッジコラスプ法とは？
〇辺を縮退させる
エッジコラスプ法にのっとり、メッシュを構成するエッジの中から最も短い辺を縮退させ構成する頂点をマージします。
しかしながらここでは単純に辺の長さを0にするのみにとどめ新しく頂点を作成し、面を張りなおす作業はしていません。
using UnityEngine;
using System.Collections.Generic;
using System.Numerics;
using UnityEngine.UIElements;
using Vector3 = UnityEngine.Vector3;
public class EdgeLengthCalculator : MonoBehaviour
{
void Start()
{
// メッシュを取得
Mesh mesh = GetComponent<MeshFilter>().mesh;
// メッシュの全頂点を取得
Vector3[] vertices = mesh.vertices;
// メッシュの三角形インデックスを取得
int[] triangles = mesh.triangles;
// 辺情報を保存するリスト (Dictionaryで重複を避ける)
Dictionary<Edge, float> edges = new Dictionary<Edge, float>();
// 三角形を一つずつ処理
for (int i = 0; i < triangles.Length; i += 3)
{
// 各三角形の頂点インデックスを取得
int v0 = triangles[i];
int v1 = triangles[i + 1];
int v2 = triangles[i + 2];
// 辺を計算 (重複を避けるため、常に小さいインデックスが前に来るようにする)
AddEdge(v0, v1, vertices, edges);
AddEdge(v1, v2, vertices, edges);
AddEdge(v2, v0, vertices, edges);
}
for(int j = 0; j<50000; j++)
{
// 最も短い辺を探す
Edge shortestEdge = null;
float shortestLength = float.MaxValue;
foreach (KeyValuePair<Edge, float> edge in edges)
{
if (edge.Value < shortestLength)
{
shortestLength = edge.Value;
shortestEdge = edge.Key;
}
}
Vector3 newpos;
newpos = (vertices[shortestEdge.VertexIndex1] + vertices[shortestEdge.VertexIndex2]) / 2;
vertices[shortestEdge.VertexIndex1] = newpos;
vertices[shortestEdge.VertexIndex2] = newpos;
// 結果を出力
if (shortestEdge != null)
{
Debug.Log($"最も短い辺の頂点ID: {shortestEdge.VertexIndex1}, {shortestEdge.VertexIndex2}");
Debug.Log($"最も短い辺の長さ: {shortestLength}");
}
}
// メッシュの頂点座標を更新
mesh.vertices = vertices;
}
// 辺をリストに追加するメソッド
private void AddEdge(int v1, int v2, Vector3[] vertices, Dictionary<Edge, float> edges)
{
// 常に小さい頂点インデックスを前にしてエッジを作成
Edge edge = new Edge(Mathf.Min(v1, v2), Mathf.Max(v1, v2));
// 辺の長さを計算
float length = Vector3.Distance(vertices[v1], vertices[v2]);
// 辺がすでにリストにあるか確認し、なければ追加
if (!edges.ContainsKey(edge))
{
edges.Add(edge, length);
}
}
}
// 辺を表現する構造体 (Dictionaryのキーとして使用するためにEqualsとGetHashCodeを実装)
public class Edge
{
public int VertexIndex1;
public int VertexIndex2;
public Edge(int v1, int v2)
{
VertexIndex1 = v1;
VertexIndex2 = v2;
}
// Dictionaryのキーとして使用できるようにEqualsとGetHashCodeをオーバーライド
public override bool Equals(object obj)
{
Edge other = obj as Edge;
return other != null && VertexIndex1 == other.VertexIndex1 && VertexIndex2 == other.VertexIndex2;
}
public override int GetHashCode()
{
return VertexIndex1 * 31 + VertexIndex2;
}
}
前回に比べ変更した処理は以下です。
for(int j = 0; j<50000; j++)
{
// 最も短い辺を探す
Edge shortestEdge = null;
float shortestLength = float.MaxValue;
foreach (KeyValuePair<Edge, float> edge in edges)
{
if (edge.Value < shortestLength)
{
shortestLength = edge.Value;
shortestEdge = edge.Key;
}
}
Vector3 newpos;
newpos = (vertices[shortestEdge.VertexIndex1] + vertices[shortestEdge.VertexIndex2]) / 2;
vertices[shortestEdge.VertexIndex1] = newpos;
vertices[shortestEdge.VertexIndex2] = newpos;
// 結果を出力
if (shortestEdge != null)
{
Debug.Log($"最も短い辺の頂点ID: {shortestEdge.VertexIndex1}, {shortestEdge.VertexIndex2}");
Debug.Log($"最も短い辺の長さ: {shortestLength}");
}
}
// メッシュの頂点座標を更新
mesh.vertices = vertices;
ここではfor文を使用して5000回最も短いエッジを見つけ、そのエッジを構成する頂点の座標を中間点に配置しています。
この処理自体は動きますが、メッシュを5000回も１フレームで処理しているのでとても無駄が多いです。
そこで処理を高速化します。
〇処理の最適化
エッジコラプスを行うたびにすべてのエッジを再計算するのではなく、影響を受けたエッジだけを再計算する方法を導入するために、優先度付きキューを使います。
優先度付きキューとはSortedDictionaryで自動的にソートされる定義するリストです。
このキューにあらかじめ辺の長さに応じて格納して、それをもとにエッジを削減します。
これによって１フレームで何度もメッシュの状態を確認しなくてよくなるためめ効率的に処理ができます。
これによって現時点ではメッシュ自体を作り直しているわけではないので、疑似的なものですがデシメートが可能となりました。
実行後のメッシュは以下になります。
これを実行したものが以下になります。
〇コード
using UnityEngine;
using System.Collections.Generic;
using UnityEngine.UIElements;
using Vector3 = UnityEngine.Vector3;
public class EdgeLengthCalculator : MonoBehaviour
{
private SortedDictionary<float, Edge> edges = new SortedDictionary<float, Edge>(); // 修正: 最も短い辺を簡単に見つけるためにSortedDictionaryを使用
void Start()
{
InitializeEdges();
CollapseEdges();
}
private void InitializeEdges()
{
// メッシュを取得
Mesh mesh = GetComponent<MeshFilter>().mesh;
// メッシュの全頂点を取得
Vector3[] vertices = mesh.vertices;
// メッシュの三角形インデックスを取得
int[] triangles = mesh.triangles;
// 三角形を一つずつ処理
for (int i = 0; i < triangles.Length; i += 3)
{
// 各三角形の頂点インデックスを取得
int v0 = triangles[i];
int v1 = triangles[i + 1];
int v2 = triangles[i + 2];
// 辺を計算 (重複を避けるため、常に小さいインデックスが前に来るようにする)
AddEdge(v0, v1, vertices);
AddEdge(v1, v2, vertices);
AddEdge(v2, v0, vertices);
}
}
private void CollapseEdges()
{
Mesh mesh = GetComponent<MeshFilter>().mesh;
Vector3[] vertices = mesh.vertices;
for (int j = 0; j < 50000; j++)
{
// 最も短い辺を取得
if (edges.Count == 0)
{
Debug.Log("エッジが存在しません。");
break;
}
KeyValuePair<float, Edge> shortestEdgeEntry = edges.First();
float shortestLength = shortestEdgeEntry.Key;
Edge shortestEdge = shortestEdgeEntry.Value;
// 頂点を統合
Vector3 newpos = (vertices[shortestEdge.VertexIndex1] + vertices[shortestEdge.VertexIndex2]) / 2;
vertices[shortestEdge.VertexIndex1] = newpos;
vertices[shortestEdge.VertexIndex2] = newpos;
// 古いエッジを削除
edges.Remove(shortestLength);
// 統合後のエッジを更新
UpdateEdges(shortestEdge, vertices);
// デバッグ出力
Debug.Log($"最も短い辺の頂点ID: {shortestEdge.VertexIndex1}, {shortestEdge.VertexIndex2}");
Debug.Log($"最も短い辺の長さ: {shortestLength}");
}
// メッシュの頂点座標を更新
mesh.vertices = vertices;
}
private void AddEdge(int v1, int v2, Vector3[] vertices)
{
// 常に小さい頂点インデックスを前にしてエッジを作成
Edge edge = new Edge(Mathf.Min(v1, v2), Mathf.Max(v1, v2));
// 辺の長さを計算
float length = Vector3.Distance(vertices[v1], vertices[v2]);
// 同じ長さのエッジが存在しない場合のみ追加
if (!edges.ContainsKey(length))
{
edges.Add(length, edge);
}
}
private void UpdateEdges(Edge collapsedEdge, Vector3[] vertices)
{
// エッジの頂点を使って新しいエッジの長さを計算し、更新する処理を追加する
// 古いエッジを削除後、新しいエッジを追加し直す
}
}
// 辺を表現する構造体
public class Edge
{
public int VertexIndex1;
public int VertexIndex2;
public Edge(int v1, int v2)
{
VertexIndex1 = v1;
VertexIndex2 = v2;
}
// Dictionaryのキーとして使用できるようにEqualsとGetHashCodeをオーバーライド
public override bool Equals(object obj)
{
Edge other = obj as Edge;
return other != null && VertexIndex1 == other.VertexIndex1 && VertexIndex2 == other.VertexIndex2;
}
public override int GetHashCode()
{
return VertexIndex1 * 31 + VertexIndex2;
}
}
