Data structure for voxels?

Game Play & Game Design
#1

Well, I’ve thought about this for quite some time now, and I’ve come to hit what I believe is a roadblock. If you’re really going to help me, prepare for a bit of a read since I tend to over-explain things.

See, each of my voxels currently stores its own position values in 3 integers: x, y, z. I understand that this is very inefficient in most cases, but more on that in a second. Within my current structure, the voxels are assigned into groups that don’t have a fixed count to them, nor a fixed position; they need to be dynamic as the player will be interacting with them, and also each group needs to be able to do things on its own - move, rotate, etc. When I got to the point of storing the data, I had two separate ideas, which are below. I’m doing the second option currently.


// first option
private Voxel[][][] group_voxels = new Voxel[w][h][l];

// second option?
private List<Voxel> voxels = new ArrayList<Voxel>();

Now, the question comes down to efficiency of storage and data, as well as perhaps processing and rendering speed - though I’m not 100 percent certain about that last one.

For the first option, the pros are that I can infer the integer positions for each voxel through the index it’s at in the 3d array. However, doing this also creates a lot of wasted space, since odds are the entire group of voxels will never be filled (Giant cube structures aren’t going to be very common). For example, if I have a tree that’s 48 voxels tall, 25 voxels wide, and 25 voxels in depth overall, the empty space (like around the trunk) is sitting there and taking up memory (I think?) where it could be better spent on other things. It also introduces a bit of unneccessary checking when looping through, since it needs to check those empty spaces as well as the far more important occupied spaces.

For the second option, the plus is that there shouldn’t ever be wasted space inside of the list, since only enough voxels are assigned at any point to the list to create their object; the wasted space around the tree trunk would disappear since the list never even bothers about that spot. In addition, I believe that there would be a boost in general speed since when iterating through the list, it again never bothers to check what isn’t there. However, with this method, I can’t come up with any way to infer the position of the voxels through usage of indices; the list doesn’t know anything about the width or length or height, it just stores the voxels. This leads me to using the 3-integer method described as above.

My question is, which is more efficient? I’m not that experienced with serious programming structure and the sort, usually I just throw it together without a care for the efficiency, so I’d like a few opinions as well as maybe some tips and tricks if anyone’s willing to share.

Also, if you actually read all of that, thanks for sticking with it. I can really be a little too wordy at times.

#2

I think an quad tree or oct tree would be the fastest solution.

Otherwise an array like this would be the fastest:

private Voxel[] group_voxels = new Voxel[w*h*l];

Memory is not such a big issue, cpu power, mostly, is.

#3

But that array again is larger than what’s necessary. Maybe the memory isn’t a big issue, but the extra space still has to be looped through. Wouldn’t that affect the cpu load required rather significantly?

#4

Well, think about when you are doing collisions. If you go with an Arraylist of voxels, you’ll have to loop through every voxel to check for collisions, rather than do some simple math. Also, when will you have to loop through the blocks, other than when you are rendering? And a simple if statement doesn’t take that much processing power.

#5

Would I not have to loop through with an array for collisions, then? If you could explain a little more how a 3d (or even 1d) array wouldn’t require looping for collisions, that’d make it a bit easier for me to wrap my head around.

Also, for the if statement, do you mean checking each index in the array like this, sorta?


...
for (int x = 0; x < width; x++ {
     for (int y = 0; y < height; y++) {
          for (int z = 0; z < depth; z++) {
               if (voxels[x][y][z] != null) {
                    // mesh update code
               }
          }
     }
}
...

As it stands, that’s what I’m using to create the VBO for the object.

While I’m typing this, another question: how would I go about applying rotations to each object individually? I know glRotate and glTranslate would work for the entire world or a single object, but I need to be able to move / rotate individual voxel groups, as well as individual voxels within a group. If I wanted rotating / moving voxels within the group, it seems inefficient to have to go through and re-work the entire mesh of the thing. So by that logic, I’m assuming I’d need to have the object have multiple groups of voxels?

Again, just brainstorming, putting it out there for any constructive folk who happen along.

EDIT: On the subject of “subgroups”, perhaps have an enum of what types of subgroups there are?

Also, things like: Would the gun on a turret need to know about what’s going on in the casing it’s attached to, AND the main body of a ship? Or would it just need to know the turret only, since the turret would already compensate for knowing the main body? Is that kind of “inheritance” going to cause issues? If so, is there another method around this? (I’m thinking mainly rotation along this path; the main hull would have its rotation, the turret casing would have its rotation relevant to the hull, and the weapons on the turret would have its rotation relevant to the casing, which is relevant to the hull.)

And on the same topic, what about collisions within the same structure? What if the turret gun knows about the casing, but not about the main ship? It would collide / be restricted to the casing, but how would it know to collide with or interact with the main hull? Is it possible to create a system that does all the collision checking and (possibly) queuing for them? How would it work? Raycasting? Or perhaps another method.

#6

HashMap<Vector3Int, Voxel>

#7

I’m no expert here, but my understanding is that the first major part of any collision detection is culling out collisions that will not happen.

After that, you can focus on which data structure will be fastest to iterate through.

So subdividing your collision data into chunks big enough to contain the largest possible movement vector would be a nice approach (which means defining an absolute universal maximum, or somesuch).