<p>I am trying to solve numerically a set of partial differential equations in three dimensions. In each of the equations the next value of the unknown in a point depends on the current value of each unknown in the closest points.</p>

<p>To write an efficient code I need to keep the points close in the three dimensions close in the (one-dimensional) memory space, so that each value is called from memory just once.</p>

<p>I was thinking of using octtrees, but I was wondering if someone knows a better method.</p>

[{'answer_id': 76185, 'author': 'Adam Rosenfield', 'author_id': 9530, 'author_profile': 'https://Stackoverflow.com/users/9530', 'pm_score': 4, 'selected': True, 'text': '<p>Octtrees are the way to go.  You subdivide the array into 8 octants:</p>\n\n<pre>\n1 2\n3 4\n\n---\n\n5 6\n7 8\n</pre>\n\n<p>And then lay them out in memory in the order 1, 2, 3, 4, 5, 6, 7, 8 as above.  You repeat this recursively within each octant until you get down to some base size, probably around 128 bytes or so (this is just a guess -- make sure to profile to determine the optimal cutoff point).  This has much, much better cache coherency and locality of reference than the naive layout.</p>\n'}, {'answer_id': 76767, 'author': 'palm3D', 'author_id': 2686, 'author_profile': 'https://Stackoverflow.com/users/2686', 'pm_score': 2, 'selected': False, 'text': '<p>The book <a href="https://rads.stackoverflow.com/amzn/click/com/0123694469" rel="nofollow noreferrer" rel="nofollow noreferrer">Foundations of Multidimensional and Metric Data Structures</a> can help you decide which data structure is fastest for range queries: octrees, kd-trees, R-trees, ...\nIt also describes data layouts for keeping points together in memory.</p>\n'}, {'answer_id': 83362, 'author': 'Nils Pipenbrinck', 'author_id': 15955, 'author_profile': 'https://Stackoverflow.com/users/15955', 'pm_score': 3, 'selected': False, 'text': "<p>One alternative to the tree-method: Use the Morton-Order to encode your data.</p>\n\n<p>In three dimension it goes like this: Take the coordinate components and interleave each bit two zero bits. Here shown in binary: 11111b becomes 1001001001b</p>\n\n<p>A C-function to do this looks like this (shown for clarity and only for 11 bits):</p>\n\n<pre><code>int morton3 (int a)\n{\n  int result = 0;\n  int i;\n  for (i=0; i&lt;11; i++)\n  {\n     // check if the i'th bit is set.\n     int bit = a&amp;(1&lt;&lt;i);\n     if (bit)\n     {\n       // if so set the 3*i'th bit in the result:\n       result |= 1&lt;&lt;(i*3);\n     }\n  }\n  return result;\n}\n</code></pre>\n\n<p>You can use this function to combine your positions like this:</p>\n\n<pre><code>index = morton3 (position.x) + \n        morton3 (position.y)*2 +\n        morton3 (position.z)*4;\n</code></pre>\n\n<p>This turns your three dimensional index into a one dimensional one. Best part of it: Values that are close in 3D space are close in 1D space as well. If you access values close to each other frequently you will also get a very nice speed-up because the morton-order encoding is optimal in terms of cache locality.</p>\n\n<p>For morton3 you better not use the code above. Use a small table to look up 4 or 8 bits at a time and combine them together. </p>\n\n<p>Hope it helps,\n  Nils</p>\n"}]
['https://Stackoverflow.com/questions/76076', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/13405/']