Debian Codegraph @

src/atlas/interpolation/method/unstructured/FiniteElement.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 "FiniteElement.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/CoordinateEnums.h"
42 #include "atlas/util/Earth.h"
43 #include "atlas/util/Point.h"
44
45
46 namespace atlas {
47 namespace interpolation {
48 namespace method {
49
50 namespace {
51
52 MethodBuilder<FiniteElement> __builder("finite-element");
53
54 // epsilon used to scale edge tolerance when projecting ray to intesect element
55 static const double parametricEpsilon = 1e-15;
56
57 } // namespace
58
59
60 void FiniteElement::do_setup(const Grid& source, const Grid& target, const Cache& cache) {
61 allow_halo_exchange_ = false;
62 // no halo_exchange because we don't have any halo with delaunay or 3d structured meshgenerator
63
64 if (interpolation::MatrixCache(cache)) {
65 setMatrix(cache);
66 ATLAS_ASSERT(matrix().rows() == target.size());
67 ATLAS_ASSERT(matrix().cols() == source.size());
68 return;
69 }
70 if (mpi::size() > 1) {
71 ATLAS_NOTIMPLEMENTED;
72 }
73 auto make_nodecolumns = [](const Grid& grid) {
74 Mesh mesh;
75 if (StructuredGrid{grid}) {
76 mesh = MeshGenerator("structured", util::Config("3d", true)).generate(grid);
77 }
78 else {
79 mesh = MeshGenerator("delaunay").generate(grid);
80 }
81 return functionspace::NodeColumns(mesh);
82 };
83
84 do_setup(make_nodecolumns(source), functionspace::PointCloud{target});
85 }
86
87 void FiniteElement::do_setup(const FunctionSpace& source, const FunctionSpace& target, const Cache& cache) {
88 if (interpolation::MatrixCache(cache)) {
89 setMatrix(cache);
90 source_ = source;
91 target_ = target;
92 ATLAS_ASSERT(matrix().rows() == target.size());
93 ATLAS_ASSERT(matrix().cols() == source.size());
94 return;
95 }
96 do_setup(source, target);
97 }
98
99 void FiniteElement::do_setup(const FunctionSpace& source, const FunctionSpace& target) {
100 ATLAS_TRACE("atlas::interpolation::method::FiniteElement::do_setup()");
101
102 source_ = source;
103 target_ = target;
104
105 ATLAS_TRACE_SCOPE("Setup target") {
106
107
108 auto create_xyz = [](Field lonlat_field) {
109 auto xyz_field = Field("xyz", array::make_datatype<double>(), array::make_shape(lonlat_field.shape(0), 3));
110 auto lonlat = array::make_view<double, 2>(lonlat_field);
111 auto xyz = array::make_view<double, 2>(xyz_field);
112 PointXYZ p2;
113 for (idx_t n = 0; n < lonlat.shape(0); ++n) {
114 const PointLonLat p1(lonlat(n, 0), lonlat(n, 1));
115 util::Earth::convertSphericalToCartesian(p1, p2);
116 xyz(n, 0) = p2.x();
117 xyz(n, 1) = p2.y();
118 xyz(n, 2) = p2.z();
119 }
120 return xyz_field;
121 };
122
123 target_ghost_ = target.ghost();
124 target_lonlat_ = target.lonlat();
125 if (functionspace::NodeColumns tgt = target) {
126 auto meshTarget = tgt.mesh();
127 target_xyz_ = mesh::actions::BuildXYZField("xyz")(meshTarget);
128 }
129 else {
130 target_xyz_ = create_xyz(target_lonlat_);
131 }
132 }
133
134 setup(source);
135 }
136
137 struct Stencil {
138 enum
139 {
140 max_stencil_size = 4
141 };
142 };
143
144 void FiniteElement::print(std::ostream& out) const {
145 functionspace::NodeColumns src(source_);
146 functionspace::NodeColumns tgt(target_);
147 out << "atlas::interpolation::method::FiniteElement{" << std::endl;
148 out << "max_fraction_elems_to_try: " << max_fraction_elems_to_try_;
149 out << ", treat_failure_as_missing_value: " << treat_failure_as_missing_value_;
150 if (not tgt) {
151 out << "}" << std::endl;
152 return;
153 }
154 out << ", NodeColumns to NodeColumns stencil weights: " << std::endl;
155 auto gidx_src = array::make_view<gidx_t, 1>(src.nodes().global_index());
156
157 ATLAS_ASSERT(tgt.nodes().size() == idx_t(matrix().rows()));
158
159
160 auto field_stencil_points_loc = tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size));
161 auto field_stencil_weights_loc = tgt.createField<double>(option::variables(Stencil::max_stencil_size));
162 auto field_stencil_size_loc = tgt.createField<int>();
163
164 auto stencil_points_loc = array::make_view<gidx_t, 2>(field_stencil_points_loc);
165 auto stencil_weights_loc = array::make_view<double, 2>(field_stencil_weights_loc);
166 auto stencil_size_loc = array::make_view<idx_t, 1>(field_stencil_size_loc);
167 stencil_size_loc.assign(0);
168
169 const auto m = atlas::linalg::make_non_owning_eckit_sparse_matrix(matrix());
170 for (auto it = m.begin(); it != m.end(); ++it) {
171 idx_t p = idx_t(it.row());
172 idx_t& i = stencil_size_loc(p);
173 stencil_points_loc(p, i) = gidx_src(it.col());
174 stencil_weights_loc(p, i) = *it;
175 ++i;
176 }
177
178 gidx_t global_size = tgt.gather().glb_dof();
179
180 auto field_stencil_points_glb =
181 tgt.createField<gidx_t>(option::variables(Stencil::max_stencil_size) | option::global(0));
182 auto field_stencil_weights_glb =
183 tgt.createField<double>(option::variables(Stencil::max_stencil_size) | option::global(0));
184 auto field_stencil_size_glb = tgt.createField<idx_t>(option::global(0));
185
186
187 auto stencil_points_glb = array::make_view<gidx_t, 2>(field_stencil_points_glb);
188 auto stencil_weights_glb = array::make_view<double, 2>(field_stencil_weights_glb);
189 auto stencil_size_glb = array::make_view<idx_t, 1>(field_stencil_size_glb);
190
191 tgt.gather().gather(stencil_size_loc, stencil_size_glb);
192 tgt.gather().gather(stencil_points_loc, stencil_points_glb);
193 tgt.gather().gather(stencil_weights_loc, stencil_weights_glb);
194
195 int precision = std::numeric_limits<double>::max_digits10;
196 for (idx_t i = 0; i < global_size; ++i) {
197 out << std::setw(10) << i + 1 << " : ";
198 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
199 out << std::setw(10) << stencil_points_glb(i, j);
200 }
201 for (idx_t j = stencil_size_glb(i); j < Stencil::max_stencil_size; ++j) {
202 out << " ";
203 }
204 for (idx_t j = 0; j < stencil_size_glb(i); ++j) {
205 out << std::setw(precision + 5) << std::left << std::setprecision(precision) << stencil_weights_glb(i, j);
206 }
207 out << std::endl;
208 }
209 out << "}" << std::endl;
210 }
211
212 void FiniteElement::setup(const FunctionSpace& source) {
213 const functionspace::NodeColumns src = source;
214 ATLAS_ASSERT(src);
215
216 ocoords_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(target_xyz_)));
217 idx_t out_npts = ocoords_->shape(0);
218 // return early if no output points on this partition reserve is called on
219 // the triplets but also during the sparseMatrix constructor. This won't
220 // work for empty matrices
221 if (out_npts == 0) {
222 return;
223 }
224
225 Mesh meshSource = src.mesh();
226
227
228 auto trace_setup_source = atlas::Trace{Here(), "Setup source"};
229
230 // generate 3D point coordinates
231 Field source_xyz = mesh::actions::BuildXYZField("xyz")(meshSource);
232
233 // generate barycenters of each triangle & insert them on a kd-tree
234 util::Config config;
235 config.set("name", "centre ");
236 config.set("flatten_virtual_elements", false);
237 Field cell_centres = mesh::actions::BuildCellCentres(config)(meshSource);
238
239 std::unique_ptr<ElemIndex3> eTree(create_element_kdtree(meshSource, cell_centres));
240
241 trace_setup_source.stop();
242
243
244 icoords_.reset(new array::ArrayView<double, 2>(array::make_view<double, 2>(source_xyz)));
245 igidx_.reset(new array::ArrayView<gidx_t, 1>(array::make_view<gidx_t, 1>(src.nodes().global_index())));
246 connectivity_ = &meshSource.cells().node_connectivity();
247 const mesh::Nodes& i_nodes = meshSource.nodes();
248
249 idx_t inp_npts = i_nodes.size();
250
251 auto target_point = [this](idx_t ip) {
252 return PointXYZ{(*ocoords_)(ip, 0), (*ocoords_)(ip, 1), (*ocoords_)(ip, 2)};
253 };
254
255
256 array::ArrayView<int, 1> out_ghosts = array::make_view<int, 1>(target_ghost_);
257
258 array::ArrayView<double, 2> out_lonlat = array::make_view<double, 2>(target_lonlat_);
259
260 idx_t Nelements = meshSource.cells().size();
261
262 // weights -- one per vertex of element, triangles (3) or quads (4)
263
264 Triplets weights_triplets; // structure to fill-in sparse matrix
265 weights_triplets.resize(out_npts * 4); // preallocate space as if all elements where quads
266 auto insert_triplets = [&weights_triplets](idx_t n, const Triplets& triplets) -> bool {
267 if (triplets.size()) {
268 std::copy(triplets.begin(), triplets.end(), weights_triplets.begin()+4*n);
269 return true;
270 }
271 return false;
272 };
273
274 double search_radius = 0.;
275 if (meshSource.metadata().has("cell_maximum_diagonal_on_unit_sphere")) {
276 search_radius = Geometry("Earth").radius() * meshSource.metadata().getDouble("cell_maximum_diagonal_on_unit_sphere");
277 ASSERT(search_radius > 0.);
278 Log::debug() << "k-d tree: search radius = " << search_radius/1000. << " km" << std::endl;
279 }
280 auto find_element_candidates_in_search_radius = [&eTree,&search_radius](const PointXYZ& p) {
281 return eTree->findInSphere(p, search_radius);
282 };
283 auto find_k_nearest_element_candidates = [&eTree](const PointXYZ& p, size_t k) {
284 return eTree->kNearestNeighbours(p, k);
285 };
286 auto try_interpolate_with_element_candidates = [&insert_triplets, this](idx_t n, const ElemIndex3::NodeList& element_candidates) -> bool {
287 if (element_candidates.empty()) {
288 return false;
289 }
290 return insert_triplets(n, projectPointToElements(n, element_candidates));
291 };
292
293
294 // search nearest k cell centres
295 const idx_t maxNbElemsToTry = std::max<idx_t>(8, idx_t(Nelements * max_fraction_elems_to_try_));
296 size_t diagnosed_max_neighbours = 0;
297 bool allowed_to_diagnose_max_neighbours = Log::debug() && atlas_omp_get_max_threads() > 1;
298
299 std::vector<size_t> failures;
300
301 ATLAS_TRACE_SCOPE("Computing interpolation matrix") {
302 std::unique_ptr<eckit::ProgressTimer> progress;
303 if (atlas_omp_get_max_threads() == 1) {
304 progress.reset(new eckit::ProgressTimer{"Computing interpolation weights", static_cast<size_t>(out_npts), "point", double(5), Log::debug()});
305 }
306 atlas_omp_parallel_for (idx_t ip = 0; ip < out_npts; ++ip) {
307 if (out_ghosts(ip)) {
308 continue;
309 }
310
311 bool success = false;
312 if (search_radius != 0.) {
313 auto p = target_point(ip);
314 success = try_interpolate_with_element_candidates(ip, find_element_candidates_in_search_radius(p));
315 }
316 else {
317 size_t k = 1;
318 auto p = target_point(ip);
319 while (!success && k <= maxNbElemsToTry) {
320 if (allowed_to_diagnose_max_neighbours) { // avoid race condition
321 diagnosed_max_neighbours = std::max(k, diagnosed_max_neighbours);
322 }
323 success = try_interpolate_with_element_candidates(ip, find_k_nearest_element_candidates(p, k));
324 k *= 2;
325 }
326 }
327
328 if (!success) {
329 atlas_omp_critical {
330 failures.emplace_back(ip);
331 }
332 }
333 if (progress) {
334 ++(*progress);
335 }
336 }
337 }
338 if (diagnosed_max_neighbours) {
339 Log::debug() << "Maximum neighbours searched was " << eckit::Plural(diagnosed_max_neighbours, "element") << std::endl;
340 }
341
342 if (failures.size()) {
343 if (treat_failure_as_missing_value_) {
344 missing_.resize(failures.size());
345 std::copy(std::begin(failures), std::end(failures), missing_.begin());
346 }
347 else {
348 // If this fails, consider lowering atlas::grid::parametricEpsilon
349 std::ostringstream msg;
350 msg << "Rank " << mpi::rank() << " failed to project points:\n";
351 for (std::vector<size_t>::const_iterator i = failures.begin(); i != failures.end(); ++i) {
352 const PointLonLat pll{out_lonlat(*i, (size_t)0), out_lonlat(*i, (size_t)1)}; // lookup point
353 msg << "\t(lon,lat) = " << pll << "\n";
354 }
355
356 Log::error() << msg.str() << std::endl;
357 throw_Exception(msg.str());
358 }
359 }
360
361 // fill sparse matrix and return, this cannot be multithreaded!
362 setMatrix(out_npts, inp_npts, weights_triplets);
363 }
364
365 struct ElementEdge {
366 std::array<idx_t, 2> idx;
367 void swap() {
368 idx_t tmp = idx[0];
369 idx[0] = idx[1];
370 idx[1] = tmp;
371 }
372 };
373
374 Method::Triplets FiniteElement::projectPointToElements(size_t ip, const ElemIndex3::NodeList& elems) const {
375 ATLAS_ASSERT(elems.begin() != elems.end());
376
377 const size_t inp_points = icoords_->shape(0);
378 std::array<size_t, 4> idx;
379 std::array<double, 4> w;
380
381 Triplets triplets;
382 triplets.reserve(4);
383 Ray ray(PointXYZ{(*ocoords_)(ip, size_t(0)), (*ocoords_)(ip, size_t(1)), (*ocoords_)(ip, size_t(2))});
384 const Vector3D p{(*ocoords_)(ip, size_t(0)), (*ocoords_)(ip, size_t(1)), (*ocoords_)(ip, size_t(2))};
385 ElementEdge edge;
386 idx_t single_point;
387 for (ElemIndex3::NodeList::const_iterator itc = elems.begin(); itc != elems.end(); ++itc) {
388 const idx_t elem_id = idx_t((*itc).value().payload());
389 ATLAS_ASSERT(elem_id < connectivity_->rows());
390
391 const idx_t nb_cols = [&]() {
392 int nb_cols = connectivity_->cols(elem_id);
393 if (nb_cols == 5) {
394 // Check if pentagon degenerates to quad. Otherwise abort.
395 // For now only check if the last point is a duplicate.
396 auto get_p = [&](idx_t i) {
397 auto n = (*connectivity_)(elem_id, i);
398 return PointXYZ{(*icoords_)(n, XX), (*icoords_)(n, YY), (*icoords_)(n, ZZ)};
399 };
400 auto p4 = get_p(4);
401 if (p4 == get_p(0)) {
402 return 4;
403 }
404 if (p4 == get_p(3)) {
405 return 4;
406 }
407 }
408 return nb_cols;
409 }();
410
411
412 ATLAS_ASSERT(nb_cols == 3 || nb_cols == 4);
413
414 for (idx_t i = 0; i < nb_cols; ++i) {
415 idx[i] = (*connectivity_)(elem_id, i);
416 ATLAS_ASSERT(idx[i] < inp_points);
417 }
418
419 constexpr double tolerance = 1.e-12;
420
421 auto on_triag_edge = [&]() {
422 if (w[0] < tolerance) {
423 edge.idx[0] = 1;
424 edge.idx[1] = 2;
425 w[0] = 0.;
426 return true;
427 }
428 if (w[1] < tolerance) {
429 edge.idx[0] = 0;
430 edge.idx[1] = 2;
431 w[1] = 0.;
432 return true;
433 }
434 if (w[2] < tolerance) {
435 edge.idx[0] = 0;
436 edge.idx[1] = 1;
437 w[2] = 0.;
438 return true;
439 }
440 return false;
441 };
442
443 auto on_quad_edge = [&]() {
444 if (w[0] < tolerance && w[1] < tolerance) {
445 edge.idx[0] = 2;
446 edge.idx[1] = 3;
447 w[0] = 0.;
448 w[1] = 0.;
449 return true;
450 }
451 if (w[1] < tolerance && w[2] < tolerance) {
452 edge.idx[0] = 0;
453 edge.idx[1] = 3;
454 w[1] = 0.;
455 w[2] = 0.;
456 return true;
457 }
458 if (w[2] < tolerance && w[3] < tolerance) {
459 edge.idx[0] = 0;
460 edge.idx[1] = 1;
461 w[2] = 0.;
462 w[3] = 0.;
463 return true;
464 }
465 if (w[3] < tolerance && w[0] < tolerance) {
466 edge.idx[0] = 1;
467 edge.idx[1] = 2;
468 w[3] = 0.;
469 w[0] = 0.;
470 return true;
471 }
472 return false;
473 };
474
475 auto on_single_point = [&]() {
476 if (w[edge.idx[0]] < tolerance) {
477 single_point = edge.idx[1];
478 w[edge.idx[0]] = 0.;
479 return true;
480 }
481 if (w[edge.idx[1]] < tolerance) {
482 single_point = edge.idx[0];
483 w[edge.idx[1]] = 0.;
484 return true;
485 }
486 return false;
487 };
488
489 auto interpolate_edge = [&](const Vector3D& p0, const Vector3D& p1) {
490 /*
491 * Given points p0,p1 defining the edge, and point p, find projected point pt
492 * on edge to compute interpolation weights.
493 * p
494 * |`.
495 * | `.v
496 * | `.
497 * p1--------------pt-----p0
498 * <--d----
499 */
500 Vector3D d = (p1 - p0) / (p1 - p0).norm();
501 Vector3D v = p - p0;
502 double t = v.dot(d);
503 Vector3D pt = p0 + d * t;
504 t = (pt - p0).norm() / (p1 - p0).norm();
505 w[edge.idx[0]] = 1. - t;
506 w[edge.idx[1]] = t;
507 };
508
509 if (nb_cols == 3) {
510 /* triangle */
511 element::Triag3D triag(PointXYZ{(*icoords_)(idx[0], XX), (*icoords_)(idx[0], YY), (*icoords_)(idx[0], ZZ)},
512 PointXYZ{(*icoords_)(idx[1], XX), (*icoords_)(idx[1], YY), (*icoords_)(idx[1], ZZ)},
513 PointXYZ{(*icoords_)(idx[2], XX), (*icoords_)(idx[2], YY), (*icoords_)(idx[2], ZZ)});
514
515 // pick an epsilon based on a characteristic length (sqrt(area))
516 // (this scales linearly so it better compares with linear weights u,v,w)
517 const double edgeEpsilon = parametricEpsilon * std::sqrt(triag.area());
518 ATLAS_ASSERT(edgeEpsilon >= 0);
519
520 Intersect is = triag.intersects(ray, edgeEpsilon);
521
522 if (is) {
523 // weights are the linear Lagrange function evaluated at u,v (aka
524 // barycentric coordinates)
525 w[0] = 1. - is.u - is.v;
526 w[1] = is.u;
527 w[2] = is.v;
528
529 if (on_triag_edge()) {
530 if (on_single_point()) {
531 triplets.emplace_back(ip, idx[single_point], w[single_point]);
532 }
533 else {
534 if ((*igidx_)(idx[edge.idx[1]]) < (*igidx_)(idx[edge.idx[0]])) {
535 edge.swap();
536 }
537 interpolate_edge(triag.p(edge.idx[0]), triag.p(edge.idx[1]));
538 for (size_t i = 0; i < 2; ++i) {
539 triplets.emplace_back(ip, idx[edge.idx[i]], w[edge.idx[i]]);
540 }
541 }
542 }
543 else {
544 for (size_t i = 0; i < 3; ++i) {
545 triplets.emplace_back(ip, idx[i], w[i]);
546 }
547 }
548
549 break; // stop looking for elements
550 }
551 }
552 else {
553 /* quadrilateral */
554 element::Quad3D quad(PointXYZ{(*icoords_)(idx[0], XX), (*icoords_)(idx[0], YY), (*icoords_)(idx[0], ZZ)},
555 PointXYZ{(*icoords_)(idx[1], XX), (*icoords_)(idx[1], YY), (*icoords_)(idx[1], ZZ)},
556 PointXYZ{(*icoords_)(idx[2], XX), (*icoords_)(idx[2], YY), (*icoords_)(idx[2], ZZ)},
557 PointXYZ{(*icoords_)(idx[3], XX), (*icoords_)(idx[3], YY), (*icoords_)(idx[3], ZZ)});
558
559 // pick an epsilon based on a characteristic length (sqrt(area))
560 // (this scales linearly so it better compares with linear weights u,v,w)
561 const double edgeEpsilon = parametricEpsilon * std::sqrt(quad.area());
562 ATLAS_ASSERT(edgeEpsilon >= 0);
563
564 Intersect is = quad.intersects(ray, edgeEpsilon);
565
566 if (is) {
567 // weights are the bilinear Lagrange function evaluated at u,v
568 w[0] = (1. - is.u) * (1. - is.v);
569 w[1] = is.u * (1. - is.v);
570 w[2] = is.u * is.v;
571 w[3] = (1. - is.u) * is.v;
572
573 if (on_quad_edge()) {
574 if (on_single_point()) {
575 triplets.emplace_back(ip, idx[single_point], w[single_point]);
576 }
577 else {
578 if ((*igidx_)(idx[edge.idx[1]]) < (*igidx_)(idx[edge.idx[0]])) {
579 edge.swap();
580 }
581 interpolate_edge(quad.p(edge.idx[0]), quad.p(edge.idx[1]));
582 for (size_t i = 0; i < 2; ++i) {
583 triplets.emplace_back(ip, idx[edge.idx[i]], w[edge.idx[i]]);
584 }
585 }
586 }
587 else {
588 for (size_t i = 0; i < 4; ++i) {
589 triplets.emplace_back(ip, idx[i], w[i]);
590 }
591 }
592 break; // stop looking for elements
593 }
594 }
595
596 } // loop over nearest elements
597
598 if (!triplets.empty()) {
599 normalise(triplets);
600 }
601 return triplets;
602 }
603
604 } // namespace method
605 } // namespace interpolation
606 } // namespace atlas