Subversion Repositories gelsvn

Rev

Rev 315 | Rev 362 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 315 Rev 357
Line 53... Line 53...
53 
 
 53
54 
						Manifold& m;
 54 
			Manifold& m;
55 
						HalfEdgeVec halfedge_vec;
 55 
			HalfEdgeVec halfedge_vec;
56 
						QEMVec qem_vec;
 56 
			QEMVec qem_vec;
57 
						SimplifyQueue sim_queue;
 57 
			SimplifyQueue sim_queue;
- 
 
 58 
			double singular_thresh;
- 
 
 59 
			bool relocate_origin;
58 
 
 60
59 
						/* Compute the error associated with contraction of he and the
 61 
			/* Compute the error associated with contraction of he and the
60 
							 optimal position of resulting vertex. */
 62 
				optimal position of resulting vertex. */
61 
						void push_simplify_rec(HalfEdgeIter he);
 63 
			void push_simplify_rec(HalfEdgeIter he);
62 
 
 64
Line 83... Line 85...
83 
						int collapse(SimplifyRec& simplify_rec);
 85 
			int collapse(SimplifyRec& simplify_rec);
84 
 
 86
85 
				public:
 87 
		public:
86 
 
 88
87 
						/* Create a simplifier for a manifold */
 89 
				/* Create a simplifier for a manifold */
88 
						QuadricSimplifier(Manifold& _m):
90 
				QuadricSimplifier(Manifold& _m, double _singular_thresh, bool _relocate_origin):
89 
								m(_m),
91 
				m(_m),
90 
								halfedge_vec(m.no_halfedges()),
92 
				halfedge_vec(m.no_halfedges()),
91 
								qem_vec(m.no_vertices())
93 
				qem_vec(m.no_vertices()),
- 
 
 94 
				singular_thresh(_singular_thresh),
- 
 
 95 
				relocate_origin(_relocate_origin)
92 
								{
 96 
			{
93 
										// Enumerate vertices
 97 
					// Enumerate vertices
94 
										m.enumerate_vertices();
 98 
					m.enumerate_vertices();
95
99
96 
										// Enumerate halfedges
 100 
					// Enumerate halfedges
Line 109... Line 113...
109 
						Vec3d p0(v0->pos);
 113 
			Vec3d p0(v0->pos);
110 
 
 114
111 
						/* This test is inspired by Garland's Ph.D. thesis. We try
 115 
			/* This test is inspired by Garland's Ph.D. thesis. We try
112 
							 to detect whether flipped triangles will occur by sort of
 116 
				to detect whether flipped triangles will occur by sort of
113 
							 ensuring that the new vertex is in the hull of the one rings
 117 
				ensuring that the new vertex is in the hull of the one rings
114 
							 of the vertices at either end of the edge being contracted */
 118 
				of the vertices at either end of the edge being contracted
- 
 
 119
- 
 
 120 
				I also had an additional check intended to ensure that poor valencies
- 
 
 121 
				would not be introduced, but it seemed to be unnecessary.
- 
 
 122
- 
 
 123 
				*/
115
124
116 
						for(VertexCirculator vc(v0); !vc.end(); ++vc)
 125 
			for(VertexCirculator vc(v0); !vc.end(); ++vc)
117 
						{
 126 
			{
118 
								HalfEdgeIter h = vc.get_halfedge();
 127 
				HalfEdgeIter h = vc.get_halfedge();
- 
 
 128
119 
								if(h->vert != v1 && h->next->vert != v1)
 129 
				if(h->vert != v1 && h->next->vert != v1)
120 
								{
 130 
				{
121 
										Vec3d pa(h->vert->pos);
 131 
					Vec3d pa(h->vert->pos);
122 
										Vec3d pb(h->next->vert->pos);
 132 
					Vec3d pb(h->next->vert->pos);
123
133
Line 129... Line 139...
129 
										if(dot(n,opt_pos - pa) <= 0)
 139 
					if(dot(n,opt_pos - pa) <= 0)
130 
												return false;
 140 
						return false;
131 
								}
 141 
				}
132 
						}
 142 
			}
133 
 
 143
134 
						/* Since the test above is not really enough, we also make sure
- 
 
135 
							 that we do not introduce vertices of very high (>=10) or low
- 
 
136 
							 (<=3) valency. Flipped faces seem to be always associated with
 - 
 
137 
							 very irregular valencies. It seems to get rid of most problems
 - 
 
138 
							 not fixed by the check above. */
 - 
 
139
- 
 
140 
						if(valency(he->next->vert)<5)
 - 
 
141 
								return false;
 - 
 
142 
 
 - 
 
143 
						if((valency(he->vert) + valency(he->opp->vert) ) > 13)
 - 
 
144 
								return false;
 - 
 
145 
 
 - 
 
146 
						return true;
 144 
			return true;
147 
				}
 145 
		}
148 
 
 146
149 
 
 147
150 
				void QuadricSimplifier::push_simplify_rec(HalfEdgeIter he)
 148 
		void QuadricSimplifier::push_simplify_rec(HalfEdgeIter he)
Line 156... Line 154...
156 
						QEM q = Q1;
 154 
			QEM q = Q1;
157 
						q += Q2;
 155 
			q += Q2;
158 
 
 156
159 
						float err;
 157 
			float err;
160 
						Vec3d opt_pos(0);
 158 
			Vec3d opt_pos(0);
- 
 
 159 
			Vec3d opt_origin = Vec3d(he->vert->pos+he->opp->vert->pos)/2.0;
- 
 
 160 
			if(relocate_origin)
- 
 
 161 
				opt_pos = q.opt_pos(singular_thresh,opt_origin);
- 
 
 162 
			else
- 
 
 163 
				opt_pos = q.opt_pos(singular_thresh,Vec3d(0));
161
164
162 
						opt_pos = q.opt_pos(0.000001);
 - 
 
163 
						err = q.error(opt_pos);
 165 
			err = q.error(opt_pos);
164 
 
 166
165 
						// Create SimplifyRec
 167 
			// Create SimplifyRec
166 
						int he_index = he->touched;
 168 
			int he_index = he->touched;
167 
						SimplifyRec simplify_rec;
 169 
			SimplifyRec simplify_rec;
Line 182... Line 184...
182 
						for(VertexCirculator vc(vi);
 184 
			for(VertexCirculator vc(vi);
183 
								!vc.end(); ++vc)
 185 
				!vc.end(); ++vc)
184 
						{
 186 
			{
185 
								HalfEdgeIter he = vc.get_halfedge();
 187 
				HalfEdgeIter he = vc.get_halfedge();
186 
								update_time_stamp(he);
 188 
				update_time_stamp(he);
- 
 
 189 
				push_simplify_rec(he);
187 
						}
 190 
			}
188 
				}
 191 
		}
189 
 
 192
190 
				int QuadricSimplifier::collapse(SimplifyRec& simplify_rec)
 193 
		int QuadricSimplifier::collapse(SimplifyRec& simplify_rec)
191 
				{
 194 
		{
Line 244... Line 247...
244 
								}
 247 
				}
245 
								// If we are here, the collapse was not allowed. If we have
 248 
				// If we are here, the collapse was not allowed. If we have
246 
								// seen this simplify record less than 100 times, we try to
 249 
				// seen this simplify record less than 100 times, we try to
247 
								// increase the error and store the record again. Maybe some
 250 
				// increase the error and store the record again. Maybe some
248 
								// other contractions will make it more digestible later.
 251 
				// other contractions will make it more digestible later.
249 
								if(simplify_rec.visits < 10)
 252 
				if(simplify_rec.visits < 100)
250 
								{
 253 
				{
251 
										simplify_rec.err += 5*simplify_rec.err + 1e-10;
 254 
					simplify_rec.err *= 1.01;
252 
										++simplify_rec.visits;
 255 
					++simplify_rec.visits;
253 
										sim_queue.push(simplify_rec);
 256 
					sim_queue.push(simplify_rec);
254 
								}
 257 
				}
255 
						}
 258 
			}
256 
						// Ok the time stamp did not match. Create a new record.
 - 
 
257 
						else if(halfedge_vec[he_index].time_stamp != -1)
 - 
 
258 
								push_simplify_rec(he);
 - 
 
259 
 
 - 
 
260 
						return 0;
 259 
			return 0;
261 
				}
 260 
		}
262 
 
 261
263 
				void QuadricSimplifier::reduce(int max_work)
 262 
		void QuadricSimplifier::reduce(int max_work)
264 
				{
 263 
		{
Line 316... Line 315...
316 
								}
 315 
				}
317 
						}
 316 
			}
318 
				}
 317 
		}
319 
		}
 318 
	}
320 
 
 319
321 
		void quadric_simplify(Manifold& m, int max_work)
 320 
	void quadric_simplify(Manifold& m, int max_work, double singular_thresh, bool relocate_origin)
322 
		{
 321 
	{
323 
				srand(1210);
 322 
		srand(1210);
324 
				QuadricSimplifier qsim(m);
 323 
		QuadricSimplifier qsim(m, singular_thresh, relocate_origin);
325 
				qsim.reduce(max_work);
 324 
		qsim.reduce(max_work);
326 
		}
 325 
	}
327 
 
 326
328 
}
 327 
}