Subversion Repositories gelsvn

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
39 bj 1 
#include <queue>
2 
#include <vector>
3 
 
4 
#include "triangulate.h"
5 
#include "HMesh/VertexCirculator.h"
6 
#include "HMesh/FaceCirculator.h"
7 
 
8 
using namespace std;
9 
using namespace CGLA;
10 
using namespace HMesh;
11 
 
12 
namespace HMeshUtil
13 
{
14 
	namespace
15 
	{
16 
		float normal_cone(vector<Vec3f>& norms)
17 
		{
18 
			float val = 1.0f;
19 
			for(int i=0;i<norms.size()-1;++i)
20 
				for(int j=i+1;j<norms.size();++j)
21 
					val = min(val, dot(norms[i], norms[j]));
22 
			return val;
23 
		}
24 
 
25 
 
26 
		void get_candidates(const VertexIter& v,
27 
												vector<VertexIter>& vertices_check)
28 
		{
29 
			VertexCirculator vc(v);
30 
			for(;!vc.end();++vc)
31 
				vertices_check.push_back(vc.get_vertex());
32 
		}
33 
 
34 
		const CGLA::Vec3f extended_normal(const VertexIter& v)
35 
		{
36 
			vector<HalfEdgeIter> hedges;
37 
 
38 
			VertexCirculator vc(v);
39 
			for(;!vc.end();++vc)
40 
				hedges.push_back(vc.get_halfedge());
41 
 
42 
			vector<Vec3f> one_ring;
43 
			int N = vc.no_steps();
44 
			for(int i=N-1;i>=0;--i)
45 
				{
46 
					HalfEdgeIter h = hedges[i];
47 
					//one_ring.push_back(h->vert->get_pos());
48 
					h = h->next;
49 
					while(h->vert != v)
50 
						{
51 
 							one_ring.push_back(h->vert->get_pos());
52 
							h = h->next;
53 
						}
54 
				}
55 
			Vec3f norm(0);
56 
			N= one_ring.size();
57 
			Vec3f p0 = v->get_pos();
58 
			for(int i=0;i<N;++i)
59 
				{
60 
					Vec3f p1 = one_ring[i];
61 
					Vec3f p2 = one_ring[(i+1)%N];
62 
					Vec3f e0 = normalize(p1-p0);
63 
					Vec3f e1 = normalize(p2-p0);
64 
					norm += cross(e0,e1)*acos(dot(e0,e1));
65 
				}
66 
			return normalize(norm);
67 
		}
68 
 
69 
 
70 
		struct PotentialEdge
71 
		{
72 
			VertexIter v0;
73 
			VertexIter v1;
74 
			FaceIter f;
75 
			int time;
76 
			float badness;
77 
		};
78 
 
79 
 
80 
	bool operator>(const PotentialEdge& e0, const PotentialEdge& e1)
81 
	{
82 
		return e0.badness>e1.badness;
83 
	}
84 
 
85 
	typedef std::priority_queue<PotentialEdge,
86 
															std::vector<PotentialEdge>,
87 
															std::greater<PotentialEdge> >
88 
	PotentialEdgeQueue;
89 
 
90 
	}
91 
 
92 
 
93 
	//algorithm: process_face(f, Q)
94 
	void process_face(FaceIter& f, PotentialEdgeQueue& Q)
95 
	{
96 
		//if f is triangle, return
97 
		if(f->last->next->next->next == f->last)
98 
			return;
99 
 
100 
		vector<VertexIter> verts;
101 
		vector<Vec3f> norms;
102 
 
103 
		typedef vector<VertexIter> VertVec;
104 
		vector<VertVec> nbrs;
105 
 
106 
		//for each vertex v in f
107 
		for(FaceCirculator fc(f);!fc.end();++fc)
108 
			{
109 
				VertexIter v = fc.get_vertex();
110 
				verts.push_back(v);
111 
				norms.push_back(extended_normal(v));
112 
				VertVec nbr_vec;
113 
				get_candidates(v, nbr_vec);
114 
				nbrs.push_back(nbr_vec);
115 
			}
116 
 
117 
		int n = verts.size();
118 
 
119 
		for(int i=0;i<n-2;++i)
120 
			for(int j=i+2;j<n;++j)
121 
				{
122 
					if(i==0 && j==(n-1)) continue;
123 
					assert((i-j)*(i-j)==1);
124 
 
125 
					// 			For each vertex pair (v0,v1)
126 
					// 		if v0 belongs to check_lists[v1] then continue with next pair
127 
					if(find(nbrs[j].begin(), nbrs[j].end(), verts[i])
128 
						 == nbrs[j].end())
129 
						{
130 
							vector<Vec3f> norms_a;
131 
							vector<Vec3f> norms_b;
132 
							int n2=j-i+1;
133 
 
134 
							for(int k=0;k<n;++k)
135 
								{
136 
									if(k>=i && k<=j)
137 
										norms_a.push_back(norms[k]);
138 
									if(k<=i || k>=j)
139 
										norms_b.push_back(norms[k]);
140 
								}
141 
							float badness_a = normal_cone(norms_a);
142 
							float badness_b = normal_cone(norms_b);
143 
 
144 
							float badness = 1.0f/(sqr(badness_a)*sqr(badness_b));
145 
							// 		add (v0,v1,f,f.touchvalue,badness) to Q;
146 
							PotentialEdge pot_edge;
147 
							pot_edge.v0 = verts[i];
148 
							pot_edge.v1 = verts[j];
149 
							pot_edge.f = f;
150 
							pot_edge.time = f->touched;
151 
							pot_edge.badness = badness;
152 
							Q.push(pot_edge);
153 
						}
154 
				}
155 
	}
156 
 
157 
 
158 
	void triangulate_face_order(Manifold& m)
159 
	{
160 
		PotentialEdgeQueue Q;
161 
 
162 
		for(FaceIter f_itr = m.faces_begin();
163 
				f_itr != m.faces_end(); ++f_itr)
164 
			process_face(f_itr, Q);
165 
 
166 
		while(!Q.empty())
167 
			{
168 
				PotentialEdge pot = Q.top();
169 
 
170 
				// If face has NOT been processed since this record
171 
				// was created.
172 
				if(pot.f->touched == pot.time)
173 
					{
174 
						// Make list of faces adjacent to f (adj_faces).
175 
						vector<FaceIter> nbr_faces;
176 
						FaceCirculator fc(pot.f);
177 
						for(; !fc.end(); ++fc)
178 
							nbr_faces.push_back(fc.get_face());
179 
 
180 
						// create edge(v0,v1) producing a new face fn;
181 
						FaceIter fn = m.split_face(pot.f, pot.v0, pot.v1);
182 
 
183 
						nbr_faces.push_back(pot.f);
184 
						nbr_faces.push_back(fn);
185 
 
186 
						for(int i=0;i<nbr_faces.size();++i)
187 
							{
188 
								nbr_faces[i]->touched++;
189 
								process_face(nbr_faces[i],Q);
190 
							}
191 
					}
192 
				Q.pop();
193 
			}
194 
	}
195 
 
196 
 
197 
 
198 
 
199 
 
200 
}