Ideas for large 3d cell-based scene...
Author
Hi all,
I''m trying to implement a large scene composed of cells (such as a 3d array). I need to work out which cells to render / process in as fast a way as possible. At the moment the world is stored as a 64x64x64 3D array (this will need to be alot larger than this for the final game world).
Each cell in the array needs to know if an event has happened to any of its neighbouring cells. It will then modify it''s state and possibly move to another position within the 3D array so you''ll have alot of movement / checking within the data structure.
At the moment this is a fairly time consuming task just to parse the array! I''ve tried implementing an Octree to store the data structure instead with the final child nodes storing several of the cells and whilst this helps the rendering times with frustum clipping it is v.slow for interrogating the neighbouring cells as can involve several tree jumps per cell in the worst cases. :-(
Any ideas would be great!
Thanks in advance :-)
Author
Anyone? :-) At the moment I''m working on the idea of keeping the data in the 3d array and creating some kind of simple space partitioning algo inorder to work out what cells to draw. This allow the array to be manipulated quickly and isolating cells to draw will be quicker. Does anyone have any experience with this type of thing?
Cheers
Cheers
Not quite sure what your problem is,
Why do you need to jump around in the tree if it is all stored in an octree? Just cull away the entire subtree.
Not sure about anyone else, but this means very little to me. What do you mean by ''event''? Is this a collision thing? A rendering thing?
What exactly are stored in the cells? Is it 3D geometry data? or is this some sort of 3D Game of Life?
Sounds like a k-d tree would work, but answer the above points before I comment further.
quote:
frustum clipping it is v.slow for interrogating the neighbouring cells as can involve several tree jumps per cell in the worst cases. :-(
Why do you need to jump around in the tree if it is all stored in an octree? Just cull away the entire subtree.
quote:
Each cell in the array needs to know if an event has happened to any of its neighbouring cells. It will then modify it''s state and possibly move to another position within the 3D array so you''ll have alot of movement / checking within the data structure.
Not sure about anyone else, but this means very little to me. What do you mean by ''event''? Is this a collision thing? A rendering thing?
What exactly are stored in the cells? Is it 3D geometry data? or is this some sort of 3D Game of Life?
quote:
Anyone? :-) At the moment I''m working on the idea of keeping the data in the 3d array and creating some kind of simple space partitioning algo inorder to work out what cells to draw. This allow the array to be manipulated quickly and isolating cells to draw will be quicker. Does anyone have any experience with this type of thing?
Sounds like a k-d tree would work, but answer the above points before I comment further.
If you are worried about finding the neighboring cells, just keep pointers to them. So each cell would have a pointer to its neighboring cells.. this can be determined once when the octree it constructed.
-BH
-BH
Author
Hi all,
JuNC: Sorry if my post is a little unclear. Yes I am culling away against whole sub-trees. The problem with the culling method is if my entire 64x64x64 grid is full, so my Octree is full and I''m viewing the whole level then I''m losing too much processing determining that the parent is visibly, then checking if the children are visible etc.. The problem is the worst case scenario is too bad and I need a routine that would be fairly consistant :-(
Yes the best way to describe this is as a giant 3d game of life. So I need to know the status of the surrounding cells to determine my current cells status. So I guess I should rephase
-> if you were going to implement a 3D game of life, how would you have stored the data?
BrianH: Thanks for the idea, unfortunatly I''m trying to squeese this into as little memory as possible and can''t afford the extra pointers per cells really :-( Still definetly an idea to consider!
Cheers
JuNC: Sorry if my post is a little unclear. Yes I am culling away against whole sub-trees. The problem with the culling method is if my entire 64x64x64 grid is full, so my Octree is full and I''m viewing the whole level then I''m losing too much processing determining that the parent is visibly, then checking if the children are visible etc.. The problem is the worst case scenario is too bad and I need a routine that would be fairly consistant :-(
Yes the best way to describe this is as a giant 3d game of life. So I need to know the status of the surrounding cells to determine my current cells status. So I guess I should rephase
-> if you were going to implement a 3D game of life, how would you have stored the data?
BrianH: Thanks for the idea, unfortunatly I''m trying to squeese this into as little memory as possible and can''t afford the extra pointers per cells really :-( Still definetly an idea to consider!
Cheers
About finding neighboring cells:
How are you storing your data? If your leaf nodes can be stored in a contiguous array, you can access the nodes by indexes without having to use any more memory than before(except for one pointer to the array). Of course, if your world is big, you might run into problems finding that much contiguous memory. You can solve that without using too much more memory by breaking it up into smaller chunks and connecting it to branches in your octree. For your example of 64x64x64, you could divide the array into 8 chunks, each 32x32x32, and connect them to your first set of nodes in your octree(1st or 2nd level, depending on how you count) When you have to look across subtrees, you'll still have to back up and traverse the tree, but within the subtree you can access the leaf nodes by index. As far as more memory, this needs a pointer to each chunk.
If you can't store your data in arrays directly, at the very least you can create new arrays with pointers to your leaf nodes. Sure, that takes memory, but not as much as adding 6 pointers to each leaf node to find its neighbors.
[edited by - jediknight219 on October 17, 2002 9:45:44 AM]
[edited by - jediknight219 on October 17, 2002 9:48:31 AM]
How are you storing your data? If your leaf nodes can be stored in a contiguous array, you can access the nodes by indexes without having to use any more memory than before(except for one pointer to the array). Of course, if your world is big, you might run into problems finding that much contiguous memory. You can solve that without using too much more memory by breaking it up into smaller chunks and connecting it to branches in your octree. For your example of 64x64x64, you could divide the array into 8 chunks, each 32x32x32, and connect them to your first set of nodes in your octree(1st or 2nd level, depending on how you count) When you have to look across subtrees, you'll still have to back up and traverse the tree, but within the subtree you can access the leaf nodes by index. As far as more memory, this needs a pointer to each chunk.
If you can't store your data in arrays directly, at the very least you can create new arrays with pointers to your leaf nodes. Sure, that takes memory, but not as much as adding 6 pointers to each leaf node to find its neighbors.
[edited by - jediknight219 on October 17, 2002 9:45:44 AM]
[edited by - jediknight219 on October 17, 2002 9:48:31 AM]
Author
Hi jediknight219,
Yup, I''ve been thinking of something along these lines. I''m running some more tests at the moment, but it looks like the best way to get performance on a large world will be to have it either ideally as a long continious array or a smaller set of arrays and the octree to govern which parts of the array(s) to render.
Thanks all!
Yup, I''ve been thinking of something along these lines. I''m running some more tests at the moment, but it looks like the best way to get performance on a large world will be to have it either ideally as a long continious array or a smaller set of arrays and the octree to govern which parts of the array(s) to render.
Thanks all!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement