1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 package ffx.potential.nonbonded.octree;
39
40 import java.util.ArrayList;
41 import java.util.logging.Logger;
42 import org.apache.commons.lang3.BooleanUtils;
43
44
45
46
47
48 public class Octree {
49
50 private static final Logger logger = Logger.getLogger(Octree.class.getName());
51
52 private final ArrayList<OctreeCell> leaves = new ArrayList<>();
53
54
55
56
57 private final int nCritical;
58
59 private final ArrayList<OctreeParticle> particles;
60
61 private final double theta;
62
63 private ArrayList<OctreeCell> cells = new ArrayList<>();
64
65
66
67
68
69
70
71 public Octree(ArrayList<OctreeParticle> particles) {
72 this.particles = particles;
73 this.nCritical = 10;
74 this.theta = 0.5;
75 }
76
77
78
79
80
81
82
83 public Octree(int nCritical, ArrayList<OctreeParticle> particles) {
84 this.nCritical = nCritical;
85 this.particles = particles;
86 this.theta = 0.5;
87 }
88
89
90
91
92
93
94
95
96 public Octree(int nCritical, ArrayList<OctreeParticle> particles, double theta) {
97 this.nCritical = nCritical;
98 this.particles = particles;
99 this.theta = theta;
100 }
101
102
103
104
105
106
107
108 public void addChild(int octant, int p) {
109 OctreeCell tempCell = new OctreeCell(nCritical);
110
111
112
113 cells.add(tempCell);
114
115
116 int c = cells.size() - 1;
117
118
119 cells.get(c).setR((cells.get(p).getR()) * 0.5);
120 cells.get(c).setX((cells.get(p).getX()) * ((octant & 1) * 2 - 1));
121 cells.get(c).setY((cells.get(p).getY()) * ((octant & 2) - 1));
122 cells.get(c).setZ((cells.get(p).getZ()) * ((octant & 4) * 0.5 - 1));
123
124
125 cells.get(c).setParentIndex(p);
126 cells.get(c).setChildren(octant, c);
127 cells.get(c).setnChild(cells.get(p).getnChild() | (1 << octant));
128 }
129
130
131
132
133
134
135 public void buildTree(OctreeCell root) {
136
137 cells = new ArrayList<>();
138
139
140 cells.add(root);
141
142
143 int n = particles.size();
144
145 for (int i = 0; i < n; i++) {
146 int current = 0;
147
148 while (cells.get(current).getNumLeaves() >= nCritical) {
149 cells.get(current).setNumLeaves(cells.get(current).getNumLeaves() + 1);
150 int octX = 0;
151 int octY = 0;
152 int octZ = 0;
153
154 if (particles.get(i).getX() > cells.get(current).getX()) {
155 octX = 1;
156 }
157 if (particles.get(i).getY() > cells.get(current).getY()) {
158 octY = 1;
159 }
160 if (particles.get(i).getZ() > cells.get(current).getZ()) {
161 octZ = 1;
162 }
163
164
165 int octant = octX + (octY << 1) + (octZ << 2);
166
167
168 boolean noChildInOctant =
169 BooleanUtils.toBoolean(cells.get(current).getnChild() & (1 << octant));
170 if (noChildInOctant) {
171 addChild(octant, current);
172 }
173
174 current = cells.get(current).getChildAtIndex(octant);
175 }
176
177
178 cells.get(current).setLeaf(cells.get(current).getNumLeaves(), i);
179 cells.get(current).setNumLeaves(cells.get(current).getNumLeaves() + 1);
180
181
182 if (cells.get(current).getNumLeaves() >= nCritical) {
183 splitCell(current);
184 }
185 }
186
187
188 }
189
190
191 public void directSum() {
192 for (int i = 0; i < particles.size(); i++) {
193 for (int j = 0; j < particles.size(); j++) {
194 if (j != i) {
195 double r = particles.get(i).distance(particles.get(j));
196 particles.get(j).addToPhi(particles.get(j).getCharge() / r);
197 }
198 }
199 }
200
201 for (OctreeParticle particle : particles) {
202 particle.addToPhi(0);
203 }
204 }
205
206
207
208
209
210
211
212
213 public double distance(double[] array, OctreePoint point) {
214 return Math.sqrt(
215 Math.pow((array[0] - point.getX()), 2)
216 + Math.pow((array[1] - point.getY()), 2)
217 + Math.pow((array[2] - point.getZ()), 2));
218 }
219
220
221 public void evalPotnetial() {
222 for (int i = 0; i < particles.size(); i++) {
223 evalAtTarget(0, i);
224 }
225 }
226
227
228
229
230
231
232
233 public void l2Error(double[] phiDirect, double[] phiTree) {
234 double errorSumNum = 0.0;
235 double errorSumDenom = 0.0;
236 for (int i = 0; i < phiDirect.length; i++) {
237 errorSumNum = errorSumNum + Math.pow((phiDirect[i] - phiTree[i]), 2);
238 errorSumDenom = errorSumDenom + Math.pow(phiDirect[i], 2);
239 }
240 double error = Math.sqrt(errorSumNum / errorSumDenom);
241 logger.info("L2 Norm Error: " + error);
242 }
243
244
245 public void upwardSweep() {
246 for (int c = (cells.size() - 1); c > 0; c--) {
247 int p = cells.get(c).getParentIndex();
248 M2M(p, c);
249 }
250 }
251
252
253
254
255
256
257 private void splitCell(int p) {
258 for (int i = 0; i < nCritical; i++) {
259 int octX = 0;
260 int octY = 0;
261 int octZ = 0;
262
263 if (particles.get(i).getX() > cells.get(p).getX()) {
264 octX = 1;
265 }
266 if (particles.get(i).getY() > cells.get(p).getY()) {
267 octY = 1;
268 }
269 if (particles.get(i).getZ() > cells.get(p).getZ()) {
270 octZ = 1;
271 }
272
273
274 int octant = octX + (octY << 1) + (octZ << 2);
275
276
277 boolean noChildInOctant = BooleanUtils.toBoolean(cells.get(p).getnChild() & (1 << octant));
278 if (noChildInOctant) {
279 addChild(octant, p);
280 }
281
282
283 int c = cells.get(p).getChildAtIndex(octant);
284 cells.get(c).setLeaf(cells.get(c).getNumLeaves(), 1);
285 cells.get(c).setNumLeaves(cells.get(c).getNumLeaves() + 1);
286
287
288 if (cells.get(c).getNumLeaves() >= nCritical) {
289 splitCell(c);
290 }
291 }
292 }
293
294
295
296
297
298
299
300 private void getMultipole(int p, ArrayList<Integer> leaves) {
301
302 if (cells.get(p).getNumLeaves() >= nCritical) {
303 for (int c = 0; c < 8; c++) {
304 if (BooleanUtils.toBoolean(cells.get(p).getnChild() & (1 << c))) {
305 getMultipole(cells.get(p).getChildAtIndex(c), leaves);
306 }
307 }
308 } else {
309
310 for (int i = 0; i < cells.get(p).getNumLeaves(); i++) {
311 int l = cells.get(p).getLeavesValueAtIndex(i);
312 double dx = cells.get(p).getX() - particles.get(l).getX();
313 double dy = cells.get(p).getY() - particles.get(l).getY();
314 double dz = cells.get(p).getZ() - particles.get(l).getZ();
315
316
317 double charge = particles.get(l).getCharge();
318 double[] calculatedMultipole = new double[10];
319
320 calculatedMultipole[0] = charge;
321
322 calculatedMultipole[1] = dx * charge;
323 calculatedMultipole[2] = dy * charge;
324 calculatedMultipole[3] = dz * charge;
325
326 calculatedMultipole[4] = (Math.pow(dx, 2) * 0.5) * charge;
327 calculatedMultipole[5] = (Math.pow(dy, 2) * 0.5) * charge;
328 calculatedMultipole[6] = (Math.pow(dz, 2) * 0.5) * charge;
329 calculatedMultipole[7] = ((dx * dy) * 0.5) * charge;
330 calculatedMultipole[8] = ((dy * dz) * 0.5) * charge;
331 calculatedMultipole[9] = ((dz * dx) * 0.5) * charge;
332
333
334 cells.get(p).addToMultipole(calculatedMultipole);
335
336
337 leaves.add(p);
338 }
339 }
340 }
341
342
343
344
345
346
347
348 private void M2M(int p, int c) {
349 double dx = cells.get(p).getX() - cells.get(c).getX();
350 double dy = cells.get(p).getY() - cells.get(c).getY();
351 double dz = cells.get(p).getZ() - cells.get(c).getZ();
352
353 double[] Dxyz = new double[] {dx, dy, dz};
354 double[] Dyzx = new double[] {dy, dz, dx};
355
356 cells.get(p).addToMultipole(cells.get(c).getMultipole());
357
358 double[] currentChildMultipole = cells.get(c).getMultipole();
359
360
361 double[] additionalMultipoleTerms = new double[10];
362
363 additionalMultipoleTerms[0] = 0;
364
365 additionalMultipoleTerms[1] = currentChildMultipole[0] * Dxyz[0];
366 additionalMultipoleTerms[2] = currentChildMultipole[0] * Dxyz[1];
367 additionalMultipoleTerms[3] = currentChildMultipole[0] * Dxyz[2];
368
369 additionalMultipoleTerms[4] =
370 currentChildMultipole[1] * Dxyz[0] + 0.5 * currentChildMultipole[0] * Math.pow(Dxyz[0], 2);
371 additionalMultipoleTerms[5] =
372 currentChildMultipole[2] * Dxyz[1] + 0.5 * currentChildMultipole[0] * Math.pow(Dxyz[1], 2);
373 additionalMultipoleTerms[6] =
374 currentChildMultipole[3] * Dxyz[2] + 0.5 * currentChildMultipole[0] * Math.pow(Dxyz[2], 2);
375
376 additionalMultipoleTerms[7] =
377 0.5 * currentChildMultipole[2] * Dyzx[0]
378 + 0.5 * currentChildMultipole[1] * Dxyz[0]
379 + 0.5 * currentChildMultipole[0] * Dxyz[0] * Dyzx[0];
380 additionalMultipoleTerms[8] =
381 0.5 * currentChildMultipole[3] * Dyzx[1]
382 + 0.5 * currentChildMultipole[2] * Dxyz[1]
383 + 0.5 * currentChildMultipole[0] * Dxyz[1] * Dyzx[1];
384 additionalMultipoleTerms[9] =
385 0.5 * currentChildMultipole[1] * Dyzx[2]
386 + 0.5 * currentChildMultipole[3] * Dxyz[2]
387 + 0.5 * currentChildMultipole[0] * Dxyz[2] * Dyzx[2];
388
389 cells.get(p).addToMultipole(additionalMultipoleTerms);
390 }
391
392
393
394
395
396
397
398 private void evalAtTarget(int p, int i) {
399
400
401 if (cells.get(p).getNumLeaves() >= nCritical) {
402
403
404 for (int oct = 0; oct < 8; oct++) {
405 if (BooleanUtils.toBoolean(cells.get(p).getnChild() & (1 << oct))) {
406 int c = cells.get(p).getChildAtIndex(oct);
407 double r = particles.get(i).distance(cells.get(c));
408
409
410 if (cells.get(c).getR() > theta * r) {
411 evalAtTarget(c, i);
412 } else {
413 double dx = particles.get(i).getX() - cells.get(c).getX();
414 double dy = particles.get(i).getY() - cells.get(c).getY();
415 double dz = particles.get(i).getZ() - cells.get(c).getZ();
416 double r3 = Math.pow(r, 3);
417 double r5 = r3 * Math.pow(r, 2);
418
419
420 double[] weight = new double[10];
421 weight[0] = 1 / r;
422 weight[1] = -dx / r3;
423 weight[2] = -dy / r3;
424 weight[3] = -dz / r3;
425 weight[4] = (3 * Math.pow(dx, 2)) / r5 - (1 / r3);
426 weight[5] = (3 * Math.pow(dy, 2)) / r5 - (1 / r3);
427 weight[6] = (3 * Math.pow(dz, 2)) / r5 - (1 / r3);
428 weight[7] = 3 * dx * dy / r5;
429 weight[8] = 3 * dy * dz / r5;
430 weight[9] = 3 * dz * dx / r5;
431
432
433 double dotProduct = 0.0;
434 for (int d = 0; d < weight.length; d++) {
435 double[] multipoleArray = cells.get(c).getMultipole();
436 dotProduct = dotProduct + multipoleArray[d] * weight[d];
437 }
438
439 particles.get(i).addToPhi(dotProduct);
440 }
441 } else {
442
443 for (int j = 0; j < cells.get(p).getNumLeaves(); j++) {
444 OctreeParticle source = particles.get(cells.get(p).getLeavesValueAtIndex(j));
445 double r = particles.get(i).distance(source);
446 if (r != 0) {
447 particles.get(i).addToPhi(source.getCharge() / r);
448 }
449 }
450 }
451 }
452 }
453 }
454 }