行进立方体问题
Marching Cubes Issues
我一直在尝试用 C++ 和 Qt 实现行进立方体算法。不管怎样,到目前为止所有的步骤都已经写好了,但是我得到了一个非常糟糕的结果。我正在寻找有关可能出错的方向或建议。我怀疑其中一个问题可能与 体素概念 有关,特别是关于哪个顶点进入哪个角 (0, 1, ..., 7)。此外,我不是 100% 确定如何解释算法的输入(我使用的是数据集)。 我应该按照ZYX的顺序阅读它并以同样的方式移动行进立方体还是完全没有关系? (抛开并非每个维度都必须具有相同大小的事实)。
这是我反对它应该是什么样子的...
http://en.wikipedia.org/wiki/Marching_cubes
http://en.wikipedia.org/wiki/Marching_cubes#External_links
保罗伯克。 "Overview and source code".
http://paulbourke.net/geometry/polygonise/
Qt_MARCHING_CUBES.zip:Qt/OpenGL 示例由 Klaus Miltenberger 博士提供。
http://paulbourke.net/geometry/polygonise/Qt_MARCHING_CUBES.zip
该示例需要 boost,但看起来应该可以。
在他的示例中,它在 marchingcubes.cpp
中有几种不同的计算行进立方体的方法:vMarchCube1
和 vMarchCube2
。
在评论中它说 vMarchCube2
通过对 vMarchTetrahedron 进行六次调用,在单个立方体上执行 Marching Tetrahedrons 算法。
下面是第一个的来源vMarchCube1
:
//vMarchCube1 performs the Marching Cubes algorithm on a single cube
GLvoid GL_Widget::vMarchCube1(const GLfloat &fX, const GLfloat &fY, const GLfloat &fZ, const GLfloat &fScale, const GLfloat &fTv)
{
GLint iCorner, iVertex, iVertexTest, iEdge, iTriangle, iFlagIndex, iEdgeFlags;
GLfloat fOffset;
GLvector sColor;
GLfloat afCubeValue[8];
GLvector asEdgeVertex[12];
GLvector asEdgeNorm[12];
//Make a local copy of the values at the cube's corners
for(iVertex = 0; iVertex < 8; iVertex++)
{
afCubeValue[iVertex] = (this->*fSample)(fX + a2fVertexOffset[iVertex][0]*fScale,fY + a2fVertexOffset[iVertex][1]*fScale,fZ + a2fVertexOffset[iVertex][2]*fScale);
}
//Find which vertices are inside of the surface and which are outside
iFlagIndex = 0;
for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
{
if(afCubeValue[iVertexTest] <= fTv) iFlagIndex |= 1<<iVertexTest;
}
//Find which edges are intersected by the surface
iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
//If the cube is entirely inside or outside of the surface, then there will be no intersections
if(iEdgeFlags == 0)
{
return;
}
//Find the point of intersection of the surface with each edge
//Then find the normal to the surface at those points
for(iEdge = 0; iEdge < 12; iEdge++)
{
//if there is an intersection on this edge
if(iEdgeFlags & (1<<iEdge))
{
fOffset = fGetOffset(afCubeValue[ a2iEdgeConnection[iEdge][0] ],afCubeValue[ a2iEdgeConnection[iEdge][1] ], fTv);
asEdgeVertex[iEdge].fX = fX + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][0] + fOffset * a2fEdgeDirection[iEdge][0]) * fScale;
asEdgeVertex[iEdge].fY = fY + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][1] + fOffset * a2fEdgeDirection[iEdge][1]) * fScale;
asEdgeVertex[iEdge].fZ = fZ + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][2] + fOffset * a2fEdgeDirection[iEdge][2]) * fScale;
vGetNormal(asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
}
}
//Draw the triangles that were found. There can be up to five per cube
for(iTriangle = 0; iTriangle < 5; iTriangle++)
{
if(a2iTriangleConnectionTable[iFlagIndex][3*iTriangle] < 0) break;
for(iCorner = 0; iCorner < 3; iCorner++)
{
iVertex = a2iTriangleConnectionTable[iFlagIndex][3*iTriangle+iCorner];
vGetColor(sColor, asEdgeVertex[iVertex], asEdgeNorm[iVertex]);
glColor4f(sColor.fX, sColor.fY, sColor.fZ, 0.6);
glNormal3f(asEdgeNorm[iVertex].fX, asEdgeNorm[iVertex].fY, asEdgeNorm[iVertex].fZ);
glVertex3f(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ);
}
}
}
更新:Github 工作示例,已测试
https://github.com/peteristhegreat/qt-marching-cubes
希望对您有所帮助。
终于找到问题了
我使用 VBO 索引器 class 来减少重复顶点的数量并使渲染速度更快。这个 class 是通过 std::map 实现的,使用 unsigned short > 的元组来查找和丢弃已经存在的顶点。正如您想象的那样,行进立方体算法生成具有数千甚至数百万个顶点的结构。普通 unsigned short 可以容纳的最大数字是 65536,或 2^16。因此,当输出几何体超过这个数量时,地图索引开始溢出,结果一团糟,因为它开始用新的顶点覆盖顶点。我只是更改了我的实现以使用普通 VBO 绘制并且在我修复 class 以支持数百万个顶点时未编制索引。
结果不言而喻,有一些小的顶点法线问题:
http://i61.tinypic.com/fep2t3.jpg
我一直在尝试用 C++ 和 Qt 实现行进立方体算法。不管怎样,到目前为止所有的步骤都已经写好了,但是我得到了一个非常糟糕的结果。我正在寻找有关可能出错的方向或建议。我怀疑其中一个问题可能与 体素概念 有关,特别是关于哪个顶点进入哪个角 (0, 1, ..., 7)。此外,我不是 100% 确定如何解释算法的输入(我使用的是数据集)。 我应该按照ZYX的顺序阅读它并以同样的方式移动行进立方体还是完全没有关系? (抛开并非每个维度都必须具有相同大小的事实)。
这是我反对它应该是什么样子的...
http://en.wikipedia.org/wiki/Marching_cubes
http://en.wikipedia.org/wiki/Marching_cubes#External_links
保罗伯克。 "Overview and source code".
http://paulbourke.net/geometry/polygonise/
Qt_MARCHING_CUBES.zip:Qt/OpenGL 示例由 Klaus Miltenberger 博士提供。
http://paulbourke.net/geometry/polygonise/Qt_MARCHING_CUBES.zip
该示例需要 boost,但看起来应该可以。
在他的示例中,它在 marchingcubes.cpp
中有几种不同的计算行进立方体的方法:vMarchCube1
和 vMarchCube2
。
在评论中它说 vMarchCube2
通过对 vMarchTetrahedron 进行六次调用,在单个立方体上执行 Marching Tetrahedrons 算法。
下面是第一个的来源vMarchCube1
:
//vMarchCube1 performs the Marching Cubes algorithm on a single cube
GLvoid GL_Widget::vMarchCube1(const GLfloat &fX, const GLfloat &fY, const GLfloat &fZ, const GLfloat &fScale, const GLfloat &fTv)
{
GLint iCorner, iVertex, iVertexTest, iEdge, iTriangle, iFlagIndex, iEdgeFlags;
GLfloat fOffset;
GLvector sColor;
GLfloat afCubeValue[8];
GLvector asEdgeVertex[12];
GLvector asEdgeNorm[12];
//Make a local copy of the values at the cube's corners
for(iVertex = 0; iVertex < 8; iVertex++)
{
afCubeValue[iVertex] = (this->*fSample)(fX + a2fVertexOffset[iVertex][0]*fScale,fY + a2fVertexOffset[iVertex][1]*fScale,fZ + a2fVertexOffset[iVertex][2]*fScale);
}
//Find which vertices are inside of the surface and which are outside
iFlagIndex = 0;
for(iVertexTest = 0; iVertexTest < 8; iVertexTest++)
{
if(afCubeValue[iVertexTest] <= fTv) iFlagIndex |= 1<<iVertexTest;
}
//Find which edges are intersected by the surface
iEdgeFlags = aiCubeEdgeFlags[iFlagIndex];
//If the cube is entirely inside or outside of the surface, then there will be no intersections
if(iEdgeFlags == 0)
{
return;
}
//Find the point of intersection of the surface with each edge
//Then find the normal to the surface at those points
for(iEdge = 0; iEdge < 12; iEdge++)
{
//if there is an intersection on this edge
if(iEdgeFlags & (1<<iEdge))
{
fOffset = fGetOffset(afCubeValue[ a2iEdgeConnection[iEdge][0] ],afCubeValue[ a2iEdgeConnection[iEdge][1] ], fTv);
asEdgeVertex[iEdge].fX = fX + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][0] + fOffset * a2fEdgeDirection[iEdge][0]) * fScale;
asEdgeVertex[iEdge].fY = fY + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][1] + fOffset * a2fEdgeDirection[iEdge][1]) * fScale;
asEdgeVertex[iEdge].fZ = fZ + (a2fVertexOffset[ a2iEdgeConnection[iEdge][0] ][2] + fOffset * a2fEdgeDirection[iEdge][2]) * fScale;
vGetNormal(asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ);
}
}
//Draw the triangles that were found. There can be up to five per cube
for(iTriangle = 0; iTriangle < 5; iTriangle++)
{
if(a2iTriangleConnectionTable[iFlagIndex][3*iTriangle] < 0) break;
for(iCorner = 0; iCorner < 3; iCorner++)
{
iVertex = a2iTriangleConnectionTable[iFlagIndex][3*iTriangle+iCorner];
vGetColor(sColor, asEdgeVertex[iVertex], asEdgeNorm[iVertex]);
glColor4f(sColor.fX, sColor.fY, sColor.fZ, 0.6);
glNormal3f(asEdgeNorm[iVertex].fX, asEdgeNorm[iVertex].fY, asEdgeNorm[iVertex].fZ);
glVertex3f(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ);
}
}
}
更新:Github 工作示例,已测试
https://github.com/peteristhegreat/qt-marching-cubes
希望对您有所帮助。
终于找到问题了
我使用 VBO 索引器 class 来减少重复顶点的数量并使渲染速度更快。这个 class 是通过 std::map 实现的,使用
结果不言而喻,有一些小的顶点法线问题: http://i61.tinypic.com/fep2t3.jpg