Line data Source code
1 : /*
2 : * Copyright (c) 2010-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #include "neighborhood.h"
34 : #include "lib_grid/algorithms/geom_obj_util/vertex_util.h"
35 :
36 : using namespace std;
37 :
38 : namespace ug
39 : {
40 :
41 : ////////////////////////////////////////////////////////////////////////
42 : //
43 0 : void CollectNeighbors(std::vector<Vertex*>& vNeighborsOut,
44 : Grid& grid, Vertex* vrt, uint nbhType,
45 : Grid::edge_traits::callback considerEdge,
46 : Grid::face_traits::callback considerFace,
47 : Grid::volume_traits::callback considerVol)
48 : {
49 : // clear the container
50 : vNeighborsOut.clear();
51 :
52 : // begin marking
53 0 : grid.begin_marking();
54 :
55 : // mark vrt - this makes things easier
56 : grid.mark(vrt);
57 :
58 : // iterate through associated edges
59 0 : if(nbhType & NHT_EDGE_NEIGHBORS){
60 0 : Grid::AssociatedEdgeIterator iterEnd = grid.associated_edges_end(vrt);
61 0 : for(Grid::AssociatedEdgeIterator iter = grid.associated_edges_begin(vrt);
62 0 : iter != iterEnd; ++iter)
63 : {
64 0 : if(considerEdge(*iter)){
65 0 : Vertex* neighbour = GetConnectedVertex(*iter, vrt);
66 0 : if(!grid.is_marked(neighbour)){
67 : grid.mark(neighbour);
68 0 : vNeighborsOut.push_back(neighbour);
69 : }
70 : }
71 : }
72 : }
73 :
74 : // iterate through associated faces
75 0 : if(nbhType & NHT_FACE_NEIGHBORS){
76 0 : Grid::AssociatedFaceIterator iterEnd = grid.associated_faces_end(vrt);
77 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(vrt);
78 0 : iter != iterEnd; ++iter)
79 : {
80 0 : if(considerFace(*iter)){
81 0 : Face* f = *iter;
82 0 : size_t numVrts = f->num_vertices();
83 0 : Face::ConstVertexArray vrts = f->vertices();
84 0 : for(size_t i = 0; i < numVrts; ++i){
85 0 : Vertex* neighbour = vrts[i];
86 0 : if(!grid.is_marked(neighbour)){
87 : grid.mark(neighbour);
88 0 : vNeighborsOut.push_back(neighbour);
89 : }
90 : }
91 : }
92 : }
93 : }
94 :
95 : // iterate through associated volumes
96 0 : if(nbhType & NHT_VOLUME_NEIGHBORS){
97 0 : Grid::AssociatedVolumeIterator iterEnd = grid.associated_volumes_end(vrt);
98 0 : for(Grid::AssociatedVolumeIterator iter = grid.associated_volumes_begin(vrt);
99 0 : iter != iterEnd; ++iter)
100 : {
101 0 : if(considerVol(*iter)){
102 0 : Volume* v = *iter;
103 0 : size_t numVrts = v->num_vertices();
104 0 : Volume::ConstVertexArray vrts = v->vertices();
105 0 : for(size_t i = 0; i < numVrts; ++i){
106 0 : Vertex* neighbour = vrts[i];
107 0 : if(!grid.is_marked(neighbour)){
108 : grid.mark(neighbour);
109 0 : vNeighborsOut.push_back(neighbour);
110 : }
111 : }
112 : }
113 : }
114 : }
115 :
116 : // end marking
117 0 : grid.end_marking();
118 0 : }
119 :
120 : ////////////////////////////////////////////////////////////////////////
121 : // CollectNeighbors
122 0 : void CollectNeighbors(std::vector<Edge*>& vNeighborsOut, Edge* e,
123 : Grid& grid, NeighborhoodType nbhType)
124 : {
125 : // clear the container
126 : vNeighborsOut.clear();
127 :
128 : // default neighbourhood:
129 0 : if(nbhType == NHT_DEFAULT)
130 : nbhType = NHT_VERTEX_NEIGHBORS;
131 :
132 : // edges can only be vertex-neighbours
133 0 : if(nbhType != NHT_VERTEX_NEIGHBORS)
134 : return;
135 :
136 : // begin marking
137 0 : grid.begin_marking();
138 :
139 : // mark the edge
140 : grid.mark(e);
141 :
142 : // mark the vertices of the edge
143 0 : grid.mark(e->vertex(0));
144 0 : grid.mark(e->vertex(1));
145 :
146 : // iterate over all edges that are connected to the vertices.
147 : // if the edge is not yet marked, we have to push it to vNeighboursOut.
148 0 : for(uint i = 0; i < 2; ++i)
149 : {
150 0 : Grid::AssociatedEdgeIterator iterEnd = grid.associated_edges_end(e->vertex(i));
151 0 : for(Grid::AssociatedEdgeIterator iter = grid.associated_edges_begin(e->vertex(i));
152 0 : iter != iterEnd; ++iter)
153 : {
154 0 : if(!grid.is_marked(*iter))
155 : {
156 0 : vNeighborsOut.push_back(*iter);
157 0 : grid.mark(*iter);
158 : }
159 : }
160 : }
161 :
162 : // end marking
163 0 : grid.end_marking();
164 : }
165 :
166 :
167 : ////////////////////////////////////////////////////////////////////////
168 : // CollectNeighbors
169 0 : void CollectNeighbors(std::vector<Face*>& vNeighborsOut, Face* f,
170 : Grid& grid, NeighborhoodType nbhType)
171 : {
172 : // clear the container
173 : vNeighborsOut.clear();
174 :
175 : // default neighbourhood:
176 0 : if(nbhType == NHT_DEFAULT)
177 : nbhType = NHT_EDGE_NEIGHBORS;
178 :
179 : // faces can't be face-neighbours
180 0 : if(nbhType == NHT_FACE_NEIGHBORS)
181 : return;
182 :
183 : // begin marking
184 0 : grid.begin_marking();
185 :
186 : // mark the face
187 : grid.mark(f);
188 :
189 : // mark the vertices of the face
190 0 : uint numVrts = f->num_vertices();
191 0 : Face::ConstVertexArray vrts = f->vertices();
192 0 : for(uint i = 0; i < numVrts; ++i)
193 0 : grid.mark(vrts[i]);
194 :
195 : // in order to get the maximum speed-up, we'll try to use
196 : // associated elements in grid.
197 : if((nbhType == NHT_EDGE_NEIGHBORS)
198 0 : && grid.option_is_enabled(FACEOPT_STORE_ASSOCIATED_EDGES
199 : | EDGEOPT_STORE_ASSOCIATED_FACES
200 : | FACEOPT_AUTOGENERATE_EDGES))
201 : {
202 : // iterate through associated edges
203 0 : Grid::AssociatedEdgeIterator eEnd = grid.associated_edges_end(f);
204 0 : for(Grid::AssociatedEdgeIterator eIter = grid.associated_edges_begin(f);
205 0 : eIter != eEnd; ++eIter)
206 : {
207 : // iterate through associated folumes of the eace
208 0 : Grid::AssociatedFaceIterator fEnd = grid.associated_faces_end(*eIter);
209 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(*eIter);
210 0 : iter != fEnd; ++iter)
211 : {
212 : // if the face is not yet marked, then add it to the neighbours
213 0 : if(!grid.is_marked(*iter))
214 : {
215 : grid.mark(*iter);
216 0 : vNeighborsOut.push_back(*iter);
217 : }
218 : }
219 : }
220 : // we're done in here. end-marking and return.
221 0 : grid.end_marking();
222 : return;
223 : }
224 :
225 :
226 : // iterate over all faces that are connected to the vertices.
227 : // if the face shares the elements as required by nbhType and
228 : // it is not yet marked, we have to push it to vNeighboursOut.
229 : // to optimize speed we'll check both valid nbhTypes separately.
230 : // the first case indeed is a subcase of the second
231 : // (compare counted marked vertices against nbhType)
232 0 : switch(nbhType)
233 : {
234 : case NHT_VERTEX_NEIGHBORS:
235 0 : for(uint i = 0; i < numVrts; ++i)
236 : {
237 0 : Grid::AssociatedFaceIterator iterEnd = grid.associated_faces_end(vrts[i]);
238 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(vrts[i]);
239 0 : iter != iterEnd; ++iter)
240 : {
241 0 : if(!grid.is_marked(*iter))
242 : {
243 0 : vNeighborsOut.push_back(*iter);
244 0 : grid.mark(*iter);
245 : }
246 : }
247 : }
248 : break;
249 :
250 : case NHT_EDGE_NEIGHBORS:
251 0 : for(uint i = 0; i < numVrts; ++i)
252 : {
253 0 : Grid::AssociatedFaceIterator iterEnd = grid.associated_faces_end(vrts[i]);
254 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(vrts[i]);
255 0 : iter != iterEnd; ++iter)
256 : {
257 0 : Face* nf = *iter;
258 0 : if(!grid.is_marked(nf))
259 : {
260 : // count the marked vertices that are contained by *iter
261 : // if there are more than 1, the faces share an edge
262 : // (at least in a regular grid)
263 : int counter = 0;
264 :
265 0 : size_t numNVrts = nf->num_vertices();
266 0 : Face::ConstVertexArray nvrts = nf->vertices();
267 :
268 0 : for(uint j = 0; j < numNVrts; ++j)
269 : {
270 0 : if(grid.is_marked(nvrts[j]))
271 : {
272 0 : ++counter;
273 0 : if(counter > 1)
274 : {
275 0 : vNeighborsOut.push_back(nf);
276 : grid.mark(nf);
277 : break;
278 : }
279 : }
280 : }
281 : }
282 : }
283 : }
284 : break;
285 : default:
286 : break;
287 : }
288 :
289 : // end marking
290 0 : grid.end_marking();
291 : }
292 :
293 : ////////////////////////////////////////////////////////////////////////
294 : // CollectNeighbors
295 0 : void CollectNeighbors(std::vector<Volume*>& vNeighborsOut, Volume* v,
296 : Grid& grid, NeighborhoodType nbhType)
297 : {
298 : // clear the container
299 : vNeighborsOut.clear();
300 :
301 : // default neighbourhood:
302 0 : if(nbhType == NHT_DEFAULT)
303 : nbhType = NHT_FACE_NEIGHBORS;
304 :
305 : // begin marking
306 0 : grid.begin_marking();
307 :
308 : // mark the volume
309 : grid.mark(v);
310 :
311 : // mark the vertices of the volume
312 0 : uint numVrts = v->num_vertices();
313 0 : Volume::ConstVertexArray vrts = v->vertices();
314 0 : for(uint i = 0; i < numVrts; ++i)
315 0 : grid.mark(vrts[i]);
316 :
317 : // in order to get the maximum speed-up, we'll try to use
318 : // associated elements in grid.
319 : if((nbhType == NHT_FACE_NEIGHBORS)
320 0 : && grid.option_is_enabled(VOLOPT_STORE_ASSOCIATED_FACES
321 : | FACEOPT_STORE_ASSOCIATED_VOLUMES
322 : | VOLOPT_AUTOGENERATE_FACES))
323 : {
324 : // iterate through associated faces
325 0 : Grid::AssociatedFaceIterator fEnd = grid.associated_faces_end(v);
326 0 : for(Grid::AssociatedFaceIterator fIter = grid.associated_faces_begin(v);
327 0 : fIter != fEnd; ++fIter)
328 : {
329 : // iterate through associated volumes of the face
330 0 : Grid::AssociatedVolumeIterator vEnd = grid.associated_volumes_end(*fIter);
331 0 : for(Grid::AssociatedVolumeIterator iter = grid.associated_volumes_begin(*fIter);
332 0 : iter != vEnd; ++iter)
333 : {
334 : // if the volume is not yet marked, then add it to the neighbours
335 0 : if(!grid.is_marked(*iter))
336 : {
337 : grid.mark(*iter);
338 0 : vNeighborsOut.push_back(*iter);
339 : }
340 : }
341 : }
342 : // we're done in here. end-marking and return.
343 0 : grid.end_marking();
344 : return;
345 : }
346 :
347 : // iterate over all volumes that are connected to the vertices.
348 : // if the volume shares the elements as required by nbhType and
349 : // it is not yet marked, we have to push it to vNeighboursOut.
350 : // to optimize speed we'll check both valid nbhTypes separately.
351 : // the first case indeed is a subcase of the second
352 0 : if(nbhType & NHT_VERTEX_NEIGHBORS)
353 0 : for(uint i = 0; i < numVrts; ++i)
354 : {
355 0 : Grid::AssociatedVolumeIterator iterEnd = grid.associated_volumes_end(vrts[i]);
356 0 : for(Grid::AssociatedVolumeIterator iter = grid.associated_volumes_begin(vrts[i]);
357 0 : iter != iterEnd; ++iter)
358 : {
359 0 : if(!grid.is_marked(*iter))
360 : {
361 0 : vNeighborsOut.push_back(*iter);
362 0 : grid.mark(*iter);
363 : }
364 : }
365 : }
366 : else
367 : {
368 : // count the number of shared vertices with volumes, which are connected by
369 : // at least one vertex. This case handles both face and edge neighborhoods.
370 : int minNumSharedVrts = -1;
371 0 : if(nbhType & NHT_FACE_NEIGHBORS)
372 : minNumSharedVrts = 3;
373 0 : if(nbhType & NHT_EDGE_NEIGHBORS)
374 : minNumSharedVrts = 2;
375 :
376 0 : if(minNumSharedVrts > 0){
377 0 : for(uint i = 0; i < numVrts; ++i)
378 : {
379 0 : Grid::AssociatedVolumeIterator iterEnd = grid.associated_volumes_end(vrts[i]);
380 0 : for(Grid::AssociatedVolumeIterator iter = grid.associated_volumes_begin(vrts[i]);
381 0 : iter != iterEnd; ++iter)
382 : {
383 0 : Volume* nv = *iter;
384 0 : if(!grid.is_marked(nv))
385 : {
386 : // count the marked vertices that are contained by *iter
387 : // if there as many as in nbhTypes, the volume is a neighbour.
388 : // (at least in a regular grid)
389 : int counter = 0;
390 0 : size_t numNVrts = nv->num_vertices();
391 0 : Volume::ConstVertexArray nvrts = nv->vertices();
392 0 : for(uint j = 0; j < numNVrts; ++j)
393 : {
394 0 : if(grid.is_marked(nvrts[j]))
395 : {
396 0 : ++counter;
397 0 : if(counter >= minNumSharedVrts)
398 : {
399 0 : vNeighborsOut.push_back(nv);
400 : grid.mark(nv);
401 : break;
402 : }
403 : }
404 : }
405 : }
406 : }
407 : }
408 : }
409 : }
410 :
411 : // end marking
412 0 : grid.end_marking();
413 : }
414 :
415 0 : void CollectNeighborhood(std::vector<Face*>& facesOut, Grid& grid,
416 : Vertex* vrt, size_t range,
417 : bool clearContainer)
418 : {
419 0 : if(clearContainer)
420 : facesOut.clear();
421 :
422 : vector<Vertex*> candidates;
423 : size_t rangeBegin = 0;
424 : size_t rangeEnd = 1;
425 :
426 0 : candidates.push_back(vrt);
427 :
428 0 : grid.begin_marking();
429 0 : grid.mark(vrt);
430 :
431 : // we iterate over the range
432 0 : for(size_t i_range = 0; i_range < range; ++i_range){
433 : // iterate from candidatesStart to candidatesEnd
434 : // this is important, since we can make sure that only triangles
435 : // in the correct range are considered
436 0 : for(size_t i_vrt = rangeBegin; i_vrt < rangeEnd; ++i_vrt)
437 : {
438 0 : Vertex* v = candidates[i_vrt];
439 : // iterate over associated faces
440 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(v);
441 0 : iter != grid.associated_faces_end(v); ++iter)
442 : {
443 0 : Face* f = *iter;
444 0 : if(!grid.is_marked(f)){
445 : grid.mark(f);
446 0 : facesOut.push_back(f);
447 0 : size_t numVrts = f->num_vertices();
448 0 : Face::ConstVertexArray vrts = f->vertices();
449 0 : for(size_t i = 0; i < numVrts; ++i){
450 0 : if(!grid.is_marked(vrts[i])){
451 : grid.mark(vrts[i]);
452 0 : candidates.push_back(vrts[i]);
453 : }
454 : }
455 : }
456 : }
457 : }
458 :
459 : // prepare next iteration
460 : rangeBegin = rangeEnd;
461 : rangeEnd = candidates.size();
462 : }
463 :
464 0 : grid.end_marking();
465 0 : }
466 :
467 : }// end of namespace
|
