Subversion Repositories gelsvn

Rev

Rev 155 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 155 Rev 169
Line 78... Line 78...
78
						VertexIter vert;
78
						VertexIter vert;
79
						HalfEdgeIter he[4];
79
						HalfEdgeIter he[4];
80
				
80
				
81
						CubeFace();
81
						CubeFace();
82
 
82
 
83
						HalfEdgeIter& get_he(Manifold* m, int i)
83
						HalfEdgeIter& get_he(Manifold& m, int i)
84
								{
84
								{
85
										if(he[i] == NULL_HALFEDGE_ITER)
85
										if(he[i] == NULL_HALFEDGE_ITER)
86
												he[i] = m->create_halfedge();
86
												he[i] = m.create_halfedge();
87
										return he[i];
87
										return he[i];
88
								}
88
								}
89
				};
89
				};
90
 
90
 
91
				CubeFace::CubeFace(): used(false), vert(NULL_VERTEX_ITER)
91
				CubeFace::CubeFace(): used(false), vert(NULL_VERTEX_ITER)
Line 107... Line 107...
107
 
107
 
108
 
108
 
109
				/* The mesher class does the actual work. It is not pretty and it
109
				/* The mesher class does the actual work. It is not pretty and it
110
					 is not seen by the user. */
110
					 is not seen by the user. */
111
				template<class T>
111
				template<class T>
112
				class Mesher
112
				class CubeGrid
113
				{
113
				{
114
						const RGrid<T>* const voxel_grid;        // The voxel grid we work on
-
 
115
						Manifold* m;		                         // Output manifold
114
						float iso;
116
						HashTable<HashKey3usi,Cube*> cube_hash;  // Hashtable of cube pointers
115
						HashTable<HashKey3usi,Cube*> cube_hash;  // Hashtable of cube pointers
117
						list<Cube> cube_table;                   // Linked list containing
116
						list<Cube> cube_table;                   // Linked list containing
118
						// the actual cubes.
117
                                          					 // the actual cubes.
119
 
118
 
120
				public:
119
				public:
121
			
120
			
122
						Mesher(const RGrid<T>* _voxel_grid, // input voxel grid
121
						CubeGrid(const RGrid<T>& _voxel_grid, // input voxel grid
123
									 Manifold* _m,                // output HMesh
122
										 float iso,                   // iso value
124
									 float iso,                   // iso value
123
										 bool inv_cont);              // invert contour?
-
 
124
 
-
 
125
						void find_neighbour_face_disconnect(Cube& cube, int face_idx, int edge_idx,
-
 
126
																								Cube*& cube_n, int& i_n, int& e_n);
-
 
127
 
-
 
128
						void find_neighbour_face_connect(Cube& cube, int face_idx, int edge_idx,
-
 
129
																						 Cube*& cube_n, int& i_n, int& e_n);
-
 
130
						
-
 
131
						void dual_cuberille_mesh(const RGrid<T>&, Manifold& m, bool connect=false);
-
 
132
						void cuberille_mesh(const RGrid<T>&, Manifold& m, bool connect=false);
-
 
133
				};
-
 
134
 
-
 
135
				template<class T>
-
 
136
				void CubeGrid<T>::find_neighbour_face_disconnect(Cube& cube, int face_idx, int edge_idx,
-
 
137
																												 Cube*& cube_n,  // Neighbouring cube
-
 
138
																												 int& i_n,  // direction from center to neighbour face
-
 
139
																												 int& e_n) // Edge vector for neighbour face
-
 
140
				{
-
 
141
						/*
-
 
142
							Algorithm: Pick faces to glue
-
 
143
 
-
 
144
							Algorithm which connects cube faces. If both A and B
-
 
145
							are above the isovalue and 0 and C are below, A and B
-
 
146
							will be seperated, i.e. the 0A and AC faces will be 
-
 
147
							connected. There is a different out-commented algorithm
-
 
148
							at the end of this file which connects AO and 0B
-
 
149
							instead.
-
 
150
															
-
 
151
							Figure.
-
 
152
 
-
 
153
							0|B
-
 
154
							-+-
-
 
155
							A|C
-
 
156
															
-
 
157
							Explanation:
-
 
158
														
-
 
159
							Let the current cube be A. Since we are here, the voxel
-
 
160
							of A is above the isovalue, and the voxel of O is below
-
 
161
							since there is a face AO.
-
 
162
 
-
 
163
							We first check if there is a face between A and C. 
-
 
164
							if that is the case, the AO face is connected to the AC 
-
 
165
							face. 
-
 
166
 
125
									 bool inv_cont);              // invert contour?
167
							Otherwise, we check if B is also inside the isocontour.
-
 
168
							If that is true there is an OB face, and we connect the
-
 
169
							A0 and the 0B faces.
-
 
170
															
-
 
171
							Failing that, there must be a CB face, and we connect
-
 
172
							with that.
-
 
173
						*/
-
 
174
						Vec3i pos = cube.pos;
-
 
175
						Vec3i dir = N6i[face_idx];
-
 
176
 
-
 
177
 
-
 
178
						Vec3i dir_n;   // direction from center to neighbour face
-
 
179
						Vec3i edge_n; // Edge vector for neighbour face
-
 
180
 
-
 
181
						Vec3i edge = edges[face_idx][edge_idx];	       // Vector _along_ edge
-
 
182
						Vec3i to_edge = cross(edge,dir); // vector to edge
-
 
183
 
-
 
184
																
-
 
185
						// Begin "Pick faces to glue"
-
 
186
						Cube* dummy;
-
 
187
						if(cube.faces[dir_to_face(to_edge)].used)
-
 
188
						{
-
 
189
								dir_n = to_edge;
-
 
190
								edge_n = - edge; 
-
 
191
								cube_n = &cube;  
-
 
192
						}
-
 
193
						else if(!cube_hash.find_entry(HashKey3usi(pos+dir+to_edge),
-
 
194
																					dummy))
-
 
195
						{
-
 
196
								assert(sqr_length(to_edge)==1);
-
 
197
								dir_n = dir;
-
 
198
								edge_n = - edge;
-
 
199
								cube_hash.find_entry(HashKey3usi(pos + to_edge), 
-
 
200
																		 cube_n);
-
 
201
						}
-
 
202
						else 
-
 
203
						{
-
 
204
								dir_n = - to_edge;
-
 
205
								edge_n = - edge;
-
 
206
								cube_n = dummy;
-
 
207
						}
126
 
208
 
127
						void process_cubes();
209
						i_n = dir_to_face(dir_n);
-
 
210
						e_n = dir_to_edge(i_n, edge_n);
-
 
211
				}
128
 
212
 
-
 
213
				template<class T>
-
 
214
				void CubeGrid<T>::find_neighbour_face_connect(Cube& cube, int face_idx, int edge_idx,
-
 
215
																											Cube*& cube_n,  // Neighbouring cube
-
 
216
																											int& i_n,  // direction from center to neighbour face
-
 
217
																											int& e_n) // Edge vector for neighbour face
-
 
218
				{
-
 
219
						Vec3i pos = cube.pos;
129
						void create_faces();
220
						Vec3i dir = N6i[face_idx];
130
 
221
 
-
 
222
						Vec3i dir_n;   // direction from center to neighbour face
131
						void triangulate(float iso);
223
						Vec3i edge_n; // Edge vector for neighbour face
132
 
224
 
-
 
225
						Vec3i edge = edges[face_idx][edge_idx];	       // Vector _along_ edge
133
						void remove_duplicates();
226
						Vec3i to_edge = cross(edge,dir); // vector to edge
134
 
227
 
-
 
228
						if(cube_hash.find_entry(HashKey3usi(pos + dir + to_edge),
-
 
229
																		cube_n))
-
 
230
						{
-
 
231
								assert(sqr_length(dir + to_edge)==2);
-
 
232
																dir_n = - to_edge;
-
 
233
																edge_n = - edge;
-
 
234
						}
-
 
235
						else if(cube_hash.find_entry(HashKey3usi(pos + to_edge), 
-
 
236
																				 cube_n))
-
 
237
						{
-
 
238
								assert(sqr_length(to_edge)==1);
-
 
239
								dir_n = dir;
-
 
240
								edge_n = - edge;
-
 
241
						}
-
 
242
						else
-
 
243
						{
-
 
244
								dir_n = to_edge;
-
 
245
								edge_n = - edge;
-
 
246
								cube_n = &cube;
-
 
247
						}
-
 
248
						
135
						void push_vertices(float iso);
249
						i_n = dir_to_face(dir_n);
-
 
250
						e_n = dir_to_edge(i_n, edge_n);
-
 
251
				}
136
 
252
 
137
				};
253
				
138
	
-
 
139
				template<class T>
254
				template<class T>
140
				inline bool comp(bool d, T a, T b)
255
				inline bool comp(bool d, T a, T b)
141
				{
256
				{
142
						return d? (a<b) : (b<a); 
257
						return d? (a<b) : (b<a); 
143
				}
258
				}
144
		
259
		
145
				template<class T>
260
				template<class T>
146
				Mesher<T>::Mesher(const RGrid<T>* _voxel_grid, 
-
 
147
													Manifold* _m, float iso, bool inv_cont): 
261
				CubeGrid<T>::CubeGrid(const RGrid<T>& voxel_grid, float _iso, bool inv_cont): iso(_iso)
148
						voxel_grid(_voxel_grid),
-
 
149
						m(_m)
-
 
150
				{
262
				{
151
						/* Loop over all voxels */
263
						/* Loop over all voxels */
152
						for(int k=0;k<voxel_grid->get_dims()[ 2 ];++k)
264
						for(int k=0;k<voxel_grid.get_dims()[ 2 ];++k)
153
								for(int j=0;j<voxel_grid->get_dims()[ 1 ];++j)
265
								for(int j=0;j<voxel_grid.get_dims()[ 1 ];++j)
154
										for(int i=0;i<voxel_grid->get_dims()[ 0 ];++i)
266
										for(int i=0;i<voxel_grid.get_dims()[ 0 ];++i)
155
										{
267
										{
156
												Vec3i pi0(i,j,k);
268
												Vec3i pi0(i,j,k);
157
												float val0 = (*voxel_grid)[pi0];
269
												float val0 = voxel_grid[pi0];
158
 
270
 
159
												/* If the voxel value is above the isovale (or below if we
271
												/* If the voxel value is above the isovale (or below if we
160
													 are finding the inverse contour) */
272
													 are finding the inverse contour) */
161
												if(comp(inv_cont,val0,iso))
273
												if(comp(inv_cont,val0,iso))
162
												{
274
												{
Line 168... Line 280...
168
														for(int l=0;l<6;++l)
280
														for(int l=0;l<6;++l)
169
														{
281
														{
170
																// First make sure the voxel is inside the voxel grid.
282
																// First make sure the voxel is inside the voxel grid.
171
																Vec3i pi1(pi0);
283
																Vec3i pi1(pi0);
172
																pi1 += N6i[l];
284
																pi1 += N6i[l];
173
																bool indom = voxel_grid->in_domain(pi1);
285
																bool indom = voxel_grid.in_domain(pi1);
174
												
286
												
175
																/* If the neighbour is **not** in the grid or it 
287
																/* If the neighbour is **not** in the grid or it 
176
																	 is on the other side of the isovalue */
288
																	 is on the other side of the isovalue */
177
																if(!indom || 
289
																if(!indom || 
178
																	 !comp(inv_cont,float((*voxel_grid)[pi1]),iso))
290
																	 !comp(inv_cont,float(voxel_grid[pi1]),iso))
179
																{
291
																{
180
																		/* Create a cube face for the interface between
-
 
181
																			 our voxel and this neighbour. */
-
 
182
 
-
 
183
																		float val1 = iso;
-
 
184
																		if(indom)
-
 
185
																				val1 = (*voxel_grid)[pi1];
-
 
186
																		
-
 
187
																		/* Store the cube in a hash table. This code is
292
																		/* Store the cube in a hash table. This code is
188
																			 executed the first time we create a face
293
																			 executed the first time we create a face
189
																			 for the cube. In other words only cubes that 
294
																			 for the cube. In other words only cubes that 
190
																			 actually have faces are stored in the hash */
295
																			 actually have faces are stored in the hash */
191
																		if(!interface_cell)
296
																		if(!interface_cell)
Line 200... Line 305...
200
																		// Now add the face to the cube.
305
																		// Now add the face to the cube.
201
																		int face_idx  = dir_to_face(N6i[l]);
306
																		int face_idx  = dir_to_face(N6i[l]);
202
																		CubeFace& face = cube->faces[face_idx];
307
																		CubeFace& face = cube->faces[face_idx];
203
																		face.used = true;
308
																		face.used = true;
204
 
309
 
205
																		// Finally, we place a vertex corresponding to the
-
 
206
																		// centre of the cube face. The vertex is 
-
 
207
																		// positioned on the line between the two voxels
-
 
208
																		// (which pierces the new face) at the point where
-
 
209
																		// the interpolated value = isovalue
-
 
210
																		float t= (iso-val0)/(val1-val0);
-
 
211
																		Vec3f p = Vec3f(pi0)*(1.0f-t)+Vec3f(pi1)*t;
-
 
212
																		face.vert = m->create_vertex(p);
-
 
213
																		
-
 
214
																		// We mark the vertex with the cube index.
-
 
215
																		face.vert->touched = reinterpret_cast<TouchType>(cube);
-
 
216
																}
310
																}
217
														}
311
														}
218
												}
312
												}
219
										}		
313
										}		
220
				}
314
				}
221
 
315
 
222
 
316
 
223
				/* This complicated function is used to connect the cube faces.
317
				/* This complicated function is used to connect the cube faces.
224
					 If the faces are cosidered to be little square pieces of paper, this
318
					 If the faces are considered to be little square pieces of paper, this
225
					 function glues them along the edges. However, it takes care to glue
319
					 function glues them along the edges. However, it takes care to glue
226
					 faces in such a way as to not create edges with more the two adjacent
320
					 faces in such a way as to not create edges with more than two adjacent
227
					 faces. */
321
					 faces. */
228
				template<class T>
322
				template<class T>
229
				void Mesher<T>::process_cubes()
323
				void CubeGrid<T>::dual_cuberille_mesh(const RGrid<T>& voxel_grid, Manifold& m, bool connect)
230
				{
324
				{
231
						/* For each cube in the table of cubes */
325
						/* For each cube in the table of cubes */
232
						typename list<Cube>::iterator cube_iter = cube_table.begin();
326
						typename list<Cube>::iterator cube_iter = cube_table.begin();
233
						for(;cube_iter != cube_table.end(); ++cube_iter)
327
						for(;cube_iter != cube_table.end(); ++cube_iter)
234
						{
328
						{
235
								/* For each of the six faces, if the face is used */
329
								/* For each of the six faces, if the face is used */
236
								Cube& cube = *cube_iter;
330
								Cube& cube = *cube_iter;
-
 
331
								Vec3i pi0 = cube.pos;
-
 
332
								float val0 = voxel_grid[pi0];
-
 
333
								for(int face_idx=0; face_idx<6; ++face_idx)
-
 
334
								{
-
 
335
										CubeFace& face = cube.faces[face_idx];
-
 
336
										if(face.used)
-
 
337
										{
-
 
338
												Vec3i pi1(pi0);
-
 
339
												pi1 += N6i[face_idx];
-
 
340
												Vec3f p;
-
 
341
												if(voxel_grid.in_domain(pi1))
-
 
342
												{
-
 
343
														float val1 = voxel_grid[pi1];
-
 
344
														float t= (iso-val0)/(val1-val0);
-
 
345
														p = Vec3f(pi0)*(1.0f-t)+Vec3f(pi1)*t;
-
 
346
												}
-
 
347
												else
-
 
348
														p = Vec3f(pi0) * 0.5 + Vec3f(pi1) * 0.5;
-
 
349
												face.vert = m.create_vertex(p);
-
 
350
												// We mark the vertex with the cube index.
-
 
351
												face.vert->touched = reinterpret_cast<TouchType>(&cube);
-
 
352
										}
-
 
353
								}
-
 
354
						}
-
 
355
						
-
 
356
						/* For each cube in the table of cubes */
-
 
357
						cube_iter = cube_table.begin();
-
 
358
						for(;cube_iter != cube_table.end(); ++cube_iter)
-
 
359
						{
-
 
360
								/* For each of the six faces, if the face is used */
-
 
361
								Cube& cube = *cube_iter;
237
								for(int i=0;i<6;++i)
362
								for(int i=0;i<6;++i)
238
										if(cube.faces[i].used)
363
										if(cube.faces[i].used)
239
										{
364
										{
240
												Vec3i pos = cube.pos;
365
												CubeFace& face = cube.faces[i];  // The face
241
												Vec3i dir = N6i[i];
366
												
242
 
-
 
243
												// Let e be one of the four edges of the face
367
												// Let e be one of the four edges of the face
244
												for(int e=0;e<4;++e)
368
												for(int e=0;e<4;++e)
245
												{
369
												{
246
														Vec3i edge = edges[i][e];	       // Vector _along_ edge
-
 
247
														Vec3i to_edge = cross(edge,dir); // vector to edge
-
 
248
														CubeFace& face = cube.faces[i];  // The face
-
 
249
 
-
 
250
														Cube* cube_n;  // Neighbouring cube
370
														Cube* cube_n;  // Neighbouring cube
251
														Vec3i dir_n;   // direction from center to neighbour face
-
 
252
														Vec3i edge_n; // Edge vector for neighbour face
-
 
253
 
-
 
254
 
-
 
255
														/*
-
 
256
															Algorithm: Pick faces to glue
-
 
257
 
-
 
258
															Algorithm which connects cube faces. If both A and B
-
 
259
															are above the isovalue and 0 and C are below, A and B
-
 
260
															will be seperated, i.e. the 0A and AC face will be 
-
 
261
															connected. There is a different out-commented algorithm
-
 
262
															at the end of this file which connects AO and 0B
-
 
263
															instead.
-
 
264
															
-
 
265
															Figure.
-
 
266
 
-
 
267
															0|B
-
 
268
															-+-
-
 
269
															A|C
-
 
270
															
-
 
271
															Explanation:
-
 
272
														
-
 
273
															Let the current cube be A. Since we are here, the voxel
-
 
274
															of A is above the isovalue, and the voxel of O is below
-
 
275
															since there is a face AO.
-
 
276
 
-
 
277
															We first check if there is a face between A and C. 
-
 
278
															if that is the case, the AO face is connected to the AC 
-
 
279
															face. 
-
 
280
 
-
 
281
															Otherwise, we check if B is also inside the isocontour.
-
 
282
															If that is true there is an OB face, and we connect the
-
 
283
															A0 and the 0B faces.
-
 
284
															
-
 
285
															Failing that, there must be a CB face, and we connect
-
 
286
															with that.
-
 
287
														*/
-
 
288
										
-
 
289
														// Begin "Pick faces to glue"
-
 
290
														Cube* dummy;
-
 
291
														if(cube.faces[dir_to_face(to_edge)].used)
-
 
292
														{
-
 
293
																dir_n = to_edge;
-
 
294
																edge_n = - edge; 
-
 
295
																cube_n = &cube;  
-
 
296
														}
-
 
297
														else if(!cube_hash.find_entry(HashKey3usi(pos+dir+to_edge),
-
 
298
																													dummy))
-
 
299
														{
-
 
300
																assert(sqr_length(to_edge)==1);
-
 
301
																dir_n = dir;
371
														int i_n, e_n;
302
																edge_n = - edge;
-
 
303
																cube_hash.find_entry(HashKey3usi(pos + to_edge), 
-
 
304
																										 cube_n);
-
 
305
														}
-
 
306
														else 
-
 
307
														{
-
 
308
																dir_n = - to_edge;
-
 
309
																edge_n = - edge;
-
 
310
																cube_n = dummy;
-
 
311
														}
-
 
312
														// End "Pick faces to glue"
-
 
313
 
372
 
314
														// Do the actual gluing ...
373
														// Do the actual gluing ...
315
														
374
														if(!connect) 
316
														/* Let the vertex of this face's halfedge be the one on
375
																find_neighbour_face_disconnect(cube, i, e, cube_n, i_n, e_n);
317
															 the connected face. */
376
														else
318
														int i_n = dir_to_face(dir_n);
377
																find_neighbour_face_connect(cube, i, e, cube_n, i_n, e_n);
-
 
378
 
319
														CubeFace& face_n = cube_n->faces[i_n];
379
														CubeFace& face_n = cube_n->faces[i_n];
320
														HalfEdgeIter& he = face.get_he(m,e);
380
														HalfEdgeIter& he = face.get_he(m,e);
321
														face.vert->he = he;
381
														face.vert->he = he;
322
														he->vert = face_n.vert;
382
														he->vert = face_n.vert;
323
 
383
 
324
														/* Link this halfedge to the _next_ halfedge on the 
384
														/* Link this halfedge to the _next_ halfedge on the 
325
															 connected face. */
385
															 connected face. */
326
														int e_n = dir_to_edge(i_n, edge_n);
-
 
327
														assert(face_n.used);
386
														assert(face_n.used);
328
														HalfEdgeIter& he_n = face_n.get_he(m, (e_n+3)%4);
387
														HalfEdgeIter& he_n = face_n.get_he(m, (e_n+3)%4);
329
														link(he, he_n);
388
														link(he, he_n);
330
 
389
 
331
														/* Glue this halfedge to the corresponding one on the
390
														/* Glue this halfedge to the corresponding one on the
Line 335... Line 394...
335
														glue(he, he_opp);
394
														glue(he, he_opp);
336
												}
395
												}
337
										}
396
										}
338
 
397
 
339
						}
398
						}
340
				}
-
 
341
 
399
 
342
				template<class T>
-
 
343
				void Mesher<T>::create_faces()
-
 
344
				{
-
 
345
						// For each halfedge
-
 
346
						HalfEdgeIter he0 = m->halfedges_begin();
400
						HalfEdgeIter he0 = m.halfedges_begin();
347
						while(he0 != m->halfedges_end())
401
						while(he0 != m.halfedges_end())
348
						{
402
						{
349
								// If this halfedge is not assigned to a face.
403
								// If this halfedge is not assigned to a face.
350
								if(he0->face == NULL_FACE_ITER)
404
								if(he0->face == NULL_FACE_ITER)
351
								{
405
								{
352
										// Create a face and let the current halfedge belong to it.
406
										// Create a face and let the current halfedge belong to it.
353
										FaceIter fi = m->create_face();
407
										FaceIter fi = m.create_face();
354
										fi->last = he0;
408
										fi->last = he0;
355
										he0->face = fi;
409
										he0->face = fi;
356
 
410
										
357
										// Loop over all connected halfedges and let them also belong 
411
										// Loop over all connected halfedges and let them also belong 
358
										// to the face.
412
										// to the face.
359
										HalfEdgeIter he = he0->next;
413
										HalfEdgeIter he = he0->next;
360
										while(he != he0)
414
										while(he != he0)
361
										{
415
										{
362
												he->face = fi;
416
												he->face = fi;
363
												he = he->next;
417
												he = he->next;
364
										}
418
										}
365
								}
419
							}
366
								++he0;
420
								++he0;
367
						}
421
						}
368
				}
422
				}
369
 
423
 
-
 
424
				template<class T>
-
 
425
				void CubeGrid<T>::cuberille_mesh(const RGrid<T>& voxel_grid, Manifold& m, bool connect)
-
 
426
				{
-
 
427
						typename list<Cube>::iterator cube_iter = cube_table.begin();
-
 
428
 
-
 
429
						/* For each cube in the table of cubes */
-
 
430
						cube_iter = cube_table.begin();
-
 
431
						for(;cube_iter != cube_table.end(); ++cube_iter)
-
 
432
						{
-
 
433
								/* For each of the six faces, if the face is used */
-
 
434
								Cube& cube = *cube_iter;
-
 
435
								for(int i=0;i<6;++i)
-
 
436
										if(cube.faces[i].used)
-
 
437
										{
-
 
438
												CubeFace& face = cube.faces[i];  // The face
-
 
439
												FaceIter hmesh_face = m.create_face();
-
 
440
												// Let e be one of the four edges of the face
-
 
441
												for(int e=0;e<4;++e)
-
 
442
												{
-
 
443
														Cube* cube_n;  // Neighbouring cube
-
 
444
														int i_n, e_n;
-
 
445
 
-
 
446
														// Do the actual gluing ...
-
 
447
														if(!connect) 
-
 
448
																find_neighbour_face_disconnect(cube, i, e, cube_n, i_n, e_n);
-
 
449
														else
-
 
450
																find_neighbour_face_connect(cube, i, e, cube_n, i_n, e_n);
-
 
451
														
-
 
452
														CubeFace& face_n = cube_n->faces[i_n];
-
 
453
														HalfEdgeIter he = face.get_he(m,e);
-
 
454
														HalfEdgeIter he_n = face_n.get_he(m,e_n);
-
 
455
														
-
 
456
														link(he,face.get_he(m,(e+1)%4));
-
 
457
														link(face.get_he(m,(e+3)%4),he);
-
 
458
														glue(he, he_n);
-
 
459
														he->face = hmesh_face;
-
 
460
												}
-
 
461
												hmesh_face->last = face.get_he(m,0);
-
 
462
 
-
 
463
 
-
 
464
										}
-
 
465
 
-
 
466
						}
-
 
467
						cube_iter = cube_table.begin();
-
 
468
						for(;cube_iter != cube_table.end(); ++cube_iter)
-
 
469
						{
-
 
470
								/* For each of the six faces, if the face is used */
-
 
471
								Cube& cube = *cube_iter;
-
 
472
								for(int i=0;i<6;++i)
-
 
473
										if(cube.faces[i].used)
-
 
474
										{
-
 
475
												CubeFace& face = cube.faces[i];  // The face
-
 
476
												// Let e be one of the four edges of the face
-
 
477
												for(int e=0;e<4;++e)
-
 
478
														if(face.he[e]->vert == NULL_VERTEX_ITER)
-
 
479
														{
-
 
480
																Vec3i to_face = N6i[i];
-
 
481
																Vec3i along_edge = edges[i][e];	
-
 
482
																Vec3i to_edge = cross(along_edge,to_face);
-
 
483
																Vec3f pos = Vec3f(cube.pos) + 0.5*Vec3f(to_face + along_edge + to_edge);
-
 
484
																HalfEdgeIter last = face.he[e];
-
 
485
																VertexIter vi = m.create_vertex(pos);
-
 
486
																vi->he = last->opp;
-
 
487
																HalfEdgeIter he = last;
-
 
488
																do
-
 
489
																{
-
 
490
																		he->vert = vi;
-
 
491
																		he = he->next->opp;
-
 
492
																}
-
 
493
																while(he != last);
-
 
494
														}
-
 
495
										}
-
 
496
						}
-
 
497
				}
370
 
498
 
371
				/* A fairly complex algorithm which triangulates faces. It triangulates
499
				/* A fairly complex algorithm which triangulates faces. It triangulates
372
					 by iteratively splitting faces. It always splits a face by picking the
500
					 by iteratively splitting faces. It always splits a face by picking the
373
					 edge whose midpoint is closest to the isovalue. */
501
					 edge whose midpoint is closest to the isovalue. */
374
					
502
					
375
				template<class T>
503
				template<class T>
376
				void Mesher<T>::triangulate(float iso)
504
				void triangulate(const RGrid<T>& voxel_grid, Manifold& m, float iso)
377
				{
505
				{
378
#ifndef NDEBUG
506
#ifndef NDEBUG
379
						cout << "Initial mesh valid : " << m->is_valid() << endl;
507
						cout << "Initial mesh valid : " << m.is_valid() << endl;
380
#endif
508
#endif
381
						Geometry::TrilinFilter<Geometry::RGrid<T> > grid_interp(voxel_grid);
509
						Geometry::TrilinFilter<Geometry::RGrid<T> > grid_interp(&voxel_grid);
382
						int work;
510
						int work;
383
						do
511
						do
384
						{
512
						{
385
								// For every face.
513
								// For every face.
386
								work = 0;
514
								work = 0;
387
								for(FaceIter fi =m->faces_begin(); fi != m->faces_end(); ++fi)
515
								for(FaceIter fi =m.faces_begin(); fi != m.faces_end(); ++fi)
388
								{
516
								{
389
										// Create a vector of vertices.
517
										// Create a vector of vertices.
390
										vector<VertexIter> verts;
518
										vector<VertexIter> verts;
391
										for(FaceCirculator fc(fi); !fc.end(); ++fc)
519
										for(FaceCirculator fc(fi); !fc.end(); ++fc)
392
												verts.push_back(fc.get_vertex());
520
												verts.push_back(fc.get_vertex());
Line 430... Line 558...
430
												}
558
												}
431
										}
559
										}
432
										assert(min_k != -1);
560
										assert(min_k != -1);
433
										
561
										
434
										{
562
										{
435
											// Split faces along edge whose midpoint is closest to isovalue
563
												// Split faces along edge whose midpoint is closest to isovalue
436
											int i = vpairs[min_k].first;
564
												int i = vpairs[min_k].first;
437
											int j = vpairs[min_k].second;
565
												int j = vpairs[min_k].second;
438
											m->split_face(fi, verts[i], verts[j]);
566
												m.split_face(fi, verts[i], verts[j]);
439
										}
567
										}
440
										++work;
568
										++work;
441
										
569
										
442
								}
570
								}
443
						}
571
						}
444
						while(work);
572
						while(work);
445
 
573
 
446
#ifndef NDEBUG
574
#ifndef NDEBUG
447
						cout << "Valid after triangulation : " << m->is_valid() << endl;
575
						cout << "Valid after triangulation : " << m.is_valid() << endl;
448
#endif
576
#endif
449
				}
577
				}
450
 
578
 
451
				/* This function collapses every edge whose endpoints belong to the same 
579
				/* This function collapses every edge whose endpoints belong to the same 
452
					 cube if this edge can be removed without violating the manifold condition*/
580
					 cube if this edge can be removed without violating the manifold condition*/
453
				template<class T>
-
 
454
				void Mesher<T>::remove_duplicates()
581
				void remove_duplicates(Manifold& m)
455
				{
582
				{
456
						// BUG --- we never do this loop more than one time.
583
						// BUG --- we never do this loop more than one time.
457
						// does it matter.
584
						// does it matter.
458
						VertexIter vi = m->vertices_begin();
585
						VertexIter vi = m.vertices_begin();
459
						bool did_work = false;
586
						bool did_work = false;
460
						do
587
						do
461
						{
588
						{
462
								did_work = false;
589
								did_work = false;
463
								while(vi != m->vertices_end())
590
								while(vi != m.vertices_end())
464
								{
591
								{
465
										bool did = false;
592
										bool did = false;
466
										VertexCirculator vc(vi);
593
										VertexCirculator vc(vi);
467
										int k=0;
594
										int k=0;
468
										for(;!vc.end();++vc)
595
										for(;!vc.end();++vc)
469
										{
596
										{
470
												assert(++k<1000);
597
												assert(++k<1000);
471
												HalfEdgeIter he = vc.get_halfedge();
598
												HalfEdgeIter he = vc.get_halfedge();
472
												VertexIter n = vc.get_vertex();
599
												VertexIter n = vc.get_vertex();
473
												if(n->touched == vi->touched && m->collapse_precond(he))
600
												if(n->touched == vi->touched && m.collapse_precond(he))
474
												{
601
												{
475
														++vi;
602
														++vi;
476
														m->collapse_halfedge(he,true);
603
														m.collapse_halfedge(he,true);
477
														did = did_work = true;
604
														did = did_work = true;
478
														break;
605
														break;
479
												}
606
												}
480
										}
607
										}
481
										if(!did) ++vi;
608
										if(!did) ++vi;
482
								}
609
								}
483
 
610
 
484
						}
611
						}
485
						while(did_work);
612
						while(did_work);
486
#ifndef NDEBUG
613
#ifndef NDEBUG
487
						cout << "Valid after removal of excess vertices : " << m->is_valid() << endl;
614
						cout << "Valid after removal of excess vertices : " << m.is_valid() << endl;
488
#endif
615
#endif
489
				}
616
				}
490
		
617
 
491
				/* A function (not used now) which pushes vertices onto the isosurface. */
618
				/* A function (not used now) which pushes vertices onto the isosurface. */
492
				template<class T>
619
				template<class T>
493
				void Mesher<T>::push_vertices(float iso)
620
				void push_vertices(const RGrid<T>& voxel_grid, Manifold& m, float iso)
494
				{
621
				{
495
						GradientFilter<RGrid<T> > grad(voxel_grid);
622
						GradientFilter<RGrid<T> > grad(&voxel_grid);
496
						TrilinFilter<GradientFilter<RGrid<T> > > ginter(&grad);
623
						TrilinFilter<GradientFilter<RGrid<T> > > ginter(&grad);
497
						TrilinFilter<RGrid<T> > inter(voxel_grid);
624
						TrilinFilter<RGrid<T> > inter(&voxel_grid);
498
		
-
 
499
						cout << "Pushing vertices" << endl;
-
 
500
						for(int i=0;i<4;++i)
625
						for(int i=0;i<4;++i)
501
						{
626
						{
502
								cout << "." << flush;
-
 
503
								for(VertexIter vi= m->vertices_begin();
627
								for(VertexIter vi= m.vertices_begin();
504
										vi != m->vertices_end(); ++vi)
628
										vi != m.vertices_end(); ++vi)
505
								{
629
								{
506
										Vec3f p = vi->pos;
630
										Vec3f p = vi->pos;
507
										if(ginter.in_domain(p))
631
										if(ginter.in_domain(p))
508
										{
632
										{
509
												Vec3f g = ginter(p);
633
												Vec3f g = ginter(p);
510
												float s = sqr_length(g);
634
												float s = sqr_length(g);
511
												if(s>0.0001)
635
												if(s>0.01)
512
												{
636
												{
513
														float v = inter(p)-iso;
637
														float v = inter(p)-iso;
514
														vi->pos = (p-g*v/s);
638
														vi->pos = (p-g*v/s);
515
												}
639
												}
516
										}
640
										}
Line 522... Line 646...
522
 
646
 
523
		template<typename T>
647
		template<typename T>
524
		void fair_polygonize(const RGrid<T>& voxel_grid, 
648
		void fair_polygonize(const RGrid<T>& voxel_grid, 
525
												 Manifold& mani, 
649
												 Manifold& mani, 
526
												 float iso,
650
												 float iso,
527
												 bool invert_contour)
651
												 bool invert_contour, 
-
 
652
												 bool connect,
-
 
653
												 bool push)
528
		{
654
		{
529
				Mesher<T> m(&voxel_grid, &mani, iso, invert_contour);
655
				CubeGrid<T> cube_grid(voxel_grid, iso, invert_contour);
-
 
656
				cube_grid.dual_cuberille_mesh(voxel_grid, mani, connect);
-
 
657
 				triangulate(voxel_grid, mani, iso);
530
				m.process_cubes();
658
 				remove_duplicates(mani);
-
 
659
				if(push) push_vertices(voxel_grid, mani, iso);
-
 
660
		}
-
 
661
 
531
				m.create_faces();
662
		template<typename T>
-
 
663
		void cuberille_polygonize(const RGrid<T>& voxel_grid, 
-
 
664
															Manifold& mani, 
532
				m.triangulate(iso);
665
															float iso,
-
 
666
															bool invert_contour, 
-
 
667
															bool connect,
533
				m.remove_duplicates();
668
															bool push)
-
 
669
		{
-
 
670
				CubeGrid<T> cube_grid(voxel_grid, iso, invert_contour);
-
 
671
				cube_grid.cuberille_mesh(voxel_grid, mani, connect);
534
				//m.push_vertices(iso);
672
				if(push) push_vertices(voxel_grid, mani, iso);
535
		}
673
		}
536
 
674
 
537
		template void fair_polygonize<unsigned char>(const RGrid<unsigned char>&,
675
		template void fair_polygonize<unsigned char>(const RGrid<unsigned char>&,
538
																								 Manifold&, float, bool);
676
																								 Manifold&, float, bool,bool,bool);
539
		template void fair_polygonize<float>(const RGrid<float>&,
677
		template void fair_polygonize<float>(const RGrid<float>&,
540
																				 Manifold&, float, bool);
678
																				 Manifold&, float, bool,bool,bool);
-
 
679
 
-
 
680
		template void cuberille_polygonize<unsigned char>(const RGrid<unsigned char>&,
-
 
681
																											Manifold&, float, bool,bool,bool);
-
 
682
		template void cuberille_polygonize<float>(const RGrid<float>&,
-
 
683
																							Manifold&, float, bool,bool,bool);
541
}
684
}
542
 
685
 
543
 
686
 
544
// --- Alternative "Pick faces to glue" code.
-
 
545
//                          if(cube_hash.find_entry(HashKey3usi(pos + dir + to_edge),
-
 
546
//                                        cube_n))
-
 
547
// 														{
-
 
548
// 																assert(sqr_length(dir + to_edge)==2);
-
 
549
// 																dir_n = - to_edge;
-
 
550
// 																edge_n = - edge;
-
 
551
// 														}
-
 
552
// 														else if(cube_hash.find_entry(HashKey3usi(pos + to_edge), 
-
 
553
// 																												 cube_n))
-
 
554
// 														{
-
 
555
// 																assert(sqr_length(to_edge)==1);
-
 
556
// 																dir_n = dir;
-
 
557
// 																edge_n = - edge;
-
 
558
// 														}
-
 
559
// 														else
-
 
560
// 														{
-
 
561
// 																dir_n = to_edge;
-
 
562
// 																edge_n = - edge;
-
 
563
// 																											cube_n = &cube;
-
 
564
// 														}
-