Developer Documentation
LongestEdgeT.hh
Go to the documentation of this file.
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 
47 //=============================================================================
48 //
49 // CLASS LongestEdgeT
50 //
51 //=============================================================================
52 
53 
54 #ifndef LINEAR_H
55 #define LINEAR_H
56 
58 #include <OpenMesh/Core/Utils/vector_cast.hh>
59 #include <OpenMesh/Core/Utils/Property.hh>
60 // -------------------- STL
61 #include <vector>
62 #include <queue>
63 #if defined(OM_CC_MIPS)
64 # include <math.h>
65 #else
66 # include <cmath>
67 #endif
68 
69 
70 //== NAMESPACE ================================================================
71 
72 namespace OpenMesh { // BEGIN_NS_OPENMESH
73 namespace Subdivider { // BEGIN_NS_DECIMATER
74 namespace Uniform { // BEGIN_NS_UNIFORM
75 
76 
77 //== CLASS DEFINITION =========================================================
78 
79 template <typename MeshType, typename RealType = double>
81  public:
82 
83  typedef std::pair<typename MeshType::EdgeHandle, RealType> queueElement;
84 
85  bool operator()(const queueElement& t1, const queueElement& t2) // Returns true if t1 is smaller than t2
86  {
87  return (t1.second < t2.second);
88  }
89 };
90 
91 
98 template <typename MeshType, typename RealType = float>
99 class LongestEdgeT : public SubdividerT<MeshType, RealType>
100 {
101 public:
102 
103  typedef RealType real_t;
104  typedef MeshType mesh_t;
106 
107  typedef std::vector< std::vector<real_t> > weights_t;
108  typedef std::vector<real_t> weight_t;
109 
110  typedef std::pair< typename mesh_t::EdgeHandle, real_t > queueElement;
111 
112 public:
113 
114 
115  LongestEdgeT() : parent_t()
116  { }
117 
118 
119  LongestEdgeT( mesh_t& _m) : parent_t(_m)
120  { }
121 
122 
123  ~LongestEdgeT() {}
124 
125 
126 public:
127 
128 
129  const char *name() const { return "Longest Edge Split"; }
130 
131  void set_max_edge_length(double _value) {
132  max_edge_length_squared_ = _value * _value;
133  }
134 
135 protected:
136 
137 
138  bool prepare( mesh_t& _m )
139  {
140  return true;
141  }
142 
143 
144  bool cleanup( mesh_t& _m )
145  {
146  return true;
147  }
148 
149 
150  bool subdivide( MeshType& _m, size_t _n , const bool _update_points = true)
151  {
152 
153  // Sorted queue containing all edges sorted by their decreasing length
154  std::priority_queue< queueElement, std::vector< queueElement > , CompareLengthFunction< mesh_t, real_t > > queue;
155 
156  // Build the initial queue
157  // First element should be longest edge
158  typename mesh_t::EdgeIter edgesEnd = _m.edges_end();
159  for ( typename mesh_t::EdgeIter eit = _m.edges_begin(); eit != edgesEnd; ++eit) {
160  const typename MeshType::Point to = _m.point(_m.to_vertex_handle(_m.halfedge_handle(*eit,0)));
161  const typename MeshType::Point from = _m.point(_m.from_vertex_handle(_m.halfedge_handle(*eit,0)));
162 
163  real_t length = (to - from).sqrnorm();
164 
165  // Only push the edges that need to be split
166  if ( length > max_edge_length_squared_ )
167  queue.push( queueElement(*eit,length) );
168  }
169 
170  bool stop = false;
171  while ( !stop && ! queue.empty() ) {
172  queueElement a = queue.top();
173  queue.pop();
174 
175  if ( a.second < max_edge_length_squared_ ) {
176  stop = true;
177  break;
178  } else {
179  const typename MeshType::Point to = _m.point(_m.to_vertex_handle(_m.halfedge_handle(a.first,0)));
180  const typename MeshType::Point from = _m.point(_m.from_vertex_handle(_m.halfedge_handle(a.first,0)));
181  const typename MeshType::Point midpoint = static_cast<typename MeshType::Point::value_type>(0.5) * (to + from);
182 
183  const typename MeshType::VertexHandle newVertex = _m.add_vertex(midpoint);
184  _m.split(a.first,newVertex);
185 
186  for ( typename MeshType::VertexOHalfedgeIter voh_it(_m,newVertex); voh_it.is_valid(); ++voh_it) {
187  typename MeshType::EdgeHandle eh = _m.edge_handle(*voh_it);
188  const typename MeshType::Point to = _m.point(_m.to_vertex_handle(*voh_it));
189  const typename MeshType::Point from = _m.point(_m.from_vertex_handle(*voh_it));
190  real_t length = (to - from).sqrnorm();
191 
192  // Only push the edges that need to be split
193  if ( length > max_edge_length_squared_ )
194  queue.push( queueElement(eh,length) );
195 
196  }
197  }
198  }
199 
200 #if defined(_DEBUG) || defined(DEBUG)
201  // Now we have an consistent mesh!
202  assert( OpenMesh::Utils::MeshCheckerT<mesh_t>(_m).check() );
203 #endif
204 
205 
206  return true;
207  }
208 
209 
210 private: // data
211  real_t max_edge_length_squared_;
212 
213 };
214 
215 } // END_NS_UNIFORM
216 } // END_NS_SUBDIVIDER
217 } // END_NS_OPENMESH
218 #endif
219 
const char * name() const
Return name of subdivision algorithm.
bool cleanup(mesh_t &_m)
Cleanup mesh after usage, e.g. remove added properties.
bool prepare(mesh_t &_m)
Prepare mesh, e.g. add properties.
bool subdivide(MeshType &_m, size_t _n, const bool _update_points=true)
Subdivide mesh _m _n times.