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 : #ifndef __H__REMESHING__SIMPLE_GRID_IMPL__
34 : #define __H__REMESHING__SIMPLE_GRID_IMPL__
35 :
36 : #include <queue>
37 : #include "lib_grid/algorithms/geom_obj_util/geom_obj_util.h"
38 : #include "lib_grid/algorithms/graph/graph.h"
39 :
40 : namespace ug
41 : {
42 : ////////////////////////////////////////////////////////////////////////
43 : // ObtainSimpleGrid
44 : template <class TPosAcc, class TIntAcc, class TNormAcc>
45 0 : bool ObtainSimpleGrid(SimpleGrid& sgOut, Grid& grid,
46 : Vertex* vrt1, Vertex* vrt2, size_t size,
47 : TPosAcc& aaPos, TNormAcc& aaNorm,
48 : TIntAcc& aaInt)
49 : {
50 : // vVrts will be reused in each call. To avoid unnecessary allocations,
51 : // we'll reuse this vector.
52 0 : static std::vector<Vertex*> vVrts;
53 : vVrts.clear();
54 :
55 : // clear the simple-grid
56 0 : sgOut.clear();
57 :
58 : // collect vertices and triangles
59 0 : grid.begin_marking();
60 :
61 : // mark the first two vertices and add them to simple-grid
62 0 : grid.mark(vrt1);
63 0 : grid.mark(vrt2);
64 0 : vVrts.push_back(vrt1);
65 0 : vVrts.push_back(vrt2);
66 0 : aaInt[vrt1] = 0;
67 0 : aaInt[vrt2] = 1;
68 :
69 : // this counter holds the next vertex for which we have to search for
70 : // associated triangles
71 : size_t nextVrt = 0;
72 : // this number holds the first index that is not checked for neighbours.
73 : size_t vrtsEnd = 2;
74 :
75 : // find the triangles that are adjacent to the edge between vrt1 and vrt2
76 : // at this point we assume that all associated faces are triangles.
77 : // If they are not they are simply treated as if they were some.
78 0 : Grid::AssociatedFaceIterator iterEnd = grid.associated_faces_end(vrt1);
79 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(vrt1);
80 0 : iter != iterEnd; ++iter)
81 : {
82 0 : Vertex* vUnmarked = NULL;
83 0 : Face* f = *iter;
84 : int counter = 0;
85 :
86 0 : for(uint j = 0; j < 3; ++j){
87 0 : if(grid.is_marked(f->vertex(j)))
88 0 : ++counter;
89 : else
90 0 : vUnmarked = f->vertex(j);
91 : }
92 :
93 0 : if(counter > 1){
94 : // we found an adjacent triangle. vUnmarked contains the connected vertex
95 0 : if(!vUnmarked) goto bail_out;
96 : // push the connected vertex to vVrts and assign the index
97 0 : aaInt[vUnmarked] = vVrts.size();
98 0 : vVrts.push_back(vUnmarked);
99 : // add the triangle
100 0 : sgOut.triangles.push_back(aaInt[f->vertex(0)]);
101 0 : sgOut.triangles.push_back(aaInt[f->vertex(1)]);
102 0 : sgOut.triangles.push_back(aaInt[f->vertex(2)]);
103 : // mark the face
104 : grid.mark(f);
105 : }
106 : }
107 :
108 : // mark the vertices in vVrts that are not yet marked
109 0 : for(size_t i = nextVrt; i < vVrts.size(); ++i)
110 0 : grid.mark(vVrts[i]);
111 :
112 : // collect all faces in the neighbourhood
113 0 : for(size_t i = 0; i < size; ++i)
114 : {
115 0 : for(; nextVrt < vrtsEnd; ++nextVrt)
116 : {
117 0 : Vertex* vrt = vVrts[nextVrt];
118 : // colelct neighbour faces
119 0 : Grid::AssociatedFaceIterator iterEnd = grid.associated_faces_end(vrt);
120 0 : for(Grid::AssociatedFaceIterator iter = grid.associated_faces_begin(vrt);
121 0 : iter != iterEnd; ++iter)
122 : {
123 0 : Face* f = *iter;
124 : // if f is unmarked
125 0 : if(!grid.is_marked(f)){
126 : // add unmarked vertices to vVrts
127 0 : for(uint j = 0; j < 3; ++j){
128 0 : if(!grid.is_marked(f->vertex(j))){
129 0 : aaInt[f->vertex(j)] = vVrts.size();
130 0 : grid.mark(f->vertex(j));
131 0 : vVrts.push_back(f->vertex(j));
132 : }
133 : }
134 :
135 : // add the triangle
136 : grid.mark(f);
137 0 : sgOut.triangles.push_back(aaInt[f->vertex(0)]);
138 0 : sgOut.triangles.push_back(aaInt[f->vertex(1)]);
139 0 : sgOut.triangles.push_back(aaInt[f->vertex(2)]);
140 : }
141 : }
142 : }
143 : // in the next iteration we'll check all vertices up to this point
144 : vrtsEnd = vVrts.size();
145 : }
146 :
147 : // copy the vertex-positions and the normals to the grid
148 0 : for(size_t i = 0; i < vVrts.size(); ++i)
149 : {
150 0 : sgOut.vertices.push_back(aaPos[vVrts[i]]);
151 0 : sgOut.vertexNormals.push_back(aaNorm[vVrts[i]]);
152 : }
153 :
154 : // calculate triangle normals
155 0 : CalculateTriangleNormals(sgOut);
156 :
157 0 : grid.end_marking();
158 : return true;
159 :
160 : bail_out:
161 0 : grid.end_marking();
162 : return false;
163 : }
164 :
165 : ////////////////////////////////////////////////////////////////////////
166 : // ObtainSimpleGrid
167 : template <class TPosAcc, class TIntAcc, class TNormAcc>
168 0 : bool ObtainSimpleGrid_CollapseEdge(SimpleGrid& sgOut, Grid& grid,
169 : Edge* e, size_t size,
170 : TPosAcc& aaPos, TNormAcc& aaNorm,
171 : TIntAcc& aaInt)
172 : {
173 : // clear the simple-grid
174 0 : sgOut.clear();
175 :
176 : // collect triangles in the neighbourhood of e.
177 : // Note that faces may (and most likely will) contain some faces twice
178 : std::vector<Face*> faces;
179 0 : CollectNeighborhood(faces, grid, e->vertex(0), size, false);
180 0 : CollectNeighborhood(faces, grid, e->vertex(1), size, false);
181 :
182 : // the first vertex resembles the collapsed edge
183 : typename TPosAcc::ValueType n;
184 0 : VecAdd(n, aaNorm[e->vertex(0)], aaNorm[e->vertex(1)]);
185 0 : VecNormalize(n, n);
186 0 : sgOut.vertices.push_back(CalculateCenter(e, aaPos));
187 0 : sgOut.vertexNormals.push_back(n);
188 :
189 : // now iterate over all associated triangles in the neighbourhood
190 : // of e and create associated triangles in sgOut.
191 0 : grid.begin_marking();
192 0 : for(size_t i_face = 0; i_face < faces.size(); ++i_face){
193 0 : Face* f = faces[i_face];
194 : // make sure that the face is a triangle
195 0 : if(f->num_vertices() != 3){
196 0 : grid.end_marking();
197 : return false;
198 : }
199 :
200 : // avoid multiple insertion of the same face
201 0 : if(!grid.is_marked(f)){
202 : grid.mark(f);
203 :
204 : // get vertex indices
205 : // make sure that the triangles adjacent to e will
206 : // not be added to the grid
207 : int ind[3];
208 : int edgeVrts = 0;// increase for each vertex that lies on e
209 :
210 0 : for(size_t i = 0; i < 3; ++i){
211 0 : Vertex* v = f->vertex(i);
212 0 : if((v == e->vertex(0)) || (v == e->vertex(1))){
213 0 : ind[i] = 0;
214 0 : edgeVrts++;
215 : }
216 : else{
217 : // get the index of v in sgOut.vertices.
218 : // If it hasn't got one, create one.
219 0 : if(!grid.is_marked(v)){
220 : // NOTE that we add the position even though it is not clear
221 : // whether the triangle will be created at all.
222 0 : sgOut.vertices.push_back(aaPos[v]);
223 0 : sgOut.vertexNormals.push_back(aaNorm[v]);
224 0 : aaInt[v] = (int)sgOut.vertices.size() - 1;
225 : grid.mark(v);
226 : }
227 0 : ind[i] = aaInt[v];
228 : }
229 : }
230 :
231 : // add the triangle
232 0 : if(edgeVrts < 2){
233 0 : sgOut.triangles.push_back(ind[0]);
234 0 : sgOut.triangles.push_back(ind[1]);
235 0 : sgOut.triangles.push_back(ind[2]);
236 : }
237 : }
238 : }
239 :
240 0 : grid.end_marking();
241 :
242 : // calculate triangle normals
243 0 : CalculateTriangleNormals(sgOut);
244 :
245 : return true;
246 0 : }
247 :
248 : }// end of namespace
249 :
250 : #endif
|
