Skip to main content
gamedev.net
🔒 Locked

marching cubes problem

Started by m0rg 5 replies 900+ views
Original Post
m0rg
m0rg
Hi! I'm trying to implement the marching cubes algorithm and have some troubles with it. The resulting mesh is really strange and some rtiangles are missing. (in fact the half of the triangles are missing) I can't find out the problem for now . My implementation is based on the article "Polygonising a scalar field" (i'm using the tables in this article) (http://astronomy.swin.edu.au/~pbourke/modelling/polygonise/)
mikeman
mikeman
Just a hint: The problem is in your code, not in the article. The "I have a problem with X technique" approach is not very descriptive. Post your code.
m0rg
m0rg
I know the problem comes from my code (even if the code is the same as in the article :) )
And you're right I've forgotten to post it so here it is:

Mesh* Data::buildSurface(float isovalue){  Mesh* result=NULL;  int edgeTable[256]={    0x0  , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c,  //same table as in the article .........    0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0   };  int triTable[256][16] =    {{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, //same table as in the article .........     {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}};  TRACE("Data::computing voxels' flag...");  for (unsigned int i=0;i<_grid.size();i++)    {      _grid.flag = 0;      if (_grid.p0->getValue() < isovalue) _grid.flag |= 1;      if (_grid.p1->getValue() < isovalue) _grid.flag |= 2;      if (_grid.p2->getValue() < isovalue) _grid.flag |= 4;      if (_grid.p3->getValue() < isovalue) _grid.flag |= 8;      if (_grid.p4->getValue() < isovalue) _grid.flag |= 16;      if (_grid.p5->getValue() < isovalue) _grid.flag |= 32;      if (_grid.p6->getValue() < isovalue) _grid.flag |= 64;      if (_grid.p7->getValue() < isovalue) _grid.flag |= 128;      i++;    }  TRACE("ok\n");    TRACE("Data::computing mesh");  //init mesh object maximum number of vertices and indices  result=new Mesh();  result->initVertices(12*_grid.size());  result->initIndices(12*_grid.size());  unsigned long nbVertices=0,nbIndices=0,nbTriangles=0;  //for each voxel  for (unsigned int i=0;i<_grid.size();i++)    {      TRACE(".");            VOXEL v=_grid;      Utils::FLOAT3 vertlist[12];      //find crossing points      if (edgeTable[v.flag]!=0)	{	  if (edgeTable[v.flag] & 1)	    {	      TRACE("Data::&1\n");	      vertlist[0] = linearInterpolation(isovalue,v.p0,v.p1);	    }	  if (edgeTable[v.flag] & 2)	    {	      TRACE("Data::&2\n");	      vertlist[1] =	linearInterpolation(isovalue,v.p1,v.p2);	    }	  if (edgeTable[v.flag] & 4)	    {	      TRACE("Data::&4\n");	      vertlist[2] =	linearInterpolation(isovalue,v.p2,v.p3);	    }	  if (edgeTable[v.flag] & 8)	    {	      TRACE("Data::&8\n");	      vertlist[3] =	linearInterpolation(isovalue,v.p3,v.p0);	    }	  if (edgeTable[v.flag] & 16)	    {	      TRACE("Data::&16\n");	      vertlist[4] =	linearInterpolation(isovalue,v.p4,v.p5);	    }	  if (edgeTable[v.flag] & 32)	    {	      TRACE("Data::&32\n");	      vertlist[5] =	linearInterpolation(isovalue,v.p5,v.p6);	    }	  if (edgeTable[v.flag] & 64)	    {	      TRACE("Data::&64\n");	      vertlist[6] =	linearInterpolation(isovalue,v.p6,v.p7);	    }	  if (edgeTable[v.flag] & 128)	    {	      TRACE("Data::&128\n");	      vertlist[7] =	linearInterpolation(isovalue,v.p7,v.p4);	    }	  if (edgeTable[v.flag] & 256)	    {	      TRACE("Data::&256\n");	      vertlist[8] =	linearInterpolation(isovalue,v.p0,v.p4);	    }	  if (edgeTable[v.flag] & 512)	    {	      TRACE("Data::&512\n");	      vertlist[9] =	linearInterpolation(isovalue,v.p1,v.p5);	    }	  if (edgeTable[v.flag] & 1024)	    {	      TRACE("Data::&1024\n");	      vertlist[10] = linearInterpolation(isovalue,v.p2,v.p6);	    }	  if (edgeTable[v.flag] & 2048)	    {	      TRACE("Data::&2048\n");	      vertlist[11] =linearInterpolation(isovalue,v.p3,v.p7);	    }	  //build triangles         	  for (unsigned int j=0;triTable[v.flag][j]!=-1;j+=3) 	    {	      TRACE("Data::creating triangles\n");	      Utils::VERTEX tmp;	      tmp.x=vertlist[triTable[v.flag][j]].x;	      tmp.y=vertlist[triTable[v.flag][j]].y;	      tmp.z=vertlist[triTable[v.flag][j]].z;	      result->addVertex(tmp,nbVertices);	      result->addIndex(nbVertices,nbIndices);	      nbVertices++;	      nbIndices++;	 	      tmp.x=vertlist[triTable[v.flag][j+1]].x;	      tmp.y=vertlist[triTable[v.flag][j+1]].y;	      tmp.z=vertlist[triTable[v.flag][j+1]].z;	      result->addVertex(tmp,nbVertices);	      result->addIndex(nbVertices,nbIndices);	      nbVertices++;	      nbIndices++;	      tmp.x=vertlist[triTable[v.flag][j+2]].x;	      tmp.y=vertlist[triTable[v.flag][j+2]].y;	      tmp.z=vertlist[triTable[v.flag][j+2]].z;	      result->addVertex(tmp,nbVertices);	      result->addIndex(nbVertices,nbIndices);	      nbVertices++;	      nbIndices++;	      nbTriangles++;	    }	}    }  result->setNbVertices(nbVertices);  result->setNbIndices(nbIndices);  result->setPrimitiveType(Utils::TRIANGLE);  TRACE("ok\n");  TRACE("Data::nbVertices:");TRACE(nbVertices);TRACE("\n");  TRACE("Data::nbIndices:");TRACE(nbIndices);TRACE("\n");  TRACE("Data::nbTriangles:");TRACE(nbTriangles);TRACE("\n");  return result;};


_grid is just a vector containing all voxels (with refs to 8 corners)

and the linearInterpolation function is the same as in the article.

I guess the problem is in the triangle construction but can't find it for now.

EDIT:how can I post a picture?
mikeman
mikeman
I have no idea how this algorithm works, but this piece of code seems wrong:

for (unsigned int i=0;i<_grid.size();i++)    {      _grid.flag = 0;      if (_grid.p0->getValue() < isovalue) _grid.flag |= 1;      if (_grid.p1->getValue() < isovalue) _grid.flag |= 2;      if (_grid.p2->getValue() < isovalue) _grid.flag |= 4;      if (_grid.p3->getValue() < isovalue) _grid.flag |= 8;      if (_grid.p4->getValue() < isovalue) _grid.flag |= 16;      if (_grid.p5->getValue() < isovalue) _grid.flag |= 32;      if (_grid.p6->getValue() < isovalue) _grid.flag |= 64;      if (_grid.p7->getValue() < isovalue) _grid.flag |= 128;      i++;    }


You have "i++" 2 times, both inside the "for" declaration and at the end before "}". Why do you do that? I think this would result in missing half the elements in the array during the iteration.
m0rg
m0rg
thanks !!!!


I've been so long watching this code that I haven't seen this error
and now it works !!!!

Thank you very much :)
fractoid
fractoid
Bingo. I think mikeman's got it - if you're still having probs in the morning I have old (working) C code based on the same article, which I could dig out.

[nitpick]Why the leading underscore on _grid[]? Technically that's a no-no, IRC variable names with one leading underscore are reserved for runtime implementers and with two underscores for compiler writers.[/nitpick]

[edit: ok, obviously it was solved while I typed that. Good work!]
m0rg
m0rg
the underscore is for members variables :)
I can't stand the "m" and "g" convention for naming variables :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.