Developer Documentation
HoleFillerT.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 * $Revision$ *
45 * $LastChangedBy$ *
46 * $Date$ *
47 * *
48 \*===========================================================================*/
49 
50 
51 //=============================================================================
52 #ifndef HOLEFILLER_HH
53 #define HOLEFILLER_HH
54 //=============================================================================
55 
56 #include <vector>
57 #include <float.h>
58 #include <cmath>
59 #include <OpenMesh/Core/Utils/vector_cast.hh>
60 #include "OpenMeshUtils.hh"
62 
63 //=============================================================================
64 
65 template< class TheMesh >
67 {
68 public:
69  typedef TheMesh Mesh;
70 
71  import_om_abbreviations( typename Mesh );
72 
73  // A weight is a tuple of area and maximum dihedral angle
74  //
75 
76  class Weight {
77  public:
78 
79  Weight() : angle_( 180 ), area_( FLT_MAX ) {}
80  Weight( Scalar _angle, Scalar _area ) : angle_( _angle ), area_( _area ) {}
81  ~Weight() {}
82 
83  Scalar angle() const { return angle_; }
84  Scalar area() const { return area_; }
85 
86  Weight operator+( const Weight & _other ) const {
87  return Weight( std::max( angle(), _other.angle() ),
88  area() + _other.area() );
89  }
90 
91  bool operator<( const Weight & _rhs ) const {
92  return ( angle() < _rhs.angle() ||
93  ( angle() == _rhs.angle() && area() < _rhs.area() ) );
94  }
95 
96  private:
97  Scalar angle_;
98  Scalar area_;
99  };
100 
101 
102  // Ctors
103  HoleFiller( Mesh & _mesh );
104  ~HoleFiller();
105 
106  // Identify and fill all holes of the mesh.
107  void fill_all_holes( int _stages = 3 );
108 
109 
110  // Fill a hole which is identified by one of its boundary edges.
111  void fill_hole( EH _eh, int _stages = 3 );
112 
113  // Fair a filling
114  void fairing( std::vector< FH >& _faceHandles );
115 
116  // Remove degenerated faces from the filling
117  void removeDegeneratedFaces( std::vector< FH >& _faceHandles );
118 
119 private:
120 
121  // Refine a face
122  bool refine( FH _fh );
123 
124  // Relax an edge
125  bool relax_edge( EH _eh );
126 
127  // Test whether a point _x lies in the circumsphere of _a,_b,_c.
128  bool in_circumsphere( const Point & _x,
129  const Point & _a,
130  const Point & _b,
131  const Point & _c ) const;
132 
133  // Create the triangulation for polygon (_i,...,_j).
134  bool fill( int _i, int _j );
135 
136  // Compute the weight of the triangle (_i,_j,_k).
137  Weight weight( int _i, int _j, int _k );
138 
139  // Does edge (_u,_v) already exist?
140  bool exists_edge( VH _u, VH _w );
141 
142  // Compute the area of the triangle (_a,_b,_c).
143  Scalar area( VH _a, VH _b, VH _c );
144 
145  // Compute the dihedral angle (in degrees) between triangle
146  // (_u,_v,_a) and triangle (_v,_u,_b).
147  Scalar dihedral_angle( VH _u, VH _v, VH _a, VH _b );
148 
149 
150  // The mesh, with each vertex we associate a scale factor that is
151  // needed for remeshing
152 
153  Mesh & mesh_;
155 
156  /*
157  HOLE
158 
159  boundary_vertex_
160  |
161  V
162  ==*=======*=======*== BOUNDARY
163  / \ / \ / \
164  / \ / \ / \
165  \ / \ /
166  * * <- opposite_vertex_
167  */
168 
169 
170  typedef std::vector< VH > VHVec;
171  typedef typename std::vector< VH >::iterator VHVecIter;
172  typedef typename std::vector< VH >::const_iterator CVHVecIter;
173 
174  typedef std::vector< FH > FHVec;
175  typedef typename std::vector< FH >::iterator FHVecIter;
176  typedef typename std::vector< FH >::const_iterator CFHVecIter;
177 
178 
179  // This vector contains all vertices of the hole (in order)
180  VHVec boundary_vertex_;
181 
182  // This vector contains all vertices that are opposite to an edge of the hole
183  VHVec opposite_vertex_;
184 
185  // This vector contains all edges of the hole (in order)
186  std::vector< EH > hole_edge_;
187 
188  // This vector stores handles to all triangles of the current hole
189  std::vector< FH > hole_triangle_;
190 
191  // These are the two central arrays that are needed for the dynamic
192  // programming approach to hole filling.
193  // w_[i][j] : stores the minimal weight that can be achieved
194  // for a triangulation of the polygon
195  // boundary_vertex_[i],...,boundary_vertex_[j]
196  // l_[i][j] : stores the third index of the triangle
197  // <boundary_vertex_[i],boundary_vertex_[l_[i][j]],
198  // boundary_vertex_[j]>
199  // that is needed for reconstructing the minimal triangulation
200 
201  std::vector< std::vector< Weight > > w_;
202  std::vector< std::vector< int > > l_;
203 };
204 
205 //=============================================================================
206 #ifndef HOLEFILLER_CC
207  #include "HoleFillerT.cc"
208 #endif
209 //=============================================================================
210 #endif // HOLEFILLER_HH defined
211 //=============================================================================
212