# Create mapping from voxel grid cube to connected edge array

This topic is 2601 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all,

Right now I have a voxelgrid of cubes, and each cube shares edges with neighboring cubes. I want to have one large edge array, which has all the shared cube edges in the grid. And I want a mapping such that for each cube, it has 12 pointers into the edge array. I can figure this out in 2d easily because its easy to draw, but 3d is a little crazier. Anyone have any advice on how to approach this?

Some background on why I need this: I'm currently using the CUDA SDK Marching Cubes example, but currently it generates triangles as one large vertex array where every 3 vertices defines a triangle. What I want is the more traditional approach, where you have one vertex array, and then an index array where the elements reference the vertex array. That way I can easily make smooth vertex normals by averaging connected faces. If its just one giant vertex array there is no efficient way to find all the triangles connected to a vertex.

Heres the website that details marching cubes: http://paulbourke.ne...try/polygonise/ towards the end they talk a bit about what I want, but they don't really say how to implement it

Thank you!
Bobby

##### Share on other sites
I'm not sure if this is exactly what you're looking for, but here's one way you could go about generating connectivity data for the grid.

For a grid of NxNxN cubes, you'll have a corresponding grid of (N+1)x(N+1)x(N+1) vertices.

Presumably the vertices will be stored in a 1-d array, so the first thing you'll want to do is create or find some wrapper code so that you can access the vertices using 3-d indexing.

For cube (i, j, k), the vertex indices are:

(i + 0, j + 0, k + 0)
(i + 1, j + 0, k + 0)
(i + 1, j + 1, k + 0)
(i + 0, j + 0, k + 0)
(i + 0, j + 0, k + 1)
(i + 1, j + 0, k + 1)
(i + 1, j + 1, k + 1)
(i + 0, j + 0, k + 1)

If you draw a picture of a cube and label the vertices accordingly, it should be easy to identify the edges, quads, and/or triangles (whichever you need) that make up the cube. For example, one of the edges will be:

(i + 0, j + 0, k + 0)->(i + 1, j + 0, k + 0)

And so on.

Typically you'd have one or more levels of indirection to reflect the fact that features are shared between cubes (the 'edge pointers' you mentioned). Let's say the edges are stored in a container, and each edge consists of two integer indices (the above 3-d indices converted to 1-d form).

Two edges are considered equal if the first endpoint index of the first edge matches the first endpoint index of the second edge and likewise for the second endpoint index, or vice versa (i.e. first matches second and second matches first).

The process for building the edge list looks something like this (untested pseudocode):

for each cube for each cube edge if edge is already in edge list point to the edge else add edge point to new edge end if end for end for
Again, not sure if that's exactly what you're looking for, but that's one way to build the connectivity data in question.

• 10
• 9
• 48
• 12
• 10
• ### Forum Statistics

• Total Topics
631385
• Total Posts
2999705
×