WebSVN – gelsvn – Diff – /branches/wireframe-experiments/src/HMesh/triangulate.cpp


#include <queue>
#include <vector>
 
#include "triangulate.h"
#include "HMesh/VertexCirculator.h"
#include "HMesh/FaceCirculator.h"
 
using namespace std;
using namespace CGLA;
using namespace HMesh;
 
namespace HMesh
{
  void get_candidates(const VertexIter& v,
											vector<HalfEdgeIter>& candidates)
											
											
  {
    vector<VertexIter> vertices;
    vector<HalfEdgeIter> hedges;
						
    VertexCirculator vc(v);
    for(;!vc.end();++vc)
      {
				vertices.push_back(vc.get_vertex());
				hedges.push_back(vc.get_halfedge());
      }
    size_t N = vc.no_steps();
    vector<VertexIter> vertices_check(vertices);
    assert(N==vertices.size());
 
    for(int i=N-1;i>=0;--i)
      {
				HalfEdgeIter h = hedges[i]->next;
				while(h->vert != vertices[(i+N-1)%N])
					{
						if(find(vertices_check.begin(),vertices_check.end(), 
										h->vert) == vertices_check.end())
							candidates.push_back(h);
						h = h->next;
						
						// TODO : does not compile in debug mode in visual studio
						//assert(h!=v);
					}
      }
  }
 
  float curv(const Vec3f& p, std::vector<Vec3f>& vec)
  {
    int N = vec.size();
    std::vector<Vec3f> normals;
    for(int i=0;i<N;++i)
      {
				
				Vec3f norm = normalize(cross(vec[i]-p, vec[(i+1)%N]-p));
				normals.push_back(norm);
      }
    float alpha = 0;
    for(int i=0;i<N;++i)
      {
				alpha += (vec[i]-p).length()*acos(dot(normals[i],normals[(i+1)%N]));
      }
    return alpha;
  }
 
  float get_badness(const VertexIter& v, const VertexIter& n)
  {
    vector<HalfEdgeIter> hedges;
						
    VertexCirculator vc(v);
    for(;!vc.end();++vc)
      hedges.push_back(vc.get_halfedge());
 
    vector<Vec3f> one_ring;
    vector<Vec3f> one_ring_n;
    int N = vc.no_steps();
    for(int i=N-1;i>=0;--i)
      {
				HalfEdgeIter h = hedges[i];
				h = h->next;
				while(h->vert != v)
					{
						one_ring.push_back(h->vert->pos);
						if(h->vert != n)
							one_ring_n.push_back(h->vert->pos);
						h = h->next;
					}
      }
    return curv(v->pos,one_ring)-curv(v->pos,one_ring_n);
  }
 
 
  const CGLA::Vec3f get_normal(const VertexIter& v)
  {
 
    vector<HalfEdgeIter> hedges;
						
    VertexCirculator vc(v);
    for(;!vc.end();++vc)
      hedges.push_back(vc.get_halfedge());
 
    vector<Vec3f> one_ring;
    int N = vc.no_steps();
    for(int i=N-1;i>=0;--i)
      {
				HalfEdgeIter h = hedges[i];
				h = h->next;
				while(h->vert != v)
					{
						one_ring.push_back(h->vert->pos);
						h = h->next;
					}
      }
    Vec3f norm(0);
    N= one_ring.size();
    Vec3f p0 = v->pos;
    for(int i=0;i<N;++i)
      {
				Vec3f p1 = one_ring[i];
				Vec3f p2 = one_ring[(i+1)%N];
				Vec3f e0 = normalize(p1-p0);
				Vec3f e1 = normalize(p2-p0);
				norm += cross(e0,e1)*acos(dot(e0,e1));
      }
    return normalize(norm);
  }
 
  void safe_triangulate(Manifold& m)
  {
    vector<FaceIter> fv;
    for(FaceIter  fi=m.faces_begin(); fi != m.faces_end(); ++fi)
      fv.push_back(fi);
    for(size_t i=0;i<fv.size();++i)
      m.safe_triangulate(fv[i]);
  }
 
  void triangulate(Manifold& m)
  {
    vector<FaceIter> fv;
    for(FaceIter  fi=m.faces_begin(); fi != m.faces_end(); ++fi)
      fv.push_back(fi);
    for(size_t i=0;i<fv.size();++i)
      m.triangulate(fv[i]);
  }
 
  struct PotentialEdge
  {
    int time_tag;
    float badness;
    FaceIter f;
    VertexIter v0, v1;
  };
 
  bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)
  {
    return e0.badness>e1.badness;
  }
 
  typedef std::priority_queue<PotentialEdge,
															std::vector<PotentialEdge>,
															std::greater<PotentialEdge> > 
  PotentialEdgeQueue;
 
  void insert_potential_edges(const VertexIter& v,
															PotentialEdgeQueue& pot_edges)
  {
    vector<Vec3f> one_ring;
    vector<HalfEdgeIter> candidates;
    get_candidates(v, candidates);
 
    Vec3f p0 = v->pos;
    Vec3f norm = normal(v);
    int n = candidates.size();
    for(int i=0;i<n;++i)
      {
				VertexIter v_n = candidates[i]->vert;
				Vec3f edir = normalize(v_n->pos-p0);
				Vec3f norm_n = normal(v_n);
				float bad = sqr(dot(edir, norm));
				float bad_n = sqr(dot(edir, norm_n));
						
				PotentialEdge pot;
 
				/* So if the edge between two vertices is not orthogonal to 
					 their normals, the badness is increased. Badness is also
					 increased if the normals are very different. */
 
				pot.badness = bad+bad_n - dot(norm_n,norm);
				pot.time_tag = v->touched;
				pot.v0 = v;
				pot.v1 = candidates[i]->vert;
				pot.f = candidates[i]->face;
						
				pot_edges.push(pot);
      }
  }
 
										
  void create_candidates(Manifold& m, PotentialEdgeQueue& pot_edges)
  {
    for(VertexIter v= m.vertices_begin(); v!= m.vertices_end();++v)
      {
				v->touched = 0;
				insert_potential_edges(v, pot_edges);
      }
  }
 
	
 
 
  void curvature_triangulate(Manifold& m)
  {
    PotentialEdgeQueue pot_edges;
 
    // Create candidates
    create_candidates(m,pot_edges);
		
    while(!pot_edges.empty())
      {
				const PotentialEdge& pot_edge = pot_edges.top();
 
				// Record all the vertices of the face. We need to 
				// recompute the candidates.
				std::vector<VertexIter> reeval_vec;
				FaceCirculator fc(pot_edge.f);
				while(!fc.end())
					{
						reeval_vec.push_back(fc.get_vertex());
						++fc;
					}
 
				VertexIter v0 = pot_edge.v0;
 
				// Make sure that the vertex has not been touched since 
				// we created the potential edge. If the vertex has been
				// touched the candidate edge has either (a) been processed,
				// (b) received a lower priority or (c) become invalid.
				if(pot_edge.time_tag == v0->touched)
					{
						VertexIter v1 = pot_edge.v1;
 
						vector<Vec3f> one_ring;
						vector<HalfEdgeIter> candidates;
												
						m.split_face(pot_edge.f, v0, v1);
 
						// Recompute priorities.
						for(size_t i=0;i<reeval_vec.size();++i)
							{
								VertexIter& v = reeval_vec[i];
								v->touched++;
								insert_potential_edges(v, pot_edges);
							}
						
					}
				pot_edges.pop();
      }
 
  }
 
		void shortest_edge_triangulate(Manifold& m)
		{
			int work;
			do
				{
					// For every face.
					work = 0;
					for(FaceIter fi =m.faces_begin(); fi != m.faces_end(); ++fi)
						{
							// Create a vector of vertices.
							vector<VertexIter> verts;
							for(FaceCirculator fc(fi); !fc.end(); ++fc)
								verts.push_back(fc.get_vertex());
								
							// If there are just three we are done.
							if(verts.size() == 3) continue;
										
							// Find vertex pairs that may be connected.
							vector<pair<int,int> > vpairs;
							const int N = verts.size();
							for(int i=0;i<N-2;++i)
								for(int j=i+2;j<N; ++j)
									if(!is_connected(verts[i], verts[j]))
										vpairs.push_back(pair<int,int>(i,j));
										
							if(vpairs.empty())
								{
									cout << "Warning: could not triangulate a face." 
											 << "Probably a vertex appears more than one time in other vertex's one-ring" << endl;
									continue;
								}
									
							/* For all vertex pairs, find the edge lengths. Combine the
								 vertices forming the shortest edge. */
											 
							float min_len=FLT_MAX;
							int min_k = -1;
							for(size_t k=0;k<vpairs.size(); ++k)
								{
									int i = vpairs[k].first;
									int j = vpairs[k].second;
									float len = sqr_length(verts[i]->pos-verts[j]->pos);
												
									if(len<min_len)
										{
											min_len = len;
											min_k = k;
										}
								}
							assert(min_k != -1);
										
							{
								// Split faces along edge whose midpoint is closest to isovalue
								int i = vpairs[min_k].first;
								int j = vpairs[min_k].second;
								m.split_face(fi, verts[i], verts[j]);
							}
							++work;
										
						}
				}
			while(work);
		}
 
 
 
 
}
 

Rev 183	Rev 393
1	`#include <queue>`	1	`#include <queue>`
2	`#include <vector>`	2	`#include <vector>`
3		3
4	`#include "triangulate.h"`	4	`#include "triangulate.h"`
5	`#include "HMesh/VertexCirculator.h"`	5	`#include "HMesh/VertexCirculator.h"`
6	`#include "HMesh/FaceCirculator.h"`	6	`#include "HMesh/FaceCirculator.h"`
7		7
8	`using namespace std;`	8	`using namespace std;`
9	`using namespace CGLA;`	9	`using namespace CGLA;`
10	`using namespace HMesh;`	10	`using namespace HMesh;`
11		11
12	`namespace HMesh`	12	`namespace HMesh`
13	`{`	13	`{`
14	`void get_candidates(const VertexIter& v,`	14	`void get_candidates(const VertexIter& v,`
15	`vector<HalfEdgeIter>& candidates)`	15	`vector<HalfEdgeIter>& candidates)`
16		16
17		17
18	`{`	18	`{`
19	`vector<VertexIter> vertices;`	19	`vector<VertexIter> vertices;`
20	`vector<HalfEdgeIter> hedges;`	20	`vector<HalfEdgeIter> hedges;`
21		21
22	`VertexCirculator vc(v);`	22	`VertexCirculator vc(v);`
23	`for(;!vc.end();++vc)`	23	`for(;!vc.end();++vc)`
24	`{`	24	`{`
25	`vertices.push_back(vc.get_vertex());`	25	`vertices.push_back(vc.get_vertex());`
26	`hedges.push_back(vc.get_halfedge());`	26	`hedges.push_back(vc.get_halfedge());`
27	`}`	27	`}`
28	`size_t N = vc.no_steps();`	28	`size_t N = vc.no_steps();`
29	`vector<VertexIter> vertices_check(vertices);`	29	`vector<VertexIter> vertices_check(vertices);`
30	`assert(N==vertices.size());`	30	`assert(N==vertices.size());`
31		31
32	`for(int i=N-1;i>=0;--i)`	32	`for(int i=N-1;i>=0;--i)`
33	`{`	33	`{`
34	`HalfEdgeIter h = hedges[i]->next;`	34	`HalfEdgeIter h = hedges[i]->next;`
35	`while(h->vert != vertices[(i+N-1)%N])`	35	`while(h->vert != vertices[(i+N-1)%N])`
36	`{`	36	`{`
37	`if(find(vertices_check.begin(),vertices_check.end(),`	37	`if(find(vertices_check.begin(),vertices_check.end(),`
38	`h->vert) == vertices_check.end())`	38	`h->vert) == vertices_check.end())`
39	`candidates.push_back(h);`	39	`candidates.push_back(h);`
40	`h = h->next;`	40	`h = h->next;`
41		41
42	`// TODO : does not compile in debug mode in visual studio`	42	`// TODO : does not compile in debug mode in visual studio`
43	`//assert(h!=v);`	43	`//assert(h!=v);`
44	`}`	44	`}`
45	`}`	45	`}`
46	`}`	46	`}`
47		47
48	`float curv(const Vec3f& p, std::vector<Vec3f>& vec)`	48	`float curv(const Vec3f& p, std::vector<Vec3f>& vec)`
49	`{`	49	`{`
50	`int N = vec.size();`	50	`int N = vec.size();`
51	`std::vector<Vec3f> normals;`	51	`std::vector<Vec3f> normals;`
52	`for(int i=0;i<N;++i)`	52	`for(int i=0;i<N;++i)`
53	`{`	53	`{`
54		54
55	`Vec3f norm = normalize(cross(vec[i]-p, vec[(i+1)%N]-p));`	55	`Vec3f norm = normalize(cross(vec[i]-p, vec[(i+1)%N]-p));`
56	`normals.push_back(norm);`	56	`normals.push_back(norm);`
57	`}`	57	`}`
58	`float alpha = 0;`	58	`float alpha = 0;`
59	`for(int i=0;i<N;++i)`	59	`for(int i=0;i<N;++i)`
60	`{`	60	`{`
61	`alpha += (vec[i]-p).length()*acos(dot(normals[i],normals[(i+1)%N]));`	61	`alpha += (vec[i]-p).length()*acos(dot(normals[i],normals[(i+1)%N]));`
62	`}`	62	`}`
63	`return alpha;`	63	`return alpha;`
64	`}`	64	`}`
65		65
66	`float get_badness(const VertexIter& v, const VertexIter& n)`	66	`float get_badness(const VertexIter& v, const VertexIter& n)`
67	`{`	67	`{`
68	`vector<HalfEdgeIter> hedges;`	68	`vector<HalfEdgeIter> hedges;`
69		69
70	`VertexCirculator vc(v);`	70	`VertexCirculator vc(v);`
71	`for(;!vc.end();++vc)`	71	`for(;!vc.end();++vc)`
72	`hedges.push_back(vc.get_halfedge());`	72	`hedges.push_back(vc.get_halfedge());`
73		73
74	`vector<Vec3f> one_ring;`	74	`vector<Vec3f> one_ring;`
75	`vector<Vec3f> one_ring_n;`	75	`vector<Vec3f> one_ring_n;`
76	`int N = vc.no_steps();`	76	`int N = vc.no_steps();`
77	`for(int i=N-1;i>=0;--i)`	77	`for(int i=N-1;i>=0;--i)`
78	`{`	78	`{`
79	`HalfEdgeIter h = hedges[i];`	79	`HalfEdgeIter h = hedges[i];`
80	`h = h->next;`	80	`h = h->next;`
81	`while(h->vert != v)`	81	`while(h->vert != v)`
82	`{`	82	`{`
83	`one_ring.push_back(h->vert->pos);`	83	`one_ring.push_back(h->vert->pos);`
84	`if(h->vert != n)`	84	`if(h->vert != n)`
85	`one_ring_n.push_back(h->vert->pos);`	85	`one_ring_n.push_back(h->vert->pos);`
86	`h = h->next;`	86	`h = h->next;`
87	`}`	87	`}`
88	`}`	88	`}`
89	`return curv(v->pos,one_ring)-curv(v->pos,one_ring_n);`	89	`return curv(v->pos,one_ring)-curv(v->pos,one_ring_n);`
90	`}`	90	`}`
91		91
92		92
93	`const CGLA::Vec3f get_normal(const VertexIter& v)`	93	`const CGLA::Vec3f get_normal(const VertexIter& v)`
94	`{`	94	`{`
95		95
96	`vector<HalfEdgeIter> hedges;`	96	`vector<HalfEdgeIter> hedges;`
97		97
98	`VertexCirculator vc(v);`	98	`VertexCirculator vc(v);`
99	`for(;!vc.end();++vc)`	99	`for(;!vc.end();++vc)`
100	`hedges.push_back(vc.get_halfedge());`	100	`hedges.push_back(vc.get_halfedge());`
101		101
102	`vector<Vec3f> one_ring;`	102	`vector<Vec3f> one_ring;`
103	`int N = vc.no_steps();`	103	`int N = vc.no_steps();`
104	`for(int i=N-1;i>=0;--i)`	104	`for(int i=N-1;i>=0;--i)`
105	`{`	105	`{`
106	`HalfEdgeIter h = hedges[i];`	106	`HalfEdgeIter h = hedges[i];`
107	`h = h->next;`	107	`h = h->next;`
108	`while(h->vert != v)`	108	`while(h->vert != v)`
109	`{`	109	`{`
110	`one_ring.push_back(h->vert->pos);`	110	`one_ring.push_back(h->vert->pos);`
111	`h = h->next;`	111	`h = h->next;`
112	`}`	112	`}`
113	`}`	113	`}`
114	`Vec3f norm(0);`	114	`Vec3f norm(0);`
115	`N= one_ring.size();`	115	`N= one_ring.size();`
116	`Vec3f p0 = v->pos;`	116	`Vec3f p0 = v->pos;`
117	`for(int i=0;i<N;++i)`	117	`for(int i=0;i<N;++i)`
118	`{`	118	`{`
119	`Vec3f p1 = one_ring[i];`	119	`Vec3f p1 = one_ring[i];`
120	`Vec3f p2 = one_ring[(i+1)%N];`	120	`Vec3f p2 = one_ring[(i+1)%N];`
121	`Vec3f e0 = normalize(p1-p0);`	121	`Vec3f e0 = normalize(p1-p0);`
122	`Vec3f e1 = normalize(p2-p0);`	122	`Vec3f e1 = normalize(p2-p0);`
123	`norm += cross(e0,e1)*acos(dot(e0,e1));`	123	`norm += cross(e0,e1)*acos(dot(e0,e1));`
124	`}`	124	`}`
125	`return normalize(norm);`	125	`return normalize(norm);`
126	`}`	126	`}`
127		127
128	`void safe_triangulate(Manifold& m)`	128	`void safe_triangulate(Manifold& m)`
129	`{`	129	`{`
130	`vector<FaceIter> fv;`	130	`vector<FaceIter> fv;`
131	`for(FaceIter fi=m.faces_begin(); fi != m.faces_end(); ++fi)`	131	`for(FaceIter fi=m.faces_begin(); fi != m.faces_end(); ++fi)`
132	`fv.push_back(fi);`	132	`fv.push_back(fi);`
133	`for(size_t i=0;i<fv.size();++i)`	133	`for(size_t i=0;i<fv.size();++i)`
134	`m.safe_triangulate(fv[i]);`	134	`m.safe_triangulate(fv[i]);`
135	`}`	135	`}`
136		136
137	`void triangulate(Manifold& m)`	137	`void triangulate(Manifold& m)`
138	`{`	138	`{`
139	`vector<FaceIter> fv;`	139	`vector<FaceIter> fv;`
140	`for(FaceIter fi=m.faces_begin(); fi != m.faces_end(); ++fi)`	140	`for(FaceIter fi=m.faces_begin(); fi != m.faces_end(); ++fi)`
141	`fv.push_back(fi);`	141	`fv.push_back(fi);`
142	`for(size_t i=0;i<fv.size();++i)`	142	`for(size_t i=0;i<fv.size();++i)`
143	`m.triangulate(fv[i]);`	143	`m.triangulate(fv[i]);`
144	`}`	144	`}`
145		145
146	`struct PotentialEdge`	146	`struct PotentialEdge`
147	`{`	147	`{`
148	`int time_tag;`	148	`int time_tag;`
149	`float badness;`	149	`float badness;`
150	`FaceIter f;`	150	`FaceIter f;`
151	`VertexIter v0, v1;`	151	`VertexIter v0, v1;`
152	`};`	152	`};`
153		153
154	`bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)`	154	`bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)`
155	`{`	155	`{`
156	`return e0.badness>e1.badness;`	156	`return e0.badness>e1.badness;`
157	`}`	157	`}`
158		158
159	`typedef std::priority_queue<PotentialEdge,`	159	`typedef std::priority_queue<PotentialEdge,`
160	`std::vector<PotentialEdge>,`	160	`std::vector<PotentialEdge>,`
161	`std::greater<PotentialEdge> >`	161	`std::greater<PotentialEdge> >`
162	`PotentialEdgeQueue;`	162	`PotentialEdgeQueue;`
163		163
164	`void insert_potential_edges(const VertexIter& v,`	164	`void insert_potential_edges(const VertexIter& v,`
165	`PotentialEdgeQueue& pot_edges)`	165	`PotentialEdgeQueue& pot_edges)`
166	`{`	166	`{`
167	`vector<Vec3f> one_ring;`	167	`vector<Vec3f> one_ring;`
168	`vector<HalfEdgeIter> candidates;`	168	`vector<HalfEdgeIter> candidates;`
169	`get_candidates(v, candidates);`	169	`get_candidates(v, candidates);`
170		170
171	`Vec3f p0 = v->pos;`	171	`Vec3f p0 = v->pos;`
172	`Vec3f norm = normal(v);`	172	`Vec3f norm = normal(v);`
173	`int n = candidates.size();`	173	`int n = candidates.size();`
174	`for(int i=0;i<n;++i)`	174	`for(int i=0;i<n;++i)`
175	`{`	175	`{`
176	`VertexIter v_n = candidates[i]->vert;`	176	`VertexIter v_n = candidates[i]->vert;`
177	`Vec3f edir = normalize(v_n->pos-p0);`	177	`Vec3f edir = normalize(v_n->pos-p0);`
178	`Vec3f norm_n = normal(v_n);`	178	`Vec3f norm_n = normal(v_n);`
179	`float bad = sqr(dot(edir, norm));`	179	`float bad = sqr(dot(edir, norm));`
180	`float bad_n = sqr(dot(edir, norm_n));`	180	`float bad_n = sqr(dot(edir, norm_n));`
181		181
182	`PotentialEdge pot;`	182	`PotentialEdge pot;`
183		183
184	`/* So if the edge between two vertices is not orthogonal to`	184	`/* So if the edge between two vertices is not orthogonal to`
185	`their normals, the badness is increased. Badness is also`	185	`their normals, the badness is increased. Badness is also`
186	`increased if the normals are very different. */`	186	`increased if the normals are very different. */`
187		187
188	`pot.badness = bad+bad_n - dot(norm_n,norm);`	188	`pot.badness = bad+bad_n - dot(norm_n,norm);`
189	`pot.time_tag = v->touched;`	189	`pot.time_tag = v->touched;`
190	`pot.v0 = v;`	190	`pot.v0 = v;`
191	`pot.v1 = candidates[i]->vert;`	191	`pot.v1 = candidates[i]->vert;`
192	`pot.f = candidates[i]->face;`	192	`pot.f = candidates[i]->face;`
193		193
194	`pot_edges.push(pot);`	194	`pot_edges.push(pot);`
195	`}`	195	`}`
196	`}`	196	`}`
197		197
198		198
199	`void create_candidates(Manifold& m, PotentialEdgeQueue& pot_edges)`	199	`void create_candidates(Manifold& m, PotentialEdgeQueue& pot_edges)`
200	`{`	200	`{`
201	`for(VertexIter v= m.vertices_begin(); v!= m.vertices_end();++v)`	201	`for(VertexIter v= m.vertices_begin(); v!= m.vertices_end();++v)`
202	`{`	202	`{`
203	`v->touched = 0;`	203	`v->touched = 0;`
204	`insert_potential_edges(v, pot_edges);`	204	`insert_potential_edges(v, pot_edges);`
205	`}`	205	`}`
206	`}`	206	`}`
207		207
208		208
209		209
210		210
211	`void curvature_triangulate(Manifold& m)`	211	`void curvature_triangulate(Manifold& m)`
212	`{`	212	`{`
213	`PotentialEdgeQueue pot_edges;`	213	`PotentialEdgeQueue pot_edges;`
214		214
215	`// Create candidates`	215	`// Create candidates`
216	`create_candidates(m,pot_edges);`	216	`create_candidates(m,pot_edges);`
217		217
218	`while(!pot_edges.empty())`	218	`while(!pot_edges.empty())`
219	`{`	219	`{`
220	`const PotentialEdge& pot_edge = pot_edges.top();`	220	`const PotentialEdge& pot_edge = pot_edges.top();`
221		221
222	`// Record all the vertices of the face. We need to`	222	`// Record all the vertices of the face. We need to`
223	`// recompute the candidates.`	223	`// recompute the candidates.`
224	`std::vector<VertexIter> reeval_vec;`	224	`std::vector<VertexIter> reeval_vec;`
225	`FaceCirculator fc(pot_edge.f);`	225	`FaceCirculator fc(pot_edge.f);`
226	`while(!fc.end())`	226	`while(!fc.end())`
227	`{`	227	`{`
228	`reeval_vec.push_back(fc.get_vertex());`	228	`reeval_vec.push_back(fc.get_vertex());`
229	`++fc;`	229	`++fc;`
230	`}`	230	`}`
231		231
232	`VertexIter v0 = pot_edge.v0;`	232	`VertexIter v0 = pot_edge.v0;`
233		233
234	`// Make sure that the vertex has not been touched since`	234	`// Make sure that the vertex has not been touched since`
235	`// we created the potential edge. If the vertex has been`	235	`// we created the potential edge. If the vertex has been`
236	`// touched the candidate edge has either (a) been processed,`	236	`// touched the candidate edge has either (a) been processed,`
237	`// (b) received a lower priority or (c) become invalid.`	237	`// (b) received a lower priority or (c) become invalid.`
238	`if(pot_edge.time_tag == v0->touched)`	238	`if(pot_edge.time_tag == v0->touched)`
239	`{`	239	`{`
240	`VertexIter v1 = pot_edge.v1;`	240	`VertexIter v1 = pot_edge.v1;`
241		241
242	`vector<Vec3f> one_ring;`	242	`vector<Vec3f> one_ring;`
243	`vector<HalfEdgeIter> candidates;`	243	`vector<HalfEdgeIter> candidates;`
244		244
245	`m.split_face(pot_edge.f, v0, v1);`	245	`m.split_face(pot_edge.f, v0, v1);`
246		246
247	`// Recompute priorities.`	247	`// Recompute priorities.`
248	`for(size_t i=0;i<reeval_vec.size();++i)`	248	`for(size_t i=0;i<reeval_vec.size();++i)`
249	`{`	249	`{`
250	`VertexIter& v = reeval_vec[i];`	250	`VertexIter& v = reeval_vec[i];`
251	`v->touched++;`	251	`v->touched++;`
252	`insert_potential_edges(v, pot_edges);`	252	`insert_potential_edges(v, pot_edges);`
253	`}`	253	`}`
254		254
255	`}`	255	`}`
256	`pot_edges.pop();`	256	`pot_edges.pop();`
257	`}`	257	`}`
258		258
259	`}`	259	`}`
260		260
261	`void shortest_edge_triangulate(Manifold& m)`	261	`void shortest_edge_triangulate(Manifold& m)`
262	`{`	262	`{`
263	`int work;`	263	`int work;`
264	`do`	264	`do`
265	`{`	265	`{`
266	`// For every face.`	266	`// For every face.`
267	`work = 0;`	267	`work = 0;`
268	`for(FaceIter fi =m.faces_begin(); fi != m.faces_end(); ++fi)`	268	`for(FaceIter fi =m.faces_begin(); fi != m.faces_end(); ++fi)`
269	`{`	269	`{`
270	`// Create a vector of vertices.`	270	`// Create a vector of vertices.`
271	`vector<VertexIter> verts;`	271	`vector<VertexIter> verts;`
272	`for(FaceCirculator fc(fi); !fc.end(); ++fc)`	272	`for(FaceCirculator fc(fi); !fc.end(); ++fc)`
273	`verts.push_back(fc.get_vertex());`	273	`verts.push_back(fc.get_vertex());`
274		274
275	`// If there are just three we are done.`	275	`// If there are just three we are done.`
276	`if(verts.size() == 3) continue;`	276	`if(verts.size() == 3) continue;`
277		277
278	`// Find vertex pairs that may be connected.`	278	`// Find vertex pairs that may be connected.`
279	`vector<pair<int,int> > vpairs;`	279	`vector<pair<int,int> > vpairs;`
280	`const int N = verts.size();`	280	`const int N = verts.size();`
281	`for(int i=0;i<N-2;++i)`	281	`for(int i=0;i<N-2;++i)`
282	`for(int j=i+2;j<N; ++j)`	282	`for(int j=i+2;j<N; ++j)`
283	`if(!is_connected(verts[i], verts[j]))`	283	`if(!is_connected(verts[i], verts[j]))`
284	`vpairs.push_back(pair<int,int>(i,j));`	284	`vpairs.push_back(pair<int,int>(i,j));`
285		285
286	`if(vpairs.empty())`	286	`if(vpairs.empty())`
287	`{`	287	`{`
288	`cout << "Warning: could not triangulate a face."`	288	`cout << "Warning: could not triangulate a face."`
289	`<< "Probably a vertex appears more than one time in other vertex's one-ring" << endl;`	289	`<< "Probably a vertex appears more than one time in other vertex's one-ring" << endl;`
290	`continue;`	290	`continue;`
291	`}`	291	`}`
292		292
293	`/* For all vertex pairs, find the edge lengths. Combine the`	293	`/* For all vertex pairs, find the edge lengths. Combine the`
294	`vertices forming the shortest edge. */`	294	`vertices forming the shortest edge. */`
295		295
296	`float min_len=FLT_MAX;`	296	`float min_len=FLT_MAX;`
297	`int min_k = -1;`	297	`int min_k = -1;`
298	`for(size_t k=0;k<vpairs.size(); ++k)`	298	`for(size_t k=0;k<vpairs.size(); ++k)`
299	`{`	299	`{`
300	`int i = vpairs[k].first;`	300	`int i = vpairs[k].first;`
301	`int j = vpairs[k].second;`	301	`int j = vpairs[k].second;`
302	`float len = sqr_length(verts[i]->pos-verts[j]->pos);`	302	`float len = sqr_length(verts[i]->pos-verts[j]->pos);`
303		303
304	`if(len<min_len)`	304	`if(len<min_len)`
305	`{`	305	`{`
306	`min_len = len;`	306	`min_len = len;`
307	`min_k = k;`	307	`min_k = k;`
308	`}`	308	`}`
309	`}`	309	`}`
310	`assert(min_k != -1);`	310	`assert(min_k != -1);`
311		311
312	`{`	312	`{`
313	`// Split faces along edge whose midpoint is closest to isovalue`	313	`// Split faces along edge whose midpoint is closest to isovalue`
314	`int i = vpairs[min_k].first;`	314	`int i = vpairs[min_k].first;`
315	`int j = vpairs[min_k].second;`	315	`int j = vpairs[min_k].second;`
316	`m.split_face(fi, verts[i], verts[j]);`	316	`m.split_face(fi, verts[i], verts[j]);`
317	`}`	317	`}`
318	`++work;`	318	`++work;`
319		319
320	`}`	320	`}`
321	`}`	321	`}`
322	`while(work);`	322	`while(work);`
323	`}`	323	`}`
324		324
325		325
326		326
327		327
328	`}`	328	`}`
329		329

Subversion Repositories gelsvn

(root)/branches/wireframe-experiments/src/HMesh/triangulate.cpp – Rev 183 → 393