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;
136 jab 19 
			for(size_t i=0;i<norms.size()-1;++i)
20 
				for(size_t j=i+1;j<norms.size();++j)
39 bj 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 
						{
62 jab 51 
 							one_ring.push_back(h->vert->pos);
39 bj 52 
							h = h->next;
53 
						}
54 
				}
55 
			Vec3f norm(0);
56 
			N= one_ring.size();
62 jab 57 
			Vec3f p0 = v->pos;
39 bj 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 
 
133 
							for(int k=0;k<n;++k)
134 
								{
135 
									if(k>=i && k<=j)
136 
										norms_a.push_back(norms[k]);
137 
									if(k<=i || k>=j)
138 
										norms_b.push_back(norms[k]);
139 
								}
140 
							float badness_a = normal_cone(norms_a);
141 
							float badness_b = normal_cone(norms_b);
142 
 
143 
							float badness = 1.0f/(sqr(badness_a)*sqr(badness_b));
144 
							// 		add (v0,v1,f,f.touchvalue,badness) to Q;
145 
							PotentialEdge pot_edge;
146 
							pot_edge.v0 = verts[i];
147 
							pot_edge.v1 = verts[j];
148 
							pot_edge.f = f;
149 
							pot_edge.time = f->touched;
150 
							pot_edge.badness = badness;
151 
							Q.push(pot_edge);
152 
						}
153 
				}
154 
	}
155 
 
156 
 
157 
	void triangulate_face_order(Manifold& m)
158 
	{
159 
		PotentialEdgeQueue Q;
160 
 
161 
		for(FaceIter f_itr = m.faces_begin();
162 
				f_itr != m.faces_end(); ++f_itr)
163 
			process_face(f_itr, Q);
164 
 
165 
		while(!Q.empty())
166 
			{
167 
				PotentialEdge pot = Q.top();
168 
 
169 
				// If face has NOT been processed since this record
170 
				// was created.
171 
				if(pot.f->touched == pot.time)
172 
					{
173 
						// Make list of faces adjacent to f (adj_faces).
174 
						vector<FaceIter> nbr_faces;
175 
						FaceCirculator fc(pot.f);
176 
						for(; !fc.end(); ++fc)
177 
							nbr_faces.push_back(fc.get_face());
178 
 
179 
						// create edge(v0,v1) producing a new face fn;
180 
						FaceIter fn = m.split_face(pot.f, pot.v0, pot.v1);
181 
 
182 
						nbr_faces.push_back(pot.f);
183 
						nbr_faces.push_back(fn);
184 
 
136 jab 185 
						for(size_t i=0;i<nbr_faces.size();++i)
39 bj 186 
							{
187 
								nbr_faces[i]->touched++;
188 
								process_face(nbr_faces[i],Q);
189 
							}
190 
					}
191 
				Q.pop();
192 
			}
193 
	}
194 
 
195 
 
196 
 
197 
 
198 
 
199 
}