A.I.M.S algorithms


geodesic_algorithm_subdivision.h
Go to the documentation of this file.
1 //Copyright (C) 2008 Danil Kirsanov, MIT License
2 #ifndef GEODESIC_ALGORITHM_SUBDIVISION_122806
3 #define GEODESIC_ALGORITHM_SUBDIVISION_122806
4 
7 #include <vector>
8 #include <set>
9 #include <assert.h>
10 
11 namespace geodesic{
12 
14 {
16 public:
18 
19  template <class Pointer>
20  SubdivisionNode(Pointer p):
21  SurfacePoint(p),
22  m_previous(NULL),
23  m_distance(0.0)
24  {};
25 
26  template <class Pointer, class Parameter>
27  SubdivisionNode(Pointer p, Parameter param):
28  SurfacePoint(p, param),
29  m_previous(NULL),
30  m_distance(0.0)
31  {};
32 
34 
35  double& distance_from_source(){return m_distance;};
36  node_pointer& previous(){return m_previous;};
37  unsigned& source_index(){return m_source_index;};
38 
39  void clear()
40  {
41  m_distance = GEODESIC_INF;
42  m_previous = NULL;
43  }
44 
45  bool operator()(node_pointer const s1, node_pointer const s2) const
46  {
47  if(s1 == s2)
48  {
49  return false;
50  }
52  {
53  return s1->distance_from_source() < s2->distance_from_source();
54  }
55 /* if(s1->type() != s2->type())
56  {
57  return s1->type() < s2->type();
58  }
59  if(s1->base_element()->id() != s2->base_element()->id())
60  {
61  return s1->base_element()->id() < s2->base_element()->id();
62  } */
63  if(s1->x() != s2->x()) //two nodes cannot be located in the same space
64  {
65  return s1->x() < s2->x();
66  }
67  if(s1->y() != s2->y())
68  {
69  return s1->y() < s2->y();
70  }
71  if(s1->z() != s2->z())
72  {
73  return s1->z() < s2->z();
74  }
75 
76  assert(0);
77  return true;
78  };
79 
80  SurfacePoint& surface_point(){return static_cast<SurfacePoint&>(*this);};
81 
82 private:
83  double m_distance; //distance to the closest source
84  unsigned m_source_index; //closest source index
85  node_pointer m_previous; //previous node in the geodesic path
86 };
87 
89 {
90  typedef SubdivisionNode Node;
91 public:
93  unsigned subdivision_level = 0):
95  {
97 
98  m_nodes.reserve(mesh->vertices().size());
99  for(unsigned i=0; i<mesh->vertices().size(); ++i)
100  {
101  vertex_pointer v = &mesh->vertices()[i];
102  m_nodes.push_back(Node(v));
103  }
104 
106  };
107 
109 
110  unsigned subdivision_level(){return m_subdivision_level;};
111 
113  {
114  m_subdivision_level = subdivision_level;
115 
116  m_nodes.resize(m_mesh->vertices().size());
117  m_nodes.reserve(m_mesh->vertices().size() +
118  m_mesh->edges().size()*subdivision_level);
119 
120  for(unsigned i=0; i<m_mesh->edges().size(); ++i)
121  {
122  edge_pointer e = &m_mesh->edges()[i];
123  for(unsigned i=0; i<subdivision_level; ++i)
124  {
125  double offset = (double)(i+1)/(double)(subdivision_level+1);
126  m_nodes.push_back(Node(e, offset));
127  }
128  }
129  };
130 
131 protected:
133  std::vector<node_pointer>& storage); //list all nodes that belong to this mesh element
134 
135  void list_nodes_visible_from_node(node_pointer node, //list all nodes that belong to this mesh element
136  std::vector<node_pointer>& storage,
137  std::vector<double>& distances,
138  double threshold_distance); //list only the nodes whose current distance is larger than the threshold
139 
141  {
142  return e->id()*m_subdivision_level + m_mesh->vertices().size();
143  };
144 
145 private:
146  void list_nodes(MeshElementBase* p, //list nodes that belong to this mesh element
147  std::vector<node_pointer>& storage,
148  double threshold_distance = -1.0); //list only the nodes whose current distance is larger than the threshold
149 
150  unsigned m_subdivision_level; //when level is equal to 1, this algorithm corresponds to the Dijkstra algorithm
151 };
152 
153 inline void GeodesicAlgorithmSubdivision::list_nodes(MeshElementBase* p,
154  std::vector<node_pointer>& storage,
155  double threshold_distance)
156 {
157  assert(p->type() != UNDEFINED_POINT);
158 
159  if(p->type() == VERTEX)
160  {
161  vertex_pointer v = static_cast<vertex_pointer>(p);
162  node_pointer node = &m_nodes[node_index(v)];
163  if(node->distance_from_source() > threshold_distance)
164  {
165  storage.push_back(node);
166  }
167  }
168  else if(p->type() == EDGE)
169  {
170  edge_pointer e = static_cast<edge_pointer>(p);
171  unsigned node_index = node_indexx(e);
172  for(unsigned i=0; i<m_subdivision_level; ++i)
173  {
174  node_pointer node = &m_nodes[node_index++];
175  if(node->distance_from_source() > threshold_distance)
176  {
177  storage.push_back(node);
178  }
179  }
180  }
181  //FACE has no nodes
182 }
183 
185  std::vector<node_pointer>& storage)
186 {
187  assert(p->type() != UNDEFINED_POINT);
188 
189  if(p->type() == FACE)
190  {
191  face_pointer f = static_cast<face_pointer>(p);
192  for(unsigned i=0; i<3; ++i)
193  {
194  list_nodes(f->adjacent_vertices()[i],storage);
195  list_nodes(f->adjacent_edges()[i],storage);
196  }
197  }
198  else if(p->type() == EDGE)
199  {
200  list_nodes(p,storage);
201  list_nodes(p->adjacent_vertices()[0],storage);
202  list_nodes(p->adjacent_vertices()[1],storage);
203  }
204  else //VERTEX
205  {
206  list_nodes(p,storage);
207  }
208 }
209 
210 void GeodesicAlgorithmSubdivision::list_nodes_visible_from_node(node_pointer node, //list all nodes that belong to this mesh element
211  std::vector<node_pointer>& storage,
212  std::vector<double>& distances,
213  double threshold_distance)
214 {
215  MeshElementBase* p = node->base_element();
216  assert(p->type() != UNDEFINED_POINT);
217  assert(storage.size() == distances.size());
218 
219  if(p->type() == VERTEX)
220  {
221  vertex_pointer v = static_cast<vertex_pointer>(p);
222 
223  for(unsigned i=0; i<v->adjacent_edges().size(); ++i)
224  {
225  edge_pointer e = v->adjacent_edges()[i];
226  vertex_pointer v_opposite = e->opposite_vertex(v);
227  list_nodes(e, storage, threshold_distance);
228  list_nodes(v_opposite, storage, threshold_distance);
229  }
230  for(unsigned i=0; i<v->adjacent_faces().size(); ++i)
231  {
232  face_pointer f = v->adjacent_faces()[i];
233  edge_pointer e = f->opposite_edge(v);
234  list_nodes(e, storage, threshold_distance);
235  }
236  }
237  else if(p->type() == EDGE)
238  {
239  edge_pointer e = static_cast<edge_pointer>(p);
240 
241  vertex_pointer v0 = e->adjacent_vertices()[0];
242  vertex_pointer v1 = e->adjacent_vertices()[1];
243  list_nodes(v0, storage, threshold_distance);
244  list_nodes(v1, storage, threshold_distance);
245 
246  for(unsigned i=0; i<e->adjacent_faces().size(); ++i)
247  {
248  face_pointer f = e->adjacent_faces()[i];
249 
250  list_nodes(f->next_edge(e,v0), storage, threshold_distance);
251  list_nodes(f->next_edge(e,v1), storage, threshold_distance);
252  list_nodes(f->opposite_vertex(e), storage, threshold_distance);
253  }
254  }
255  else
256  {
257  assert(0);
258  }
259 
260  unsigned index = distances.size();
261  distances.resize(storage.size());
262  for(; index<storage.size(); ++index)
263  {
264  distances[index] = node->distance(&storage[index]->surface_point());
265  }
266 }
267 
268 } //geodesic
269 
270 #endif //GEODESIC_ALGORITHM_SUBDIVISION_122806
void set_subdivision_level(unsigned subdivision_level)
void list_nodes_visible_from_node(node_pointer node, std::vector< node_pointer > &storage, std::vector< double > &distances, double threshold_distance)
vertex_pointer_vector & adjacent_vertices()
edge_pointer_vector & adjacent_edges()
std::vector< Edge > & edges()
Definition: geodesic_mesh.h:44
bool operator()(node_pointer const s1, node_pointer const s2) const
SubdivisionNode(Pointer p, Parameter param)
void list_nodes_visible_from_source(MeshElementBase *p, std::vector< node_pointer > &storage)
Vertex * vertex_pointer
std::vector< Vertex > & vertices()
Definition: geodesic_mesh.h:43
GeodesicAlgorithmSubdivision(geodesic::Mesh *mesh=NULL, unsigned subdivision_level=0)
vertex_pointer opposite_vertex(edge_pointer e)
edge_pointer opposite_edge(vertex_pointer v)
face_pointer_vector & adjacent_faces()
double distance(double *v)
vertex_pointer opposite_vertex(vertex_pointer v)
edge_pointer next_edge(edge_pointer e, vertex_pointer v)