Debian Codegraph @

src/atlas/mesh/actions/ReorderHilbert.cc

raw
1 /*
2 * (C) Copyright 2013 ECMWF.
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 * In applying this licence, ECMWF does not waive the privileges and immunities
7 * granted to it by virtue of its status as an intergovernmental organisation
8 * nor does it submit to any jurisdiction.
9 */
10
11 #include <array>
12 #include <bitset>
13 #include <utility>
14 #include <vector>
15
16 #include "atlas/array.h"
17 #include "atlas/domain/Domain.h"
18 #include "atlas/grid/Grid.h"
19 #include "atlas/mesh/Elements.h"
20 #include "atlas/mesh/HybridElements.h"
21 #include "atlas/mesh/Mesh.h"
22 #include "atlas/mesh/Nodes.h"
23 #include "atlas/mesh/actions/ReorderHilbert.h"
24 #include "atlas/parallel/mpi/mpi.h"
25 #include "atlas/runtime/Exception.h"
26 #include "atlas/runtime/Log.h"
27 #include "atlas/runtime/Trace.h"
28 #include "atlas/util/CoordinateEnums.h"
29 #include "atlas/util/Point.h"
30
31 namespace atlas {
32 namespace mesh {
33 namespace actions {
34
35 // -------------------------------------------------------------------------------------
36
37 /// @brief Class to compute a global index given a coordinate, based on the
38 /// Hilbert Spacefilling Curve.
39 ///
40 /// This algorithm is based on:
41 /// - John J. Bartholdi and Paul Goldsman "Vertex-Labeling Algorithms for the Hilbert Spacefilling Curve"\n
42 /// It is adapted to return contiguous numbers of the gidx_t type, instead of a double [0,1]
43 ///
44 /// Given a bounding box and number of hilbert recursions, the bounding box can be divided in
45 /// 2^(dim*levels) equally spaced cells. A given coordinate falling inside one of these cells, is assigned
46 /// the 1-dimensional Hilbert-index of this cell. To make sure that 1 coordinate corresponds to only 1
47 /// Hilbert index, the number of levels have to be increased.
48 /// In 2D, the recursion cannot be higher than 15, if you want the indices to fit in "unsigned int" type of 32bit.
49 /// In 2D, the recursion cannot be higher than 30, if you want the indices to fit in "unsigned int" type of 64bit.
50 ///
51 ///
52 /// No attempt is made to provide the most efficient algorithm. There exist other open-source
53 /// libraries with more efficient algorithms, such as libhilbert, but its LGPL license
54 /// is not compatible with this licence.
55 ///
56 /// @author Willem Deconinck
57 class Hilbert {
58 public:
59 /// Constructor
60 /// Initializes the hilbert space filling curve with a given "space" and "levels"
61 Hilbert(const Domain& domain, idx_t levels);
62
63 /// Compute the hilbert code for a given point in 2D
64 gidx_t operator()(const PointXY& point);
65
66 /// Compute the hilbert code for a given point in 2D
67 /// @param [out] relative_tolerance cell-size of smallest level divided by bounding-box size
68 gidx_t operator()(const PointXY& point, double& relative_tolerance);
69
70 /// Return the maximum hilbert code possible with the initialized levels
71 ///
72 /// Care has to be taken that this number is not larger than the precision of the type storing
73 /// the hilbert codes.
74 gidx_t nb_keys() const { return nb_keys_; }
75
76 private: // functions
77 using box_t = std::array<PointXY, 4>;
78
79 /// @brief Recursive algorithm
80 gidx_t recursive_algorithm(const PointXY& p, const box_t& box, idx_t level);
81
82 private: // data
83 /// Vertex label type (4 vertices in 2D)
84 enum VertexLabel
85 {
86 A = 0,
87 B = 1,
88 C = 2,
89 D = 3
90 };
91
92 /// Bounding box, defining the space to be filled
93 const RectangularDomain domain_;
94
95 /// maximum recursion level of the Hilbert space filling curve
96 idx_t max_level_;
97
98 /// maximum number of unique codes, computed by max_level
99 gidx_t nb_keys_;
100 gidx_t nb_keys_2_;
101 };
102
103 // -------------------------------------------------------------------------------------
104
105 Hilbert::Hilbert(const Domain& domain, idx_t levels): domain_{domain}, max_level_(levels) {
106 nb_keys_2_ = gidx_t(std::pow(gidx_t(4), gidx_t(max_level_)));
107 nb_keys_ = nb_keys_2_ * 2;
108 }
109
110
111 gidx_t Hilbert::operator()(const PointXY& point) {
112 box_t box;
113 box[A] = {domain_.xmin(), domain_.ymax()};
114 box[B] = {domain_.xmin(), domain_.ymin()};
115 box[C] = {domain_.xmax(), domain_.ymin()};
116 box[D] = {domain_.xmax(), domain_.ymax()};
117 const double xmid = (domain_.xmin() + domain_.xmax()) * 0.5;
118 if (point.x() < xmid) {
119 box[C].x() = xmid;
120 box[D].x() = xmid;
121 return recursive_algorithm(point, box, 0);
122 }
123 else {
124 box[A].x() = xmid;
125 box[B].x() = xmid;
126 return recursive_algorithm(point, box, 0) + nb_keys_2_;
127 }
128 }
129
130 gidx_t Hilbert::recursive_algorithm(const PointXY& p, const box_t& box, idx_t level) {
131 if (level == max_level_) {
132 return 0;
133 }
134
135 double min_distance = std::numeric_limits<double>::max();
136
137 auto compute_distance2 = [](const PointXY& p1, const PointXY& p2) {
138 // workaround because of eckit 1.3.2 issue with constness in KPoint
139 double d = 0;
140 for (size_t i = 0; i < 2; i++) {
141 double dx = p1[i] - p2[i];
142 d += dx * dx;
143 }
144 return d;
145 };
146
147 auto compute_average = [](const PointXY& p1, const PointXY& p2) {
148 // workaround because of eckit 1.3.2 issue with constness in KPoint
149 PointXY avg;
150 avg.x() = p1.x() + p2.x();
151 avg.x() *= 0.5;
152 avg.y() = p1.y() + p2.y();
153 avg.y() *= 0.5;
154 return avg;
155 };
156
157 idx_t quadrant{0};
158 for (idx_t idx = 0; idx < 4; ++idx) {
159 // double distance = box[idx].distance2( p ); // does not compile with eckit 1.3.2
160 double distance = compute_distance2(p, box[idx]); // workaround
161 if (distance < min_distance) {
162 quadrant = idx;
163 min_distance = distance;
164 }
165 }
166
167 box_t box_quadrant;
168 switch (quadrant) {
169 case A:
170 box_quadrant[A] = box[A];
171 // box_quadrant[B] = ( box[A] + box[D] ) * 0.5; // does not compile with eckit 1.3.2
172 // box_quadrant[C] = ( box[A] + box[C] ) * 0.5; // does not compile with eckit 1.3.2
173 // box_quadrant[D] = ( box[A] + box[B] ) * 0.5; // does not compile with eckit 1.3.2
174 box_quadrant[B] = compute_average(box[A], box[D]); // workaround
175 box_quadrant[C] = compute_average(box[A], box[C]); // workaround
176 box_quadrant[D] = compute_average(box[A], box[B]); // workaround
177 break;
178 case B:
179 // box_quadrant[A] = ( box[B] + box[A] ) * 0.5; // does not compile with eckit 1.3.2
180 box_quadrant[B] = box[B];
181 // box_quadrant[C] = ( box[B] + box[C] ) * 0.5; // does not compile with eckit 1.3.2
182 // box_quadrant[D] = ( box[B] + box[D] ) * 0.5; // does not compile with eckit 1.3.2
183 box_quadrant[A] = compute_average(box[B], box[A]); // workaround
184 box_quadrant[C] = compute_average(box[B], box[C]); // workaround
185 box_quadrant[D] = compute_average(box[B], box[D]); // workaround
186 break;
187 case C:
188 // box_quadrant[A] = ( box[C] + box[A] ) * 0.5; // does not compile with eckit 1.3.2
189 // box_quadrant[B] = ( box[C] + box[B] ) * 0.5; // does not compile with eckit 1.3.2
190 box_quadrant[C] = box[C];
191 // box_quadrant[D] = ( box[C] + box[D] ) * 0.5; // does not compile with eckit 1.3.2
192 box_quadrant[A] = compute_average(box[C], box[A]); // workaround
193 box_quadrant[B] = compute_average(box[C], box[B]); // workaround
194 box_quadrant[D] = compute_average(box[C], box[D]); // workaround
195
196 break;
197 case D:
198 // box_quadrant[A] = ( box[D] + box[C] ) * 0.5; // does not compile with eckit 1.3.2
199 // box_quadrant[B] = ( box[D] + box[B] ) * 0.5; // does not compile with eckit 1.3.2
200 // box_quadrant[C] = ( box[D] + box[A] ) * 0.5; // does not compile with eckit 1.3.2
201 box_quadrant[D] = box[D];
202 box_quadrant[A] = compute_average(box[D], box[C]); // workaround
203 box_quadrant[B] = compute_average(box[D], box[B]); // workaround
204 box_quadrant[C] = compute_average(box[D], box[A]); // workaround
205
206 break;
207 }
208
209 // The key has 4 possible values per recursion (1 for each quadrant),
210 // which can be represented by 2 bits per recursion
211 // A --> 00
212 // B --> 01
213 // C --> 10
214 // D --> 11
215 // Trailing zero-bits are added depending on the level:
216 // level max_level_-1 --> none
217 // level max_level_-2 --> 00
218 // level max_level_-2 --> 0000
219 // level max_level_-3 --> 000000
220 gidx_t key = 0;
221 auto index = (max_level_ - level) * 2 - 1;
222 gidx_t mask;
223
224 // Create a mask value with all trailing bits for leftmost bit (of 2)
225 mask = gidx_t(1) << index;
226
227 // Add mask to key
228 if (quadrant == C || quadrant == D) {
229 key |= mask;
230 }
231
232 // Create a mask value with all trailing bits for rightmost bit (of 2)
233 mask = gidx_t(1) << (index - 1);
234
235 // Add mask to key
236 if (quadrant == B || quadrant == D) {
237 key |= mask;
238 }
239
240 return recursive_algorithm(p, box_quadrant, level + 1) + key;
241 }
242
243 // ------------------------------------------------------------------
244
245 ReorderHilbert::ReorderHilbert(const eckit::Parametrisation& config) {
246 config.get("recursion", recursion_);
247 config.get("ghost_at_end", ghost_at_end_);
248 }
249
250
251 Domain global_bounding_box(const Mesh& mesh) {
252 auto xy = array::make_view<double, 2>(mesh.nodes().xy());
253
254 double xmin = std::numeric_limits<double>::max();
255 double xmax = -std::numeric_limits<double>::max();
256 double ymin = std::numeric_limits<double>::max();
257 double ymax = -std::numeric_limits<double>::max();
258 for (idx_t i = 0; i < xy.shape(0); ++i) {
259 xmin = std::min(xmin, xy(i, XX));
260 xmax = std::max(xmax, xy(i, XX));
261 ymin = std::min(ymin, xy(i, YY));
262 ymax = std::max(ymax, xy(i, YY));
263 }
264 const auto& comm = atlas::mpi::comm();
265
266 comm.allReduceInPlace(xmin, eckit::mpi::min());
267 comm.allReduceInPlace(xmax, eckit::mpi::max());
268 comm.allReduceInPlace(ymin, eckit::mpi::min());
269 comm.allReduceInPlace(ymax, eckit::mpi::max());
270 return RectangularDomain({xmin, xmax}, {ymin, ymax});
271 }
272
273 std::vector<idx_t> ReorderHilbert::computeNodesOrder(Mesh& mesh) {
274 using hilbert_reordering_t = std::vector<std::pair<gidx_t, idx_t>>;
275
276 Hilbert hilbert{global_bounding_box(mesh), recursion_};
277
278 auto xy = array::make_view<double, 2>(mesh.nodes().xy());
279 auto ghost = array::make_view<int, 1>(mesh.nodes().ghost());
280
281 idx_t size = xy.shape(0);
282 hilbert_reordering_t hilbert_reordering;
283 hilbert_reordering.reserve(size);
284 ATLAS_TRACE_SCOPE("hilbert nodes") {
285 for (idx_t n = 0; n < size; ++n) {
286 PointXY p{xy(n, XX), xy(n, YY)};
287 if (not ghost(n)) {
288 hilbert_reordering.emplace_back(hilbert(p), n);
289 }
290 else {
291 if (ghost_at_end_) {
292 // ghost nodes get a fake "hilbert_idx" at the end
293 hilbert_reordering.emplace_back(hilbert.nb_keys() + n, n);
294 }
295 else {
296 hilbert_reordering.emplace_back(hilbert(p), n);
297 }
298 }
299 }
300 }
301
302 std::sort(hilbert_reordering.begin(), hilbert_reordering.end());
303 std::vector<idx_t> order;
304 order.reserve(size);
305 for (const auto& pair : hilbert_reordering) {
306 order.emplace_back(pair.second);
307 }
308 return order;
309 }
310
311
312 #if 0
313 // Reorder elements
314 if ( 0 ) {
315 hilbert_reordering_t hilbert_reordering;
316 std::vector<idx_t> order;
317 std::vector<idx_t> order_inverse;
318
319 auto cell_centres =
320 Field( "cell_centres", array::make_datatype<double>(), array::make_shape( mesh.cells().size(), 2 ) );
321 auto nodes_xy = array::make_view<double, 2>( mesh.nodes().xy() );
322 for ( idx_t t = 0; t < mesh.cells().nb_types(); ++t ) {
323 auto& cells = mesh.cells().elements( t );
324 auto xy = cells.view<double, 2>( cell_centres );
325 auto flags = cells.view<int, 1>( mesh.cells().flags() );
326 auto halo = cells.view<idx_t, 1>( mesh.cells().halo() );
327
328 // Compute cell-centres
329 {
330 const auto& node_connectivity = cells.node_connectivity();
331 const idx_t nb_nodes = cells.nb_nodes();
332 const double nb_nodes_double = nb_nodes;
333 for ( idx_t e = 0; e < cells.size(); ++e ) {
334 double x{0};
335 double y{0};
336 for ( idx_t c = 0; c < nb_nodes; ++c ) {
337 idx_t n = node_connectivity( e, c );
338 x += nodes_xy( n, XX );
339 y += nodes_xy( n, YY );
340 }
341 xy( e, XX ) = x / nb_nodes_double;
342 xy( e, YY ) = y / nb_nodes_double;
343 }
344 }
345
346
347 auto skip = [&]( idx_t n ) {
348 if ( halo( n ) || mesh::Nodes::Topology::check( flags( n ), mesh::Nodes::Topology::PATCH ) ) {
349 return true;
350 }
351 return false;
352 };
353 idx_t size = xy.shape( 0 );
354 hilbert_reordering.clear();
355 hilbert_reordering.reserve( size );
356 ATLAS_TRACE_SCOPE( "hilbert elements[" + std::to_string( t ) + "]" ) {
357 for ( idx_t n = 0; n < size; ++n ) {
358 PointXY p{xy( n, XX ), xy( n, YY )};
359 if ( not skip( n ) ) {
360 hilbert_reordering.emplace_back( hilbert( p ), n );
361 }
362 else { // halo elements get a fake "hilbert_idx" at the end
363 hilbert_reordering.emplace_back( hilbert.nb_keys() + n, n );
364 }
365 }
366 }
367 ATLAS_ASSERT( hilbert_reordering.size() == size );
368 std::sort( hilbert_reordering.begin(), hilbert_reordering.end() );
369 order.clear();
370 order.reserve( size );
371 order_inverse.resize( size );
372 idx_t c{0};
373 for ( const auto& pair : hilbert_reordering ) {
374 order.emplace_back( pair.second );
375 order_inverse[pair.second] = c++;
376 ATLAS_ASSERT( pair.second < size );
377 }
378
379 for ( idx_t ifield = 0; ifield < mesh.cells().nb_fields(); ++ifield ) {
380 reorder_field( mesh.cells().field( ifield ), order, cells.begin(), cells.end() );
381 }
382
383 reorder_connectivity( cells.node_connectivity(), order );
384 }
385 }
386 #endif
387
388 namespace {
389 static ReorderBuilder<ReorderHilbert> __ReorderHilbert("hilbert");
390 } // namespace
391
392
393 } // namespace actions
394 } // namespace mesh
395 } // namespace atlas