1 #ifndef _REVOROPT_MESH_MEASURE_DEF_HPP_
2 #define _REVOROPT_MESH_MEASURE_DEF_HPP_
3
4 #include "measure_fwd.hpp"
5
6 #include <Revoropt/Tools/measure_def.hpp>
7 #include <Revoropt/Neighbours/neighbourhood_def.hpp>
8
9 #include <Eigen/Dense>
10
11 namespace Revoropt {
12
13 /*{{{ Area */
14
15 /* Area of a face of a mesh */
16 template<typename Mesh>
mesh_face_area(const Mesh * mesh,unsigned int face)17 typename Mesh::Scalar mesh_face_area(const Mesh* mesh, unsigned int face) {
18 //scalar type
19 typedef typename Mesh::Scalar Scalar ;
20
21 //result
22 double area = 0 ;
23
24 //iterate over the faces
25 unsigned int fsize = mesh->face_size(face) ;
26 const unsigned int* fverts = mesh->face(face) ;
27 for(unsigned int v = 1; v < fsize-1; ++v) {
28 area += triangle_area<Mesh::VertexDim,Scalar>(
29 mesh->vertex(fverts[0]),
30 mesh->vertex(fverts[v]),
31 mesh->vertex(fverts[v+1])
32 ) ;
33 }
34
35 return area ;
36 }
37
38 /* Area of a mesh */
39 template<typename Mesh>
mesh_area(const Mesh * mesh)40 typename Mesh::Scalar mesh_area(const Mesh* mesh) {
41 //scalar type
42 typedef typename Mesh::Scalar Scalar ;
43
44 //the area will be stored here
45 Scalar area = 0 ;
46
47 //iterate over the faces
48 for(unsigned int face = 0; face < mesh->faces_size(); ++face) {
49 area += mesh_face_area(mesh, face) ;
50 }
51
52 return area ;
53 }
54
55 //}}}
56
57 /*{{{ Edge length */
58
59 template< typename Mesh >
edge_length_from_vertices(const Mesh * mesh,unsigned int v0,unsigned int v1)60 typename Mesh::Scalar edge_length_from_vertices( const Mesh* mesh,
61 unsigned int v0,
62 unsigned int v1
63 ) {
64 //scalar type
65 typedef typename Mesh::Scalar Scalar ;
66 //vector type
67 typedef Eigen::Matrix<Scalar,Mesh::VertexDim,1> Vector ;
68 //vertex positions
69 Eigen::Map<const Vector> v0_pos(mesh->vertex(v0)) ;
70 Eigen::Map<const Vector> v1_pos(mesh->vertex(v1)) ;
71 //length
72 return (v1_pos-v0_pos).norm() ;
73 }
74
75 template< typename Mesh >
edge_length_from_face_index(const Mesh * mesh,unsigned int face,unsigned int edge)76 typename Mesh::Scalar edge_length_from_face_index( const Mesh* mesh,
77 unsigned int face,
78 unsigned int edge
79 ) {
80 //edge vertex indices
81 const unsigned int v0 = mesh->face_edge_start_vertex(face, edge) ;
82 const unsigned int v1 = mesh->face_edge_end_vertex(face, edge) ;
83 return edge_length_from_vertices(mesh,v0,v1) ;
84 }
85
86 /* Longest edge of a face */
87
88 template< typename Mesh >
face_longest_edge(const Mesh * mesh,unsigned int face,typename Mesh::Scalar * output_length)89 unsigned int face_longest_edge( const Mesh* mesh,
90 unsigned int face,
91 typename Mesh::Scalar* output_length
92 ) {
93 //scalar type
94 typedef typename Mesh::Scalar Scalar ;
95 //size of the face
96 const unsigned int face_size = mesh->face_size(face) ;
97 //initialization
98 unsigned int longest_edge = 0 ;
99 Scalar longest_length = 0 ;
100 //iterate over the edges
101 for(unsigned int edge = 0; edge < face_size; ++edge) {
102 //length
103 Scalar length = edge_length_from_face_index(mesh, face, edge) ;
104 //update
105 if(length == longest_length) {
106 //decide depending on edge vertices in lexicographic order
107 const unsigned int v0 = mesh->face_edge_start_vertex(face, edge) ;
108 const unsigned int v1 = mesh->face_edge_end_vertex(face, edge) ;
109 const unsigned int v2 = mesh->face_edge_start_vertex(face, longest_edge) ;
110 const unsigned int v3 = mesh->face_edge_end_vertex(face, longest_edge) ;
111 const unsigned int v0_min = v0 < v1 ? v0 : v1 ;
112 const unsigned int v0_max = v0 < v1 ? v1 : v0 ;
113 const unsigned int v1_min = v2 < v3 ? v2 : v3 ;
114 const unsigned int v1_max = v2 < v3 ? v3 : v2 ;
115 if(v0_max == v1_max) {
116 if(v0_min > v1_min) {
117 longest_edge = edge ;
118 longest_length = length ;
119 }
120 } else if(v0_max > v1_max){
121 longest_edge = edge ;
122 longest_length = length ;
123 }
124
125 } else if(length > longest_length) {
126 longest_edge = edge ;
127 longest_length = length ;
128 }
129 }
130 //result
131 if(output_length != NULL) {
132 *output_length = longest_length ;
133 }
134 return longest_edge ;
135 }
136
137 /* Longest edge of a mesh */
138 template< typename Mesh >
mesh_longest_edge_vertices(const Mesh * mesh,unsigned int * v0,unsigned int * v1,typename Mesh::Scalar * output_length)139 void mesh_longest_edge_vertices( const Mesh* mesh,
140 unsigned int* v0,
141 unsigned int* v1,
142 typename Mesh::Scalar* output_length
143 ) {
144 //scalar type
145 typedef typename Mesh::Scalar Scalar ;
146 //initialization
147 unsigned int longest_face = 0 ;
148 unsigned int longest_edge = 0 ;
149 Scalar longest_length = 0 ;
150 //variables to store edges and lengths
151 unsigned int edge ;
152 Scalar length ;
153 for(unsigned int face = 0; face < mesh->faces_size(); ++face) {
154 //longest edge of the face
155 edge = face_longest_edge(mesh, face, &length) ;
156 if(length > longest_length) {
157 longest_face = face ;
158 longest_edge = edge ;
159 longest_length = length ;
160 }
161 }
162 //result
163 if(output_length != NULL) {
164 *output_length = longest_length ;
165 }
166 return mesh->face_edge_vertices(longest_face,longest_edge,v0,v1) ;
167 }
168
169 //}}}
170
171 /*{{{ Angles */
172
173 template<typename Mesh>
face_angle_cos(const Mesh * mesh,unsigned int face,unsigned int vertex)174 typename Mesh::Scalar face_angle_cos( const Mesh* mesh,
175 unsigned int face,
176 unsigned int vertex
177 ) {
178 //size of the face
179 const unsigned int fsize = mesh->face_size(face) ;
180 //vertices of the face
181 const unsigned int* fverts = mesh->face(face) ;
182 //previous and next vertex
183 const unsigned int prev = fverts[(vertex+fsize-1) % fsize] ;
184 const unsigned int next = fverts[(vertex +1) % fsize] ;
185 //angle cosine
186 return angle_cos<Mesh::VertexDim>( mesh->vertex(vertex),
187 mesh->vertex(prev),
188 mesh->vertex(next)
189 ) ;
190 }
191
192 //}}}
193
194 /*{{{ Normalization */
195
196 template<typename Mesh>
normalize_mesh(Mesh * mesh,double * out_center,double * out_scale)197 void normalize_mesh( Mesh* mesh, double* out_center, double* out_scale ) {
198 //typedefs
199 typedef typename Mesh::Scalar Scalar ;
200 typedef Eigen::Matrix<Scalar,Mesh::VertexDim,1> Vector ;
201 //compute the new center
202 Vector center = Vector::Zero() ;
203 for(unsigned int i=0; i<mesh->vertices_size(); ++i) {
204 Eigen::Map<const Vector> x(mesh->vertex(i)) ;
205 center += x ;
206 }
207 center /= mesh->vertices_size() ;
208
209 if(out_center) {
210 for(int i = 0; i < 3; ++i) {
211 out_center[i] = center[i] ;
212 }
213 }
214
215 //center the mesh
216 for(unsigned int i=0; i<mesh->vertices_size(); ++i) {
217 Eigen::Map<Vector> x(mesh->vertex(i)) ;
218 x -= center ;
219 }
220
221 //compute the scene radius
222 Scalar radius = 0 ;
223 for(unsigned int i=0; i<mesh->vertices_size(); ++i) {
224 Eigen::Map<const Vector> x(mesh->vertex(i)) ;
225 radius = std::max(radius,(center - x).norm()) ;
226 }
227
228 //scale the mesh
229 for(unsigned int i=0; i<mesh->vertices_size(); ++i) {
230 Eigen::Map<Vector> x(mesh->vertex(i)) ;
231 x /= radius ;
232 }
233
234 if(out_scale) {
235 *out_scale = radius ;
236 }
237
238 mesh->set_dirty() ;
239 }
240
241 //}}}
242
243 /*{{{ Distance to a mesh */
244
245 /* Action passed to a neighbourhood computer to compute normals */
246 template<typename Triangulation>
247 class NeighDistanceCompute {
248
249 public :
250
251 //scalar type, dimension and vector
252 typedef typename Triangulation::Scalar Scalar ;
253 enum { Dim = Triangulation::VertexDim } ;
254 typedef Eigen::Matrix<Scalar,Dim,1> Vector ;
255
NeighDistanceCompute(const Triangulation * mesh,const Scalar * queries,const unsigned int * indices,Scalar * output,bool translate_queries=true)256 NeighDistanceCompute( const Triangulation* mesh,
257 const Scalar* queries,
258 const unsigned int* indices,
259 Scalar* output,
260 bool translate_queries = true
261 ) : mesh_(mesh),
262 queries_(queries),
263 indices_(indices),
264 output_(output),
265 translate_queries_(translate_queries) {} ;
266
NeighDistanceCompute(const Triangulation * mesh,const Scalar * queries,Scalar * output)267 NeighDistanceCompute( const Triangulation* mesh,
268 const Scalar* queries,
269 Scalar* output
270 ) : mesh_(mesh),
271 queries_(queries),
272 indices_(NULL),
273 output_(output),
274 translate_queries_(false) {} ;
275
operator ()(unsigned int query,unsigned int triangle)276 void operator()( unsigned int query,
277 unsigned int triangle
278 ) {
279 //position of the query
280 const unsigned int q_in_index =
281 translate_queries_ ? indices_[query] : query ;
282 const Scalar* qp = queries_ +Dim*q_in_index ;
283 Eigen::Map<const Vector> qv(qp) ;
284
285 //vertices of the triangle
286 const unsigned int* tverts = mesh_->face(triangle) ;
287 Eigen::Map<const Vector> x0(mesh_->vertex(tverts[0])) ;
288 Eigen::Map<const Vector> x1(mesh_->vertex(tverts[1])) ;
289 Eigen::Map<const Vector> x2(mesh_->vertex(tverts[2])) ;
290
291 //distance of the query to the triangle
292 Scalar uv[2] ;
293 point_in_triangle<Dim, Scalar>( qp, x0.data(), x1.data(), x2.data(), uv ) ;
294 const Scalar distance = (uv[0]*x0+uv[1]*x1+(1-uv[0]-uv[1])*x2 - qv).norm() ;
295
296 //assign the minimum distance
297 const unsigned int q_out_index =
298 indices_ == NULL ? query : indices_[query] ;
299 output_[q_out_index] =
300 distance < output_[q_out_index] ? distance : output_[q_out_index] ;
301 }
302
303 private :
304
305 const Triangulation* mesh_ ;
306 const Scalar* queries_ ;
307 const unsigned int* indices_ ;
308 bool translate_queries_ ;
309 Scalar* output_ ;
310
311 } ;
312
313 template<typename Mesh>
mesh_distances(const Mesh * mesh,typename Mesh::Scalar * queries,unsigned int queries_size,typename Mesh::Scalar radius,typename Mesh::Scalar * output)314 void mesh_distances( const Mesh* mesh,
315 typename Mesh::Scalar* queries,
316 unsigned int queries_size,
317 typename Mesh::Scalar radius,
318 typename Mesh::Scalar* output
319 ) {
320 //typedefs
321 enum { Dim = Mesh::VertexDim, Offset = Mesh::VertexOffset } ;
322 typedef typename Mesh::Scalar Scalar ;
323 typedef ROMesh<3, Dim, Scalar, Offset> Triangulation ;
324
325 //initialize the distance array
326 for(unsigned int i = 0; i < queries_size; ++i) {
327 output[i] = 2*radius ;
328 }
329
330 //wrap the mesh as a triangle mesh
331 ROTriangulationWrapper<Dim, Scalar, Offset> trimesh(mesh) ;
332
333 //use the neighbourhoods of the queries
334 NeighbourhoodComputer<Triangulation> n_computer(
335 &trimesh, queries, queries_size
336 ) ;
337 NeighDistanceCompute<Triangulation> action(&trimesh, queries, output) ;
338 n_computer.compute(radius, action) ;
339 }
340
341 //}}}
342
343 /**{{{ Gradient of the mesh area wrt. its vertices **/
344
345 template<typename Triangulation>
mesh_area_gradient(const Triangulation * mesh,double * output,double factor)346 void mesh_area_gradient(
347 const Triangulation* mesh,
348 double* output,
349 double factor
350 ) {
351 typedef typename Triangulation::Scalar Scalar ;
352 enum { Dim = Triangulation::VertexDim } ;
353 typedef Eigen::Matrix<Scalar, Dim, 1> Vector ;
354
355 for(unsigned int f = 0; f < mesh->faces_size(); ++f) {
356 //flag for degenerate triangle
357 bool degenerate = false ;
358 //vertices of the triangle
359 const unsigned int* fverts = mesh->face(f) ;
360
361 //edges of the triangle
362 Vector edges[3] ;
363 Scalar e_len[3] ;
364 for(unsigned int v = 0; v < 3; ++v) {
365 Eigen::Map<const Vector> x0(mesh->vertex(fverts[v])) ;
366 Eigen::Map<const Vector> x1(mesh->vertex(fverts[(v+1)%3])) ;
367 edges[v] = x1 - x0 ;
368 e_len[v] = edges[v].norm() ;
369 degenerate |= (e_len[v] == 0) ;
370 if(degenerate) break ;
371 }
372 if(degenerate) continue ;
373
374 //heights of the triangle
375 Vector heights[3] ;
376 Scalar h_len[3] ;
377 for(unsigned int v = 0; v < 3; ++v) {
378 const Scalar& base_len = e_len[(v+1)%3] ;
379 const Vector& base = edges[(v+1)%3] ;
380 heights[v] = edges[(v+2)%3]
381 - edges[(v+2)%3].dot(base) * base / (base_len*base_len) ;
382 h_len[v] = heights[v].norm() ;
383 degenerate |= (h_len[v] == 0) ;
384 if(degenerate) break ;
385 }
386 if(degenerate) continue ;
387
388 //fill the gradient for the appropriate variables
389 for(unsigned int v = 0; v < 3; ++v) {
390 Eigen::Map<Vector> g(output + Dim*fverts[v]) ;
391 g += factor * 0.5 * e_len[(v+1)%3] * heights[v] / h_len[v] ;
392 }
393
394 }
395
396 }
397
398 //}}}
399
400 } //end of namespace Revoropt
401
402 #endif
403