げんめんアルゴリズム
22223 ワード
using System;
using System.Collections.Generic;
using System.Linq;
using GenesisWinForm;
using GenesisWinForm.G3DObject.G3DCore;
//using System.Threading.Tasks;
using GenesisWinForm.MathG3D;
using OpenTK;
public static class CollapseVertexFunction
{
///
/// cost
///
public static double ComputeEdgeCollapseCost(Vertex u, Vertex v)
{
// if we collapse edge uv by moving u to v then how
// much different will the model change, i.e. the “error”.
double edgelength = (v.position - u.position).Length;
double curvature = 0;
// find the “sides” triangles that are on the edge uv
List sides = new List();
for (int i = 0; i < u.Face.Count; i++)
{
if (u.Face[i].HasVertex(v.id))
{
sides.Add(u.Face[i]);
}
}
// use the triangle facing most away from the sides
// to determine our curvature term
for (int i = 0; i < u.Face.Count; i++)
{
double mincurv = 1;
for (int j = 0; j < sides.Count; j++)
{
// use dot product of face normals.
double dotprod = Vector3d.Dot(u.Face[i].normal, sides[j].normal);
mincurv = Math.Min(mincurv, (1 - dotprod) / 2.0f);
}
curvature = Math.Max(curvature, mincurv);
}
////Debug.Log("curvature" + curvature);
return edgelength * curvature;
}
///
/// cost
///
public static void ComputeEdgeCostAtVertex(Vertex v)
{
if (v.neighbor.Count == 0)
{
v.collapse = null;
v.cost = -0.01f;
return;
}
v.cost = 1000000;
v.collapse = null;
// search all neighboring edges for “least cost” edge
for (int i = 0; i < v.neighbor.Count; i++)
{
double c;
c = ComputeEdgeCollapseCost(v, v.neighbor[i]);
if (c < v.cost)
{
v.collapse = v.neighbor[i];
v.cost = c;
}
}
}
#region
///
///
///
//public static int FindTriangleByVertexs(Vertex v1, Vertex v2, Vertex v3)
//{
// TriangleP t = new TriangleP(0);
// for (int i = 0; i < v1.Face.Count; i++)
// {
// for (int j = 0; j < v2.Face.Count; j++)
// {
// for (int k = 0; k < v3.Face.Count; k++)
// {
// if (v1.Face[i] == v2.Face[j] && v2.Face[j] == v3.Face[k])
// {
// return v1.Face[i].id;
// }
// }
// }
// }
// return t.id;
//}
//public static bool DeleteFace(G3DCore3DObjectOptimize _mesh, TriangleP _triangleP)
//{
// _mesh.DeleteTriangleP(_triangleP.id);
// return true;
//}
//public static bool DeleteVertexs(G3DCore3DObjectOptimize _mesh, Vertex _v1)
//{
// #region
// //Vertex v1 = _v1;
// //Vertex v2 = _v1.collapse;
// //List v3v4 = FindVertexsHavingSameSide(v1, v2);
// //Vertex v3 = v3v4[0];
// //Vertex v4 = v3v4[1];
// //Vertex v5;//v1v3 ， v1v3v5 neighbor
// //Vertex v6;//v1v4 ， v1v4v6 neighbor
// //Vertex v7;//v2v3 ， v2v3v7 neighbor
// //Vertex v8;//v2v4 ， v2v4v7 neighbor
// //List V2V5 = FindVertexsHavingSameSide(v1, v3);
// //List V2V6 = FindVertexsHavingSameSide(v1, v4);
// //List V7V1 = FindVertexsHavingSameSide(v2, v3);
// //List V8V1 = FindVertexsHavingSameSide(v2, v4);
// ////v5
// //if (V2V5[0] == v2)
// //{
// // v5 = V2V5[1];
// //}
// //else
// //{
// // v5 = V2V5[0];
// //}
// ////v6
// //if (V2V6[0] == v2)
// //{
// // v6 = V2V6[1];
// //}
// //else
// //{
// // v6 = V2V6[0];
// //}
// ////v7
// //if (V7V1[0] == v1)
// //{
// // v7 = V7V1[1];
// //}
// //else
// //{
// // v7 = V7V1[0];
// //}
// ////v8
// //if (V8V1[0] == v1)
// //{
// // v8 = V8V1[1];
// //}
// //else
// //{
// // v8 = V8V1[0];
// //}
// //// v135,v146,v237,v248 id
// //int v135 = FindTriangleByVertexs(v1, v3, v5);
// //int v146 = FindTriangleByVertexs(v1, v4, v6);
// //int v237 = FindTriangleByVertexs(v2, v3, v7);
// //int v248 = FindTriangleByVertexs(v2, v4, v8);
// //int v123 = FindTriangleByVertexs(v1, v2, v3);
// //int v124 = FindTriangleByVertexs(v1, v2, v4);
// //// face->neighbor
// //for (int i = 0; i < _mesh.AllTrianglesOld[v135].NeighborID.Length; i++)
// //{
// // if (_mesh.AllTrianglesOld[v135].NeighborID[i] == v123)
// // {// v135
// // _mesh.AllTrianglesOld[v135].NeighborID[i] = v237;
// // }
// //}
// //for (int i = 0; i < _mesh.AllTrianglesOld[v146].NeighborID.Length; i++)
// //{
// // if (_mesh.AllTrianglesOld[v146].NeighborID[i] == v124)
// // {// v146
// // _mesh.AllTrianglesOld[v146].NeighborID[i] = v248;
// // }
// //}
// //for (int i = 0; i < _mesh.AllTrianglesOld[v237].NeighborID.Length; i++)
// //{
// // if (_mesh.AllTrianglesOld[v237].NeighborID[i] == v123)
// // {// v237
// // _mesh.AllTrianglesOld[v237].NeighborID[i] = v135;
// // }
// //}
// //for (int i = 0; i < _mesh.AllTrianglesOld[v248].NeighborID.Length; i++)
// //{
// // if (_mesh.AllTrianglesOld[v248].NeighborID[i] == v124)
// // {// v248
// // _mesh.AllTrianglesOld[v248].NeighborID[i] = v146;
// // }
// //}
// //if (v135 == 0 || v146 == 0 || v237 == 0 || v248 == 0)
// //{
// // return false;
// //}
// #endregion
// List v3v4 = FindVertexsHavingSameSide(_v1, _v1.collapse);
// int v123 = FindTriangleByVertexs(_v1, _v1.collapse, v3v4[0]);
// int v124 = FindTriangleByVertexs(_v1, _v1.collapse, v3v4[1]);
// for (int i = 0; i < _v1.Face.Count; i++)
// {
// for (int j = 0; j < _v1.collapse.Face.Count; j++)
// {
// if (_v1.Face[i].HasVertex(v3v4[0].id) == _v1.collapse.Face[j].HasVertex(v3v4[0].id))
// {
// for (int k = 0; k < _v1.Face[i].NeighborID.Length; k++)
// {
// if (_v1.Face[i].NeighborID[k] == v123)
// {
// _v1.Face[i].NeighborID[k] = _v1.collapse.Face[j].id;
// break;
// }
// }
// for (int k = 0; k < _v1.collapse.Face[j].NeighborID.Length; k++)
// {
// if (_v1.Face[i].NeighborID[k] == v123)
// {
// _v1.Face[i].NeighborID[k] = _v1.collapse.Face[j].id;
// break;
// }
// }
// }
// if (_v1.Face[i].HasVertex(v3v4[1].id) == _v1.collapse.Face[j].HasVertex(v3v4[1].id))
// {
// for (int k = 0; k < _v1.Face[i].NeighborID.Length; k++)
// {
// if (_v1.Face[i].NeighborID[k] == v124)
// {
// _v1.Face[i].NeighborID[k] = _v1.collapse.Face[j].id;
// break;
// }
// }
// for (int k = 0; k < _v1.collapse.Face[j].NeighborID.Length; k++)
// {
// if (_v1.Face[i].NeighborID[k] == v124)
// {
// _v1.Face[i].NeighborID[k] = _v1.collapse.Face[j].id;
// break;
// }
// }
// }
// }
// }
// _mesh.DeleteVertex(_v1.id);
// return true;
//}
#endregion
///
/// mesh
///
public static bool UpdateMesh(ref G3DCore3DObjectOptimize _mesh)
{
// VertexOld VertexX
_mesh.AllVertexsX.Clear();
foreach (KeyValuePair t in _mesh.AllVertexsOld)
{
_mesh.AllVertexsX.Add(t.Value);
}
foreach (KeyValuePair t in _mesh.AllTrianglesOld)
{
t.Value.ComputeNormalByPostion();
}
for (int i = 0; i < _mesh.AllVertexsX.Count; i++)
{
_mesh.AllVertexsX[i].ComputeNormal();
}
return true;
}
///
///
///
public static bool IsPointInTriangle(Vertex _v1)
{
////Debug.Log(" IsPointInTriangle ，_v1 " + _v1.id);
if (_v1.neighbor.Count < 3)
{
return false;
}
for (int vertexCont = 0; vertexCont < _v1.neighbor.Count; vertexCont++)
{// v1 , v1
List v3v4 = FindVertexsHavingSameSide(_v1, _v1.neighbor[vertexCont]);
if (v3v4.Count < 2)// ， v1
{
return false;
}
else if (vertexCont < _v1.neighbor.Count - 1)
{// ，
////Debug.Log(" " + _v1.neighbor.Count+ ", "+ vertexCont+" ");
}
if (vertexCont == _v1.neighbor.Count - 1)
{ // 2， v1
return true;
}
}
return false;
}
///
///
///
public static List FindVertexsHavingSameSide(Vertex v1, Vertex v2)
{
List list = new List();
for (int i = 0; i < v1.neighbor.Count; i++)
{
for (int j = 0; j < v2.neighbor.Count; j++)
{
if (v1.neighbor[i].id == v2.neighbor[j].id)
{
list.Add(v1.neighbor[i]);
}
if (list.Count == 2)
{
return list;
}
}
}
return list;
}
///
/// mesh ,threshold ， ， d
public static void Start(ref G3DCore3DObjectOptimize object3D, int targetCount)
{
int count = object3D.AllVertexsX.Count;//
UpdateMesh(ref object3D);
//List contractileValueList = new List();
//SortedList contractileValueList1 = new SortedList();// ,
Dictionary VertexIDToCost = new Dictionary();
VertexIDToCost.Clear();
foreach (KeyValuePair t in object3D.AllVertexsOld)// ,
{
////Debug.Log(" " + (i+1) + " ， " + (count - i-1) + " ");
ComputeEdgeCostAtVertex(t.Value);
VertexIDToCost.Add(t.Value.id, t.Value.cost);
//ContractileValue temp = new ContractileValue(t.Value);
//idToIndex.Add(t.Key,indx);
//contractileValueList.Add(temp);
//contractileValueListOrigin.Add(temp);
}//
Dictionary dic1_SortedByValue = VertexIDToCost.OrderBy(o => o.Value).ToDictionary(p => p.Key, o => o.Value);
VertexIDToCost = dic1_SortedByValue;
//SortContractileValueList(ref contractileValueList);// ，
//contractileValueList.OrderBy(p => p.value); //
////Debug.Log("OrderList.Count = " + contractileValueList.Count);
int targetNumber = object3D.AllVertexsOld.Count - targetCount;
////Debug.Log("targetNumber" + targetNumber + "object3D.AllTrianglesOld.Count - targetCount" + (object3D.AllTrianglesOld.Count - targetCount));
while (targetNumber != 0)
{
if (VertexIDToCost.Count > 0)
{
////Debug.Log(" " + targetNumber + " ");
int temp = VertexIDToCost.Keys.First();
////Debug.Log(" id" + temp);
////Debug.Log("if costToVertexs " + VertexIDToCost.Count);
if (IsPointInTriangle(object3D.AllVertexsOld[temp]))
{
////Debug.Log(" contractileValueList "+ contractileValueList.Count);
targetNumber--;
if (targetNumber == 0) {
Console.Write("");
}
//bool b = Collapse(ref object3D, contractileValueList[0].v1, contractileValueList[0].v1.collapse,ref contractileValueList);// ， ， ,
//if (b)
//{
// #region
// contractileValueList.Clear();
// foreach (KeyValuePair t in object3D.AllVertexsOld)
// {
// ContractileValue temp1 = new ContractileValue(t.Value);
// contractileValueList.Add(temp1);
// }
// SortContractileValueList(ref contractileValueList);
// #endregion
//}
Collapse(ref object3D, object3D.AllVertexsOld[temp], object3D.AllVertexsOld[temp].collapse, ref VertexIDToCost);
}
else
{
// //Debug.Log(" ");
VertexIDToCost.Remove(VertexIDToCost.Keys.First());
//contractileValueList.RemoveAt(0);
}
}
else
{
break;
}
}
UpdateMesh(ref object3D);
//Debug.Log(" " + (count - object3D.AllVertexsX.Count) * 2);
//Debug.Log(" ");
}
///
///
///
public static bool Collapse(ref G3DCore3DObjectOptimize _mesh, Vertex u, Vertex v, ref Dictionary dic)
{
List xxx = FindVertexsHavingSameSide(u, v);//v3v4
TriangleP t1 = new TriangleP(-1);
TriangleP t2 = new TriangleP(-1); //
int i;
List tmp = new List();// u
v.RemoveNeighbor(u);//v u
u.RemoveNeighbor(v);//u v
// Collapse the edge uv by moving vertex u onto v
if (v == null)
{
// u is a vertex all by itself so just delete it
_mesh.DeleteVertex(u.id);
return true;
}
// List tmpTList = new List();
// make tmp a list of all the neighbors of u
for (i = 0; i < u.neighbor.Count; i++)
{
tmp.Add(u.neighbor[i]);
}
tmp.Remove(v);
// delete triangles on edge uv:
int iddd = 0;
for (i = u.Face.Count - 1; i >= 0; i--)
{
if (u.Face[i].HasVertex(v.id))
{
// delete(u.face[i]);
// u u.Face[i]
iddd++;
if (iddd == 1)
{
t1 = u.Face[i];
}
if (iddd == 2)
{
t2 = u.Face[i];
break;
}
//List trianglePs = new List()
}
}// t1 t2 u v，u t1t2 v u，v t1t2
v.Face.Remove(t1);
u.Face.Remove(t1);
v.Face.Remove(t2);
u.Face.Remove(t2);
// t3t4t5t6 neighborID
bool bo = false;
for (int k = 0; k < u.Face.Count; k++)
{
for (int m = 0; m < v.Face.Count; m++)
{
if (u.Face[k].NeighborID.Contains(t1.id) && v.Face[m].NeighborID.Contains(t1.id))
{
int tem1 = Array.IndexOf(u.Face[k].NeighborID, t1.id);
int tem2 = Array.IndexOf(v.Face[m].NeighborID, t1.id);
u.Face[k].NeighborID[tem1] = v.Face[m].id;
v.Face[m].NeighborID[tem2] = u.Face[k].id;
//_mesh.DeleteTriangleP(u.Face[i].id);
//iddd++;
bo = true;
//v.Face.Add(u.Face[k]);
}
if (bo)
{
break;
}
}
if (bo)
{
break;
}
}
bo = false;
for (int k = 0; k < u.Face.Count; k++)
{
for (int m = 0; m < v.Face.Count; m++)
{
if (u.Face[k].NeighborID.Contains(t2.id) && v.Face[m].NeighborID.Contains(t2.id))
{
int tem1 = Array.IndexOf(u.Face[k].NeighborID, t2.id);
int tem2 = Array.IndexOf(v.Face[m].NeighborID, t2.id);
u.Face[k].NeighborID[tem1] = v.Face[m].id;
v.Face[m].NeighborID[tem2] = u.Face[k].id;
//_mesh.DeleteTriangleP(u.Face[i].id);
//iddd++;
bo = true;
//v.Face.Add(u.Face[k]);
}
if (bo)
{
break;
}
}
if (bo)
{
break;
}
}
for (i = u.Face.Count - 1; i >= 0; i--)
{
u.Face[i].ReplaceVertex(u, v);
u.Face[i].ComputeNormalByPostion();
}//u t1t2 v u
foreach (TriangleP t in u.Face)
{
v.Face.Add(t);
}//v t1t2 u t1t2 v face
////Debug.Log("mesh " + _mesh.AllTrianglesOld.Count);
// update remaining triangles to have v instead of u
int j = u.neighbor.Count;//u v
for (i = 0; i < j; i++)
{
u.neighbor[i].RemoveNeighbor(u);
u.neighbor[i].AddNeighbor(v);//u v v neighbor
v.AddNeighbor(u.neighbor[i]);//v u neighbor
}
_mesh.DeleteTriangleP(t1.id);
_mesh.DeleteTriangleP(t2.id);//mesh t1t2
_mesh.DeleteVertex(u.id);//mesh u
xxx[0].Face.Remove(t1);
xxx[1].Face.Remove(t1);
xxx[0].Face.Remove(t2);
xxx[1].Face.Remove(t2);//v3v4 t1t2
v.ComputeNormal();//v t1t2 u t1t2 ，
ComputeEdgeCostAtVertex(v);// v cost
if (dic.ContainsKey(v.id))
{
dic[v.id] = v.cost;
}
//DeleteVertexs(_mesh, u);
////Debug.Log(" " + _mesh.AllVertexsOld.Count);
// recompute the edge collapse costs in neighborhood
//UpdateMesh(_mesh);
// //Debug.Log(" contractileValueList " + _list.Count);
int jjjj = dic.Keys.First();
//Debug.Log(" " + jjjj + " ");
dic.Remove(jjjj);
for (i = 0; i < tmp.Count; i++)
{
//ContractileValue tt = new ContractileValue(tmp[i]);
//if (_list.Remove(tt)) {
// //Debug.Log(" " + i + " ");
//}
ComputeEdgeCostAtVertex(tmp[i]);
if (dic.ContainsKey(tmp[i].id))
{
dic[tmp[i].id] = tmp[i].cost;
}
//ContractileValue ttt = new ContractileValue(tmp[i]);
////Debug.Log(" " + i + " ");
//_list.Add(ttt);
// //Debug.Log(" " + i + " ");
}
//dic[v.id] = v.cost;
Dictionary dic1_SortedByValue = dic.OrderBy(o => o.Value).ToDictionary(p => p.Key, o => o.Value);
dic = dic1_SortedByValue;
//Debug.Log(" "+ dic.Keys.First());
//_list.OrderBy(p => p.value);
// //Debug.Log(" contractileValueList " + _list.Count);
return true;
}
}
namespace GenesisWinForm
{
///
/// v1 v2
///
public class CollapseVertex
{
public CollapseVertex(double _value, Vertex _v1)
{
value = _value;
v1 = _v1;
}
public CollapseVertex(Vertex _v1)
{
value = _v1.cost;
v1 = _v1;
}
public double value;
public Vertex v1;
}
}
， 。 ，