seams-core v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Loading...
Searching...
No Matches
euclidean_mic.hpp
Go to the documentation of this file.
1//-----------------------------------------------------------------------------------
2// d-SEAMS - Deferred Structural Elucidation Analysis for Molecular Simulations
3//
4// Copyright (c) 2018--present d-SEAMS core team
5//
6// SPDX-License-Identifier: MIT
7//-----------------------------------------------------------------------------------
8
9#ifndef SEAMS_EUCLIDEAN_MIC_H_
10#define SEAMS_EUCLIDEAN_MIC_H_
11
12// Euclidean minimum image for a triclinic cell when libminimage is not
13// linked. The fractional wrap is the nearest image only inside the Smith
14// ball. Past that ball the closest lattice point is Babai rounding in a
15// Selling superbasis, then the Sommer–Feder–Shalvi slicer. This is the
16// same reduction libminimage applies, so a build without that library
17// still rejects the longer fractional image.
18
19#include <array>
20#include <cmath>
21#include <cstddef>
22#include <limits>
23#include <utility>
24
25namespace gen {
26namespace mic {
27namespace {
28
29struct Vec3 {
30 double x = 0.0;
31 double y = 0.0;
32 double z = 0.0;
33};
34
35inline double n2(Vec3 v) { return v.x * v.x + v.y * v.y + v.z * v.z; }
36
37inline double dot(Vec3 a, Vec3 b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
38
39inline Vec3 add(Vec3 a, Vec3 b) { return {a.x + b.x, a.y + b.y, a.z + b.z}; }
40
41inline Vec3 scale(double s, Vec3 v) { return {s * v.x, s * v.y, s * v.z}; }
42
43// Half away from zero, matching a truncation after adding just under 1/2.
44inline double roundAway(double x) {
45 constexpr double kIntegral = 4503599627370496.0;
46 if (std::abs(x) < kIntegral) {
47 const double t = x + std::copysign(0.49999999999999994, x);
48 return static_cast<double>(static_cast<long long>(t));
49 }
50 return x;
51}
52
53struct Obtuse {
54 Vec3 v[4]{};
55 double rel[3][8]{};
56 double halfN2[8]{};
57 double gram[8][8]{};
58 double inv[3][3]{};
59 int idx[3] = {0, 1, 2};
60 bool ok = false;
61};
62
63inline void relevantOf(const Vec3 v[4], Obtuse &o) {
64 const Vec3 vecs[8] = {v[0],
65 v[1],
66 v[2],
67 v[3],
68 add(v[0], v[1]),
69 add(v[0], v[2]),
70 add(v[0], v[3]),
71 {}};
72 for (int k = 0; k < 8; k++) {
73 o.rel[0][k] = vecs[k].x;
74 o.rel[1][k] = vecs[k].y;
75 o.rel[2][k] = vecs[k].z;
76 o.halfN2[k] = (k < 7) ? 0.5 * n2(vecs[k]) * (1.0 + 1e-12)
77 : std::numeric_limits<double>::infinity();
78 for (int j = 0; j < 8; j++) {
79 o.gram[k][j] = dot(vecs[k], vecs[j]);
80 }
81 }
82}
83
84inline bool alreadyObtuse(const Vec3 v[4], double tol) {
85 for (int i = 0; i < 3; i++) {
86 for (int j = i + 1; j < 4; j++) {
87 if (dot(v[i], v[j]) > tol) {
88 return false;
89 }
90 }
91 }
92 return true;
93}
94
95inline void lagrangeReduce(Vec3 v[3]) {
96 for (int pass = 0; pass < 24; pass++) {
97 for (int i = 1; i < 3; i++) {
98 int j = i;
99 while (j > 0 && n2(v[j]) < n2(v[j - 1])) {
100 const Vec3 tmp = v[j];
101 v[j] = v[j - 1];
102 v[j - 1] = tmp;
103 j--;
104 }
105 }
106 bool changed = false;
107 for (int i = 1; i < 3; i++) {
108 for (int j = i - 1; j >= 0; j--) {
109 const double lj = n2(v[j]);
110 if (lj < 1e-30) {
111 continue;
112 }
113 const double q = roundAway(dot(v[i], v[j]) / lj);
114 if (q != 0.0) {
115 v[i] = add(v[i], scale(-q, v[j]));
116 changed = true;
117 }
118 }
119 }
120 if (!changed) {
121 break;
122 }
123 }
124}
125
126inline bool sellingSteps(Vec3 v[4], double tol, int budget) {
127 for (int step = 0; step < budget; step++) {
128 int si = -1;
129 int sj = -1;
130 for (int i = 0; i < 3 && si < 0; i++) {
131 for (int j = i + 1; j < 4; j++) {
132 if (dot(v[i], v[j]) > tol) {
133 si = i;
134 sj = j;
135 break;
136 }
137 }
138 }
139 if (si < 0) {
140 return true;
141 }
142 const Vec3 taken = v[si];
143 for (int k = 0; k < 4; k++) {
144 if (k != si && k != sj) {
145 v[k] = add(v[k], taken);
146 }
147 }
148 v[si] = scale(-1.0, taken);
149 }
150 return false;
151}
152
153// Inverse of the matrix with columns cols[0..2]. inv is stored so that
154// coeff k is sum_i inv[i][k] * y[i]. Returns |det|, or 0 when singular.
155inline double invertColumns(const Vec3 cols[3], double inv[3][3]) {
156 const Vec3 &a = cols[0];
157 const Vec3 &b = cols[1];
158 const Vec3 &c = cols[2];
159 const double det = a.x * (b.y * c.z - b.z * c.y) - a.y * (b.x * c.z - b.z * c.x) +
160 a.z * (b.x * c.y - b.y * c.x);
161 if (!std::isfinite(det) || std::abs(det) < 1e-18) {
162 return 0.0;
163 }
164 const double invdet = 1.0 / det;
165 const double cof[3][3] = {
166 {b.y * c.z - b.z * c.y, a.z * c.y - a.y * c.z, a.y * b.z - a.z * b.y},
167 {b.z * c.x - b.x * c.z, a.x * c.z - a.z * c.x, a.z * b.x - a.x * b.z},
168 {b.x * c.y - b.y * c.x, a.y * c.x - a.x * c.y, a.x * b.y - a.y * b.x}};
169 for (int i = 0; i < 3; i++) {
170 for (int j = 0; j < 3; j++) {
171 inv[i][j] = cof[i][j] * invdet;
172 }
173 }
174 return std::abs(det);
175}
176
177inline Obtuse finish(const Vec3 v[4]) {
178 Obtuse o;
179 for (int i = 0; i < 4; i++) {
180 o.v[i] = v[i];
181 }
182 double bestAbs = 0.0;
183 bool have = false;
184 for (int drop = 0; drop < 4; drop++) {
185 int idx[3];
186 int n = 0;
187 for (int t = 0; t < 4; t++) {
188 if (t != drop) {
189 idx[n++] = t;
190 }
191 }
192 const Vec3 cols[3] = {v[idx[0]], v[idx[1]], v[idx[2]]};
193 double inv[3][3];
194 const double absDet = invertColumns(cols, inv);
195 if (absDet > bestAbs) {
196 bestAbs = absDet;
197 have = true;
198 for (int k = 0; k < 3; k++) {
199 o.idx[k] = idx[k];
200 for (int j = 0; j < 3; j++) {
201 o.inv[k][j] = inv[k][j];
202 }
203 }
204 }
205 }
206 relevantOf(v, o);
207 o.ok = have && bestAbs > 1e-18;
208 return o;
209}
210
211inline Obtuse obtuseSuperbasis(Vec3 a, Vec3 b, Vec3 c) {
212 const Vec3 original[4] = {a, b, c, scale(-1.0, add(add(a, b), c))};
213 const double scaleLen = std::max(n2(a) + n2(b) + n2(c), 1.0);
214 const double tol = 1e-10 * scaleLen;
215 if (alreadyObtuse(original, tol)) {
216 return finish(original);
217 }
218 Vec3 reduced[3] = {a, b, c};
219 lagrangeReduce(reduced);
220 Vec3 v[4] = {reduced[0], reduced[1], reduced[2],
221 scale(-1.0, add(add(reduced[0], reduced[1]), reduced[2]))};
222 if (sellingSteps(v, tol, 64) || sellingSteps(v, tol, 1000)) {
223 return finish(v);
224 }
225 Obtuse failed = finish(original);
226 failed.ok = false;
227 return failed;
228}
229
230inline Vec3 descend(const Obtuse &s, Vec3 x) {
231 double t[8];
232 for (int k = 0; k < 8; k++) {
233 t[k] = x.x * s.rel[0][k] + x.y * s.rel[1][k] + x.z * s.rel[2][k];
234 }
235 for (int iter = 0; iter < 64; iter++) {
236 double g[8];
237 for (int k = 0; k < 8; k++) {
238 g[k] = std::abs(t[k]) - s.halfN2[k];
239 }
240 const auto larger = [](int i, double gi, int j, double gj) {
241 return gj > gi ? std::pair<int, double>{j, gj} : std::pair<int, double>{i, gi};
242 };
243 const auto p01 = larger(0, g[0], 1, g[1]);
244 const auto p23 = larger(2, g[2], 3, g[3]);
245 const auto p45 = larger(4, g[4], 5, g[5]);
246 const auto p03 = larger(p01.first, p01.second, p23.first, p23.second);
247 const auto p46 = larger(p45.first, p45.second, 6, g[6]);
248 const auto best = larger(p03.first, p03.second, p46.first, p46.second);
249 const double gain = best.second;
250 const int at = best.first;
251 const double f = gain > 0.0 ? (t[at] > 0.0 ? 1.0 : -1.0) : 0.0;
252 x.x -= f * s.rel[0][at];
253 x.y -= f * s.rel[1][at];
254 x.z -= f * s.rel[2][at];
255 for (int k = 0; k < 8; k++) {
256 t[k] -= f * s.gram[at][k];
257 }
258 bool any = false;
259 for (int k = 0; k < 8; k++) {
260 any = any || std::abs(t[k]) > s.halfN2[k];
261 }
262 if (!any) {
263 break;
264 }
265 }
266 return x;
267}
268
269inline Vec3 babai(const Obtuse &s, Vec3 y) {
270 double c[3];
271 const double yv[3] = {y.x, y.y, y.z};
272 for (int k = 0; k < 3; k++) {
273 c[k] = s.inv[0][k] * yv[0] + s.inv[1][k] * yv[1] + s.inv[2][k] * yv[2];
274 }
275 const double z0 = roundAway(c[0]);
276 const double z1 = roundAway(c[1]);
277 const double z2 = roundAway(c[2]);
278 const Vec3 b0 = s.v[s.idx[0]];
279 const Vec3 b1 = s.v[s.idx[1]];
280 const Vec3 b2 = s.v[s.idx[2]];
281 return {y.x - (z0 * b0.x + z1 * b1.x + z2 * b2.x),
282 y.y - (z0 * b0.y + z1 * b1.y + z2 * b2.y),
283 y.z - (z0 * b0.z + z1 * b1.z + z2 * b2.z)};
284}
285
286inline Vec3 shell(Vec3 a, Vec3 b, Vec3 c, Vec3 y) {
287 Vec3 best = y;
288 double best2 = n2(y);
289 for (int r = 0; r <= 16; r++) {
290 for (int i = -r; i <= r; i++) {
291 for (int j = -r; j <= r; j++) {
292 for (int k = -r; k <= r; k++) {
293 if (r > 0 && std::abs(i) != r && std::abs(j) != r && std::abs(k) != r) {
294 continue;
295 }
296 const Vec3 d = {y.x - (i * a.x + j * b.x + k * c.x),
297 y.y - (i * a.y + j * b.y + k * c.y),
298 y.z - (i * a.z + j * b.z + k * c.z)};
299 const double d2 = n2(d);
300 if (d2 < best2) {
301 best2 = d2;
302 best = d;
303 }
304 }
305 }
306 }
307 }
308 return best;
309}
310
311inline Vec3 closestDisplacement(const Obtuse &s, Vec3 y) {
312 if (s.ok) {
313 return descend(s, babai(s, y));
314 }
315 return shell(s.v[0], s.v[1], s.v[2], y);
316}
317
318inline bool engineIsShort(Vec3 a, Vec3 b, Vec3 c) {
319 const double scaleLen = std::max(std::abs(a.x) + std::abs(b.y) + std::abs(c.z), 1.0);
320 const double tol = 1e-10 * scaleLen;
321 return std::abs(a.y) <= tol && std::abs(a.z) <= tol && std::abs(b.z) <= tol &&
322 std::abs(b.x) <= 0.5 * std::abs(a.x) + tol &&
323 std::abs(c.x) <= 0.5 * std::abs(a.x) + tol &&
324 std::abs(c.y) <= 0.5 * std::abs(b.y) + tol;
325}
326
327struct Cached {
328 double key[6]{};
329 Obtuse s{};
330 bool engineStart = false;
331 bool filled = false;
332};
333
334inline bool sameKey(const double *a, const double *b) {
335 for (int i = 0; i < 6; i++) {
336 if (a[i] != b[i]) {
337 return false;
338 }
339 }
340 return true;
341}
342
343inline const Cached &cachedBasis(double lx, double ly, double lz, double xy, double xz,
344 double yz) {
345 thread_local Cached slots[4];
346 thread_local int hand = 0;
347 const double key[6] = {lx, ly, lz, xy, xz, yz};
348 for (const Cached &slot : slots) {
349 if (slot.filled && sameKey(slot.key, key)) {
350 return slot;
351 }
352 }
353 const int i = hand;
354 hand = (hand + 1) % 4;
355 Cached &slot = slots[i];
356 for (int k = 0; k < 6; k++) {
357 slot.key[k] = key[k];
358 }
359 const Vec3 a{lx, 0.0, 0.0};
360 const Vec3 b{xy, ly, 0.0};
361 const Vec3 c{xz, yz, lz};
362 slot.s = obtuseSuperbasis(a, b, c);
363 slot.engineStart = engineIsShort(a, b, c);
364 slot.filled = true;
365 return slot;
366}
367
368} // namespace
369
370// Cartesian displacement from (xj, yj, zj) to (xi, yi, zi) on the
371// recovered dump cell. `wrapped` is the fractional image of that
372// difference. The fractional vector is kept when it is not strictly
373// longer than the Selling image.
374inline std::array<double, 3>
375euclideanIfShorter(double lx, double ly, double lz, double xy, double xz, double yz,
376 const std::array<double, 3> &raw, const std::array<double, 3> &wrapped) {
377 const Cached &slot = cachedBasis(lx, ly, lz, xy, xz, yz);
378 const Vec3 y{raw[0], raw[1], raw[2]};
379 const Vec3 w{wrapped[0], wrapped[1], wrapped[2]};
380 const Vec3 euc = (slot.engineStart && slot.s.ok) ? descend(slot.s, w)
381 : closestDisplacement(slot.s, y);
382 const double f2 = n2(w);
383 const double e2 = n2(euc);
384 if (e2 + 1e-12 * (1.0 + f2) < f2) {
385 return {euc.x, euc.y, euc.z};
386 }
387 return wrapped;
388}
389
390} // namespace mic
391} // namespace gen
392
393#endif
std::array< double, 3 > euclideanIfShorter(double lx, double ly, double lz, double xy, double xz, double yz, const std::array< double, 3 > &raw, const std::array< double, 3 > &wrapped)
Small generic functions that are shared by all namespaces.