marching cubes efficiency- you can reduce 3/4rs of the edge calculations?

Question

Normal marching cubes finds 12 edges per cube, but you can do 3 edges per cube, save the edges inside an array, and then go through the cubes again, referencing the edges from the cubes adjacent rather than calculating them.

The process to reference adjacent cubes isn't clearly discussed on the Internet so anyone using marching cubes would be welcome to help find the details of the solution. do you know an implementation already?

here is a picture showing the 3 edges in yellow that you need for each cube, instead of 12.

EDIT- I just found this solution, although it's just a part of it:

Imagine 3 edges coming from the corner of the cube with lowerest coordinates. Then all other edges just belong to other cubes. If our cube has coordinates (x,y,z), the neiboring cubes have coordinates (x+1,y,z), (x,y+1,z), (x,y,z+1), (x+1,y+1,z), (x+1,y,z+1), (x,y+1,z+1). You can imagine the edge as a vector. Then the corner of the cube have edges (1,0,0), (0,1,0), (0,0,1). The cube with coordinates (x+1,y,z) have edges (0,1,0) and (0,0,1) that belong to our cube. The cube (x+1,y+1,z) has only one edge (0,0,1) that belongs to our cube. So if you store 4 elements for the cube you can access them like that:

edge1 = cube[x][y][z][0];
edge2 = cube[x][y][z][1];
edge3 = cube[x][y][z][2];
edge4 = cube[x+1][y][z][1];
edge5 = cube[x+1][y][z][2];
edge6 = cube[x][y+1][z][0];
edge7 = cube[x][y+1][z][2];
edge8 = cube[x][y][z+1][0];
edge9 = cube[x][y][z+1][1];
edge10 = cube[x+1][y+1][z][2];
edge11 = cube[x+1][y][z+1][1];
edge12 = cube[x][y+1][z+1][0];

Now which points edge7 connect? The answer is (x,y+1,z) and (x,y+1,z)+(0,0,1)=(x,y+1,z+1).

Now which cubes edge7 connect? It is more harder. We see that coordinate z is changes along the edge this means that neibour cube has the same z coordinate. Now all others coordinates change. Where we have +1, the cube has large coordinate. Where we have +0, the cube has smaller coordinates. So the edge connects cubes (x,y,z) and (x-1,y+1,z). Other 2 cubes that has the same edge are (x,y+1,z) and (x-1,y,z).

-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=--=-=

EDIT2- So I am doing this, and it isn't so simple. I have a loop which simultaneously calculate 8 points, 12 edges, the interpolation of edges, the bit values and a vertex the values for the edges, all in one loop.

so I am doing a new loop previous to it to calculate as much as possible and place it in arrays to used in the complicated loop.

I can recycle the interpolated values of the intersection points along edges, in an array, although I will have to recalculate all the points again in the complicated loop, because the values of the points I used to decide bit numbers that reference values in the vertex table. That confuses me! I thought that once I have the edge intersection values, I could use those directly to get the triangle tables, without having to calculate the points all over again!

in fact no. anyway, here is another bit of information with someone that already did it, if only it was readable! http://www.new-npac.org/projects/sv2all/sv2/vtk/patented/vtkImageMarchingCubes.cxx scroll to this line: Cubes are responsible for edges on their min faces.

Maseru

So I am doing this, and it isn't so simple. I have a loop which simultaneously calculate 8 points, 12 edges, the interpolation of edges, the bit values and a vertex the values for the edges, all in one loop. – Maseru

solution was to do a grid 1x cubes larger on XYZ using only 3 edges for each cube , results in an array and then cross reference them when checking the 12 edges of each cube. using GPU goes 100 times faster than CPU so cpu is lame these days performance wise. – Maseru

Answer 1

A simple way to reduce edge calculations in the way you are suggesting is to compute cubes one axis aligned plane at a time.

If you kept all of the cubes, with their edges, in memory, it would be easy to compute each edge only once and to find adjacent edges by indexing. However, you usually don't want to keep all the cubes in memory at once because of the space requirements.

A solution to this is to compute one plane of cubes at a time. i.e. an axis aligned cross-section, starting from one side and progressing to the opposite side. You then only need to keep at most two full planes of cubes in memory at a time. As you move through each plane you can reference shared edges in the previous plane and previously computed cubes in the current plane. As you move to the next plane you can deallocate the plane you will no longer need.

Edit: This article discusses doing just what I suggest: http://alphanew.net/index.php?section=articles&site=marchoptim&lang=eng

Jovi

Answer 2

Funny, because when I implemented my own MCs I came up with similar solution.

When you start working with MCs you treat them as a distinct cubes but if you want to go for high performance you'll need to create entire mesh as a whole, and creating vertex indices etc. is not so easy here. It gets even more interesting when you want to add smooth per-vertex normals :).

To solve this I created a simple index cache mechanism to store vertex indices for each edge. Then, for each computed edge I have cube position x,y,z and edge index and I do as follows:

For each axis:
    if the edge is on '+' side of axis:
        replace edge index with its '-' side sibling
        increment cube position along axis

This simple operation gives me the correct cube position, and edge index of 0,1,2. Then I compute a total cache index from x,y,z,edgeIndex values with simple bit rotations.

When I have cache index I check if it's bigger than -1. If it is then there was an already computed vertex at this edge and I can reuse it. If it's -1 I need to create a new vertex and store its index in the cache. This way you'll compute each vertex only once, and you can even add a normal value shared between every triangle containing your vertex.

Overthecounter

Thanks! i worked on this for a while and made an index with 3 edges per cube, adding an extra row for the outer sides, and it wasnt much faster for some reason. the future is compute shader MC that's 100 times faster than processor. – Maseru

The vertex-sharing alone won't give you much of performance gain, but it's really helpful if you want to compute per-vertex normals, which I did. I'm still working on some ambiguous cases resolution, but when I finish I'll make it public. – Overthecounter

@ufomorace If you're interested, nVidia's GPU Gems has some fascinating stuff on terrain generation using the GPU, including how you can implement collision detection. – Company

I am confused about how it's faster with per vertex normals? as the vertices all arrive in an array, and then the normals are made with the vertices of the same triangle, it's just array indices. – Maseru

if you want a slow and complicated option, you can do super precise isosurface forcefield normals, except it gets confused at fast changing mesh zones. – Maseru

@ufomorace: I wanted to get smooth normals for vertices so I needed to sum all normals of triangles that share a vertex. It's hard to do in a triangle soup you get from MCs, but it gets a lot easier when I use my vertex index cache. Additional gain is that I interpolate each vertex only once, even if it's shared by a few cubes. – Overthecounter

Good Point! using triangle array is only for shared vertices. The most difficult thing is finding border same vertices of two marching cubes if the mesh is devided into 65k vertex objects for example, using arrays of vertices/triangles. in that situation it's advantageous to do isofield normals... Yes it's great for shared vertices in MC. I dont think a compute shader version has shared vertices. perhaps using ddx ddy – Maseru

Answer 3

Yes, I think I do it similar to kolenda. I have a struct with 5 ints: (cube)index and 4 vertexindices (A, B, C, D).

for the most inner loop (x), I have just lastXCache and nextXCache. On the 4 edges pointing in the -x direction, i ask if lastXCache.A != -1 and if so, assign the previously calculated value, etc. In the +x direction I store calculated vertices in nextXCache. when cube is done: lastXCache = nextXCache; For y and z direction it needs to be a list (unity term for mutable array), next y is next row (so sizex) and next z is the next plane (so sizex * sizey)

only diadvantage is that this way it has to run cube after cube, so serially. But you can calculate different chunks in parallel.

Another way I thought of that could be more parallel would need 2 passes: 1. calculate 3 edges every cube, when 1 is done -> 2. draw the triangles.

Don't really know what is better, but the way it actually works seems to be fast enough. even better with unity jobs. Create one IJob for 1 chunk/mesh.

Cleistogamy