algorithm - 非凸 3D モデル アルゴリズム

Question

3D ポイント (レリーフ) の雲があり、凸でない 3D モデルを作成する単純なアルゴリズムが必要です。私たちを手伝ってくれますか？

Answer 1

ポイントの周り (外側と内側!) の適切な三角形のハルを取得するための、すばやく簡単に実装できるアルゴリズムは、 「マーチング キューブ」アルゴリズムに基づいています。

• グリッドを定義します (最小 x,y,z 値 + x,y,z 方向のグリッド解像度 + x,y,z 方向のポイント数)
• 各グリッド ポイントの値をゼロに初期化する
• 指定されたポイントを「ラスタライズ」します (座標を最も近いグリッド ポイントに丸めます)。単純なバージョンでは、対応するグリッド ポイントの値を 1 に設定するだけです
• これで、グリッドの各基本立方体を の「マーチング キューブ」アルゴリズムでポリゴン化でき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);
    }
}

これは、産業用アプリケーションで私にとってはうまくいきました。