Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
adaptive_subdivider.cc
1 /* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openmesh.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenMesh. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 * ========================================================================= */
41
42 /*===========================================================================*\
43 * *
44 * $Revision$ *
45 * $Date$ *
46 * *
47 \*===========================================================================*/
48
49 // -------------------------------------------------------------- includes ----
50
51 // -------------------- OpenMesh
52 #include <OpenMesh/Core/IO/MeshIO.hh>
53 #include <OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh>
54 #include <OpenMesh/Tools/Utils/Timer.hh>
55 #include <OpenMesh/Tools/Utils/getopt.h>
56 // -------------------- OpenMesh Adaptive Composite Subdivider
57 #include <OpenMesh/Tools/Subdivider/Adaptive/Composite/CompositeT.hh>
58 #include <OpenMesh/Tools/Subdivider/Adaptive/Composite/RulesT.hh>
59 // -------------------- STL
60 #include <iostream>
61 #include <fstream>
62 #include <sstream>
63 #if defined(OM_CC_MIPS)
64 # include <math.h>
65 #else
66 # include <cmath>
67 using std::pow;
68 #endif
69
70
71 using OpenMesh::Subdivider::Adaptive::CompositeTraits;
72
73 // define mesh, rule interface, and subdivider types
74 typedef OpenMesh::TriMesh_ArrayKernelT<CompositeTraits> MyMesh;
75 typedef OpenMesh::Subdivider::Adaptive::RuleInterfaceT<MyMesh> Rule;
76 typedef OpenMesh::Subdivider::Adaptive::CompositeT<MyMesh> Subdivider;
77
78 // ----------------------------------------------------------------------------
79
80 using namespace OpenMesh::Subdivider;
81
82 // factory function to add a RULE to a subdivider
83 #define ADD_FN( RULE ) \
84 bool add_ ## RULE( Subdivider& _sub ) \
85 { return _sub.add< Adaptive:: RULE < MyMesh > >(); }
86
87 ADD_FN( Tvv3 );
88 ADD_FN( Tvv4 );
89 ADD_FN( VF );
90 ADD_FN( FF );
91 ADD_FN( FFc );
92 ADD_FN( FV );
93 ADD_FN( FVc );
94 ADD_FN( VV );
95 ADD_FN( VVc );
96 ADD_FN( VE );
97 ADD_FN( VdE );
98 ADD_FN( VdEc );
99 ADD_FN( EV );
100 ADD_FN( EVc );
101 ADD_FN( EF );
102 ADD_FN( FE );
103 ADD_FN( EdE );
104 ADD_FN( EdEc );
105
106 #undef ADD_FN
107
108 typedef bool (*add_rule_ft)( Subdivider& );
109
110 // map rule name to factory function
111 struct RuleMap : std::map< std::string, add_rule_ft >
112 {
113 RuleMap()
114 {
115 #define ADD( RULE ) \
116 (*this)[ #RULE ] = add_##RULE;
117
118 ADD( Tvv3 );
119 ADD( Tvv4 );
120 ADD( VF );
121 ADD( FF );
122 ADD( FFc );
123 ADD( FV );
124 ADD( FVc );
125 ADD( VV );
126 ADD( VVc );
127 ADD( VE );
128 ADD( VdE );
129 ADD( VdEc );
130 ADD( EV );
131 ADD( EVc );
132 ADD( EF );
133 ADD( FE );
134 ADD( EdE );
135 ADD( EdEc );
136
137 #undef ADD
138 }
139
140 } available_rules;
141
142
143 // ----------------------------------------------------------------------------
144
145 std::string basename( const std::string& _fname );
146 void usage_and_exit(const std::string& _fname, int xcode);
147
148 // ----------------------------------------------------------------------------
149
150
151 int main(int argc, char **argv)
152 {
153 size_t n_iter = 0; // n iteration
154 size_t max_nv = size_t(-1); // max. number of vertices in the end
155 std::string ifname; // input mesh
156 std::string ofname; // output mesh
157 std::string rule_sequence = "Tvv3 VF FF FVc"; // sqrt3 default
158 bool uniform = false;
159 int c;
160
161 // ---------------------------------------- evaluate command line
162 while ( (c=getopt(argc, argv, "hlm:n:r:sU"))!=-1 )
163 {
164 switch(c)
165 {
166 case 's': rule_sequence = "Tvv3 VF FF FVc"; break; // sqrt3
167 case 'l': rule_sequence = "Tvv4 VdE EVc VdE EVc"; break; // loop
168 case 'n': { std::stringstream s; s << optarg; s >> n_iter; } break;
169 case 'm': { std::stringstream s; s << optarg; s >> max_nv; } break;
170 case 'r': rule_sequence = optarg; break;
171 case 'U': uniform = true; break;
172 case 'h': usage_and_exit(argv[0],0);
173 case '?':
174 default: usage_and_exit(argv[0],1);
175 }
176 }
177
178 if ( optind == argc )
179 usage_and_exit(argv[0],2);
180
181 if ( optind < argc )
182 ifname = argv[optind++];
183
184 if ( optind < argc )
185 ofname = argv[optind++];
186
187 // if ( optind < argc ) // too many arguments
188
189 // ---------------------------------------- mesh and subdivider
190 MyMesh mesh;
191 Subdivider subdivider(mesh);
192
193
194 // -------------------- read mesh from file
195 std::cout << "Input mesh : " << ifname << std::endl;
196 if (!OpenMesh::IO::read_mesh(mesh, ifname))
197 {
198 std::cerr << " Error reading file!\n";
199 return 1;
200 }
201
202 // store orignal size of mesh
203 size_t n_vertices = mesh.n_vertices();
204 size_t n_edges = mesh.n_edges();
205 size_t n_faces = mesh.n_faces();
206
207 if ( n_iter > 0 )
208 std::cout << "Desired #iterations: " << n_iter << std::endl;
209
210 if ( max_nv < size_t(-1) )
211 {
212 std::cout << "Desired max. #V : " << max_nv << std::endl;
213 if (!n_iter )
214 n_iter = size_t(-1);
215 }
216
217
218 // -------------------- Setup rule sequence
219 {
220 std::stringstream s;
221 std::string token;
222
223 RuleMap::iterator it = available_rules.end();
224
225 for (s << rule_sequence; s >> token; )
226 {
227 if ( (it=available_rules.find( token )) != available_rules.end() )
228 {
229 it->second( subdivider );
230 }
231 else if ( token[0]=='(' && (subdivider.n_rules() > 0) )
232 {
233 std::string::size_type beg(1);
234 if (token.length()==1)
235 {
236 s >> token;
237 beg = 0;
238 }
239
240 std::string::size_type
241 end = token.find_last_of(')');
242 std::string::size_type
243 size = end==std::string::npos ? token.size()-beg : end-beg;
244
245 std::stringstream v;
246 MyMesh::Scalar coeff;
247 std::cout << " " << token << std::endl;
248 std::cout << " " << beg << " " << end << " " << size << std::endl;
249 v << token.substr(beg, size);
250 v >> coeff;
251 std::cout << " coeffecient " << coeff << std::endl;
252 subdivider.rule( subdivider.n_rules()-1 ).set_coeff(coeff);
253
254 if (end == std::string::npos)
255 {
256 s >> token;
257 if (token[0]!=')')
258 {
259 std::cerr << "Syntax error: Missing ')'\n";
260 return 1;
261 }
262 }
263 }
264 else
265 {
266 std::cerr << "Syntax error: " << token << "?\n";
267 return 1;
268 }
269 }
270 }
271
272 std::cout << "Rule sequence : "
273 << subdivider.rules_as_string() << std::endl;
274
275 // -------------------- Initialize subdivider
276 std::cout << "Initialize subdivider\n";
277 if (!subdivider.initialize())
278 {
279 std::cerr << " Error!\n";
280 return 1;
281 }
282
283 //
284 MyMesh::FaceFaceIter ff_it;
285 double quality(0.0);
286
287 // ---------------------------------------- subdivide
288 std::cout << "\nSubdividing...\n";
289
290 OpenMesh::Utils::Timer timer, timer2;
291 size_t i;
292
293 if ( uniform )
294 { // unifom
295 MyMesh::VertexHandle vh;
296 MyMesh::VertexIter v_it;
297 MyMesh::FaceHandle fh;
298 MyMesh::FaceIter f_it;
299
300
301 // raise all vertices to target state
302 timer.start();
303
304 size_t n = n_iter;
305 size_t n_rules = subdivider.n_rules();
306
307 i = 0;
308
309 // calculate target states for faces and vertices
310 size_t target1 = (n - 1) * n_rules + subdivider.subdiv_rule().number() + 1;
311 size_t target2 = n * n_rules;
312
313 for (f_it = mesh.faces_begin(); f_it != mesh.faces_end(); ++f_it) {
314
315 if (mesh.data(*f_it).state() < int(target1) ) {
316 ++i;
317 fh = *f_it;
318 timer2.start();
319 subdivider.refine(fh);
320 timer2.stop();
321 }
322 }
323
324 for (v_it = mesh.vertices_begin(); v_it != mesh.vertices_end(); ++v_it) {
325
326 if (mesh.data(*v_it).state() < int(target2) ) {
327 vh = *v_it;
328 timer2.cont();
329 subdivider.refine(vh);
330 timer2.stop();
331 }
332 }
333 timer.stop();
334 }
335 else
336 { // adaptive
337
338 MyMesh::FaceIter f_it;
339 MyMesh::FaceHandle fh;
340
341 std::vector<double> __acos;
342 size_t buckets(3000);
343 double range(2.0);
344 double range2bucket(buckets/range);
345
346 for (i = 0; i < buckets; ++i)
347 __acos.push_back( acos(-1.0 + i * range / buckets) );
348
349 timer.start(); // total time needed
350
351 // n iterations or until desired number of vertices reached approx.
352 for (i = 0; i < n_iter && mesh.n_vertices() < max_nv; ++i)
353 {
354 mesh.update_face_normals();
355
356 // calculate quality
357 quality = 0.0;
358
359 fh = *(mesh.faces_begin());
360
361 // check every face
362 for (f_it = mesh.faces_begin(); f_it != mesh.faces_end(); ++f_it) {
363
364 double face_quality = 0.0;
365 int valence = 0;
366
367 for (ff_it = mesh.ff_iter(*f_it); ff_it.is_valid(); ++ff_it) {
368
369 double temp_quality = OpenMesh::dot( mesh.normal(*f_it), mesh.normal(*ff_it) );
370
371 if (temp_quality >= 1.0)
372 temp_quality = .99;
373 else if (temp_quality <= -1.0)
374 temp_quality = -.99;
375 temp_quality = (1.0+temp_quality) * range2bucket;
376 face_quality += __acos[int(temp_quality+.5)];
377
378 ++valence;
379 }
380
381 face_quality /= valence;
382
383 // calaculate face area
384 MyMesh::Point p1, p2, p3;
385 MyMesh::Scalar area;
386
387 #define heh halfedge_handle
388 #define nheh next_halfedge_handle
389 #define tvh to_vertex_handle
390 #define fvh from_vertex_handle
391 p1 = mesh.point(mesh.tvh(mesh.heh(*f_it)));
392 p2 = mesh.point(mesh.fvh(mesh.heh(*f_it)));
393 p3 = mesh.point(mesh.tvh(mesh.nheh(mesh.heh(*f_it))));
394 #undef heh
395 #undef nheh
396 #undef tvh
397 #undef fvh
398
399 area = ((p2 - p1) % (p3 - p1)).norm();
400
401 // weight face_quality
402 face_quality *= pow(double(area), double(.1));
403 //face_quality *= area;
404
405 if (face_quality >= quality && !mesh.is_boundary(*f_it))
406 {
407 quality = face_quality;
408 fh = *f_it;
409 }
410 }
411
412 // Subdivide Face
413 timer2.cont();
414 subdivider.refine(fh);
415 timer2.stop();
416 }
417
418 // calculate time
419 timer.stop();
420
421 } // uniform/adaptive?
422
423 // calculate maximum refinement level
424 Adaptive::state_t max_level(0);
425
426 for (MyMesh::VertexIter v_it = mesh.vertices_begin();
427 v_it != mesh.vertices_end(); ++v_it)
428 {
429 if (mesh.data(*v_it).state() > max_level)
430 max_level = mesh.data(*v_it).state();
431 }
432
433
434 // output results
435 std::cout << "\nDid " << i << (uniform ? " uniform " : "" )
436 << " subdivision steps in "
437 << timer.as_string()
438 << ", " << i/timer.seconds() << " steps/s\n";
439 std::cout << " only refinement: " << timer2.as_string()
440 << ", " << i/timer2.seconds() << " steps/s\n\n";
441
442 std::cout << "Before: ";
443 std::cout << n_vertices << " Vertices, ";
444 std::cout << n_edges << " Edges, ";
445 std::cout << n_faces << " Faces. \n";
446
447 std::cout << "Now : ";
448 std::cout << mesh.n_vertices() << " Vertices, ";
449 std::cout << mesh.n_edges() << " Edges, ";
450 std::cout << mesh.n_faces() << " Faces. \n\n";
451
452 std::cout << "Maximum quality : " << quality << std::endl;
453 std::cout << "Maximum Subdivision Level: " << max_level/subdivider.n_rules()
454 << std::endl << std::endl;
455
456 // ---------------------------------------- write mesh to file
457 {
458 if ( ofname.empty() )
459 {
460 std::stringstream s;
461
462 s << "result." << subdivider.rules_as_string("_")
463 << "-" << i << "x.off";
464 s >> ofname;
465 }
466
467 std::cout << "Output file: '" << ofname << "'.\n";
468 if (!OpenMesh::IO::write_mesh(mesh, ofname, OpenMesh::IO::Options::Binary))
469 {
470 std::cerr << " Error writing file!\n";
471 return 1;
472 }
473 }
474 return 0;
475 }
476
477 // ----------------------------------------------------------------------------
478 // helper
479
480 void usage_and_exit(const std::string& _fname, int xcode)
481 {
482 using namespace std;
483
484 cout << endl
485 << "Usage: " << basename(_fname)
486 << " [Options] input-mesh [output-mesh]\n\n";
487 cout << "\tAdaptively refine an input-mesh. The refined mesh is stored in\n"
488 << "\ta file named \"result.XXX.off\" (binary .off), if not specified\n"
489 << "\texplicitely (optional 2nd parameter of command line).\n\n";
490 cout << "Options:\n\n";
491 cout << "-m <int>\n\tAdaptively refine up to approx. <int> vertices.\n\n"
492 << "-n <int>\n\tAdaptively refine <int> times.\n\n"
493 << "-r <rule sequence>\n\tDefine a custom rule sequence.\n\n"
494 << "-l\n\tUse rule sequence for adaptive Loop.\n\n"
495 << "-s\n\tUse rule sequence for adaptive sqrt(3).\n\n"
496 << "-U\n\tRefine mesh uniformly (simulates uniform subdivision).\n\n";
497
498 exit(xcode);
499 }
500
501 std::string basename(const std::string& _f)
502 {
503 std::string::size_type dot = _f.rfind("/");
504 if (dot == std::string::npos)
505 return _f;
506 return _f.substr(dot+1, _f.length()-(dot+1));
507 }
508
509 // ----------------------------------------------------------------------------
510 // end of file
511 // ============================================================================
OpenMesh::IO::read_mesh
bool read_mesh(Mesh &_mesh, const std::string &_filename)
Read a mesh from file _filename.
Definition: MeshIO.hh:104
OpenMesh::Subdivider::Adaptive::CompositeT
Definition: CompositeT.hh:138
OpenMesh::Utils::Timer::stop
void stop(void)
Stop measurement.
OpenMesh::PolyMeshT::Point
Kernel::Point Point
Coordinate type.
Definition: PolyMeshT.hh:115
OpenMesh::TriMesh_ArrayKernelT
Definition: TriMesh_ArrayKernelT.hh:98
OpenMesh::Subdivider::Adaptive::CompositeTraits
Definition: CompositeTraits.hh:86
OpenMesh::Utils::Timer::as_string
std::string as_string(Format format=Automatic)
OpenMesh::PolyMeshT::FaceFaceIter
Kernel::FaceFaceIter FaceFaceIter
Circulator.
Definition: PolyMeshT.hh:173
Timer.hh
RulesT.hh
RuleMap
Definition: adaptive_subdivider.cc:111
OpenMesh::Subdivider
OpenMesh::PolyMeshT::update_face_normals
void update_face_normals()
Update normal vectors for all faces.
Definition: PolyMeshT.cc:259
OpenMesh::Utils::Timer::start
void start(void)
Start measurement.
OpenMesh::dot
osg::Vec3f::ValueType dot(const osg::Vec3f &_v1, const osg::Vec3f &_v2)
Adapter for osg vector member computing a scalar product.
Definition: VectorAdapter.hh:181
OpenMesh::PolyMeshT::Scalar
Kernel::Scalar Scalar
Scalar type.
Definition: PolyMeshT.hh:113
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
OpenMesh::IO::Options::Binary
Set binary mode for r/w.
Definition: Options.hh:105
OpenMesh::Utils::Timer::seconds
double seconds(void) const
Returns measured time in seconds, if the timer is in state 'Stopped'.
std
STL namespace.
OpenMesh::Subdivider::Adaptive::RuleInterfaceT
Definition: CompositeT.hh:84
OpenMesh::Utils::Timer::cont
void cont(void)
Continue measurement.
OpenMesh::IO::write_mesh
bool write_mesh(const Mesh &_mesh, const std::string &_filename, Options _opt=Options::Default, std::streamsize _precision=6)
Write a mesh to the file _filename.
Definition: MeshIO.hh:199
CompositeT.hh
OpenMesh::Subdivider::Adaptive::state_t
CompositeTraits::state_t state_t
Definition: CompositeTraits.hh:255
OpenMesh::Utils::Timer
Definition: Timer.hh:87