2
\$\begingroup\$

I've been playing around with Unity3d, seeing if I can make a voxel-based engine out of it (a la Castle Story, or Minecraft).

I've dynamically built a mesh from a volume of cubes, and now I'm looking into reducing the number of vertices built into each mesh, as right now, I'm "rendering" vertices and triangles for cubes that are fully hidden within the larger voxel volume.

The simple solution is to check each of the 6 directions for each cube, and only add the face to the mesh if the neighboring voxel in that direction is "empty". Parsing a voxel volume is BigO(N^3), and checking the 6 neighbors keeps it BigO(7*N^3)->BigO(N^3).

The one thing this results in is a lot of redundant calls, as the same voxel will be polled up to 7 times, just to build the mesh.

My question, then, is:

Is there a way to parse a cubic volume (and find which faces have neighbors) with fewer redundant calls? And perhaps more importantly, does it matter (as BigO complexity is the same in both cases)?

\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

Yes, you can make fewer calls. You can give each voxel data containing it's face information. Then go through and set the face data of all the voxels. The simple solid or not situation produces 4 cases:

for each voxel for each face not set if thisVoxel is solid if oppositeVoxel is solid // both voxels are solid and touching, no faces set thisFace to zero set oppositeVoxelFace to zero else // this voxel is solid, other is not, this voxel has a face set thisFace to one set oppositeVoxelFace to zero else if oppositeVoxel is solid // this voxel is not solid, other is, other has face set thisFace to zero set oppositeVoxelFace to one else // both voxels are not solid no faces set thisFace to zero set oppositeVoxleFace to zero

As you can see, you'll cut out at least one check for the opposite voxel by setting both at the same time. Ensure that you only loop over faces not set. This will reduce the number of checks you need to do.

Additionally, when rebuilding the mesh, you can reuse almost all the face data. When a voxel is added or removed, reset it's face data and the face data of those voxels surrounding it.

You probably realize that this is a trade off. You either get faster execution, or more memory usage. This will take more memory.

\$\endgroup\$
1
  • \$\begingroup\$ That's a very good point about rebuilding the mesh! \$\endgroup\$ Commented Oct 17, 2012 at 15:49
1
\$\begingroup\$

I made some progress in my marching cube implementation where I kept the previous slice of the YZ plane to prevent needing to resample a value twice, but this was to reduce the number of calls when using perlin noise and similar. If your voxel data is stored as an array I doubt there is much you can do to reduce the number of queries.

I suggest you go ahead with the simplest solution that works, and then after its made simply measure how long it really takes to make the mesh. This is not something you will be doing every frame after all, and creating the mesh can be done in a separate thread to prevent stalling the game when you need to recreate a mesh, or load a new section.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.