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