C++實現(xiàn)移動立方體示例講解
本文描述了一個創(chuàng)建三維標量場等值面多邊形曲面表示的算法。這類問題的一個常見名稱是所謂的“移動立方體”算法。它結合了簡單和高速,因為它幾乎完全用于查找表。
這種技術有很多應用,兩個非常常見的是:
從醫(yī)學體積數(shù)據(jù)集重建表面。例如,MRI掃描在常規(guī)3d網(wǎng)格的頂點處產(chǎn)生一個3d體積的樣本。
創(chuàng)建數(shù)學標量場的三維輪廓。在這種情況下,函數(shù)是已知的,但在一個常規(guī)的3D網(wǎng)格的頂點采樣。
1.解決方案
其基本問題是通過在矩形三維網(wǎng)格上采樣的標量場形成一個面逼近等值面。給定一個由頂點和每個頂點的標量值定義的網(wǎng)格單元,有必要創(chuàng)建通過該網(wǎng)格單元最能代表等值面的平面facet。等值面可能不會穿過網(wǎng)格單元格,它可能切斷任何一個頂點,或者它可能通過許多更復雜的方式中的任何一種。每一種可能性都將以等值面以上或以下值的頂點數(shù)來表征。如果一個頂點在等值面上,而另一個相鄰頂點在等值面上,那么我們就知道等值面上切割這兩個頂點之間的邊。它切割邊緣的位置將被線性插值,兩個頂點之間的長度之比將與等值面值與網(wǎng)格單元格頂點處值之比相同。
算法中使用的頂點和邊的索引約定如下所示
例如,如果頂點3的值低于等值面值,而所有其他頂點的值都高于等值面值,那么我們將創(chuàng)建一個三角形面,它穿過邊2、3和11。三角形面的頂點的確切位置分別取決于等值面值與頂點3-2、3-0、3-7上的值的關系。
使算法“困難”的是大量的可能組合(256個),以及需要為每個解決方案導出一致的facet組合,以便相鄰網(wǎng)格單元的facet正確地連接在一起。
算法的第一部分使用一個表(edgeTable),它將等值面下的頂點映射到相交的邊緣。一個8位的索引是由每個位對應一個頂點形成的。
cubeindex = 0;
if (grid.val[0] < isolevel) cubeindex |= 1;
if (grid.val[1] < isolevel) cubeindex |= 2;
if (grid.val[2] < isolevel) cubeindex |= 4;
if (grid.val[3] < isolevel) cubeindex |= 8;
if (grid.val[4] < isolevel) cubeindex |= 16;
if (grid.val[5] < isolevel) cubeindex |= 32;
if (grid.val[6] < isolevel) cubeindex |= 64;
if (grid.val[7] < isolevel) cubeindex |= 128;
查找邊緣表返回一個12位的數(shù)字,每一位對應一條邊,0表示該邊沒有被等值面切割,1表示該邊被等值面切割。如果沒有任何邊被切割,則表返回0,當cubeindex為0(等值面以下的所有頂點)或0xff(等值面以上的所有頂點)時就會發(fā)生這種情況。
使用前面的例子,只有頂點3低于等值面,cubeindex將等于0000 1000或8。edgeTable[8] = 1000 0000 1100。這意味著邊2,3和11與等值面相交。
交點現(xiàn)在由線性插值計算。如果P1和P2是切邊的兩個頂點,V1和V2是每個頂點的標量值,那么交點P是
P = P1 +(等值- V1) (P2 - P1) / (V2 - V1)
算法的最后一部分涉及到從等值面與網(wǎng)格單元的邊緣相交的位置形成正確的facet。同樣使用了一個表(triTable),這次使用相同的立方體索引,但允許查找頂點序列,因為在網(wǎng)格單元中表示等值面需要多少三角形面就需要多少三角形面。最多需要5個三角形面。
回到我們的例子,在前面的步驟中,我們計算了沿邊2、3和11的交點。triTable中的第8個元素是
{3、11、2、1,1,1,1,1,1,1,1,1,1,1,1,1},
這是一個特別簡單的示例,請確保facet組合對于表中的許多情況不是那么明顯。
2.舉例子
假設頂點0和3在等值面以下。Cubeindex將是0000 1001 == 9。進入egdeTable的第9項是905hex == 1001 0000 0101,這意味著邊11、8、2和0被切割,所以我們計算出等面與這些邊相交的頂點。
接下來,triitable中的9是0,11,2,8,11,0。這對應于兩個三角形面片,一個在邊0,11和2的交點之間。另一個在沿邊8 11和0的交點之間。
3.網(wǎng)格分辨率
當對一個值已知或可以在空間中任意位置插值的字段進行多邊形化時,一個非常理想的控制是采樣網(wǎng)格的分辨率。這允許根據(jù)所需的平滑度和/或顯示表面的處理能力生成等面的過程或精細近似。
4.源代碼
基于OpenGL繪制(VS可直接運行)
#include "stdio.h" #include "math.h" //This program requires the OpenGL and GLUT libraries // You can obtain them for free from http://www.opengl.org #include "GL/glut.h" struct GLvector { GLfloat fX; GLfloat fY; GLfloat fZ; }; //These tables are used so that everything can be done in little loops that you can look at all at once // rather than in pages and pages of unrolled code. //a2fVertexOffset lists the positions, relative to vertex0, of each of the 8 vertices of a cube static const GLfloat a2fVertexOffset[8][3] = { {0.0, 0.0, 0.0},{1.0, 0.0, 0.0},{1.0, 1.0, 0.0},{0.0, 1.0, 0.0}, {0.0, 0.0, 1.0},{1.0, 0.0, 1.0},{1.0, 1.0, 1.0},{0.0, 1.0, 1.0} }; //a2iEdgeConnection lists the index of the endpoint vertices for each of the 12 edges of the cube static const GLint a2iEdgeConnection[12][2] = { {0,1}, {1,2}, {2,3}, {3,0}, {4,5}, {5,6}, {6,7}, {7,4}, {0,4}, {1,5}, {2,6}, {3,7} }; //a2fEdgeDirection lists the direction vector (vertex1-vertex0) for each edge in the cube static const GLfloat a2fEdgeDirection[12][3] = { {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0}, {1.0, 0.0, 0.0},{0.0, 1.0, 0.0},{-1.0, 0.0, 0.0},{0.0, -1.0, 0.0}, {0.0, 0.0, 1.0},{0.0, 0.0, 1.0},{ 0.0, 0.0, 1.0},{0.0, 0.0, 1.0} }; //a2iTetrahedronEdgeConnection lists the index of the endpoint vertices for each of the 6 edges of the tetrahedron static const GLint a2iTetrahedronEdgeConnection[6][2] = { {0,1}, {1,2}, {2,0}, {0,3}, {1,3}, {2,3} }; //a2iTetrahedronEdgeConnection lists the index of verticies from a cube // that made up each of the six tetrahedrons within the cube static const GLint a2iTetrahedronsInACube[6][4] = { {0,5,1,6}, {0,1,2,6}, {0,2,3,6}, {0,3,7,6}, {0,7,4,6}, {0,4,5,6}, }; static const GLfloat afAmbientWhite [] = {0.25, 0.25, 0.25, 1.00}; static const GLfloat afAmbientRed [] = {0.25, 0.00, 0.00, 1.00}; static const GLfloat afAmbientGreen [] = {0.00, 0.25, 0.00, 1.00}; static const GLfloat afAmbientBlue [] = {0.00, 0.00, 0.25, 1.00}; static const GLfloat afDiffuseWhite [] = {0.75, 0.75, 0.75, 1.00}; static const GLfloat afDiffuseRed [] = {0.75, 0.00, 0.00, 1.00}; static const GLfloat afDiffuseGreen [] = {0.00, 0.75, 0.00, 1.00}; static const GLfloat afDiffuseBlue [] = {0.00, 0.00, 0.75, 1.00}; static const GLfloat afSpecularWhite[] = {1.00, 1.00, 1.00, 1.00}; static const GLfloat afSpecularRed [] = {1.00, 0.25, 0.25, 1.00}; static const GLfloat afSpecularGreen[] = {0.25, 1.00, 0.25, 1.00}; static const GLfloat afSpecularBlue [] = {0.25, 0.25, 1.00, 1.00}; GLenum ePolygonMode = GL_LINE; GLint iDataSetSize = 26; GLfloat fStepSize = 1.0/iDataSetSize; GLfloat fTargetValue = 48.0; GLfloat fTime = 0.0; GLvector sSourcePoint[3]; GLboolean bSpin = true; GLboolean bMove = true; GLboolean bLight = true; void vIdle(); void vDrawScene(); void vResize(GLsizei, GLsizei); void vKeyboard(unsigned char cKey, int iX, int iY); void vSpecial(int iKey, int iX, int iY); GLvoid vPrintHelp(); GLvoid vSetTime(GLfloat fTime); GLfloat fSample1(GLfloat fX, GLfloat fY, GLfloat fZ); GLfloat fSample2(GLfloat fX, GLfloat fY, GLfloat fZ); GLfloat fSample3(GLfloat fX, GLfloat fY, GLfloat fZ); GLfloat (*fSample)(GLfloat fX, GLfloat fY, GLfloat fZ) = fSample1; GLvoid vMarchingCubes(); GLvoid vMarchCube1(GLfloat fX, GLfloat fY, GLfloat fZ, GLfloat fScale); GLvoid vMarchCube2(GLfloat fX, GLfloat fY, GLfloat fZ, GLfloat fScale); GLvoid (*vMarchCube)(GLfloat fX, GLfloat fY, GLfloat fZ, GLfloat fScale) = vMarchCube1; void main(int argc, char **argv) { GLfloat afPropertiesAmbient [] = {0.50, 0.50, 0.50, 1.00}; GLfloat afPropertiesDiffuse [] = {0.75, 0.75, 0.75, 1.00}; GLfloat afPropertiesSpecular[] = {1.00, 1.00, 1.00, 1.00}; GLsizei iWidth = 640.0; GLsizei iHeight = 480.0; glutInit(&argc, argv); glutInitWindowPosition( 0, 0); glutInitWindowSize(iWidth, iHeight); glutInitDisplayMode( GLUT_RGB | GLUT_DEPTH | GLUT_DOUBLE ); glutCreateWindow( "Marching Cubes" ); glutDisplayFunc( vDrawScene ); glutIdleFunc( vIdle ); glutReshapeFunc( vResize ); glutKeyboardFunc( vKeyboard ); glutSpecialFunc( vSpecial ); glClearColor( 0.0, 0.0, 0.0, 1.0 ); glClearDepth( 1.0 ); glEnable(GL_DEPTH_TEST); glEnable(GL_LIGHTING); glPolygonMode(GL_FRONT_AND_BACK, ePolygonMode); glLightfv( GL_LIGHT0, GL_AMBIENT, afPropertiesAmbient); glLightfv( GL_LIGHT0, GL_DIFFUSE, afPropertiesDiffuse); glLightfv( GL_LIGHT0, GL_SPECULAR, afPropertiesSpecular); glLightModelf(GL_LIGHT_MODEL_TWO_SIDE, 1.0); glEnable( GL_LIGHT0 ); glMaterialfv(GL_BACK, GL_AMBIENT, afAmbientGreen); glMaterialfv(GL_BACK, GL_DIFFUSE, afDiffuseGreen); glMaterialfv(GL_FRONT, GL_AMBIENT, afAmbientBlue); glMaterialfv(GL_FRONT, GL_DIFFUSE, afDiffuseBlue); glMaterialfv(GL_FRONT, GL_SPECULAR, afSpecularWhite); glMaterialf( GL_FRONT, GL_SHININESS, 25.0); vResize(iWidth, iHeight); vPrintHelp(); glutMainLoop(); } GLvoid vPrintHelp() { printf("Marching Cubes Example by Cory Bloyd (dejaspaminacan@my-deja.com)\n\n"); printf("+/- increase/decrease sample density\n"); printf("PageUp/PageDown increase/decrease surface value\n"); printf("s change sample function\n"); printf("c toggle marching cubes / marching tetrahedrons\n"); printf("w wireframe on/off\n"); printf("l toggle lighting / color-by-normal\n"); printf("Home spin scene on/off\n"); printf("End source point animation on/off\n"); } void vResize( GLsizei iWidth, GLsizei iHeight ) { GLfloat fAspect, fHalfWorldSize = (1.4142135623730950488016887242097/2); glViewport( 0, 0, iWidth, iHeight ); glMatrixMode (GL_PROJECTION); glLoadIdentity (); if(iWidth <= iHeight) { fAspect = (GLfloat)iHeight / (GLfloat)iWidth; glOrtho(-fHalfWorldSize, fHalfWorldSize, -fHalfWorldSize*fAspect, fHalfWorldSize*fAspect, -10*fHalfWorldSize, 10*fHalfWorldSize); } else { fAspect = (GLfloat)iWidth / (GLfloat)iHeight; glOrtho(-fHalfWorldSize*fAspect, fHalfWorldSize*fAspect, -fHalfWorldSize, fHalfWorldSize, -10*fHalfWorldSize, 10*fHalfWorldSize); } glMatrixMode( GL_MODELVIEW ); } void vKeyboard(unsigned char cKey, int iX, int iY) { switch(cKey) { case 'w' : { if(ePolygonMode == GL_LINE) { ePolygonMode = GL_FILL; } else { ePolygonMode = GL_LINE; } glPolygonMode(GL_FRONT_AND_BACK, ePolygonMode); } break; case '+' : case '=' : { ++iDataSetSize; fStepSize = 1.0/iDataSetSize; } break; case '-' : { if(iDataSetSize > 1) { --iDataSetSize; fStepSize = 1.0/iDataSetSize; } } break; case 'c' : { if(vMarchCube == vMarchCube1) { vMarchCube = vMarchCube1;//Use Marching Tetrahedrons } else { vMarchCube = vMarchCube1;//Use Marching Cubes } } break; case 's' : { if(fSample == fSample1) { fSample = fSample1; } else if(fSample == fSample2) { fSample = fSample1; } else { fSample = fSample1; } } break; case 'l' : { if(bLight) { glDisable(GL_LIGHTING);//use vertex colors } else { glEnable(GL_LIGHTING);//use lit material color } bLight = !bLight; }; } } void vSpecial(int iKey, int iX, int iY) { switch(iKey) { case GLUT_KEY_PAGE_UP : { if(fTargetValue < 1000.0) { fTargetValue *= 1.1; } } break; case GLUT_KEY_PAGE_DOWN : { if(fTargetValue > 1.0) { fTargetValue /= 1.1; } } break; case GLUT_KEY_HOME : { bSpin = !bSpin; } break; case GLUT_KEY_END : { bMove = !bMove; } break; } } void vIdle() { glutPostRedisplay(); } void vDrawScene() { static GLfloat fPitch = 0.0; static GLfloat fYaw = 0.0; static GLfloat fTime = 0.0; glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT ); glPushMatrix(); if(bSpin) { fPitch += 4.0; fYaw += 2.5; } if(bMove) { fTime += 0.025; } vSetTime(fTime); glTranslatef(0.0, 0.0, -1.0); glRotatef( -fPitch, 1.0, 0.0, 0.0); glRotatef( 0.0, 0.0, 1.0, 0.0); glRotatef( fYaw, 0.0, 0.0, 1.0); glPushAttrib(GL_LIGHTING_BIT); glDisable(GL_LIGHTING); glColor3f(1.0, 1.0, 1.0); glutWireCube(1.0); glPopAttrib(); glPushMatrix(); glTranslatef(-0.5, -0.5, -0.5); glBegin(GL_TRIANGLES); vMarchingCubes(); glEnd(); glPopMatrix(); glPopMatrix(); glutSwapBuffers(); } //fGetOffset finds the approximate point of intersection of the surface // between two points with the values fValue1 and fValue2 GLfloat fGetOffset(GLfloat fValue1, GLfloat fValue2, GLfloat fValueDesired) { GLdouble fDelta = fValue2 - fValue1; if(fDelta == 0.0) { return 0.5; } return (fValueDesired - fValue1)/fDelta; } //vGetColor generates a color from a given position and normal of a point GLvoid vGetColor(GLvector &rfColor, GLvector &rfPosition, GLvector &rfNormal) { GLfloat fX = rfNormal.fX; GLfloat fY = rfNormal.fY; GLfloat fZ = rfNormal.fZ; rfColor.fX = (fX > 0.0 ? fX : 0.0) + (fY < 0.0 ? -0.5*fY : 0.0) + (fZ < 0.0 ? -0.5*fZ : 0.0); rfColor.fY = (fY > 0.0 ? fY : 0.0) + (fZ < 0.0 ? -0.5*fZ : 0.0) + (fX < 0.0 ? -0.5*fX : 0.0); rfColor.fZ = (fZ > 0.0 ? fZ : 0.0) + (fX < 0.0 ? -0.5*fX : 0.0) + (fY < 0.0 ? -0.5*fY : 0.0); } GLvoid vNormalizeVector(GLvector &rfVectorResult, GLvector &rfVectorSource) { GLfloat fOldLength; GLfloat fScale; fOldLength = sqrtf( (rfVectorSource.fX * rfVectorSource.fX) + (rfVectorSource.fY * rfVectorSource.fY) + (rfVectorSource.fZ * rfVectorSource.fZ) ); if(fOldLength == 0.0) { rfVectorResult.fX = rfVectorSource.fX; rfVectorResult.fY = rfVectorSource.fY; rfVectorResult.fZ = rfVectorSource.fZ; } else { fScale = 1.0/fOldLength; rfVectorResult.fX = rfVectorSource.fX*fScale; rfVectorResult.fY = rfVectorSource.fY*fScale; rfVectorResult.fZ = rfVectorSource.fZ*fScale; } } //Generate a sample data set. fSample1(), fSample2() and fSample3() define three scalar fields whose // values vary by the X,Y and Z coordinates and by the fTime value set by vSetTime() GLvoid vSetTime(GLfloat fNewTime) { GLfloat fOffset; GLint iSourceNum; for(iSourceNum = 0; iSourceNum < 3; iSourceNum++) { sSourcePoint[iSourceNum].fX = 0.5; sSourcePoint[iSourceNum].fY = 0.5; sSourcePoint[iSourceNum].fZ = 0.5; } fTime = fNewTime; fOffset = 1.0 + sinf(fTime); sSourcePoint[0].fX *= fOffset; sSourcePoint[1].fY *= fOffset; sSourcePoint[2].fZ *= fOffset; } //fSample1 finds the distance of (fX, fY, fZ) from three moving points GLfloat fSample3(GLfloat fX, GLfloat fY, GLfloat fZ) { GLdouble fResult = 0.0; GLdouble fDx, fDy, fDz; fDx = fX - sSourcePoint[0].fX; fDy = fY - sSourcePoint[0].fY; fDz = fZ - sSourcePoint[0].fZ; fResult += 0.5/(fDx*fDx + fDy*fDy + fDz*fDz); fDx = fX - sSourcePoint[1].fX; fDy = fY - sSourcePoint[1].fY; fDz = fZ - sSourcePoint[1].fZ; fResult += 1.0/(fDx*fDx + fDy*fDy + fDz*fDz); fDx = fX - sSourcePoint[2].fX; fDy = fY - sSourcePoint[2].fY; fDz = fZ - sSourcePoint[2].fZ; fResult += 1.5/(fDx*fDx + fDy*fDy + fDz*fDz); return fResult; } //fSample2 finds the distance of (fX, fY, fZ) from three moving lines GLfloat fSample2(GLfloat fX, GLfloat fY, GLfloat fZ) { GLdouble fResult = 0.0; GLdouble fDx, fDy, fDz; fDx = fX - sSourcePoint[0].fX; fDy = fY - sSourcePoint[0].fY; fResult += 0.5/(fDx*fDx + fDy*fDy); fDx = fX - sSourcePoint[1].fX; fDz = fZ - sSourcePoint[1].fZ; fResult += 0.75/(fDx*fDx + fDz*fDz); fDy = fY - sSourcePoint[2].fY; fDz = fZ - sSourcePoint[2].fZ; fResult += 1.0/(fDy*fDy + fDz*fDz); return fResult; } //fSample2 defines a height field by plugging the distance from the center into the sin and cos functions GLfloat fSample1(GLfloat fX, GLfloat fY, GLfloat fZ) { GLfloat fHeight = ((sqrt((0.5-fX)*(0.5-fX) + (0.5-fY)*(0.5-fY))) +48); GLdouble fResult = (fHeight-fZ); return fResult; } //vGetNormal() finds the gradient of the scalar field at a point //This gradient can be used as a very accurate vertx normal for lighting calculations GLvoid vGetNormal(GLvector &rfNormal, GLfloat fX, GLfloat fY, GLfloat fZ) { rfNormal.fX = fSample(fX-0.01, fY, fZ) - fSample(fX+0.01, fY, fZ); rfNormal.fY = fSample(fX, fY-0.01, fZ) - fSample(fX, fY+0.01, fZ); rfNormal.fZ = fSample(fX, fY, fZ-0.01) - fSample(fX, fY, fZ+0.01); vNormalizeVector(rfNormal, rfNormal); } //vMarchCube1 performs the Marching Cubes algorithm on a single cube GLvoid vMarchCube1(GLfloat fX, GLfloat fY, GLfloat fZ, GLfloat fScale) { extern GLint aiCubeEdgeFlags[256]; extern GLint a2iTriangleConnectionTable[256][16]; 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] = 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] <= fTargetValue) 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] ], fTargetValue); 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]); glColor3f(sColor.fX, sColor.fY, sColor.fZ); glNormal3f(asEdgeNorm[iVertex].fX, asEdgeNorm[iVertex].fY, asEdgeNorm[iVertex].fZ); glVertex3f(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ); } } } //vMarchTetrahedron performs the Marching Tetrahedrons algorithm on a single tetrahedron GLvoid vMarchTetrahedron(GLvector *pasTetrahedronPosition, GLfloat *pafTetrahedronValue) { extern GLint aiTetrahedronEdgeFlags[16]; extern GLint a2iTetrahedronTriangles[16][7]; GLint iEdge, iVert0, iVert1, iEdgeFlags, iTriangle, iCorner, iVertex, iFlagIndex = 0; GLfloat fOffset, fInvOffset, fValue = 0.0; GLvector asEdgeVertex[6]; GLvector asEdgeNorm[6]; GLvector sColor; //Find which vertices are inside of the surface and which are outside for(iVertex = 0; iVertex < 4; iVertex++) { if(pafTetrahedronValue[iVertex] <= fTargetValue) iFlagIndex |= 1<<iVertex; } //Find which edges are intersected by the surface iEdgeFlags = aiTetrahedronEdgeFlags[iFlagIndex]; //If the tetrahedron 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 < 6; iEdge++) { //if there is an intersection on this edge if(iEdgeFlags & (1<<iEdge)) { iVert0 = a2iTetrahedronEdgeConnection[iEdge][0]; iVert1 = a2iTetrahedronEdgeConnection[iEdge][1]; fOffset = fGetOffset(pafTetrahedronValue[iVert0], pafTetrahedronValue[iVert1], fTargetValue); fInvOffset = 1.0 - fOffset; asEdgeVertex[iEdge].fX = fInvOffset*pasTetrahedronPosition[iVert0].fX + fOffset*pasTetrahedronPosition[iVert1].fX; asEdgeVertex[iEdge].fY = fInvOffset*pasTetrahedronPosition[iVert0].fY + fOffset*pasTetrahedronPosition[iVert1].fY; asEdgeVertex[iEdge].fZ = fInvOffset*pasTetrahedronPosition[iVert0].fZ + fOffset*pasTetrahedronPosition[iVert1].fZ; vGetNormal(asEdgeNorm[iEdge], asEdgeVertex[iEdge].fX, asEdgeVertex[iEdge].fY, asEdgeVertex[iEdge].fZ); } } //Draw the triangles that were found. There can be up to 2 per tetrahedron for(iTriangle = 0; iTriangle < 2; iTriangle++) { if(a2iTetrahedronTriangles[iFlagIndex][3*iTriangle] < 0) break; for(iCorner = 0; iCorner < 3; iCorner++) { iVertex = a2iTetrahedronTriangles[iFlagIndex][3*iTriangle+iCorner]; vGetColor(sColor, asEdgeVertex[iVertex], asEdgeNorm[iVertex]); glColor3f(sColor.fX, sColor.fY, sColor.fZ); glNormal3f(asEdgeNorm[iVertex].fX, asEdgeNorm[iVertex].fY, asEdgeNorm[iVertex].fZ); glVertex3f(asEdgeVertex[iVertex].fX, asEdgeVertex[iVertex].fY, asEdgeVertex[iVertex].fZ); } } } //vMarchCube2 performs the Marching Tetrahedrons algorithm on a single cube by making six calls to vMarchTetrahedron GLvoid vMarchCube2(GLfloat fX, GLfloat fY, GLfloat fZ, GLfloat fScale) { GLint iVertex, iTetrahedron, iVertexInACube; GLvector asCubePosition[8]; GLfloat afCubeValue[8]; GLvector asTetrahedronPosition[4]; GLfloat afTetrahedronValue[4]; //Make a local copy of the cube's corner positions for(iVertex = 0; iVertex < 8; iVertex++) { asCubePosition[iVertex].fX = fX + a2fVertexOffset[iVertex][0]*fScale; asCubePosition[iVertex].fY = fY + a2fVertexOffset[iVertex][1]*fScale; asCubePosition[iVertex].fZ = fZ + a2fVertexOffset[iVertex][2]*fScale; } //Make a local copy of the cube's corner values for(iVertex = 0; iVertex < 8; iVertex++) { afCubeValue[iVertex] = fSample(asCubePosition[iVertex].fX, asCubePosition[iVertex].fY, asCubePosition[iVertex].fZ); } for(iTetrahedron = 0; iTetrahedron < 6; iTetrahedron++) { for(iVertex = 0; iVertex < 4; iVertex++) { iVertexInACube = a2iTetrahedronsInACube[iTetrahedron][iVertex]; asTetrahedronPosition[iVertex].fX = asCubePosition[iVertexInACube].fX; asTetrahedronPosition[iVertex].fY = asCubePosition[iVertexInACube].fY; asTetrahedronPosition[iVertex].fZ = asCubePosition[iVertexInACube].fZ; afTetrahedronValue[iVertex] = afCubeValue[iVertexInACube]; } vMarchTetrahedron(asTetrahedronPosition, afTetrahedronValue); } } //vMarchingCubes iterates over the entire dataset, calling vMarchCube on each cube GLvoid vMarchingCubes() { GLint iX, iY, iZ; for(iX = 0; iX < iDataSetSize; iX++) for(iY = 0; iY < iDataSetSize; iY++) for(iZ = 0; iZ < iDataSetSize; iZ++) { vMarchCube(iX*fStepSize, iY*fStepSize, iZ*fStepSize, fStepSize); } } // For any edge, if one vertex is inside of the surface and the other is outside of the surface // then the edge intersects the surface // For each of the 4 vertices of the tetrahedron can be two possible states : either inside or outside of the surface // For any tetrahedron the are 2^4=16 possible sets of vertex states // This table lists the edges intersected by the surface for all 16 possible vertex states // There are 6 edges. For each entry in the table, if edge #n is intersected, then bit #n is set to 1 GLint aiTetrahedronEdgeFlags[16]= { 0x00, 0x0d, 0x13, 0x1e, 0x26, 0x2b, 0x35, 0x38, 0x38, 0x35, 0x2b, 0x26, 0x1e, 0x13, 0x0d, 0x00, }; // For each of the possible vertex states listed in aiTetrahedronEdgeFlags there is a specific triangulation // of the edge intersection points. a2iTetrahedronTriangles lists all of them in the form of // 0-2 edge triples with the list terminated by the invalid value -1. // // I generated this table by hand GLint a2iTetrahedronTriangles[16][7] = { {-1, -1, -1, -1, -1, -1, -1}, { 0, 3, 2, -1, -1, -1, -1}, { 0, 1, 4, -1, -1, -1, -1}, { 1, 4, 2, 2, 4, 3, -1}, { 1, 2, 5, -1, -1, -1, -1}, { 0, 3, 5, 0, 5, 1, -1}, { 0, 2, 5, 0, 5, 4, -1}, { 5, 4, 3, -1, -1, -1, -1}, { 3, 4, 5, -1, -1, -1, -1}, { 4, 5, 0, 5, 2, 0, -1}, { 1, 5, 0, 5, 3, 0, -1}, { 5, 2, 1, -1, -1, -1, -1}, { 3, 4, 2, 2, 4, 1, -1}, { 4, 1, 0, -1, -1, -1, -1}, { 2, 3, 0, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1}, }; // For any edge, if one vertex is inside of the surface and the other is outside of the surface // then the edge intersects the surface // For each of the 8 vertices of the cube can be two possible states : either inside or outside of the surface // For any cube the are 2^8=256 possible sets of vertex states // This table lists the edges intersected by the surface for all 256 possible vertex states // There are 12 edges. For each entry in the table, if edge #n is intersected, then bit #n is set to 1 GLint aiCubeEdgeFlags[256]= { 0x000, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x099, 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230, 0x339, 0x033, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3, 0x0aa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 0x460, 0x569, 0x663, 0x76a, 0x066, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0x0ff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x055, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0x0cc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0x0cc, 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x055, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0x0ff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x066, 0x76a, 0x663, 0x569, 0x460, 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0x0aa, 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x033, 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x099, 0x190, 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x000 }; // For each of the possible vertex states listed in aiCubeEdgeFlags there is a specific triangulation // of the edge intersection points. a2iTriangleConnectionTable lists all of them in the form of // 0-5 edge triples with the list terminated by the invalid value -1. // For example: a2iTriangleConnectionTable[3] list the 2 triangles formed when corner[0] // and corner[1] are inside of the surface, but the rest of the cube is not. // // I found this table in an example program someone wrote long ago. It was probably generated by hand GLint a2iTriangleConnectionTable[256][16] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1}, {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1}, {3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1}, {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1}, {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1}, {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1}, {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1}, {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1}, {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1}, {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1}, {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1}, {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1}, {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1}, {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1}, {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1}, {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1}, {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1}, {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1}, {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1}, {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1}, {2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1}, {7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1}, {2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1}, {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1}, {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1}, {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1}, {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1}, {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1}, {2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1}, {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1}, {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1}, {6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1}, {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1}, {6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1}, {8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1}, {7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1}, {3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1}, {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1}, {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1}, {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1}, {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1}, {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1}, {6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1}, {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1}, {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1}, {8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1}, {1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1}, {0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1}, {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1}, {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1}, {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1}, {9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1}, {8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1}, {3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1}, {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1}, {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1}, {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1}, {2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1}, {7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1}, {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1}, {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1}, {1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1}, {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1}, {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1}, {0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1}, {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1}, {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1}, {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1}, {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1}, {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1}, {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1}, {7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1}, {6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1}, {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1}, {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1}, {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1}, {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1}, {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1}, {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1}, {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1}, {1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1}, {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1}, {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1}, {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1}, {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1}, {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1}, {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1}, {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1}, {7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1}, {3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1}, {6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1}, {9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1}, {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1}, {4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1}, {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1}, {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1}, {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1}, {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1}, {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1}, {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1}, {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1}, {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1}, {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1}, {9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1}, {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1}, {1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1}, {10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1}, {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1}, {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1}, {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1}, {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1}, {9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1}, {7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1}, {2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1}, {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1}, {9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1}, {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1}, {1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1}, {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1}, {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1}, {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1}, {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1}, {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1}, {0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1}, {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1}, {9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1}, {5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1}, {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1}, {5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1}, {8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1}, {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1}, {9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1}, {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1}, {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1}, {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1}, {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1}, {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1}, {11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1}, {2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1}, {9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1}, {3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1}, {1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1}, {4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1}, {3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1}, {0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1}, {9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1}, {1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1} };
親測運行效果如下:
5.算法細節(jié)
這個算法有兩個主要組成部分。第一個是決定如何定義切割單個立方體的截面或表面截面。如果我們將每個角分類為低于或高于等值,就有256種可能的角分類構型。其中兩個是無關緊要的;所有點都在立方體內(nèi)部或外部的位置對等值面沒有影響。對于所有其他構型,我們需要確定在每個立方體邊緣上等值面相交的位置,并使用這些邊緣交點為等值面創(chuàng)建一個或多個三角形塊。
如果考慮對稱性,在剩下的254種可能中,實際上只有14種構型是唯一的。當只有一個角小于等值時,這就形成了一個三角形,它與在這個角上相交的邊緣相交,而補丁法線朝向這個角。顯然,這種類型有8個相關配置(例如,配置2 -你可能需要調(diào)整colormap來查看球體/像素之間的平面)。通過反轉(zhuǎn)法線,我們得到8種構型它們有7個角比等值小。然而,我們并不認為這些是獨一無二的。對于兩個角小于等值的構型,有3種獨特的構型(例如,構型12),這取決于這些角是否屬于同一條邊,屬于立方體的同一面,或相對于彼此的對角位置。對于3個角小于等值的構型,也有3個獨特的構型(例如構型14),這取決于是否有0、1或2個共享邊(2個共享邊會給你一個L形)。有7獨特配置有4個角小于等值時,根據(jù)是否有0,2、3(3變體在這一點),或4共享邊緣(例如配置30 -你可能需要調(diào)整顏色看到孤立(遠)范圍內(nèi)的三角形/像素)。
每一種非平凡構型都會導致1到4個三角形被添加到等值面上。實際的頂點本身可以通過沿邊的插值來計算,或者默認它們的位置在邊的中間。插值位置顯然會給你更好的陰影計算和更平滑的表面。
現(xiàn)在我們可以為單個體素創(chuàng)建表面補丁,我們可以將這個過程應用到整個體素。我們可以在板中處理體積,其中每個板由2個像素片組成。我們可以獨立對待每個立方體,或者我們可以傳播共享邊的立方體之間的邊相交。這種共享也可以在相鄰的板之間完成,這增加了一些存儲和復雜性,但節(jié)省了計算時間。邊緣/頂點信息的共享也導致了一個更緊湊的模型,一個更易于插值著色。
6.總結
Marching Cubes是一種用于繪制立體數(shù)據(jù)中等值面的算法。基本概念是,我們可以通過立方體8個角的像素值來定義體素(立方體)。如果一個立方體中的一個或多個像素的值小于用戶指定的等值,并且一個或多個像素的值大于這個值,我們知道體素必須貢獻等值面的某個分量。通過確定立方體的哪些邊與等值面相交,我們可以創(chuàng)建三角形塊,將立方體劃分為等值面內(nèi)部區(qū)域和外部區(qū)域。通過連接等值面邊界上所有立方體的小塊,我們得到了一個表面表示法。
到此這篇關于C++實現(xiàn)移動立方體示例講解的文章就介紹到這了,更多相關C++移動立方體內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用
這篇文章主要介紹了C語言中的setlinebuf()、utmpname()、rewind函數(shù)使用,是C語言中操作文件的一些基本函數(shù),需要的朋友可以參考下2015-08-08