Debian Codegraph @

src/atlas/interpolation/method/unstructured/UnstructuredBilinearLonLat.cc

raw
1 /*
2 * (C) Crown Copyright 2021 Met Office
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 */
7
8 #include <cmath>
9 #include <iomanip>
10 #include <limits>
11
12 #include "UnstructuredBilinearLonLat.h"
13
14 #include "eckit/log/Plural.h"
15 #include "eckit/log/ProgressTimer.h"
16 #include "eckit/log/Seconds.h"
17
18 #include "atlas/functionspace/NodeColumns.h"
19 #include "atlas/functionspace/PointCloud.h"
20 #include "atlas/grid.h"
21 #include "atlas/interpolation/element/Quad2D.h"
22 #include "atlas/interpolation/element/Triag2D.h"
23 #include "atlas/interpolation/method/MethodFactory.h"
24 #include "atlas/interpolation/method/Ray.h"
25 #include "atlas/linalg/sparse/MakeEckitSparseMatrix.h"
26 #include "atlas/mesh/ElementType.h"
27 #include "atlas/mesh/Nodes.h"
28 #include "atlas/mesh/actions/BuildCellCentres.h"
29 #include "atlas/mesh/actions/BuildXYZField.h"
30 #include "atlas/meshgenerator.h"
31 #include "atlas/parallel/GatherScatter.h"
32 #include "atlas/parallel/mpi/Buffer.h"
33 #include "atlas/parallel/mpi/mpi.h"
34 #include "atlas/parallel/omp/omp.h"
35 #include "atlas/runtime/Exception.h"
36 #include "atlas/runtime/Log.h"
37 #include "atlas/runtime/Trace.h"
38 #include "atlas/util/CoordinateEnums.h"
39 #include "atlas/util/Earth.h"
40 #include "atlas/util/Point.h"
41
42
43 namespace atlas {
44 namespace interpolation {
45 namespace method {
46
47 namespace {
48
49 MethodBuilder<UnstructuredBilinearLonLat> __builder_2("unstructured-bilinear-lonlat");
50
51 // epsilon used to scale edge tolerance when projecting ray to intesect element
52 static const double parametricEpsilon = 1e-15;
53
54 } // namespace
55
56
57 void UnstructuredBilinearLonLat::do_setup(const Grid& source, const Grid& target, const Cache& cache) {
58 allow_halo_exchange_ = false;
59 // no halo_exchange because we don't have any halo with delaunay or 3d structured meshgenerator
60
61 if (interpolation::MatrixCache(cache)) {
62 setMatrix(cache);
63 ATLAS_ASSERT(matrix().rows() == target.size());
64 ATLAS_ASSERT(matrix().cols() == source.size());
65 return;
66 }
67 if (mpi::size() > 1) {
68 ATLAS_NOTIMPLEMENTED;
69 }
70 auto make_nodecolumns = [](const Grid& grid) {
71 Mesh mesh;
72 if (StructuredGrid{grid}) {
73 mesh = MeshGenerator("structured", util::Config("3d", true)).generate(grid);
74 }
75 else {
76 mesh = MeshGenerator("delaunay").generate(grid);
77 }
78 return functionspace::NodeColumns(mesh);
79 };
80
81 do_setup(make_nodecolumns(source), functionspace::PointCloud{target});
82 }
83
84 void UnstructuredBilinearLonLat::do_setup(const FunctionSpace& source, const FunctionSpace& target, const Cache& cache) {
85 allow_halo_exchange_ = false;
86 // no halo_exchange because we don't have any halo with delaunay or 3d structured meshgenerator
87 if (interpolation::MatrixCache(cache)) {
88 setMatrix(cache);
89 source_ = source;
90 target_ = target;
91 ATLAS_ASSERT(matrix().rows() == target.size());
92 ATLAS_ASSERT(matrix().cols() == source.size());
93 return;
94 }
95 do_setup(source, target);
96 }
97
98 void UnstructuredBilinearLonLat::do_setup(const FunctionSpace& source, const FunctionSpace& target) {
99 ATLAS_TRACE("atlas::interpolation::method::BilinearRemapping::do_setup()");
100
101 source_ = source;
102 target_ = target;
103
104 ATLAS_TRACE_SCOPE("Setup target") {
105
106 auto create_xyz = [](Field lonlat_field) {
107 auto xyz_field = Field("xyz", array::make_datatype<double>(), array::make_shape(lonlat_field.shape(0), 3));
108 auto lonlat = array::make_view<double, 2>(lonlat_field);
109 auto xyz = array::make_view<double, 2>(xyz_field);
110 PointXYZ p2;
111 for (idx_t n = 0; n < lonlat.shape(0); ++n) {
112 const PointLonLat p1(lonlat(n, 0), lonlat(n, 1));
113 util::Earth::convertSphericalToCartesian(p1, p2);
114 xyz(n, 0) = p2.x();
115 xyz(n, 1) = p2.y();
116 xyz(n, 2) = p2.z();
117 }
118 return xyz_field;
119 };
120
121 target_ghost_ = target.ghost();
122 target_lonlat_ = target.lonlat();
123 if (functionspace::NodeColumns tgt = target) {
124 auto meshTarget = tgt.mesh();
125 target_xyz_ = mesh::actions::BuildXYZField("xyz")(meshTarget);
126 }
127 else {
128 target_xyz_ = create_xyz(target_lonlat_);
129 }
130 }
131
132 setup(source);
133 }
134
135 struct Stencil {
136 enum
137 {
138 max_stencil_size = 4
139 };
140 };
141
142 void UnstructuredBilinearLonLat::print(std::ostream& out) const {
143 functionspace::NodeColumns src(source_);
144 functionspace::NodeColumns tgt(target_);
145 out << "atlas::interpolation::method::BilinearRemapping{" << std::endl;
146 out << "treat_failure_as_missing_value: " << treat_failure_as_missing_value_;
147 if (not tgt) {
148 out << "}" << std::endl;
149 return;
150 }
151 out << ", NodeColumns to NodeColumns stencil weights: " << std::endl;
152 auto gidx_src = array::make_view<gidx_t, 1>(src.nodes().global_index());
153
154 ATLAS_ASSERT(tgt.nodes().size() == idx_t(matrix().rows()));
155
156
157 auto field_stencil_points_loc = tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size));
158 auto field_stencil_weights_loc = tgt.createField<double>(option::variables(Stencil::max_stencil_size));
159 auto field_stencil_size_loc = tgt.createField<int>();
160
161 auto stencil_points_loc = array::make_view<gidx_t, 2>(field_stencil_points_loc);
162 auto stencil_weights_loc = array::make_view<double, 2>(field_stencil_weights_loc);
163 auto stencil_size_loc = array::make_view<idx_t, 1>(field_stencil_size_loc);
164 stencil_size_loc.assign(0);
165
166 const auto m = atlas::linalg::make_non_owning_eckit_sparse_matrix(matrix());
167 for (auto it = m.begin(); it != m.end(); ++it) {
168 idx_t p = idx_t(it.row());
169 idx_t& i = stencil_size_loc(p);
170 stencil_points_loc(p, i) = gidx_src(it.col());
171 stencil_weights_loc(p, i) = *it;
172 ++i;
173 }
174
175
176 gidx_t global_size = tgt.gather().glb_dof();
177
178 auto field_stencil_points_glb =
179 tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size) | option::global(0));
180 auto field_stencil_weights_glb =
181 tgt.createField<double>(option::variables(Stencil::max_stencil_size) | option::global(0));
182 auto field_stencil_size_glb = tgt.createField<idx_t>(option::global(0));
183
184
185 auto stencil_points_glb = array::make_view<gidx_t, 2>(field_stencil_points_glb);
186 auto stencil_weights_glb = array::make_view<double, 2>(field_stencil_weights_glb);
187 auto stencil_size_glb = array::make_view<idx_t, 1>(field_stencil_size_glb);
188
189 tgt.gather().gather(stencil_size_loc, stencil_size_glb);
190 tgt.gather().gather(stencil_points_loc, stencil_points_glb);
191 tgt.gather().gather(stencil_weights_loc, stencil_weights_glb);
192
193 int precision = std::numeric_limits<double>::max_digits10;
194 for (idx_t i = 0; i < global_size; ++i) {
195 out << std::setw(10) << i + 1 << " : ";
196 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
197 out << std::setw(10) << stencil_points_glb(i, j);
198 }
199 for (idx_t j = stencil_size_glb(i); j < Stencil::max_stencil_size; ++j) {
200 out << " ";
201 }
202 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
203 out << std::setw(precision + 5) << std::left << std::setprecision(precision) << stencil_weights_glb(i, j);
204 }
205 out << std::endl;
206 }
207 out << "}" << std::endl;
208 }
209
210 void UnstructuredBilinearLonLat::setup(const FunctionSpace& source) {
211 const functionspace::NodeColumns src = source;
212 ATLAS_ASSERT(src);
213
214 Mesh meshSource = src.mesh();
215
216
217 auto trace_setup_source = atlas::Trace{Here(), "Setup source"};
218
219 if (target_lonlat_.shape(0) == 0) {
220 // return early if no output points on this partition reserve is called on
221 // the triplets but also during the sparseMatrix constructor. This won't
222 // work for empty matrices
223 return;
224 }
225
226 // 3D point coordinates
227 Field source_xyz = mesh::actions::BuildXYZField("xyz")(meshSource);
228
229 // generate barycenters of each triangle & insert them on a kd-tree
230 util::Config config;
231 config.set("name", "centre ");
232 config.set("flatten_virtual_elements", false);
233 Field cell_centres = mesh::actions::BuildCellCentres(config)(meshSource);
234
235 std::unique_ptr<ElemIndex3> eTree(create_element_kdtree(meshSource, cell_centres));
236
237 trace_setup_source.stop();
238
239 ilonlat_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(meshSource.nodes().lonlat())));
240 olonlat_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(target_lonlat_)));
241 oxyz_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(target_xyz_)));
242 igidx_.reset(new array::ArrayView<gidx_t, 1>(array::make_view<gidx_t, 1>(src.nodes().global_index())));
243 connectivity_ = &meshSource.cells().node_connectivity();
244 const mesh::Nodes& i_nodes = meshSource.nodes();
245
246
247 idx_t inp_npts = i_nodes.size();
248 idx_t out_npts = olonlat_->shape(0);
249
250 array::ArrayView<int, 1> out_ghosts = array::make_view<int, 1>(target_ghost_);
251
252 // weights -- one per vertex of element, triangles (3) or quads (4)
253
254 Triplets weights_triplets; // structure to fill-in sparse matrix
255 weights_triplets.resize(out_npts * 4); // preallocate space
256 auto insert_triplets = [&weights_triplets](idx_t n, const Triplets& triplets) -> bool {
257 if (triplets.size()) {
258 std::copy(triplets.begin(), triplets.end(), weights_triplets.begin()+4*n);
259 return true;
260 }
261 return false;
262 };
263
264 auto target_point = [this](idx_t ip) {
265 return PointXYZ{(*oxyz_)(ip, 0), (*oxyz_)(ip, 1), (*oxyz_)(ip, 2)};
266 };
267 auto find_k_nearest_element_candidates = [&eTree](const PointXYZ& p, size_t k) {
268 return eTree->kNearestNeighbours(p, k);
269 };
270 auto try_interpolate_with_element_candidates = [&insert_triplets, this](idx_t n, const ElemIndex3::NodeList& element_candidates) -> bool {
271 if (element_candidates.empty()) {
272 return false;
273 }
274 return insert_triplets(n, projectPointToElements(n, element_candidates));
275 };
276
277 // search nearest k cell centres
278
279 std::vector<idx_t> failures;
280
281 ATLAS_TRACE_SCOPE("Computing interpolation matrix") {
282 std::unique_ptr<eckit::ProgressTimer> progress;
283 if (atlas_omp_get_max_threads() == 1) {
284 progress.reset(new eckit::ProgressTimer{"Computing interpolation weights", static_cast<size_t>(out_npts), "point", double(5), Log::debug()});
285 }
286 atlas_omp_parallel_for (idx_t ip = 0; ip < out_npts; ++ip) {
287 if (out_ghosts(ip)) {
288 continue;
289 }
290
291 auto p = target_point(ip);
292 bool success = try_interpolate_with_element_candidates(ip, find_k_nearest_element_candidates(p, 8));
293
294 if (!success) {
295 atlas_omp_critical {
296 failures.emplace_back(ip);
297 }
298 }
299 }
300 }
301
302 if (failures.size()) {
303 if (treat_failure_as_missing_value_) {
304 missing_.resize(failures.size());
305 std::copy(std::begin(failures), std::end(failures), missing_.begin());
306 }
307 else {
308 // If this fails, consider lowering atlas::grid::parametricEpsilon
309 std::ostringstream msg;
310 msg << "Rank " << mpi::rank() << " failed to project points:\n";
311 for (auto i : failures) {
312 const PointLonLat pll{(*olonlat_)(i, LON), (*olonlat_)(i, LAT)}; // lookup point
313 msg << "\t(lon,lat) = " << pll << "\n";
314 }
315
316 Log::error() << msg.str() << std::endl;
317 throw_Exception(msg.str());
318 }
319 }
320
321 // fill sparse matrix and return
322 setMatrix(out_npts, inp_npts, weights_triplets);
323 }
324
325 Method::Triplets UnstructuredBilinearLonLat::projectPointToElements(size_t ip, const ElemIndex3::NodeList& elems) const {
326 ATLAS_ASSERT(elems.begin() != elems.end());
327
328 const size_t inp_points = ilonlat_->shape(0);
329 std::array<size_t, 4> idx;
330 std::array<double, 4> w;
331 std::array<double, 4> inv_dist_w;
332
333 Triplets triplets;
334 triplets.reserve(4);
335
336 double o_lon{(*olonlat_)(ip, LON)};
337 while (o_lon >= 360.0) {
338 o_lon -= 360.0;
339 }
340 while (o_lon < 0.0) {
341 o_lon += 360.0;
342 }
343 PointLonLat o_loc{o_lon, (*olonlat_)(ip, LAT)}; // lookup point
344
345 auto inv_dist_weight_quad = [](element::Quad2D& q, const PointXY& loc, std::array<double, 4>& w) {
346 double d[4];
347 d[0] = util::Earth::distance({q.p(0).data()}, loc);
348 d[1] = util::Earth::distance({q.p(1).data()}, loc);
349 d[2] = util::Earth::distance({q.p(2).data()}, loc);
350 d[3] = util::Earth::distance({q.p(3).data()}, loc);
351 w[0] = d[1] * d[2] * d[3];
352 w[1] = d[0] * d[2] * d[3];
353 w[2] = d[1] * d[0] * d[3];
354 w[3] = d[1] * d[0] * d[2];
355
356 double suminv = 1. / (w[0] + w[1] + w[2] + w[3]);
357 for (size_t i = 0; i < 4; ++i) {
358 w[i] *= suminv;
359 }
360 };
361 auto inv_dist_weight_triag = [](element::Triag2D& q, const PointXY& loc, std::array<double, 4>& w) {
362 double d[3];
363 d[0] = util::Earth::distance({q.p(0).data()}, loc);
364 d[1] = util::Earth::distance({q.p(1).data()}, loc);
365 d[2] = util::Earth::distance({q.p(2).data()}, loc);
366 w[0] = d[1] * d[2];
367 w[1] = d[0] * d[2];
368 w[2] = d[1] * d[0];
369 w[3] = 0.;
370
371 double suminv = 1. / (w[0] + w[1] + w[2]);
372 for (size_t i = 0; i < 3; ++i) {
373 w[i] *= suminv;
374 }
375 };
376
377
378 for (ElemIndex3::NodeList::const_iterator itc = elems.begin(); itc != elems.end(); ++itc) {
379 const idx_t elem_id = idx_t((*itc).value().payload());
380 ATLAS_ASSERT(elem_id < connectivity_->rows());
381
382 const idx_t nb_cols = connectivity_->cols(elem_id);
383 ATLAS_ASSERT(nb_cols == 3 || nb_cols == 4);
384
385 for (idx_t i = 0; i < nb_cols; ++i) {
386 idx[i] = (*connectivity_)(elem_id, i);
387 ATLAS_ASSERT(idx[i] < inp_points);
388 }
389
390 if (nb_cols == 3) {
391 /* triangle */
392 element::Triag2D triag(PointLonLat{(*ilonlat_)(idx[0], LON), (*ilonlat_)(idx[0], LAT)},
393 PointLonLat{(*ilonlat_)(idx[1], LON), (*ilonlat_)(idx[1], LAT)},
394 PointLonLat{(*ilonlat_)(idx[2], LON), (*ilonlat_)(idx[2], LAT)});
395
396 if (itc == elems.begin()) {
397 inv_dist_weight_triag(triag, o_loc, inv_dist_w);
398 }
399
400 // pick an epsilon based on a characteristic length (sqrt(area))
401 // (this scales linearly so it better compares with linear weights u,v,w)
402 const double edgeEpsilon = parametricEpsilon * std::sqrt(triag.area());
403 ATLAS_ASSERT(edgeEpsilon >= 0);
404
405 Intersect is = triag.intersects(o_loc, edgeEpsilon);
406
407 if (is) {
408 // weights are the linear Lagrange function evaluated at u,v (aka
409 // barycentric coordinates)
410 w[0] = 1. - is.u - is.v;
411 w[1] = is.u;
412 w[2] = is.v;
413
414 for (size_t i = 0; i < 3; ++i) {
415 triplets.emplace_back(ip, idx[i], w[i]);
416 }
417
418 break; // stop looking for elements
419 }
420 }
421 else {
422 /* quadrilateral */
423 double lons[4];
424 lons[0] = (*ilonlat_)(idx[0], LON);
425 lons[1] = (*ilonlat_)(idx[1], LON);
426 lons[2] = (*ilonlat_)(idx[2], LON);
427 lons[3] = (*ilonlat_)(idx[3], LON);
428 // adjust quadrilaterals to lie within [0,360]
429 for (idx_t i = 0; i < 4; ++i) {
430 while (lons[i] > 360.0) {
431 lons[i] -= 360.0;
432 }
433 while (lons[i] < 0.0) {
434 lons[i] += 360.0;
435 }
436 }
437 // shift cells on the east-west periodic boundary from the east to the west
438 // so that the quad surrounds a point with output longitude in [0,360)
439 double minlon = std::numeric_limits<double>::max();
440 for ( int i = 0; i < 4; i++ ) {
441 minlon = std::min( minlon, lons[i] );
442 }
443 for ( int i = 0; i < 4; i++ ) {
444 if ( (lons[i] - minlon) > 180 ) {
445 lons[i] -= 360;
446 }
447 }
448
449 element::Quad2D quad(
450 PointLonLat{lons[0], (*ilonlat_)(idx[0], LAT)}, PointLonLat{lons[1], (*ilonlat_)(idx[1], LAT)},
451 PointLonLat{lons[2], (*ilonlat_)(idx[2], LAT)}, PointLonLat{lons[3], (*ilonlat_)(idx[3], LAT)});
452
453 ATLAS_ASSERT( quad.validate() );
454
455 if (itc == elems.begin()) {
456 inv_dist_weight_quad(quad, o_loc, inv_dist_w);
457 }
458
459 // pick an epsilon based on a characteristic length (sqrt(area))
460 // (this scales linearly so it better compares with linear weights u,v,w)
461 const double edgeEpsilon = parametricEpsilon * std::sqrt(quad.area());
462 ATLAS_ASSERT(edgeEpsilon >= 0);
463
464 Intersect is = quad.localRemap(o_loc, edgeEpsilon);
465
466 if (!is) {
467 // repeat the calculation to catch points which are near the east boundary of the grid.
468 is = quad.localRemap({o_lon - 360, (*olonlat_)(ip, LAT)}, edgeEpsilon);
469 }
470
471 if (is) {
472 // weights are the bilinear Lagrange function evaluated at u,v
473 w[0] = (1. - is.u) * (1. - is.v);
474 w[1] = is.u * (1. - is.v);
475 w[2] = is.u * is.v;
476 w[3] = (1. - is.u) * is.v;
477 for (size_t i = 0; i < 4; ++i) {
478 triplets.emplace_back(ip, idx[i], w[i]);
479 }
480 break; // stop looking for elements
481 }
482 }
483 } // loop over nearest elements
484
485 if (triplets.empty()) {
486 // Crude inverse distance weighting to catch cells that are difficult
487 // to identify and interpolate in a lon/lat projection, near the north
488 // pole
489 const idx_t elem_id = idx_t((*elems.begin()).value().payload());
490 for (size_t i = 0; i < connectivity_->cols(elem_id); ++i) {
491 idx[i] = (*connectivity_)(elem_id, i);
492 triplets.emplace_back(ip, idx[i], inv_dist_w[i]);
493 }
494 }
495
496 if (!triplets.empty()) {
497 normalise(triplets);
498 }
499 return triplets;
500 }
501
502 } // namespace method
503 } // namespace interpolation
504 } // namespace atlas