Debian Codegraph @

src/atlas/interpolation/method/unstructured/SphericalMeanValue.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. and Interpolation
9 */
10
11 #include <cmath>
12 #include <iomanip>
13 #include <limits>
14
15 #include "SphericalMeanValue.h"
16
17 #include "eckit/log/Plural.h"
18 #include "eckit/log/ProgressTimer.h"
19 #include "eckit/log/Seconds.h"
20
21 #include "atlas/functionspace/NodeColumns.h"
22 #include "atlas/functionspace/PointCloud.h"
23 #include "atlas/grid.h"
24 #include "atlas/interpolation/element/Quad3D.h"
25 #include "atlas/interpolation/element/Triag3D.h"
26 #include "atlas/interpolation/method/MethodFactory.h"
27 #include "atlas/interpolation/method/Ray.h"
28 #include "atlas/linalg/sparse/MakeEckitSparseMatrix.h"
29 #include "atlas/mesh/ElementType.h"
30 #include "atlas/mesh/Nodes.h"
31 #include "atlas/mesh/actions/BuildCellCentres.h"
32 #include "atlas/mesh/actions/BuildXYZField.h"
33 #include "atlas/meshgenerator.h"
34 #include "atlas/parallel/GatherScatter.h"
35 #include "atlas/parallel/mpi/Buffer.h"
36 #include "atlas/parallel/mpi/mpi.h"
37 #include "atlas/parallel/omp/omp.h"
38 #include "atlas/runtime/Exception.h"
39 #include "atlas/runtime/Log.h"
40 #include "atlas/runtime/Trace.h"
41 #include "atlas/util/ConvexSphericalPolygon.h"
42 #include "atlas/util/CoordinateEnums.h"
43 #include "atlas/util/Earth.h"
44 #include "atlas/util/Point.h"
45
46
47 namespace atlas {
48 namespace interpolation {
49 namespace method {
50
51 namespace {
52 MethodBuilder<SphericalMeanValue> __builder("spherical-mean-value");
53 } // namespace
54
55 void SphericalMeanValue::do_setup(const Grid& source, const Grid& target, const Cache& cache) {
56 allow_halo_exchange_ = false;
57 // no halo_exchange because we don't have any halo with delaunay or 3d structured meshgenerator
58
59 if (interpolation::MatrixCache(cache)) {
60 setMatrix(cache);
61 ATLAS_ASSERT(matrix().rows() == target.size());
62 ATLAS_ASSERT(matrix().cols() == source.size());
63 return;
64 }
65 if (mpi::size() > 1) {
66 ATLAS_NOTIMPLEMENTED;
67 }
68 auto make_nodecolumns = [](const Grid& grid) {
69 Mesh mesh;
70 if (StructuredGrid{grid}) {
71 mesh = MeshGenerator("structured", util::Config("3d", true)).generate(grid);
72 }
73 else {
74 mesh = MeshGenerator("delaunay").generate(grid);
75 }
76 return functionspace::NodeColumns(mesh);
77 };
78
79 do_setup(make_nodecolumns(source), functionspace::PointCloud{target});
80 }
81
82 void SphericalMeanValue::do_setup(const FunctionSpace& source, const FunctionSpace& target, const Cache& cache) {
83 if (interpolation::MatrixCache(cache)) {
84 setMatrix(cache);
85 source_ = source;
86 target_ = target;
87 ATLAS_ASSERT(matrix().rows() == target.size());
88 ATLAS_ASSERT(matrix().cols() == source.size());
89 return;
90 }
91 do_setup(source, target);
92 }
93
94 void SphericalMeanValue::do_setup(const FunctionSpace& source, const FunctionSpace& target) {
95 ATLAS_TRACE("atlas::interpolation::method::FiniteElement::do_setup()");
96
97 source_ = source;
98 target_ = target;
99
100 ATLAS_TRACE_SCOPE("Setup target") {
101 auto create_xyz = [](Field lonlat_field) {
102 auto xyz_field = Field("xyz", array::make_datatype<double>(), array::make_shape(lonlat_field.shape(0), 3));
103 auto lonlat = array::make_view<double, 2>(lonlat_field);
104 auto xyz = array::make_view<double, 2>(xyz_field);
105 PointXYZ p2;
106 for (idx_t n = 0; n < lonlat.shape(0); ++n) {
107 const PointLonLat p1(lonlat(n, 0), lonlat(n, 1));
108 util::Earth::convertSphericalToCartesian(p1, p2);
109 xyz(n, 0) = p2.x();
110 xyz(n, 1) = p2.y();
111 xyz(n, 2) = p2.z();
112 }
113 return xyz_field;
114 };
115
116 target_ghost_ = target.ghost();
117 target_lonlat_ = target.lonlat();
118 if (functionspace::NodeColumns tgt = target) {
119 auto meshTarget = tgt.mesh();
120 target_xyz_ = mesh::actions::BuildXYZField("xyz")(meshTarget);
121 }
122 else {
123 target_xyz_ = create_xyz(target_lonlat_);
124 }
125 }
126
127 setup(source);
128 }
129
130 struct Stencil {
131 enum
132 {
133 max_stencil_size = 4
134 };
135 };
136
137 void SphericalMeanValue::print(std::ostream& out) const {
138 functionspace::NodeColumns src(source_);
139 functionspace::NodeColumns tgt(target_);
140 out << "atlas::interpolation::method::FiniteElement{" << std::endl;
141 out << "max_fraction_elems_to_try: " << max_fraction_elems_to_try_;
142 out << ", treat_failure_as_missing_value: " << treat_failure_as_missing_value_;
143 if (not tgt) {
144 out << "}" << std::endl;
145 return;
146 }
147 out << ", NodeColumns to NodeColumns stencil weights: " << std::endl;
148 auto gidx_src = array::make_view<gidx_t, 1>(src.nodes().global_index());
149
150 ATLAS_ASSERT(tgt.nodes().size() == idx_t(matrix().rows()));
151
152
153 auto field_stencil_points_loc = tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size));
154 auto field_stencil_weights_loc = tgt.createField<double>(option::variables(Stencil::max_stencil_size));
155 auto field_stencil_size_loc = tgt.createField<int>();
156
157 auto stencil_points_loc = array::make_view<gidx_t, 2>(field_stencil_points_loc);
158 auto stencil_weights_loc = array::make_view<double, 2>(field_stencil_weights_loc);
159 auto stencil_size_loc = array::make_view<idx_t, 1>(field_stencil_size_loc);
160 stencil_size_loc.assign(0);
161
162 const auto m = atlas::linalg::make_non_owning_eckit_sparse_matrix(matrix());
163 for (auto it = m.begin(); it != m.end(); ++it) {
164 idx_t p = idx_t(it.row());
165 idx_t& i = stencil_size_loc(p);
166 stencil_points_loc(p, i) = gidx_src(it.col());
167 stencil_weights_loc(p, i) = *it;
168 ++i;
169 }
170
171 gidx_t global_size = tgt.gather().glb_dof();
172
173 auto field_stencil_points_glb =
174 tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size) | option::global(0));
175 auto field_stencil_weights_glb =
176 tgt.createField<double>(option::variables(Stencil::max_stencil_size) | option::global(0));
177 auto field_stencil_size_glb = tgt.createField<idx_t>(option::global(0));
178
179
180 auto stencil_points_glb = array::make_view<gidx_t, 2>(field_stencil_points_glb);
181 auto stencil_weights_glb = array::make_view<double, 2>(field_stencil_weights_glb);
182 auto stencil_size_glb = array::make_view<idx_t, 1>(field_stencil_size_glb);
183
184 tgt.gather().gather(stencil_size_loc, stencil_size_glb);
185 tgt.gather().gather(stencil_points_loc, stencil_points_glb);
186 tgt.gather().gather(stencil_weights_loc, stencil_weights_glb);
187
188 int precision = std::numeric_limits<double>::max_digits10;
189 for (idx_t i = 0; i < global_size; ++i) {
190 out << std::setw(10) << i + 1 << " : ";
191 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
192 out << std::setw(10) << stencil_points_glb(i, j);
193 }
194 for (idx_t j = stencil_size_glb(i); j < Stencil::max_stencil_size; ++j) {
195 out << " ";
196 }
197 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
198 out << std::setw(precision + 5) << std::left << std::setprecision(precision) << stencil_weights_glb(i, j);
199 }
200 out << std::endl;
201 }
202 out << "}" << std::endl;
203 }
204
205 void SphericalMeanValue::setup(const FunctionSpace& source) {
206 const functionspace::NodeColumns src = source;
207 ATLAS_ASSERT(src);
208
209 ocoords_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(target_xyz_)));
210 idx_t out_npts = ocoords_->shape(0);
211 // return early if no output points on this partition reserve is called on
212 // the triplets but also during the sparseMatrix constructor. This won't
213 // work for empty matrices
214 if (out_npts == 0) {
215 return;
216 }
217
218 Mesh meshSource = src.mesh();
219
220
221 auto trace_setup_source = atlas::Trace{Here(), "Setup source"};
222
223 // generate 3D point coordinates
224 Field source_xyz = mesh::actions::BuildXYZField("xyz")(meshSource);
225
226 // generate barycenters of each triangle & insert them on a kd-tree
227 util::Config config;
228 config.set("name", "centre ");
229 config.set("flatten_virtual_elements", false);
230 Field cell_centres = mesh::actions::BuildCellCentres(config)(meshSource);
231
232 std::unique_ptr<ElemIndex3> eTree(create_element_kdtree(meshSource, cell_centres));
233
234 trace_setup_source.stop();
235
236
237 icoords_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(source_xyz)));
238 igidx_.reset(new array::ArrayView<gidx_t, 1>(array::make_view<gidx_t, 1>(src.nodes().global_index())));
239 connectivity_ = &meshSource.cells().node_connectivity();
240 const mesh::Nodes& i_nodes = meshSource.nodes();
241
242 idx_t inp_npts = i_nodes.size();
243
244 auto target_point = [this](idx_t ip) {
245 return PointXYZ{(*ocoords_)(ip, 0), (*ocoords_)(ip, 1), (*ocoords_)(ip, 2)};
246 };
247
248
249 array::ArrayView<int, 1> out_ghosts = array::make_view<int, 1>(target_ghost_);
250
251 array::ArrayView<double, 2> out_lonlat = array::make_view<double, 2>(target_lonlat_);
252
253 idx_t Nelements = meshSource.cells().size();
254
255 // weights -- one per vertex of element, triangles (3) or quads (4)
256
257 Triplets weights_triplets; // structure to fill-in sparse matrix
258 weights_triplets.resize(out_npts * 4); // preallocate space as if all elements where quads
259 auto insert_triplets = [&weights_triplets](idx_t n, const Triplets& triplets) -> bool {
260 if (triplets.size()) {
261 std::copy(triplets.begin(), triplets.end(), weights_triplets.begin() + 4 * n);
262 return true;
263 }
264 return false;
265 };
266
267 double search_radius = 0.;
268 if (meshSource.metadata().has("cell_maximum_diagonal_on_unit_sphere")) {
269 search_radius =
270 Geometry("Earth").radius() * meshSource.metadata().getDouble("cell_maximum_diagonal_on_unit_sphere");
271 ASSERT(search_radius > 0.);
272 Log::debug() << "k-d tree: search radius = " << search_radius / 1000. << " km" << std::endl;
273 }
274 auto find_element_candidates_in_search_radius = [&eTree, &search_radius](const PointXYZ& p) {
275 return eTree->findInSphere(p, search_radius);
276 };
277 auto find_k_nearest_element_candidates = [&eTree](const PointXYZ& p, size_t k) {
278 return eTree->kNearestNeighbours(p, k);
279 };
280 auto try_interpolate_with_element_candidates =
281 [&insert_triplets, this](idx_t n, const ElemIndex3::NodeList& element_candidates) -> bool {
282 if (element_candidates.empty()) {
283 return false;
284 }
285 return insert_triplets(n, projectPointToElements(n, element_candidates));
286 };
287
288
289 // search nearest k cell centres
290 const idx_t maxNbElemsToTry = std::max<idx_t>(8, idx_t(Nelements * max_fraction_elems_to_try_));
291 size_t diagnosed_max_neighbours = 0;
292 bool allowed_to_diagnose_max_neighbours = Log::debug() && atlas_omp_get_max_threads() > 1;
293
294 std::vector<size_t> failures;
295
296 ATLAS_TRACE_SCOPE("Computing interpolation matrix") {
297 std::unique_ptr<eckit::ProgressTimer> progress;
298 if (atlas_omp_get_max_threads() == 1) {
299 progress.reset(new eckit::ProgressTimer{"Computing interpolation weights", static_cast<size_t>(out_npts),
300 "point", double(5), Log::debug()});
301 }
302 atlas_omp_parallel_for(idx_t ip = 0; ip < out_npts; ++ip) {
303 if (out_ghosts(ip)) {
304 continue;
305 }
306
307 bool success = false;
308 if (search_radius != 0.) {
309 auto p = target_point(ip);
310 success = try_interpolate_with_element_candidates(ip, find_element_candidates_in_search_radius(p));
311 }
312 else {
313 size_t k = 1;
314 auto p = target_point(ip);
315 while (!success && k <= maxNbElemsToTry) {
316 if (allowed_to_diagnose_max_neighbours) { // avoid race condition
317 diagnosed_max_neighbours = std::max(k, diagnosed_max_neighbours);
318 }
319 success = try_interpolate_with_element_candidates(ip, find_k_nearest_element_candidates(p, k));
320 k *= 2;
321 }
322 }
323
324 if (!success) {
325 atlas_omp_critical {
326 failures.emplace_back(ip);
327 }
328 }
329 if (progress) {
330 ++(*progress);
331 }
332 }
333 }
334 if (diagnosed_max_neighbours) {
335 Log::debug() << "Maximum neighbours searched was " << eckit::Plural(diagnosed_max_neighbours, "element")
336 << std::endl;
337 }
338
339 if (failures.size()) {
340 if (treat_failure_as_missing_value_) {
341 missing_.resize(failures.size());
342 std::copy(std::begin(failures), std::end(failures), missing_.begin());
343 }
344 else {
345 // If this fails, consider lowering atlas::grid::parametricEpsilon
346 std::ostringstream msg;
347 msg << "Rank " << mpi::rank() << " failed to project points:\n";
348 for (std::vector<size_t>::const_iterator i = failures.begin(); i != failures.end(); ++i) {
349 const PointLonLat pll{out_lonlat(*i, (size_t)0), out_lonlat(*i, (size_t)1)}; // lookup point
350 msg << "\t(lon,lat) = " << pll << "\n";
351 }
352
353 Log::error() << msg.str() << std::endl;
354 throw_Exception(msg.str());
355 }
356 }
357
358 // fill sparse matrix and return, this cannot be multithreaded!
359 setMatrix(out_npts, inp_npts, weights_triplets);
360 }
361
362 Method::Triplets SphericalMeanValue::projectPointToElements(size_t ip, const ElemIndex3::NodeList& elems) const {
363 ATLAS_ASSERT(elems.begin() != elems.end());
364
365 const size_t inp_points = icoords_->shape(0);
366
367 Triplets triplets;
368 triplets.reserve(4);
369
370 const PointXYZ candidatePoint = PointXYZ::normalize(
371 PointXYZ{(*ocoords_)(ip, size_t(0)), (*ocoords_)(ip, size_t(1)), (*ocoords_)(ip, size_t(2))});
372
373 for (ElemIndex3::NodeList::const_iterator itc = elems.begin(); itc != elems.end(); ++itc) {
374 const idx_t elem_id = idx_t((*itc).value().payload());
375 ATLAS_ASSERT(elem_id < connectivity_->rows());
376
377 size_t nb_cols = connectivity_->cols(elem_id);
378
379 std::vector<size_t> idx;
380 idx.reserve(nb_cols);
381
382 for (idx_t i = 0; i < nb_cols; ++i) {
383 idx.emplace_back((*connectivity_)(elem_id, i));
384 ATLAS_ASSERT(idx[i] < inp_points);
385 }
386
387 std::vector<PointXYZ> listVertices;
388 listVertices.reserve(util::ConvexSphericalPolygon::MAX_SIZE);
389
390 for (idx_t i = 0; i < nb_cols; ++i) {
391 listVertices.emplace_back(PointXYZ::normalize(PointXYZ{
392 (*icoords_)(idx[i], size_t(0)), (*icoords_)(idx[i], size_t(1)), (*icoords_)(idx[i], size_t(2))}));
393 }
394
395 util::ConvexSphericalPolygon currentPolygon(listVertices.data(), listVertices.size());
396
397 nb_cols = currentPolygon.size();
398 ATLAS_ASSERT(nb_cols == 3 || nb_cols == 4);
399
400 std::vector<double> polygonWeights(nb_cols);
401
402 if (currentPolygon.compute_vertex_weights(candidatePoint, polygonWeights.data(), polygonWeights.size()) == 1) {
403 if (normalisation_) {
404 double weightsSum = 0;
405 for (size_t i = 0; i < nb_cols; ++i) {
406 weightsSum += (polygonWeights)[i];
407 }
408 for (size_t i = 0; i < nb_cols; ++i) {
409 (polygonWeights)[i] /= weightsSum;
410 }
411 }
412 for (size_t i = 0; i < nb_cols; ++i) {
413 triplets.emplace_back(ip, idx[i], (polygonWeights)[i]);
414 }
415 break;
416 }
417 }
418
419 return triplets;
420 }
421
422
423 } // namespace method
424 } // namespace interpolation
425 } // namespace atlas