Jump to content
  • Advertisement
Sign in to follow this  

Create mapping from voxel grid cube to connected edge array

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

If you intended to correct an error in the post then please contact us.

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!

Share this post

Link to post
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
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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!