Appearance
会社ロゴのimg2model メッシュ分割編
会社などのロゴのpngなどをモデルにする際のメッシュ分割をコードに落とす作業記録です。
全体の処理内容
- 画像取り込み
- 輪郭点抽出
- 輪郭点領域内で三角形分割 ←ここをやります
- 三角形分割で作ったメッシュと、側面の点を利用してモデル化
- エクスポート
C#でドロネー三角形分割をするgitやコードがありはしたのですが、今回の目的にあったコードを見つけられなかったのと、各メソッドの使い方が把握しきれなかったので自作することにしました。
三角形分割のやり方
いろいろな三角形分割のやり方があるみたいなのですが、今回はドロネー三角形分割という方法を使って実装します。
選んだ理由は、実装方法やアルゴリズムの日本語を使った記事がたくさんあったのと、
外接円条件（Empty Circle Property）
各三角形の外接円内に、他の点が存在してはいけません。これがドロネー分割の基本的な性質であり、結果として「最大の最小角」を持つという利点につながります。
一般位置の仮定
・同一直線上の点がないこと
複数の点が同一直線上に並んでいると、三角形を作ることができず、分割が定義できません。
・同一円周上に4点以上の点が存在しないこと
もし4点以上が同一の円周上に存在すると、どの三角形分割が正しいのか一意に決定できなくなり、複数の有効なドロネー分割が存在する場合があります。
これらの特徴がモデルのメッシュ分割という目的において適切だと判断したからです。
ただ、単純に三角形分割しただけだと輪郭点領域外に三角形が作成されてしまうので、
https://x.com/toygramming/status/1771379376535580782
↑のツイートにあるように、三角形分割した後に領域外に出てしまった三角形を除外するアルゴリズムも一緒に作っていこうと思います。
追加してメッシュについかされる三角形の頂点は時計回りに並べられないとならないという制約もあるのでそれも考慮しなけらばなりません。
コーディング
テスト用画像
三角形分割のコード（プロトタイプ）
List<vector2>を渡して三角形分割して、頂点となる点を３点ずつセットにして返してもらうコード
csharpusing System.Collections.Generic; using UnityEngine; public class DelaunayTriangulation { // 入力点群（Scene上などで設定） public List<Vector2> _contours = new List<Vector2>(); // 出力：Meshに使う頂点（Vector3：z=0）と三角形インデックス（List<int>：3点ずつ） public List<Vector3> _vertices3; public List<int> _triangleIndices; #region // 内部で利用するデータ構造 class PointData { public Vector2 pos; public int index; // 入力リストでの元インデックス public PointData(Vector2 p, int idx) { pos = p; index = idx; } } class Triangle { public PointData p0, p1, p2; public Triangle(PointData a, PointData b, PointData c) { p0 = a; p1 = b; p2 = c; // 時計回りでなければ p1 と p2 を入れ替える if (!IsClockwise(p0.pos, p1.pos, p2.pos)) { PointData temp = p1; p1 = p2; p2 = temp; } } /// <summary> /// エッジがこの三角形に含まれているか（向きは考慮しない） /// </summary> public bool HasEdge(Edge edge) { return (edge.Equals(new Edge(p0, p1)) || edge.Equals(new Edge(p1, p2)) || edge.Equals(new Edge(p2, p0))); } } class Edge { public PointData a, b; public Edge(PointData p1, PointData p2) { a = p1; b = p2; } public override bool Equals(object obj) { Edge other = obj as Edge; if (other == null) return false; return ((a == other.a && b == other.b) || (a == other.b && b == other.a)); } public override int GetHashCode() { return a.GetHashCode() ^ b.GetHashCode(); } } /// <summary> /// ドロネー三角形分割（Bowyer-Watson）のメイン関数 /// </summary> List<Triangle> Triangulate(List<PointData> points) { List<Triangle> triangles = new List<Triangle>(); // 1. スーパー三角形を作成 float minX = float.MaxValue, minY = float.MaxValue; float maxX = float.MinValue, maxY = float.MinValue; foreach (var pt in points) { if (pt.pos.x < minX) minX = pt.pos.x; if (pt.pos.y < minY) minY = pt.pos.y; if (pt.pos.x > maxX) maxX = pt.pos.x; if (pt.pos.y > maxY) maxY = pt.pos.y; } float dx = maxX - minX, dy = maxY - minY; float deltaMax = Mathf.Max(dx, dy); float midx = (minX + maxX) / 2; float midy = (minY + maxY) / 2; // スーパー三角形の頂点（index=-1 として管理） PointData sp0 = new PointData(new Vector2(midx - 2 * deltaMax, midy - deltaMax), -1); PointData sp1 = new PointData(new Vector2(midx, midy + 2 * deltaMax), -1); PointData sp2 = new PointData(new Vector2(midx + 2 * deltaMax, midy - deltaMax), -1); Triangle superTriangle = new Triangle(sp0, sp1, sp2); triangles.Add(superTriangle); // 2. 各点を順次追加（Bowyer-Watson アルゴリズム） foreach (PointData pt in points) { List<Triangle> badTriangles = new List<Triangle>(); List<Edge> polygon = new List<Edge>(); // (a) pt を含む外接円内の三角形を探索 foreach (Triangle tri in triangles) { if (IsPointInsideCircumcircle(pt.pos, tri)) { badTriangles.Add(tri); } } // (b) badTriangles に含まれる三角形の辺の中で、境界（共通しない辺）を抽出 foreach (Triangle tri in badTriangles) { Edge[] edges = new Edge[] { new Edge(tri.p0, tri.p1), new Edge(tri.p1, tri.p2), new Edge(tri.p2, tri.p0) }; foreach (Edge edge in edges) { bool isShared = false; foreach (Triangle other in badTriangles) { if (other == tri) continue; if (other.HasEdge(edge)) { isShared = true; break; } } if (!isShared) { polygon.Add(edge); } } } // (c) badTriangles を削除 foreach (Triangle tri in badTriangles) { triangles.Remove(tri); } // (d) 境界の各エッジと pt を結んで新たな三角形を生成 foreach (Edge edge in polygon) { Triangle newTri = new Triangle(edge.a, edge.b, pt); triangles.Add(newTri); } } // 3. スーパー三角形に由来する頂点を含む三角形を削除 triangles.RemoveAll(tri => tri.p0.index == -1 || tri.p1.index == -1 || tri.p2.index == -1); return triangles; } /// <summary> /// 三角形の外接円内に点 p が含まれるかを判定する（行列式を利用） /// </summary> static bool IsPointInsideCircumcircle(Vector2 p, Triangle tri) { // 座標を移動 float ax = tri.p0.pos.x - p.x; float ay = tri.p0.pos.y - p.y; float bx = tri.p1.pos.x - p.x; float by = tri.p1.pos.y - p.y; float cx = tri.p2.pos.x - p.x; float cy = tri.p2.pos.y - p.y; float det = (ax * ax + ay * ay) * (bx * cy - cx * by) - (bx * bx + by * by) * (ax * cy - cx * ay) + (cx * cx + cy * cy) * (ax * by - bx * ay); // 時計回りの場合、det < 0 の時に p は外接円内にあると判断 return det < 0; } /// <summary> /// 3点が時計回りの順序かを判定（trueなら時計回り） /// </summary> static bool IsClockwise(Vector2 a, Vector2 b, Vector2 c) { float cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); return cross < 0; // 交差が負なら時計回り } /// <summary> /// Triangulate した結果から、元データのインデックスリスト（List<int>）を生成 /// </summary> List<int> GetTriangleIndices(List<Triangle> triangles) { List<int> indices = new List<int>(); foreach (var tri in triangles) { // 各三角形はすでに時計回り順に整えられているので、そのまま元のインデックスを追加 indices.Add(tri.p0.index); indices.Add(tri.p1.index); indices.Add(tri.p2.index); } return indices; } /// <summary> /// 入力の List<Vector2> を List<Vector3>（z=0）に変換する /// </summary> List<Vector3> ConvertToVector3(List<Vector2> points) { List<Vector3> verts = new List<Vector3>(); foreach (Vector2 p in points) { verts.Add(new Vector3(p.x, p.y, 0)); } return verts; } #endregion /// <summary> /// ここに輪郭点を渡すと三角形分割してくれる /// </summary> /// <param name="contours">引数:入力点</param> /// <param name="triangles">返り値：三角形の頂点のインデックスリスト</param> /// <param name="vertice3">返り値：入力点の３次元版</param> public void Triangulator (List<Vector2> contours,out List<int>triangles) { List<PointData> points = new List<PointData>(); for (int i = 0; i < contours.Count;i++) { points.Add(new PointData(contours[i], i)); } List<Triangle> delaunayTriangles = Triangulate(points); //三角形化した頂点のインデックス triangles = GetTriangleIndices(delaunayTriangles); Debug.Log($"【三角形分割終了】頂点数:{triangles.Count}入力点:{contours.Count}"); } }呼び出す側のコード
csharpusing System.Collections; using System.Collections.Generic; using UnityEngine; using OpenCvSharp; using System.IO; using System.Text; using UnityEngine.UIElements; using UnityEditor.Build; using System; using UnityEngine.UI; using UnityEngine.Rendering; using System.Linq; public class LogoModelManager : MonoBehaviour { [Header("入力画像")] [SerializeField] public Texture2D inputLogo; [Header("モデルの厚さ")] [SerializeField, Range(0f, 20f)] public float Depth = 5f; [Header("無視して生成する面積の閾値")] public double minAreaThreshold = 0.005; [Header("生成先の親オブジェクト")] [SerializeField] public GameObject parentObject; public RawImage preview; private Mesh generatedMesh; // Start is called before the first frame update void Start() { //輪郭線の作成 List<List<Vector2>> allOutLines = ExtractOutLine(inputLogo); if (allOutLines == null || allOutLines.Count == 0) { Debug.LogError("輪郭線が作れんかった"); return; } Debug.Log("輪郭線が作れた"); List<Mesh> meshs = new List<Mesh>(); DelaunayTriangulation triangulation = new DelaunayTriangulation(); //三角形分割,メッシュ生成 foreach (List<Vector2> outlinePoints in allOutLines) { List<int> triangles; triangulation.Triangulator(outlinePoints, out triangles); //メッシュ化 Mesh mesh = CreateMesh(outlinePoints,triangles,Depth); //メッシュ生成 GameObject contourObj = new GameObject("childMesh"); contourObj.transform.parent = parentObject.transform; MeshFilter mf = contourObj.AddComponent<MeshFilter>(); mf.mesh = mesh; MeshRenderer mr = contourObj.AddComponent<MeshRenderer>(); mr.material = new Material(Shader.Find("Standard")); } Debug.Log("メッシュ生成できた"); } /// <summary> /// 輪郭点抽出 /// </summary> /// <param name="_input"></param> /// <returns></returns> List<List<Vector2>> ExtractOutLine(Texture2D _input) { Mat src = OpenCvSharp.Unity.TextureToMat(_input); preview = GetComponent<RawImage>(); Mat input = OpenCvSharp.Unity.TextureToMat(_input); Mat gray = new Mat(); Cv2.CvtColor(input, gray, ColorConversionCodes.BGR2GRAY); Mat binary = new Mat(); Cv2.Threshold(gray, binary, 0, 255, ThresholdTypes.Binary | ThresholdTypes.Otsu); Mat Mask = new Mat(); Cv2.BitwiseNot(binary, Mask); Point[][] contours; HierarchyIndex[] hierarchy; Cv2.FindContours ( Mask, out contours, out hierarchy, RetrievalModes.List, ContourApproximationModes.ApproxSimple ); List<List<Vector2>> contourList = new List<List<Vector2>>(); double minArea = (src.Width * src.Height) * minAreaThreshold; //輪郭線配列への追加 for (int i = 0; i < contours.Length; i++) { double area = Cv2.ContourArea(contours[i]); if (area < minArea) continue; List<Vector2> points = new List<Vector2>(); foreach (var p in contours[i]) { points.Add(new Vector2(p.X, p.Y)); } contourList.Add(points); } return contourList; } private Mesh CreateMesh(List<Vector2> vertice2D, List<int> triangleindex, float depth) { Mesh mesh = new Mesh(); int n = vertice2D.Count; List<Vector3> vertice3 = new List<Vector3>(); List<int> triangles = new List<int>(); //前面の頂点 foreach (var v in vertice2D) { vertice3.Add(new Vector3(v.x,v.y,depth / 2f)); } //背面の頂点 foreach (var v in vertice2D) { vertice3.Add(new Vector3(v.x, v.y, depth / 2f)); } //前面の三角形 for (int i = 0; i < triangleindex.Count; i += 3) { triangles.Add(triangleindex[i]); triangles.Add(triangleindex[i + 1]); triangles.Add(triangleindex[i + 2]); } //背面の三角形 for (int i = 0; i > triangleindex.Count; i += 3) { triangles.Add(triangleindex[i + 2] + n); triangles.Add(triangleindex[i + 1] + n); triangles.Add(triangleindex[i] + n); } //側面 for (int i = 0; i < n; i++) { int next = (i + 1) % n; int frontA = i; int frontB = next; int backA = i + n; int backB = next + n; //△これ triangles.Add(frontA); triangles.Add(frontB); triangles.Add(backB); //▽これ triangles.Add(frontA); triangles.Add(backB); triangles.Add(backA); } mesh.vertices = vertice3.ToArray(); mesh.triangles = triangles.ToArray(); mesh.RecalculateNormals(); mesh.RecalculateBounds(); return mesh; } }
ここから輪郭線外に作られた三角形を取り除かないといけない。
今生成されてるやつ↓
できた；；
表面のメッシュだけだけど；；
三角形分割及び領域外の三角形を取り除く処理は以下です。
csharp
using System.Collections.Generic;
using UnityEditor.Build;
using UnityEngine;
using UnityEngine.UIElements;
public class DelaunayTriangulation
{
// 入力点群（Scene上などで設定）
public List<Vector2> _contours = new List<Vector2>();
// 出力：Meshに使う頂点（Vector3：z=0）と三角形インデックス（List<int>：3点ずつ）
public List<Vector3> _vertices3;
public List<int> _triangleIndices;
#region
// 内部で利用するデータ構造
class PointData
{
public Vector2 pos;
public int index; // 入力リストでの元インデックス
public PointData(Vector2 p, int idx)
{
pos = p;
index = idx;
}
}
class Triangle
{
public PointData p0, p1, p2;
public Triangle(PointData a, PointData b, PointData c)
{
p0 = a; p1 = b; p2 = c;
// 時計回りでなければ p1 と p2 を入れ替える
if (!IsClockwise(p0.pos, p1.pos, p2.pos))
{
PointData temp = p1;
p1 = p2;
p2 = temp;
}
}
/// <summary>
/// エッジがこの三角形に含まれているか（向きは考慮しない）
/// </summary>
public bool HasEdge(Edge edge)
{
return (edge.Equals(new Edge(p0, p1)) ||
edge.Equals(new Edge(p1, p2)) ||
edge.Equals(new Edge(p2, p0)));
}
}
class Edge
{
public PointData a, b;
public Edge(PointData p1, PointData p2)
{
a = p1;
b = p2;
}
public override bool Equals(object obj)
{
Edge other = obj as Edge;
if (other == null) return false;
return ((a == other.a && b == other.b) || (a == other.b && b == other.a));
}
public override int GetHashCode()
{
return a.GetHashCode() ^ b.GetHashCode();
}
}
/// <summary>
/// ドロネー三角形分割（Bowyer-Watson）のメイン関数
/// </summary>
List<Triangle> Triangulate(List<PointData> points,List<Vector2> contours)
{
//テスト用変数
int remove = 0;
int clear = 0;
List<Triangle> triangles = new List<Triangle>();
// 1. スーパー三角形を作成
float minX = float.MaxValue, minY = float.MaxValue;
float maxX = float.MinValue, maxY = float.MinValue;
foreach (var pt in points)
{
if (pt.pos.x < minX) minX = pt.pos.x;
if (pt.pos.y < minY) minY = pt.pos.y;
if (pt.pos.x > maxX) maxX = pt.pos.x;
if (pt.pos.y > maxY) maxY = pt.pos.y;
}
float dx = maxX - minX, dy = maxY - minY;
float deltaMax = Mathf.Max(dx, dy);
float midx = (minX + maxX) / 2;
float midy = (minY + maxY) / 2;
// スーパー三角形の頂点（index=-1 として管理）
PointData sp0 = new PointData(new Vector2(midx - 2 * deltaMax, midy - deltaMax), -1);
PointData sp1 = new PointData(new Vector2(midx, midy + 2 * deltaMax), -1);
PointData sp2 = new PointData(new Vector2(midx + 2 * deltaMax, midy - deltaMax), -1);
Triangle superTriangle = new Triangle(sp0, sp1, sp2);
triangles.Add(superTriangle);
// 2. 各点を順次追加（Bowyer-Watson アルゴリズム）
foreach (PointData pt in points)
{
List<Triangle> badTriangles = new List<Triangle>();
List<Edge> polygon = new List<Edge>();
// (a) pt を含む外接円内の三角形を探索
foreach (Triangle tri in triangles)
{
if (IsPointInsideCircumcircle(pt.pos, tri))
{
badTriangles.Add(tri);
}
}
// (b) badTriangles に含まれる三角形の辺の中で、境界（共通しない辺）を抽出
foreach (Triangle tri in badTriangles)
{
Edge[] edges = new Edge[]
{
new Edge(tri.p0, tri.p1),
new Edge(tri.p1, tri.p2),
new Edge(tri.p2, tri.p0)
};
foreach (Edge edge in edges)
{
bool isShared = false;
foreach (Triangle other in badTriangles)
{
if (other == tri) continue;
if (other.HasEdge(edge))
{
isShared = true;
break;
}
}
if (!isShared)
{
polygon.Add(edge);
}
}
}
// (c) badTriangles を削除
foreach (Triangle tri in badTriangles)
{
triangles.Remove(tri);
}
// (d) 境界の各エッジと pt を結んで新たな三角形を生成
foreach (Edge edge in polygon)
{
Triangle newTri = new Triangle(edge.a, edge.b, pt);
triangles.Add(newTri);
}
}
// 3. スーパー三角形に由来する頂点を含む三角形を削除
triangles.RemoveAll(tri =>
tri.p0.index == -1 || tri.p1.index == -1 || tri.p2.index == -1);
List<Triangle> insideContourTriangles = new List<Triangle>();
foreach (var tri in triangles)
{
if (IsPointInPolygon(tri, contours))
{
insideContourTriangles.Add(tri);
clear++;
Debug.Log($"突破した:{clear}");
}
else
{
remove++;
Debug.Log($"除外した:{remove}");
}
}
Debug.Log($"【リザルト】〇{clear}×{remove} 総数:{insideContourTriangles.Count}");
return insideContourTriangles;
}
/// <summary>
/// 三角形の外接円内に点 p が含まれるかを判定する（行列式を利用）
/// </summary>
static bool IsPointInsideCircumcircle(Vector2 p, Triangle tri)
{
// 座標を移動
float ax = tri.p0.pos.x - p.x;
float ay = tri.p0.pos.y - p.y;
float bx = tri.p1.pos.x - p.x;
float by = tri.p1.pos.y - p.y;
float cx = tri.p2.pos.x - p.x;
float cy = tri.p2.pos.y - p.y;
float det = (ax * ax + ay * ay) * (bx * cy - cx * by)
- (bx * bx + by * by) * (ax * cy - cx * ay)
+ (cx * cx + cy * cy) * (ax * by - bx * ay);
// 時計回りの場合、det < 0 の時に p は外接円内にあると判断
return det < 0;
}
/// <summary>
/// 3点が時計回りの順序かを判定（trueなら時計回り）
/// </summary>
static bool IsClockwise(Vector2 a, Vector2 b, Vector2 c)
{
float cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return cross < 0; // 交差が負なら時計回り
}
/// <summary>
/// Triangulate した結果から、元データのインデックスリスト（List<int>）を生成
/// </summary>
List<int> GetTriangleIndices(List<Triangle> triangles)
{
List<int> indices = new List<int>();
foreach (var tri in triangles)
{
// 各三角形はすでに時計回り順に整えられているので、そのまま元のインデックスを追加
indices.Add(tri.p0.index);
indices.Add(tri.p1.index);
indices.Add(tri.p2.index);
}
return indices;
}
/// <summary>
/// 作成した三角形（の重心）が輪郭線内にあるかどうかを調べるメソッド。
/// </summary>
/// <param name="tri">調査する三角形</param>
/// <param name="contour">輪郭線</param>
/// <returns></returns>
bool IsPointInPolygon(Triangle tri,List<Vector2> contour)
{
bool inside = false;
int count = contour.Count;
//三角形の重心
Vector2 point = (tri.p0.pos + tri.p1.pos + tri.p2.pos) / 3f;
//射影線アルゴリズム（重心から一方向に線を引いて、輪郭の辺と南海交差するかを調べる）
//交差回数が奇数なら内側にあって、偶数なら外側にある。
for (int i = 0, j = count - 1; i < count; j = i++)
{
//辺の両端のy座標が点のy座標をまたいでいるか
if (
(contour[i].y > point.y) != (contour[j].y > point.y)
&&
(point.x <(contour[j].x - contour[i].x) * (point.y - contour[i].y)
/ (contour[j].y - contour[i].y) + contour[i].x)
)
{
//奇数回目にtrueになる。
inside = !inside;
}
}
return inside;
}
#endregion
/// <summary>
/// ここに輪郭点を渡すと三角形分割してくれる
/// </summary>
/// <param name="contours">引数:入力点</param>
/// <param name="triangles">返り値：三角形の頂点のインデックスリスト</param>
/// <param name="vertice3">返り値：入力点の３次元版</param>
public void Triangulator
(List<Vector2> contours,out List<int>triangles)
{
List<PointData> points = new List<PointData>();
for (int i = 0; i < contours.Count;i++)
{
points.Add(new PointData(contours[i], i));
}
List<Triangle> delaunayTriangles = Triangulate(points,contours);
//三角形化した頂点のインデックス
triangles = GetTriangleIndices(delaunayTriangles);
Debug.Log($"【三角形分割終了】頂点数:{triangles.Count}入力点:{contours.Count}");
}
}輪郭線の抽出の方法が変わっても、輪郭点さえ算出できえばvetor2のリストをこいつに投げてあげれば三角形分割はこいつがやってくれるので今後もっとガタガタじゃない輪郭点を抽出する方法が見つかったとしても流用できます！！
Author: 松崎 | Source:
松崎\会社ロゴのimg2model メッシュ分割編 1b3aba435ee7800480d1ce0382547921.md