Developer Documentation

HoleFillerT_impl.hh
1 /*===========================================================================*\
2 * *
3 * OpenFlipper *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openflipper.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenFlipper. *
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 //=============================================================================
45 #define HOLEFILLER_CC
46 #include "HoleFillerT.hh"
47 //=============================================================================
48 #include <QInputDialog>
49
50 template< class MeshT >
51 HoleFiller< MeshT >::HoleFiller( Mesh & _mesh )
52 : mesh_( _mesh )
53 {
54 mesh_.request_vertex_status();
55 mesh_.request_edge_status();
56
57 if (! mesh_.get_property_handle(scale_,"scale") )
58 mesh_.add_property( scale_ , "scale" );
59 }
60
61
62 //=============================================================================
63
64
65
66 template< class MeshT >
67 HoleFiller< MeshT >::~HoleFiller()
68 {
69 mesh_.release_vertex_status();
70 mesh_.release_edge_status();
71
72 if ( mesh_.get_property_handle(scale_,"scale") )
73 mesh_.remove_property( scale_ );
74 }
75
76
77 //=============================================================================
78 //
79 // Identify and fill all holes of the mesh.
80 //
81 //=============================================================================
82
83
84 template< class MeshT >
85 void
86 HoleFiller< MeshT >::fill_all_holes( int _stages )
87 {
88 // Collect all boundary edges
89
90 std::vector< EH > bdry_edge;
91
92 for ( EI ei = mesh_.edges_begin();
93 ei != mesh_.edges_end(); ++ei )
94 if ( mesh_.is_boundary( *ei ) )
95 bdry_edge.push_back( *ei );
96
97 // Fill holes
98
99 int cnt = 0;
100 for ( typename std::vector< EH >::iterator i = bdry_edge.begin();
101 i != bdry_edge.end(); ++i )
102 if ( mesh_.is_boundary( *i ) )
103 {
104 ++cnt;
105 std::cerr << "Filling hole " << cnt << "\n";
106 fill_hole( *i, _stages );
107 }
108
109
110 // Smooth fillings
111
112 if ( _stages <= 2 )
113 return;
114
115 std::cerr << "Stage 3 : Smoothing the hole fillings ... ";
116
117 OpenMesh::Smoother::JacobiLaplaceSmootherT< Mesh > smoother( mesh_ );
118 smoother.initialize( OpenMesh::Smoother::SmootherT< Mesh >::
119 Tangential_and_Normal,
120 OpenMesh::Smoother::SmootherT< Mesh >::C1 );
121
122 smoother.smooth( 500 );
123 std::cerr << "ok\n";
124 }
125
126
127 //=============================================================================
128 //
129 // Fill a hole which is identified by one of its boundary edges.
130 //
131 //=============================================================================
132
133
134 template< class MeshT >
135 void
136 HoleFiller< MeshT >::fill_hole( EH _eh, int _stages )
137 {
138 std::cerr << " Stage 1 : Computing a minimal triangulation ... ";
139
140 //remember last vertex for selection of new ones
141 typename MeshT::VertexHandle old_last_handle = *(--mesh_.vertices_end());
142
143 // No boundary edge, no hole
144
145 if ( ! mesh_.is_boundary( _eh ) )
146 return;
147
148
149 // Get boundary halfedge
150
151 HH hh = mesh_.halfedge_handle( _eh, 0 );
152 if ( ! mesh_.is_boundary( hh ) )
153 hh = mesh_.opposite_halfedge_handle( hh );
154
155
156 // Collect boundary vertices
157
158 boundary_vertex_.clear();
159 opposite_vertex_.clear();
160
161 HH ch = hh;
162
163 do {
164 boundary_vertex_.push_back( mesh_.from_vertex_handle( ch ) );
165 opposite_vertex_.push_back( mesh_.to_vertex_handle
166 (mesh_.next_halfedge_handle( mesh_.opposite_halfedge_handle( ch ) ) ) );
167
168 //check number of outgoing boundary HEH's at Vertex
169 int c = 0;
170 VH vh = mesh_.to_vertex_handle(ch);
171
172 for ( typename MeshT::VertexOHalfedgeIter voh_it(mesh_,vh); voh_it.is_valid(); ++voh_it)
173 if ( mesh_.is_boundary( *voh_it ) )
174 c++;
175
176 if ( c >= 2){
177 HH op = mesh_.opposite_halfedge_handle( ch );
178 typename MeshT::VertexOHalfedgeIter voh_it(mesh_,op);
179
180 ch = *(++voh_it);
181 }else
182 ch = mesh_.next_halfedge_handle( ch );
183
184 } while ( ch != hh );
185
186
187 int nv = boundary_vertex_.size();
188
189 // Compute an initial triangulation
190
191 w_.clear();
192 w_.resize( nv, std::vector<Weight>( nv, Weight() ) );
193
194 l_.clear();
195 l_.resize( nv, std::vector<int>( nv, 0 ) );
196
197
198 for ( int i = 0; i < nv - 1; ++i )
199 w_[i][i+1] = Weight( 0, 0 );
200
201 for ( int j = 2; j < nv; ++j )
202 {
203 #pragma omp parallel for shared(j, nv)
204 for(int i = 0; i < nv-j; ++i)
205 {
206 Weight valmin;
207 int argmin = -1;
208 for ( int m = i + 1; m < i + j; ++m )
209 {
210 Weight newval = w_[i][m] + w_[m][i+j] + weight( i, m, i+j );
211 if ( newval < valmin )
212 {
213 valmin = newval;
214 argmin = m;
215 }
216 }
217
218 w_[i][i+j] = valmin;
219 l_[i][i+j] = argmin;
220 }
221 }
222
223
224 // Actually fill the hole. We collect all triangles and edges of
225 // this filling for further processing.
226
227 hole_edge_.clear();
228 hole_triangle_.clear();
229 if ( fill( 0, nv - 1 ) ){
230
231 std::cerr << "ok\n";
232
233 if ( _stages <= 1 )
234 return;
235
236 std::cerr << " Stage 2 : Fairing the filling ... ";
237
238 std::vector< FH > handles = hole_triangle_;
239
240 fairing(handles);
241
242 //select all new vertices
243 typename MeshT::VertexIter old_end = ++typename MeshT::VertexIter(mesh_,old_last_handle);
244 typename MeshT::VertexIter v_end = mesh_.vertices_end();
245
246 for(; old_end != v_end; ++old_end)
247 if ( !mesh_.status(*old_end).deleted() )
248 mesh_.status(*old_end).set_selected( true );
249
250 std::cerr << "ok\n";
251 }else
252 std::cerr << "Could not create triangulation" << std::endl;
253 }
254
255
257 template< class MeshT >
258 void
259 HoleFiller< MeshT >::fairing( std::vector< FH >& _faceHandles ){
260
261 //generate vector of all edges
262 hole_edge_.clear();
263
264 hole_triangle_ = _faceHandles;
265
266 OpenMesh::EPropHandleT< bool > edgeProp;
267 OpenMesh::VPropHandleT< bool > vertexProp;
268 OpenMesh::FPropHandleT< bool > faceProp;
269 OpenMesh::FPropHandleT< bool > orderProp;
270
271 if (! mesh_.get_property_handle(edgeProp,"edgeProp") )
272 mesh_.add_property( edgeProp, "edgeProp" );
273 if (! mesh_.get_property_handle(vertexProp,"vertexProp") )
274 mesh_.add_property( vertexProp, "vertexProp" );
275 if (! mesh_.get_property_handle(faceProp,"faceProp") )
276 mesh_.add_property( faceProp, "faceProp" );
277 if (! mesh_.get_property_handle(orderProp,"orderProp") )
278 mesh_.add_property( orderProp, "orderProp" );
279
280 EI eIt;
281 EI eEnd = mesh_.edges_end();
282 VI vIt;
283 VI vEnd = mesh_.vertices_end();
284 FI fIt;
285 FI fEnd = mesh_.faces_end();
286
287 //init properties by setting all of them to false
288 for (fIt = mesh_.faces_begin(); fIt != fEnd; ++fIt){
289 mesh_.property( orderProp, *fIt ) = false;
290 mesh_.property( faceProp, *fIt ) = false;
291 }
292
293 for (eIt = mesh_.edges_begin(); eIt != eEnd; ++eIt)
294 mesh_.property( edgeProp, *eIt ) = false;
295
296 for (vIt = mesh_.vertices_begin(); vIt != vEnd; ++vIt){
297 mesh_.property( vertexProp, *vIt ) = false;
298 }
299
300 //set face property
301 for (uint i = 0; i < hole_triangle_.size(); i++){
302 mesh_.property( faceProp, hole_triangle_[i] ) = true;
303 }
304
305 //set properties
306 for (unsigned int i = 0; i < hole_triangle_.size(); i++){
307 for (FEI fei = mesh_.fe_iter( hole_triangle_[i] ); fei.is_valid(); ++fei){
308 mesh_.status( *fei ).set_locked(true);
309 //set edge property for all edges inside the hole (eg not on the hole boundary)
310 if (mesh_.property( faceProp, mesh_.face_handle(mesh_.halfedge_handle(*fei, 0) ) ) &&
311 mesh_.property( faceProp, mesh_.face_handle(mesh_.halfedge_handle(*fei, 1) ) ) ){
312
313 mesh_.property( edgeProp, *fei ) = true;
314 hole_edge_.push_back( *fei );
315 mesh_.status( *fei ).set_locked(false);
316 }
317 }
318
320 for (FVI fvi = mesh_.fv_iter( hole_triangle_[i] ); fvi.is_valid(); ++fvi){
321 //set vertex property for all vertices of the hole
322 for ( VFI vfi = mesh_.vf_iter( *fvi ); vfi.is_valid(); ++vfi )
323 mesh_.property( vertexProp, *fvi ) = true;
324 }
325 }
326
327 //calculate scaling weights for vertices
328 for (vIt = mesh_.vertices_begin(); vIt != vEnd; ++vIt)
329 if (mesh_.property(vertexProp, *vIt)){
330
331 Scalar cnt = 0;
332 Scalar scale = 0;
333
334 for ( VOHI voh_it = mesh_.voh_iter( *vIt ); voh_it.is_valid(); ++voh_it )
335 {
336 HH h2 = mesh_.opposite_halfedge_handle( *voh_it );
337
338 if (mesh_.face_handle(*voh_it).is_valid() &&
339 mesh_.face_handle(h2).is_valid() &&
340 mesh_.property(faceProp, mesh_.face_handle( *voh_it ) ) &&
341 mesh_.property(faceProp, mesh_.face_handle(h2) ))
342 continue;
343
344 cnt += 1.0f;
345 Point p0 = mesh_.point( *vIt );
346 Point p1 = mesh_.point( mesh_.to_vertex_handle( *voh_it ) );
347 scale += ( p1 - p0 ).norm();
348
349 }
350
351 scale /= cnt;
352
353 mesh_.property( scale_, *vIt ) = scale;
354 }
355
356 mesh_.remove_property(edgeProp);
357 mesh_.remove_property(vertexProp);
358 mesh_.remove_property(faceProp);
359 mesh_.remove_property(orderProp);
360
361 // Do the patch fairing
362
363 bool did_refine = true;
364
365 for ( int k = 0; k < 40 && did_refine; ++k )
366 {
367 uint end = hole_triangle_.size();
368
369 did_refine = false;
370 for ( unsigned int j = 0; j < end; ++j )
371 did_refine |= refine( hole_triangle_[j] );
372
373 for ( int i = 0; i < 10; ++i )
374 for ( unsigned int j = 0; j < hole_edge_.size(); ++j )
375 relax_edge( hole_edge_[j] );
376 }
377
378 // unlock everything
379 for ( EI ei = mesh_.edges_begin(); ei != mesh_.edges_end(); ++ei )
380 mesh_.status( *ei ).set_locked( false );
381 }
382
383 //=============================================================================
384 //
385 // Refine a face: Apply a 1-to-3 split if the edge lengths of the
386 // face do not match the interpolated edge lengths of the hole
387 // boundary.
388 //
389 //=============================================================================
390
391
392 template< class MeshT >
393 bool
394 HoleFiller< MeshT >::refine( FH _fh )
395 {
396
397 // Collect the three edges of the face into e0, e1, e2
398
399 FEI fei = mesh_.fe_iter( _fh );
400 EH e0 = *fei; ++fei;
401 EH e1 = *fei; ++fei;
402 EH e2 = *fei; ++fei;
403
404
405 // Collect the vertices, vertex positions and scale factors of the face.
406
407 FVI fvi = mesh_.fv_iter( _fh );
408
409 VH v0 = *fvi; ++fvi;
410 VH v1 = *fvi; ++fvi;
411 VH v2 = *fvi; ++fvi;
412
413 Point p0 = mesh_.point( v0 );
414 Point p1 = mesh_.point( v1 );
415 Point p2 = mesh_.point( v2 );
416
417 Scalar scale0 = mesh_.property( scale_, v0 );
418 Scalar scale1 = mesh_.property( scale_, v1 );
419 Scalar scale2 = mesh_.property( scale_, v2 );
420
421 // Interpolate the scale factor.
422
423 Scalar scale = ( scale0 + scale1 + scale2 ) / 3.0f;
424 Point center = typename MeshT::Scalar(1.0/3.0) * ( p0 + p1 + p2 );
425
426 Scalar d0 = 1.0f * ( p0 - center ).norm();
427 Scalar d1 = 1.0f * ( p1 - center ).norm();
428 Scalar d2 = 1.0f * ( p2 - center ).norm();
429
430
431 //dont split triangles which tend to degenerate
432 if ( (d0 + d1 + d2) / 3.0f < scale) return false;
433
434
435 // If the edge lengths differ too much from the scale, perform a
436 // triangle split.
437
438 if ( ( d0 > scale && d0 > scale0 ) ||
439 ( d1 > scale && d1 > scale1 ) ||
440 ( d2 > scale && d2 > scale2 ) )
441 {
442 // Split the face ...
443
444 VH ch = mesh_.add_vertex( center );
445 mesh_.split( _fh, ch );
446
447 // ... put the new triangles into the global triangle list ...
448
449 for ( VFI vfi = mesh_.vf_iter( ch ); vfi.is_valid(); ++vfi )
450 if ( *vfi != _fh )
451 hole_triangle_.push_back( *vfi );
452
453 // ... put the new edges into the global edge list ...
454
455 for ( VEI vei = mesh_.ve_iter( ch ); vei.is_valid(); ++vei )
456 hole_edge_.push_back( *vei );
457
458 // ... and set the appropriate scale factor for the new vertex.
459
460 mesh_.property( scale_, ch ) = scale;
461
462 relax_edge( e0 );
463 relax_edge( e1 );
464 relax_edge( e2 );
465
466 return true;
467 }
468
469 return false;
470 }
471
472
473 //=============================================================================
474 //
475 // Relax an edge: Flip it if one of its opposing vertices lies in
476 // the circumsphere of the other three vertices.
477 //
478 //=============================================================================
479
480
481 template< class MeshT >
482 bool
483 HoleFiller< MeshT >::relax_edge( EH _eh )
484 {
485 if ( mesh_.status( _eh ).locked() )
486 return false;
487
488 // Abbreviations for the two halfedges of _eh
489
490 HH h0 = mesh_.halfedge_handle( _eh, 0 );
491 HH h1 = mesh_.halfedge_handle( _eh, 1 );
492
493 // Get the two end-vertices u and v of the edge
494
495 Point u( mesh_.point( mesh_.to_vertex_handle( h0 ) ) );
496 Point v( mesh_.point( mesh_.to_vertex_handle( h1 ) ) );
497
498 // Get the two opposing vertices a and b
499
500 Point a( mesh_.point
501 ( mesh_.to_vertex_handle
502 ( mesh_.next_halfedge_handle( h0 ) ) ) );
503
504 Point b( mesh_.point
505 ( mesh_.to_vertex_handle
506 ( mesh_.next_halfedge_handle( h1 ) ) ) );
507
508 // If the circumsphere criterion is fullfilled AND if the flip is
509 // topologically admissible, we do it.
510
511 if ( in_circumsphere( a, u, v, b ) || in_circumsphere( b, u, v, a ) ){
512 if ( mesh_.is_flip_ok( _eh ) )
513 {
514
515 mesh_.flip( _eh );
516
517 return true;
518 }else
519 mesh_.status(_eh).set_selected( true );
520 }
521 return false;
522 }
523
524
525 //=============================================================================
526 //
527 // Test whether a point _x lies in the circumsphere of _a,_b,_c.
528 //
529 //=============================================================================
530
531
532 template< class MeshT >
533 bool
534 HoleFiller< MeshT >::in_circumsphere( const Point & _x,
535 const Point & _a,
536 const Point & _b,
537 const Point & _c ) const
538 {
539 Point ab = _b - _a;
540 Point ac = _c - _a;
541
542 Scalar a00 = -2.0f * ( ab | _a );
543 Scalar a01 = -2.0f * ( ab | _b );
544 Scalar a02 = -2.0f * ( ab | _c );
545 Scalar b0 = _a.sqrnorm() - _b.sqrnorm();
546
547 Scalar a10 = -2.0f * ( ac | _a );
548 Scalar a11 = -2.0f * ( ac | _b );
549 Scalar a12 = -2.0f * ( ac | _c );
550 Scalar b1 = _a.sqrnorm() - _c.sqrnorm();
551
552 typename MeshT::Scalar alpha = -(-a11*a02+a01*a12-a12*b0+b1*a02+a11*b0-a01*b1)
553 / (-a11*a00+a11*a02-a10*a02+a00*a12+a01*a10-a01*a12);
554 typename MeshT::Scalar beta = (a10*b0-a10*a02-a12*b0+a00*a12+b1*a02-a00*b1)
555 / (-a11*a00+a11*a02-a10*a02+a00*a12+a01*a10-a01*a12);
556 typename MeshT::Scalar gamma = (-a11*a00-a10*b0+a00*b1+a11*b0+a01*a10-a01*b1)
557 / (-a11*a00+a11*a02-a10*a02+a00*a12+a01*a10-a01*a12);
558
559 Point center = alpha * _a + beta * _b + gamma * _c;
560
561 return ( _x - center ).sqrnorm() < ( _a - center ).sqrnorm();
562 }
563
564
565 //=============================================================================
566 //
567 // Create the triangulation
568 //
569 // Recursively creates the triangulation for polygon (_i,...,_j).
570 //
571 //=============================================================================
572
573
574 template< class MeshT >
575 bool
576 HoleFiller< MeshT >::fill( int _i, int _j )
577 {
578 // If the two vertices _i and _j are adjacent, there is nothing to do.
579
580 if ( _i + 1 == _j )
581 return true;
582
583
584 // Create and store the middle triangle, store its edges.
585
586 FH fh = mesh_.add_face( boundary_vertex_[_i],
587 boundary_vertex_[ l_[_i][_j] ],
588 boundary_vertex_[_j] );
589 hole_triangle_.push_back( fh );
590
591 if (!fh.is_valid())
592 return false;
593
594 hole_edge_.push_back( mesh_.edge_handle
595 ( mesh_.find_halfedge( boundary_vertex_[_i],
596 boundary_vertex_[ l_[_i][_j] ] ) ) );
597 hole_edge_.push_back( mesh_.edge_handle
598 ( mesh_.find_halfedge( boundary_vertex_[ l_[_i][_j] ],
599 boundary_vertex_[_j] ) ) );
600
601
602 // Recursively create the left and right side of the
603 // triangulation.
604
605 if (!fill( _i, l_[_i][_j] ) || !fill( l_[_i][_j], _j ))
606 return false;
607 else
608 return true;
609 }
610
611
612
613 //=============================================================================
614 //
615 // Compute the weight of the triangle (_i,_j,_k).
616 //
617 //=============================================================================
618
619
620 template< class MeshT >
621 typename HoleFiller< MeshT >::Weight
622 HoleFiller< MeshT >::weight( int _i, int _j, int _k )
623 {
624 // Return an infinite weight if the insertion of this triangle
625 // would create complex edges.
626
627 if ( exists_edge( boundary_vertex_[_i], boundary_vertex_[_j] ) ||
628 exists_edge( boundary_vertex_[_j], boundary_vertex_[_k] ) ||
629 exists_edge( boundary_vertex_[_k], boundary_vertex_[_i] ) )
630 return Weight();
631
632
633 // Return an infinite weight, if one of the neighboring patches
634 // could not be created.
635
636
637 if ( l_[_i][_j] == -1 ) return Weight();
638 if ( l_[_j][_k] == -1 ) return Weight();
639
640
641 // Compute the maxmimum dihedral angles to the adjacent triangles
642 // (if they exist)
643
644 Scalar angle = 0.0f;
645
646 if ( _i + 1 == _j )
647 angle = std::max( angle, dihedral_angle( boundary_vertex_[_i],
648 boundary_vertex_[_j],
649 boundary_vertex_[_k],
650 opposite_vertex_[_i] ) );
651 else
652 angle = std::max( angle, dihedral_angle( boundary_vertex_[_i],
653 boundary_vertex_[_j],
654 boundary_vertex_[_k],
655 boundary_vertex_[l_[_i][_j]] ) );
656
657 if ( _j + 1 == _k )
658 angle = std::max( angle, dihedral_angle( boundary_vertex_[_j],
659 boundary_vertex_[_k],
660 boundary_vertex_[_i],
661 opposite_vertex_[_j] ) );
662 else
663 angle = std::max( angle, dihedral_angle( boundary_vertex_[_j],
664 boundary_vertex_[_k],
665 boundary_vertex_[_i],
666 boundary_vertex_[l_[_j][_k]] ) );
667
668 if ( _i == 0 && _k == (int) boundary_vertex_.size() - 1 )
669 angle = std::max( angle, dihedral_angle( boundary_vertex_[_k],
670 boundary_vertex_[_i],
671 boundary_vertex_[_j],
672 opposite_vertex_[_k] ) );
673
674
675 return Weight( angle, area( boundary_vertex_[_i],
676 boundary_vertex_[_j],
677 boundary_vertex_[_k] ) );
678 }
679
680
681
682 //=============================================================================
683 //
684 // Does an edge from vertex _u to _v exist?
685 //
686 //=============================================================================
687
688
689 template< class MeshT >
690 bool
691 HoleFiller< MeshT >::exists_edge( VH _u, VH _w )
692 {
693 for ( VOHI vohi = mesh_.voh_iter( _u ); vohi.is_valid(); ++vohi )
694 if ( ! mesh_.is_boundary( mesh_.edge_handle( *vohi ) ) )
695 if ( mesh_.to_vertex_handle( *vohi ) == _w )
696 return true;
697
698 return false;
699 }
700
701
702
703 //=============================================================================
704 //
705 // Compute the area of the triangle (_a,_b,_c).
706 //
707 //=============================================================================
708
709
710 template< class MeshT >
711 typename MeshT::Scalar
712 HoleFiller< MeshT >::area( VH _a, VH _b, VH _c )
713 {
714 Point a( mesh_.point( _a ) );
715 Point b( mesh_.point( _b ) );
716 Point c( mesh_.point( _c ) );
717
718 Point n( ( b - a ) % ( c - b ) );
719
720 return 0.5 * n.norm();
721 }
722
723
724 //=============================================================================
725 //
726 // Compute a dihedral angle
727 //
728 // Computes the dihedral angle (in degrees) between triangle
729 // (_u,_v,_a) and triangle (_v,_u,_b), no matter whether these
730 // triangles actually exist in the current mesh or not).
731 //
732 //=============================================================================
733
734
735 template< class MeshT >
736 typename MeshT::Scalar
737 HoleFiller< MeshT >::dihedral_angle( VH _u, VH _v, VH _a, VH _b )
738 {
739 Point u( mesh_.point( _u ) );
740 Point v( mesh_.point( _v ) );
741 Point a( mesh_.point( _a ) );
742 Point b( mesh_.point( _b ) );
743
744 Point n0( ( v - u ) % ( a - v ) );
745 Point n1( ( u - v ) % ( b - u ) );
746
747 n0.normalize();
748 n1.normalize();
749
750 return acos( n0 | n1 ) * 180.0 / M_PI;
751 }
752
753
755 template< class MeshT >
756 void
757 HoleFiller< MeshT >::removeDegeneratedFaces( std::vector< FH >& _faceHandles ){
758
759 for (int i = _faceHandles.size()-1; i >= 0 ; i--){
760
761 if ( mesh_.status( _faceHandles[i] ).deleted() ){
762 // face might be deleted because of a previous edge collapse
763 // erase the face from the vector
764 _faceHandles.erase( _faceHandles.begin() + i );
765 continue;
766 }
767
768 //get the vertices (works only on triMeshes)
769 FVI fvi = mesh_.fv_iter( _faceHandles[i] );
770 Point v0 = mesh_.point( *fvi);
771 ++fvi;
772 Point v1 = mesh_.point( *fvi );
773 ++fvi;
774 Point v2 = mesh_.point( *fvi );
775
776 //check if its degenerated
777 Point v0v1 = v1 - v0;
778 Point v0v2 = v2 - v0;
779 Point n = v0v1 % v0v2; // not normalized !
780 double d = n.sqrnorm();
781
782 if (d < FLT_MIN && d > -FLT_MIN) {
783 // degenerated face found
784 FHI hIt = mesh_.fh_iter( _faceHandles[i] );
785
786 //try to collapse one of the edges
787 while (hIt.is_valid()){
788 if ( mesh_.is_collapse_ok( *hIt ) ){
789 // collapse the edge to remove the triangle
790 mesh_.collapse( *hIt );
791 // and erase the corresponding face from the vector
792 _faceHandles.erase( _faceHandles.begin() + i );
793 break;
794 } else {
795 ++hIt;
796 }
797 }
798 }
799 }
800 }
801
802 //=============================================================================
803
OpenMesh::TriMesh_ArrayKernelT
Definition: PolyMesh_ArrayKernelT.hh:73
OpenMesh::EPropHandleT
Definition: Property.hh:510
OpenMesh::PolyMeshT::add_vertex
VertexHandle add_vertex(const Point &_p)
Alias for new_vertex(const Point&).
Definition: PolyMeshT.hh:235
HoleFiller
Definition: HoleFillerT.hh:60
OpenMesh::Smoother::JacobiLaplaceSmootherT
Definition: JacobiLaplaceSmootherT.hh:75
OpenMesh::FPropHandleT< bool >
OpenMesh::Smoother::SmootherT
Definition: SmootherT.hh:76
OpenMesh::TriMeshT::split
VertexHandle split(EdgeHandle _eh, const Point &_p)
Edge split (= 2-to-4 split)
Definition: TriMeshT.hh:267
OpenMesh::VPropHandleT< bool >