- Home /
Mesh from Vertices (Polygon from Spline)
I want generate a 2d polygonal area from vertice XZ coordinates. Local Y is 0. Vertices indexed like a closed spline. Spline edges do not intersecting with other edges.
I need a new Triangle calculation method. For example if our spline like a E shape, current calculation messing it. Because one vertex is static.
Also added an example shape showing some triangles (selected faces) and what i expect.
I need to generate polygonal areas dynamically. Can someone help me?
GameObject CreatePolygonalArea (Vector2[] XZofVertices) {
Vector3[] Vertices = new Vector3[XZofVertices.Length];
int[] Triangles = new int[3 * (XZofVertices.Length - 2)];
for (int i = 0; i < XZofVertices.Length; i++)
{
Vertices[i] = new Vector3(XZofVertices[i].x,0,XZofVertices[i].y);
}
int C1 = 0, C2 = 1, C3 = 2;
for(int i = 0; i < Triangles.Length; i+=3)
{
Triangles[i] = C3;
Triangles[i+1] = C2;
Triangles[i+2] = C1;
C2++;
C3++;
}
GameObject OurNewMesh = new GameObject("PolygonalArea");
Mesh mesh = new Mesh();
mesh.vertices = Vertices;
mesh.uv = XZofVertices;
mesh.triangles = Triangles;
mesh.RecalculateNormals();
OurNewMesh.AddComponent("MeshFilter");
OurNewMesh.AddComponent("MeshRenderer");
OurNewMesh.GetComponent().castShadows = false;
OurNewMesh.GetComponent().receiveShadows = false;
OurNewMesh.GetComponent().mesh = mesh;
return OurNewMesh;
}
Currently not well answered. But lets say true answer Constrained Delaunay Triangulations.
Answer by Fattie · Aug 24, 2012 at 08:14 PM
You're joking dude, you want a total solution for space filling with triangles !!??
You realise this is a pretty big field. Look in to Delauney Triangulation to get started! (Wikipedia)
http://www.cadanda.com/CAD_5_6__889-899.pdf
http://netcode.ru/dotnet/?lang=&katID=30&skatID=249&artID=6531
http://www.meshrepair.org
http://www.robertschneiders.de/meshgeneration/software.html
I guess Prof Shewchuk's is pretty ancient now !
Here it is:
http://www.cs.cmu.edu/~quake/triangle.html
If you are asking something simpler than this, please explain more clearly if possible.
It's actually quite hard to find resources for 2D mesh, since everything you google up is 3D mesh.
Hope it helps !
Thanks polygon triangulation is my answer.
I coded Delauney Triangulation. $$anonymous$$aybe its not very optimized but It seems working very well. I am happy :)
Now i will try for Constrained Delaunay Triangulations.
Answer by SuperProgrammer · Aug 25, 2012 at 10:57 AM
I am sharing Delaunay Triangulation Calculation maybe it can be helpful for others. Its useful for basic polygons. Currently searching for Constrained Delaunay Triangulations.
Codes working well but maybe i can forget some unnecessary rows. You can write for optimization.
Function That is Creating Mesh:
GameObject CreateInfluencePolygon (Vector2[] XZofVertices) {
Vector3[] Vertices = new Vector3[XZofVertices.Length];
for (int ii1 = 0; ii1 < XZofVertices.Length; ii1++)
{
Vertices[ii1] = new Vector3(XZofVertices[ii1].x,0,XZofVertices[ii1].y);
}
GameObject OurNewMesh = new GameObject("OurNewMesh1");
Mesh mesh = new Mesh();
mesh.vertices = Vertices;
mesh.uv = XZofVertices;
mesh.triangles = TriangulatePolygon(XZofVertices);
mesh.RecalculateNormals();
OurNewMesh.AddComponent("MeshFilter");
OurNewMesh.AddComponent("MeshRenderer");
OurNewMesh.GetComponent().castShadows = false;
OurNewMesh.GetComponent().receiveShadows = false;
OurNewMesh.GetComponent().mesh = mesh;
return OurNewMesh;
}
Function Calculating Triangles:
int[] TriangulatePolygon (Vector2[] XZofVertices) {
int VertexCount = XZofVertices.Length;
float xmin = XZofVertices[0].x;
float ymin = XZofVertices[0].y;
float xmax = xmin;
float ymax = ymin;
for (int ii1 = 1; ii1 < VertexCount; ii1++)
{
if (XZofVertices[ii1].x < xmin) { xmin = XZofVertices[ii1].x; }
else if (XZofVertices[ii1].x > xmax) { xmax = XZofVertices[ii1].x; }
if (XZofVertices[ii1].y < ymin) { ymin = XZofVertices[ii1].y; }
else if (XZofVertices[ii1].y > ymax) { ymax = XZofVertices[ii1].y; }
}
float dx = xmax - xmin;
float dy = ymax - ymin;
float dmax = (dx > dy) ? dx : dy;
float xmid = (xmax + xmin) * 0.5f;
float ymid = (ymax + ymin) * 0.5f;
Vector2[] ExpandedXZ = new Vector2[3 + VertexCount];
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
ExpandedXZ[ii1] = XZofVertices[ii1];
}
ExpandedXZ[VertexCount] = new Vector2((xmid - 2 * dmax), (ymid - dmax));
ExpandedXZ[VertexCount + 1] = new Vector2(xmid, (ymid + 2 * dmax));
ExpandedXZ[VertexCount + 2] = new Vector2((xmid + 2 * dmax), (ymid - dmax));
System.Collections.Generic.List TriangleList = new System.Collections.Generic.List();
TriangleList.Add(new Triangle(VertexCount, VertexCount+1, VertexCount+2));
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
System.Collections.Generic.List Edges = new System.Collections.Generic.List();
for (int ii2 = 0; ii2 < TriangleList.Count; ii2++)
{
if (TriangulatePolygonSubFunc_InCircle(
ExpandedXZ[ii1], ExpandedXZ[TriangleList[ii2].p1],
ExpandedXZ[TriangleList[ii2].p2],
ExpandedXZ[TriangleList[ii2].p3]))
{
Edges.Add(new Edge(TriangleList[ii2].p1, TriangleList[ii2].p2));
Edges.Add(new Edge(TriangleList[ii2].p2, TriangleList[ii2].p3));
Edges.Add(new Edge(TriangleList[ii2].p3, TriangleList[ii2].p1));
TriangleList.RemoveAt(ii2);
ii2--;
}
}
if (ii1 >= VertexCount) { continue; }
for (int ii2 = Edges.Count - 2; ii2 >= 0; ii2--)
{
for (int ii3 = Edges.Count - 1; ii3 >= ii2 + 1; ii3--)
{
if (Edges[ii2].Equals(Edges[ii3]))
{
Edges.RemoveAt(ii3);
Edges.RemoveAt(ii2);
ii3--;
continue;
}
}
}
for (int ii2 = 0; ii2 < Edges.Count; ii2++)
{
TriangleList.Add(new Triangle(Edges[ii2].p1, Edges[ii2].p2, ii1));
}
Edges.Clear();
Edges = null;
}
for (int ii1 = TriangleList.Count - 1; ii1 >= 0; ii1--)
{
if (TriangleList[ii1].p1 >= VertexCount ||
TriangleList[ii1].p2 >= VertexCount ||
TriangleList[ii1].p3 >= VertexCount)
{ TriangleList.RemoveAt(ii1); }
}
TriangleList.TrimExcess();
int[] Triangles = new int[3 * TriangleList.Count];
for (int ii1 = 0; ii1 < TriangleList.Count; ii1++)
{
Triangles[3 * ii1] = TriangleList[ii1].p1;
Triangles[3 * ii1 + 1] = TriangleList[ii1].p2;
Triangles[3 * ii1 + 2] = TriangleList[ii1].p3;
}
return Triangles;
}
SubFunction of Triangle Calculation:
bool TriangulatePolygonSubFunc_InCircle(
Vector2 p, Vector2 p1, Vector2 p2, Vector2 p3) {
if (Mathf.Abs(p1.y - p2.y) < float.Epsilon &&
Mathf.Abs(p2.y - p3.y) < float.Epsilon)
{ return false; }
float m1, m2, mx1, mx2, my1, my2, xc, yc;
if (Mathf.Abs(p2.y - p1.y) < float.Epsilon)
{
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx2 = (p2.x + p3.x) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (p2.x + p1.x) * 0.5f;
yc = m2 * (xc - mx2) + my2;
}
else if (Mathf.Abs(p3.y - p2.y) < float.Epsilon)
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
mx1 = (p1.x + p2.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
xc = (p3.x + p2.x) * 0.5f;
yc = m1 * (xc - mx1) + my1;
}
else
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx1 = (p1.x + p2.x) * 0.5f;
mx2 = (p2.x + p3.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
yc = m1 * (xc - mx1) + my1;
}
float dx = p2.x - xc;
float dy = p2.y - yc;
float rsqr = dx * dx + dy * dy;
dx = p.x - xc;
dy = p.y - yc;
double drsqr = dx * dx + dy * dy;
return (drsqr <= rsqr);
}
Class and struct:
struct Triangle
{
public int p1;
public int p2;
public int p3;
public Triangle(int point1, int point2, int point3)
{
p1 = point1; p2 = point2; p3 = point3;
}
}
class Edge : System.IEquatable
{
public int p1;
public int p2;
public Edge(int point1, int point2)
{
p1 = point1; p2 = point2;
}
public Edge() : this(0, 0)
{
}
#region System.IEquatable Members
public bool Equals(Edge other)
{
return
((this.p1 == other.p2) && (this.p2 == other.p1)) ||
((this.p1 == other.p1) && (this.p2 == other.p2));
}
#endregion
}
Edit: (text edited by Fattie 4/2013)
Here is a formatted version of SuperProgrammer's response:
Did you ever find a solution for constrained delaunay triangulation?
Answer by IsGreen · Feb 05, 2014 at 08:55 PM
Script Action Video: http://www.youtube.com/watch?v=ZFt2gsJ0ZQk
Project Download: https://app.box.com/s/g3xozyq1ljhr385rceq7
3D Delaunay Triangulation.
Blue Boxes: 3 initial vertices. Vertices type 0. Yellow Boxes: Intersections points. Area between this yellow points, will not fill. Different vertices of type 0.
using UnityEngine;
using System.Collections.Generic;
public class csTriangulation : MonoBehaviour {
public Transform Vertices;
Vector3[] tri;
public class Triangulation{
public class Vertex{
public Vector3 pos;
public Vector3 normal;
public Vector2 uv;
public int type;
public Vertex(Vector3 p, int t){
this.pos = p;
this.type = t;
}
public Vertex(Vector3 p, int t, Vector3 n, Vector2 u){
this.pos = p;
this.type = t;
this.normal = n;
this.uv = u;
}
}
List<Vertex> vertices;
public float lowerAngle;
public Triangulation(){
this.vertices = new List<Vertex>();
this.lowerAngle = 3f;
}
public Triangulation(float lower_Angle){
this.vertices = new List<Vertex>();
this.lowerAngle = lower_Angle;
}
public void Add(Vector3 p, int t){
this.vertices.Add(new Vertex(p,t));
}
public Vector3[] Calculate(){
if(this.vertices.Count == 0) return new Vector3[1];
Vector3[] result;
int i;
if(this.vertices.Count<=3) {
result = new Vector3[vertices.Count];
for(i=0;i<vertices.Count;i++) result[i]=vertices[i].pos;
return result;
}
List<int[]> triangles = new List<int[]>();
int[] triangle;
int w,x;
float circumsphereRadius;
Vector3 a,b,c,ac,ab,abXac,toCircumsphereCenter,ccs;
//All Combinations without repetition, some vertice of different type, only one vertice different of type 0
for(i=0;i<vertices.Count-2;i++){ for(w=i+1;w<vertices.Count-1;w++){ for(x=w+1;x<vertices.Count;x++){
if(vertices[i].type==vertices[w].type && vertices[i].type==vertices[x].type) continue; // Same type
if(Vector3.Angle(vertices[w].pos-vertices[i].pos,vertices[x].pos-vertices[i].pos) < this.lowerAngle) continue; // Remove triangles with angle near to 180º
triangle = new int[3]{i,w,x};
triangles.Add(triangle);
} } }
//Delaunay Condition
for(i=triangles.Count-1;i>=0;i--){
//Points
triangle = triangles[i];
a = vertices[triangle[0]].pos;
b = vertices[triangle[1]].pos;
c = vertices[triangle[2]].pos;
//Circumcenter 3Dpoints
//http://gamedev.stackexchange.com/questions/60630/how-do-i-find-the-circumcenter-of-a-triangle-in-3d
ac = c - a ;
ab = b - a ;
abXac = Vector3.Cross(ab,ac);
// this is the vector from a TO the circumsphere center
toCircumsphereCenter = (Vector3.Cross(abXac,ab)*ac.sqrMagnitude + Vector3.Cross(ac,abXac)*ab.sqrMagnitude) / (2f*abXac.sqrMagnitude);
// The 3 space coords of the circumsphere center then:
ccs = a + toCircumsphereCenter ; // now this is the actual 3space location
// The three vertices A, B, C of the triangle ABC are the same distance from the circumcenter ccs.
circumsphereRadius = toCircumsphereCenter.magnitude;
// As defined by the Delaunay condition, circumcircle is empty if it contains no other vertices besides the three that define.
for(w=0;w<vertices.Count;w++) if(w!=triangle[0] && w!=triangle[1] && w!=triangle[2]) if(Vector3.Distance(vertices[w].pos,ccs)<=circumsphereRadius) break;
// If it's not empty, remove.
if(w!=vertices.Count) triangles.RemoveAt(i);
}
result = new Vector3[triangles.Count*3];
for(i=0;i<triangles.Count;i++){
triangle = triangles[i];
result[i*3] = vertices[triangle[0]].pos;
result[i*3+1] = vertices[triangle[1]].pos;
result[i*3+2] = vertices[triangle[2]].pos;
}
return result;
}
}
// Use this for initialization
void Start () {
Triangulation meshTriangle = new Triangulation();
int i,w;
for(i=0;i<Vertices.childCount;i++){
if(Vertices.GetChild(i).renderer.materials[0].name=="amarillo (Instance)") w = 1; else w = 0;
meshTriangle.Add(Vertices.GetChild(i).position,w);
}
tri = meshTriangle.Calculate();
}
void Update() {
for(int i=0;i<tri.Length;i+=3){
Debug.DrawLine(tri[i],tri[i+1],Color.red);
Debug.DrawLine(tri[i],tri[i+2],Color.red);
Debug.DrawLine(tri[i+1],tri[i+2],Color.red);
}
}
}
Hi @IsGreen,
This is exactly what I have been looking for. Thanks for sharing the code and the project. I do have two question though. 1) How can I visualize the triangulation in the game window ins$$anonymous$$d of the scene window when I go into play mode 2) Is there anyway I can shade the triangles with some color
Thanks, Pranav
Your answer
Follow this Question
Related Questions
Using compute shader, how to take every vertex of a mesh and make a cube spawn and move to each one? 0 Answers
Any script to 'fix' normals/winding order? 3 Answers
How do I check if the mouse is over a VISIBLE vertex? 1 Answer
Mesh.vertices are all 0? 1 Answer
Having trouble implementing edge collapse operation with half-edge data structure 0 Answers