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
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"
61 #include <OpenMesh/Tools/Smoother/JacobiLaplaceSmootherT.hh>
62
63 //=============================================================================
64
65 template< class TheMesh >
66 class HoleFiller
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_;
154 OpenMesh::VPropHandleT< Scalar > scale_;
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
HoleFiller::Weight
Definition: HoleFillerT.hh:76
HoleFiller
Definition: HoleFillerT.hh:66
OpenMesh::VPropHandleT< Scalar >
JacobiLaplaceSmootherT.hh