A.I.M.S algorithms


geodesic_mesh_elements.h
Go to the documentation of this file.
1 //Copyright (C) 2008 Danil Kirsanov, MIT License
2 #ifndef GEODESIC_MESH_ELEMENTS_20071231
3 #define GEODESIC_MESH_ELEMENTS_20071231
4 
5 // here we define the building elements of the mesh:
6 // 3D-points, vertices, edges, faces, and surface points
7 
8 #include <assert.h>
9 #include <cstddef>
10 
11 namespace geodesic{
12 
13 class Vertex;
14 class Edge;
15 class Face;
16 class Mesh;
18 
19 typedef Vertex* vertex_pointer;
20 typedef Edge* edge_pointer;
21 typedef Face* face_pointer;
22 typedef Mesh* mesh_pointer;
24 
25 template <class Data> //simple vector that stores info about mesh references
26 class SimpleVector //for efficiency, it uses an outside memory allocator
27 {
28 public:
30  m_size(0),
31  m_begin(NULL)
32  {};
33 
34  typedef Data* iterator;
35 
36  unsigned size(){return m_size;};
37  iterator begin(){return m_begin;};
38  iterator end(){return m_begin + m_size;};
39 
40  template<class DataPointer>
41  void set_allocation(DataPointer begin, unsigned size)
42  {
43  assert(begin != NULL || size == 0);
44  m_size = size;
45  m_begin = (iterator)begin;
46  }
47 
48  Data& operator[](unsigned i)
49  {
50  assert(i < m_size);
51  return *(m_begin + i);
52  }
53 
54  void clear()
55  {
56  m_size = 0;
57  m_begin = NULL;
58  }
59 
60 private:
61  unsigned m_size;
62  Data* m_begin;
63 };
64 
66 {
71 };
72 
73 class MeshElementBase //prototype of vertices, edges and faces
74 {
75 public:
79 
81  m_id(0),
83  {};
84 
88 
89  unsigned& id(){return m_id;};
90  PointType type(){return m_type;};
91 
92 protected:
93  vertex_pointer_vector m_adjacent_vertices; //list of the adjacent vertices
94  edge_pointer_vector m_adjacent_edges; //list of the adjacent edges
95  face_pointer_vector m_adjacent_faces; //list of the adjacent faces
96 
97  unsigned m_id; //unique id
98  PointType m_type; //vertex, edge or face
99 };
100 
101 class Point3D //point in 3D and corresponding operations
102 {
103 public:
104  Point3D(){};
106  {
107  x() = p->x();
108  y() = p->y();
109  z() = p->z();
110  };
111 
112  double* xyz(){return m_coordinates;};
113  double& x(){return *m_coordinates;};
114  double& y(){return *(m_coordinates+1);};
115  double& z(){return *(m_coordinates+2);};
116 
117  void set(double new_x, double new_y, double new_z)
118  {
119  x() = new_x;
120  y() = new_y;
121  z() = new_z;
122  }
123 
124  void set(double* data)
125  {
126  x() = *data;
127  y() = *(data+1);
128  z() = *(data+2);
129  }
130 
131  double distance(double* v)
132  {
133  double dx = m_coordinates[0] - v[0];
134  double dy = m_coordinates[1] - v[1];
135  double dz = m_coordinates[2] - v[2];
136 
137  return sqrt(dx*dx + dy*dy + dz*dz);
138  };
139 
140  double distance(Point3D* v)
141  {
142  return distance(v->xyz());
143  };
144 
145  void add(Point3D* v)
146  {
147  x() += v->x();
148  y() += v->y();
149  z() += v->z();
150  };
151 
152  void multiply(double v)
153  {
154  x() *= v;
155  y() *= v;
156  z() *= v;
157  };
158 
159 private:
160  double m_coordinates[3]; //xyz
161 };
162 
163 class Vertex: public MeshElementBase, public Point3D
164 {
165 public:
167  {
168  m_type = VERTEX;
169  };
170 
171  ~Vertex(){};
172 
173  bool& saddle_or_boundary(){return m_saddle_or_boundary;};
174 private:
175  //this flag speeds up exact geodesic algorithm
176  bool m_saddle_or_boundary; //it is true if total adjacent angle is larger than 2*PI or this vertex belongs to the mesh boundary
177 };
178 
179 
180 class Face: public MeshElementBase
181 {
182 public:
184  {
185  m_type = FACE;
186  };
187 
188  ~Face(){};
189 
193 
195  {
196  for(unsigned i=0; i<3; ++i)
197  {
198  if(adjacent_vertices()[i]->id() == v->id())
199  {
200  return m_corner_angles[i];
201  }
202  }
203  assert(0);
204  return 0;
205  }
206 
207  double* corner_angles(){return m_corner_angles;};
208 
209 private:
210  double m_corner_angles[3]; //triangle angles in radians; angles correspond to vertices in m_adjacent_vertices
211 };
212 
213 class Edge: public MeshElementBase
214 {
215 public:
217  {
218  m_type = EDGE;
219  };
220 
221  ~Edge(){};
222 
223  double& length(){return m_length;};
224 
226  {
227  if(adjacent_faces().size() == 1)
228  {
229  assert(adjacent_faces()[0]->id() == f->id());
230  return NULL;
231  }
232 
233  assert(adjacent_faces()[0]->id() == f->id() ||
234  adjacent_faces()[1]->id() == f->id());
235 
236  return adjacent_faces()[0]->id() == f->id() ?
237  adjacent_faces()[1] : adjacent_faces()[0];
238  };
239 
241  {
242  assert(belongs(v));
243 
244  return adjacent_vertices()[0]->id() == v->id() ?
246  };
247 
249  {
250  return adjacent_vertices()[0]->id() == v->id() ||
251  adjacent_vertices()[1]->id() == v->id();
252  }
253 
254  bool is_boundary(){return adjacent_faces().size() == 1;};
255 
258 
260  double& x,
261  double& y)
262  {
263  double d0 = point->distance(v0());
264  if(d0 < 1e-50)
265  {
266  x = 0.0;
267  y = 0.0;
268  return;
269  }
270 
271  double d1 = point->distance(v1());
272  if(d1 < 1e-50)
273  {
274  x = m_length;
275  y = 0.0;
276  return;
277  }
278 
279  x = m_length/2.0 + (d0*d0 - d1*d1)/(2.0*m_length);
280  y = sqrt(std::max(0.0, d0*d0 - x*x));
281  return;
282  }
283 
284 private:
285  double m_length; //length of the edge
286 };
287 
288 class SurfacePoint:public Point3D //point on the surface of the mesh
289 {
290 public:
292  m_p(NULL)
293  {};
294 
295  SurfacePoint(vertex_pointer v): //set the surface point in the vertex
296  SurfacePoint::Point3D(v),
297  m_p(v)
298  {};
299 
300  SurfacePoint(face_pointer f): //set the surface point in the center of the face
301  m_p(f)
302  {
303  set(0,0,0);
304  add(f->adjacent_vertices()[0]);
305  add(f->adjacent_vertices()[1]);
306  add(f->adjacent_vertices()[2]);
307  multiply(1./3.);
308  };
309 
310  SurfacePoint(edge_pointer e, //set the surface point in the middle of the edge
311  double a = 0.5):
312  m_p(e)
313  {
314  double b = 1 - a;
315 
316  vertex_pointer v0 = e->adjacent_vertices()[0];
317  vertex_pointer v1 = e->adjacent_vertices()[1];
318 
319  x() = b*v0->x() + a*v1->x();
320  y() = b*v0->y() + a*v1->y();
321  z() = b*v0->z() + a*v1->z();
322  };
323 
325  double x,
326  double y,
327  double z,
329  m_p(g)
330  {
331  set(x,y,z);
332  };
333 
334  void initialize(SurfacePoint const& p)
335  {
336  *this = p;
337  }
338 
340 
343 protected:
344  base_pointer m_p; //could be face, vertex or edge pointer
345 };
346 
348 {
349  for(unsigned i=0; i<3; ++i)
350  {
351  edge_pointer e = adjacent_edges()[i];
352  if(!e->belongs(v))
353  {
354  return e;
355  }
356  }
357  assert(0);
358  return NULL;
359 }
360 
362 {
363  for(unsigned i=0; i<3; ++i)
364  {
366  if(!e->belongs(v))
367  {
368  return v;
369  }
370  }
371  assert(0);
372  return NULL;
373 }
374 
376 {
377  assert(e->belongs(v));
378 
379  for(unsigned i=0; i<3; ++i)
380  {
381  edge_pointer next = adjacent_edges()[i];
382  if(e->id() != next->id() && next->belongs(v))
383  {
384  return next;
385  }
386  }
387  assert(0);
388  return NULL;
389 }
390 
391 struct HalfEdge //prototype of the edge; used for mesh construction
392 {
393  unsigned face_id;
394  unsigned vertex_0; //adjacent vertices sorted by id value
395  unsigned vertex_1; //they are sorted, vertex_0 < vertex_1
396 };
397 
398 inline bool operator < (const HalfEdge &x, const HalfEdge &y)
399 {
400  if(x.vertex_0 == y.vertex_0)
401  {
402  return x.vertex_1 < y.vertex_1;
403  }
404  else
405  {
406  return x.vertex_0 < y.vertex_0;
407  }
408 }
409 
410 inline bool operator != (const HalfEdge &x, const HalfEdge &y)
411 {
412  return x.vertex_0 != y.vertex_0 || x.vertex_1 != y.vertex_1;
413 }
414 
415 inline bool operator == (const HalfEdge &x, const HalfEdge &y)
416 {
417  return x.vertex_0 == y.vertex_0 && x.vertex_1 == y.vertex_1;
418 }
419 
420 } //geodesic
421 
422 #endif
void set(double *data)
float max(float x, float y)
Definition: thickness.h:97
face_pointer opposite_face(face_pointer f)
void local_coordinates(Point3D *point, double &x, double &y)
vertex_pointer_vector & adjacent_vertices()
edge_pointer_vector & adjacent_edges()
SurfacePoint(base_pointer g, double x, double y, double z, PointType t=UNDEFINED_POINT)
void set(double new_x, double new_y, double new_z)
void set_allocation(DataPointer begin, unsigned size)
edge_pointer_vector m_adjacent_edges
SimpleVector< face_pointer > face_pointer_vector
Vertex * vertex_pointer
vertex_pointer v0()
Data & operator[](unsigned i)
void initialize(SurfacePoint const &p)
bool operator==(const HalfEdge &x, const HalfEdge &y)
vertex_pointer_vector m_adjacent_vertices
double vertex_angle(vertex_pointer v)
face_pointer_vector m_adjacent_faces
vertex_pointer opposite_vertex(edge_pointer e)
SurfacePoint(edge_pointer e, double a=0.5)
SimpleVector< edge_pointer > edge_pointer_vector
bool operator<(const HalfEdge &x, const HalfEdge &y)
vertex_pointer v1()
edge_pointer opposite_edge(vertex_pointer v)
MeshElementBase * base_pointer
double distance(Point3D *v)
SimpleVector< vertex_pointer > vertex_pointer_vector
face_pointer_vector & adjacent_faces()
double distance(double *v)
vertex_pointer opposite_vertex(vertex_pointer v)
bool operator!=(const HalfEdge &x, const HalfEdge &y)
bool belongs(vertex_pointer v)
edge_pointer next_edge(edge_pointer e, vertex_pointer v)