algorithm - 非凸 3d 模型算法

Question

我有 3d 点云（浮雕），我需要一个创建非凸 3d 模型的简单算法。你可以帮帮我吗？

Answer 1

一种快速且相当容易实现的算法，用于在点（外部和内部！）周围获得一个体面的三角形外壳，它基于“Marching Cubes”算法：

• 定义一个网格（最小 x,y,z 值 + x,y,z 方向上的网格分辨率 + x,y,z 方向上的点数）
• 将每个网格点的值初始化为零
• “栅格化”给定点（将坐标四舍五入到最近的网格点）；对于普通版本，只需将相应网格点的值设置为 1
• 现在，您可以使用“Marching Cubes”算法对网格的每个基本立方体进行多边形化，isolevel其中0.9.

这些代码片段可能会对您有所帮助。对于初始化：

union XYZ {
    struct {
        double x,y,z;
    };
    double coord[3];
};
typedef std::vector<XYZ> TPoints;
TPoints points;
// get points from file or another data structure

// initialize these values for your needs (the bounding box of the points will help)    
XYZ coordsMin, coordsMax;
XYZ voxelSize; // grid resolution in each coordinate direction
int gridSize; // number of grid points, here the same for each coordinate direction

int gridSize2 = gridSize*gridSize;
char* gridVals = new char[gridSize2*gridSize];
for (int i=0; i<gridSize; ++i)
for (int j=0; j<gridSize; ++j)
for (int k=0; k<gridSize; ++k)
    gridVals[i*gridSize2+j*gridSize+k] = 0;

for (size_t i=0; i<points,size(); ++i)
{
    XYZ const& p = points[i];
    int gridCoords[3];
    for (int c=0; c<3; ++c)
        gridCoords[c] = (int)((p.coord[c]-coordsMin.coord[c])/voxelSize.coord[c]);
    int gridIdx = gridCoords[0]*gridSize2 + gridCoords[1]*gridSize + gridCoords[2];
    gridVals[gridIdx] = 1;
}

Polygonize然后根据引用的实现中的函数计算三角形：

const double isolevel = 0.9;

TRIANGLE triangles[5]; // maximally 5 triangles for each voxel
int cellCnt = 0;
for (int i=0; exportOk && i<gridSize-1; ++i)
for (int j=0; exportOk && j<gridSize-1; ++j)
for (int k=0; exportOk && k<gridSize-1; ++k)
{
    GRIDCELL cell;
    for (int cornerIdx=0; cornerIdx<8; ++cornerIdx)
    {
        XYZ& corner = cell.p[cornerIdx];
        // the function Polygonize expects this strange order of corner indexing ...
        // (see http://paulbourke.net/geometry/polygonise/)
        int xoff = ((cornerIdx+1)/2)%2;
        int yoff = (cornerIdx/2)%2;
        int zoff = cornerIdx/4;
        corner.x = (i+xoff)*voxelSize.x + coordsMin.x;
        corner.y = (j+yoff)*voxelSize.y + coordsMin.y;
        corner.z = (k+zoff)*voxelSize.z + coordsMin.z;
        cell.val[cornerIdx] = gridVals[(i+xoff)*gridSize2+(j+yoff)*gridSize+k+zoff];
    }
    int triangCnt = Polygonise(cell, isolevel, triangles);
    triangCntTotal += triangCnt;
    triangCntTotal += triangCnt;
    for (int t=0; t<triangCnt; ++t)
    {
        TTriangle const& triangle = triangles[t].p;
        ExportTriangle(triangle);
    }
}

这在工业应用中对我有用。