Debian Codegraph @

src/atlas/util/CGALSphericalTriangulation.cc

raw
1 #include "CGALSphericalTriangulation.h"
2
3 #include "atlas/library/defines.h"
4
5 #include <cmath>
6 #include <random>
7 #include <algorithm>
8 #include <utility>
9
10 #include "atlas/runtime/Exception.h"
11
12 #if ATLAS_HAVE_CGAL
13
14 // CGAL needs -DCGAL_NDEBUG to reach peak performance ...
15 #define CGAL_NDEBUG
16
17 #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
18 #include <CGAL/Polyhedron_3.h>
19 #include <CGAL/Real_timer.h>
20 #include <CGAL/algorithm.h>
21 #include <CGAL/convex_hull_3.h>
22 #include <CGAL/point_generators_3.h>
23
24
25 using K = ::CGAL::Exact_predicates_inexact_constructions_kernel;
26 using Polyhedron_3 = ::CGAL::Polyhedron_3<K>;
27 using Point_3 = Polyhedron_3::Point_3;
28
29 #endif
30
31
32 namespace atlas{
33 namespace util{
34
35 #if ATLAS_HAVE_CGAL
36 struct CGALSphericalTriangulation::CGAL {
37 CGAL(const std::vector<std::array<double,3>>& pts) {
38 std::vector<Point_3> vertices(pts.size());
39 for (size_t i = 0, size = vertices.size(); i < size; ++i) {
40 vertices[i] = Point_3(pts[i][0], pts[i][1], pts[i][2]);
41 point_map_[vertices[i]] = i;
42 }
43
44 // compute convex hull of non-collinear points
45 ::CGAL::convex_hull_3(vertices.begin(), vertices.end(), poly_);
46 }
47 std::unordered_map<Point_3,size_t> point_map_;
48 Polyhedron_3 poly_;
49 };
50 #else
51 struct CGALSphericalTriangulation::CGAL {
52 template<typename... Args>
53 CGAL(Args...) {
54 throw_Exception("Atlas has not been compiled with CGAL",Here());
55 }
56 };
57 #endif
58
59 CGALSphericalTriangulation::~CGALSphericalTriangulation() = default;
60
61 CGALSphericalTriangulation::CGALSphericalTriangulation(size_t N, const double lonlat[]) :
62 CGALSphericalTriangulation(N, lonlat, lonlat+1, 2, 2) {
63 }
64
65 CGALSphericalTriangulation::CGALSphericalTriangulation(size_t N, const double lon[], const double lat[]) :
66 CGALSphericalTriangulation(N, lon, lat, 1, 1) {
67 }
68
69 CGALSphericalTriangulation::CGALSphericalTriangulation(size_t N, const double lon[], const double lat[], int lon_stride, int lat_stride) {
70 auto lonlat2xyz = [](double lon, double lat, auto& xyz) {
71 constexpr double deg2rad = M_PI / 180.;
72 const double lambda = deg2rad * lon;
73 const double phi = deg2rad * lat;
74
75 const double sin_phi = std::sin(phi);
76 const double cos_phi = std::cos(phi);
77 const double sin_lambda = std::sin(lambda);
78 const double cos_lambda = std::cos(lambda);
79
80 xyz[0] = cos_phi * cos_lambda;
81 xyz[1] = cos_phi * sin_lambda;
82 xyz[2] = sin_phi;
83 };
84
85 points_xyz_.resize(N);
86
87 for (size_t i = 0; i < N; ++i) {
88 lonlat2xyz(lon[i*lon_stride], lat[i*lat_stride], points_xyz_[i]);
89 }
90
91 cgal_ = std::make_unique<CGAL>(points_xyz_);
92 }
93
94 size_t CGALSphericalTriangulation::size() const {
95 #if ATLAS_HAVE_CGAL
96 return cgal_->poly_.size_of_facets();
97 #else
98 return 0;
99 #endif
100 }
101
102
103 template <typename CGAL, typename Points, typename Value>
104 static inline void CGAL_get_triangles(const CGAL& cgal, const Points& points_xyz_, std::array<Value,3> triangles[]) {
105 #if ATLAS_HAVE_CGAL
106 auto ensure_outward_normal = [&](auto& tri) {
107
108 auto dot = [](const auto& p1, const auto& p2) {
109 return p1[0]*p2[0] + p1[1]*p2[1] + p1[2]*p2[2];
110 };
111 auto cross = [](const auto& p1, const auto& p2) {
112 return std::array<double,3>{
113 p1[1] * p2[2] - p1[2] * p2[1], p1[2] * p2[0] - p1[0] * p2[2],
114 p1[0] * p2[1] - p1[1] * p2[0]
115 };
116 };
117
118 const std::array<double,3>& a = points_xyz_[tri[0]];
119 const std::array<double,3>& b = points_xyz_[tri[1]];
120 const std::array<double,3>& c = points_xyz_[tri[2]];
121 std::array<double,3> ba {a[0]-b[0], a[1]-b[1], a[2]-b[2]};
122 std::array<double,3> bc {c[0]-b[0], c[1]-b[1], c[2]-b[2]};
123
124 bool outward = dot(b, cross(bc,ba)) > 0;
125
126 if (not outward) {
127 std::swap(tri[1], tri[2]);
128 }
129 };
130
131 size_t jtri{0};
132
133 const auto& poly = cgal.poly_;
134 const auto& point_map = cgal.point_map_;
135 const idx_t nb_points = idx_t(points_xyz_.size());
136
137 /* triangles */
138
139 const idx_t nb_triags = poly.size_of_facets();
140
141 idx_t idx[3];
142 Polyhedron_3::Vertex_const_handle vts[3];
143
144 idx_t tidx = 0;
145 for (Polyhedron_3::Facet_const_iterator f = poly.facets_begin(); f != poly.facets_end(); ++f) {
146 // loop over half-edges and take each vertex()
147
148 auto& tri = triangles[jtri++];
149
150 size_t jvrt{0};
151
152 idx_t iedge = 0;
153 Polyhedron_3::Halfedge_around_facet_const_circulator edge = f->facet_begin();
154 do {
155 Polyhedron_3::Vertex_const_handle vh = edge->vertex();
156 const Polyhedron_3::Point_3& p = vh->point();
157 tri[jvrt++] = point_map.at(vh->point());
158
159 ++iedge;
160 ++edge;
161 } while (edge != f->facet_begin() && iedge < 3);
162
163 ATLAS_ASSERT(iedge == 3);
164
165 ensure_outward_normal(tri);
166 }
167
168 ATLAS_ASSERT(jtri == nb_triags);
169 #endif
170 }
171
172 void CGALSphericalTriangulation::triangles(std::array<int,3> triangles[]) const {
173 CGAL_get_triangles(*cgal_,points_xyz_,triangles);
174 }
175
176 void CGALSphericalTriangulation::triangles(std::array<long,3> triangles[]) const {
177 CGAL_get_triangles(*cgal_,points_xyz_,triangles);
178 }
179
180 void CGALSphericalTriangulation::triangles(std::array<long long,3> triangles[]) const {
181 CGAL_get_triangles(*cgal_,points_xyz_,triangles);
182 }
183
184 void CGALSphericalTriangulation::triangles(std::array<size_t,3> triangles[]) const {
185 CGAL_get_triangles(*cgal_,points_xyz_,triangles);
186 }
187
188 std::vector<std::array<idx_t,3>> CGALSphericalTriangulation::triangles() const {
189 return triangles<idx_t>();
190 }
191
192 } // namespace util
193 } // namespace atlas