c++ - 任何快速有效的方式来生成 3D 网格？

Question

除了使用通过 3 个“for()”循环的标准方法之外，是否有更快更有效的方法来生成 3D 网格？我没有使用 VTK、OpenGL、TetGen、CGAL 或任何其他复杂的库……只是基本的 C++ 软件，即 CodeBlocks。我的代码如下所示:

#define Dimension 3
#define N_face 5000
struct Point{ float value[Dimension];};

struct Cube{ Point p1, p2, p3, p4, p5, p6, p7, p8;};

int main()
{
    Cube* Grid = (Cube*) malloc(N_face*sizeof(Cube));
    int m=0;
    /*......*/
    delta = ....
    for(int i=0; i<nx; ++i)
    {
        z = i*delta + ....
        for(int j=0; j<ny; ++j)
        {
            y = j*delta + ....
            for(int k=0; k<nz; ++k)
            {
                x = k*delta + ....
                Grid[m].p1= {{x,       y,       z}};
                Grid[m].p2= {{x+delta, y,       z}};
                Grid[m].p3= {{x,       y+delta, z}};
                Grid[m].p4= {{x+delta, y+delta, z}};
                Grid[m].p5= {{x,       y,       z+delta}};
                Grid[m].p6= {{x+delta, y,       z+delta}};
                Grid[m].p7= {{x,       y+delta, z+delta}};
                Grid[m].p8= {{x+delta, y+delta, z+delta}};
                m++;
            }
        }
    }
    /*......*/
}

在上面的代码中，x, y, z, delta 是 float 值，计算这些值是为了将网格大小缩放到某个输入几何体。我目前正在使用这个网格，来检查网格点和多边形的交叉点(内部/外部)(指的是多边形内部/外部点的算法[http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf])我已经设法完成了程序并获得了预期结果，但运行它需要很长时间，因为我要处理数千个点。因此，现在我正在努力改进编码......真的需要你的帮助......T.T

Answer 1

首先，如果您的代码已经运行缓慢只有几千点，我认为这是一个错误，即使我不能立即发现您的代码有任何问题......

关于优化: 如果您必须访问大量元素，可以通过两种方式提高性能:内存访问优化和并行性。

第一个是确保您始终以 block 为单位读/写内存，而不是在遥远的地址之间跳来跳去。这减少了将新页面加载到缓存中所损失的时间。 但是:在您的示例中，您已经通过编写 Grid[m] = ...; 顺序写入内存； m++;，所以这已经是最优的了。

第二种方法是使用 SIMD 指令:SSE 允许您同时写入多个浮点值，从而加快您的进程。

#include <xmmintrin.h>
...
__m128 your_first_four_floats  = _mm_set_ps (a, b, c, d);
__m128 your_second_four_floats = _mm_set_ps (e, f, g, h);
...
_mm_store_ps(((float*)&Grid[m])+0,your_first_four_floats);
_mm_store_ps(((float*)&Grid[m])+4,your_second_four_floats);
...

这是一个非常蹩脚的例子，所以请不要当真。您可以找到更好的方法来轻松产生您的值(value)! 还要确保您分配的内存是 16 字节对齐的(在 64 位代码中应该是默认值，在 32 位代码中您需要使用 _aligned_malloc(bytes, 16))。否则，您将不得不使用速度较慢的 _mm_storeu_ps。

如果你有一个多核 CPU(通常是现在的标准)，你也可以使用多个线程来生成值，但为此你需要一些线程库或一个相当新版本的 C++ (C++11)并不总是支持。此外，如果内存访问是您的瓶颈，这不一定会给您任何加速。