Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (636)
Games in Android Showcase (178)
games submitted by our members
Games in WIP (685)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Data structure for voxels?  (Read 2251 times)
0 Members and 1 Guest are viewing this topic.
Offline EliwoodL

Senior Newbie

« Posted 2013-07-11 20:52:01 »

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.
Offline RobinB

JGO Ninja

Medals: 44
Projects: 1
Exp: 3 years

Spacegame in progress

« Reply #1 - Posted 2013-07-11 21:50:57 »

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.
Offline EliwoodL

Senior Newbie

« Reply #2 - Posted 2013-07-11 22:20:07 »

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?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Geemili

Senior Devvie

Medals: 9
Projects: 1
Exp: 2 years

No Games Finished

« Reply #3 - Posted 2013-07-11 22:27:19 »

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.
Offline EliwoodL

Senior Newbie

« Reply #4 - Posted 2013-07-11 22:52:44 »

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.
Offline HeroesGraveDev

JGO Kernel

Medals: 360
Projects: 11
Exp: 3 years

┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻

« Reply #5 - Posted 2013-07-12 03:42:41 »

HashMap<Vector3Int, Voxel>

Offline Oskuro

JGO Knight

Medals: 46
Exp: 6 years

Coding in Style

« Reply #6 - Posted 2013-07-12 09:21:38 »

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).

Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Dwinin (59 views)
2015-11-07 13:29:08

Rems19 (72 views)
2015-10-31 01:36:56

Rems19 (64 views)
2015-10-31 01:32:37

williamwoles (102 views)
2015-10-23 10:42:59

williamwoles (88 views)
2015-10-23 10:42:45

Jervac_ (102 views)
2015-10-18 23:29:12

DarkCart (128 views)
2015-10-16 00:58:11

KaiHH (112 views)
2015-10-11 14:10:14

KaiHH (150 views)
2015-10-11 13:26:18

BurntPizza (164 views)
2015-10-08 03:11:46
Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30

Rendering resources
by Roquen
2015-10-15 07:40:48

Math: Inequality properties
by Roquen
2015-10-01 13:30:46

Math: Inequality properties
by Roquen
2015-09-30 16:06:05

HotSpot Options
by Roquen
2015-08-29 11:33:11 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!