我正在尝试数值解三维偏微分方程组。在每个方程中,点的下一个未知值取决于最近点中每个未知量的当前值。
为了编写高效的代码,我需要将在三个维度上靠近的点保持在(一维)内存空间中靠近,以便每个值只需从内存中调用一次。
我考虑使用八叉树,但我想知道是否有更好的方法。
为了编写高效的代码,我需要将在三个维度上靠近的点保持在(一维)内存空间中靠近,以便每个值只需从内存中调用一次。
我考虑使用八叉树,但我想知道是否有更好的方法。
一种替代树状结构的方法是:使用Morton-Order对数据进行编码。
在三维空间中,它的实现方式如下:取坐标分量,然后交错插入两个零位。下面以二进制形式展示:11111b变成了1001001001b。
一个执行这种操作的C函数如下所示(仅展示11位):
int morton3 (int a)
{
int result = 0;
int i;
for (i=0; i<11; i++)
{
// check if the i'th bit is set.
int bit = a&(1<<i);
if (bit)
{
// if so set the 3*i'th bit in the result:
result |= 1<<(i*3);
}
}
return result;
}
index = morton3 (position.x) +
morton3 (position.y)*2 +
morton3 (position.z)*4;
1 2 3 4然后按照上面的顺序在内存中排列它们,即1、2、3、4、5、6、7、8。在每个八分体内部递归地重复此过程,直到达到某个基本大小,大约为128字节左右(这只是一个猜测,请务必进行性能测试以确定最佳截止点)。这种布局比朴素布局具有更好的缓存协同性和引用局部性。
---
5 6 7 8