about Octree in huge scene
Author
hi, i have a question.
We used to manage the scene in Octree, like QUAKE game. I think the scene Octree must have been created once, and when the room mesh input, the Octree be created.
But, if the scene data is very huge, how can we create the Octree? It will cost too much time to create a scene Octree, and it's impossibility to create Octree in each frame.
So, a buge scene, like WORLD OF WARCRAFT, how do we manager the scene in Octree?
thanks.
You could create the oct-tree (or something comparable) in an offline process and store it with the rest of the scene. Later, when you load the scene you just load the oct-tree with it.
I've experimented with quadtrees of 32 Gigabyte data / 32k^2 pixels in size / 2 billion triangles in the past very heavily, having written an mmap-based huge array implementation that could eat indices beyond 32bit. That was fun, but it could take hours and days to create those, so I know your pain.
I've rewritten my quadtree in the meanwhile, and now create it lazily. Later I mabye implement caching. But the lazy thing is a gigantic improvement: picogen.deviantart.com (Memory usages are described in all images).
So,
* lazy (the first recursions won't hurt much, but if they do, you could, on top, create a grid of octrees)
* level of detail (i.e., don't expand nodes beyond their level of detail)
* culling
the culling part is of course quite easy in a ray tracer like picogen :)
I've rewritten my quadtree in the meanwhile, and now create it lazily. Later I mabye implement caching. But the lazy thing is a gigantic improvement: picogen.deviantart.com (Memory usages are described in all images).
So,
* lazy (the first recursions won't hurt much, but if they do, you could, on top, create a grid of octrees)
* level of detail (i.e., don't expand nodes beyond their level of detail)
* culling
the culling part is of course quite easy in a ray tracer like picogen :)
Why do you want to create an oct-tree every frame?
Also, Quake didn't use oct-trees, it used pre-compiled BSP-trees.
Also, Quake didn't use oct-trees, it used pre-compiled BSP-trees.
I usually build the octree during the level creation process.
Your method will work too. Just save a "cached" copy of the build octree and re-build it if the level data file changes.
That way you only have to build the tree once without the need for an offline preprocessing step.
I once made a game engine where you could input whatever and it would cache models, sounds, octrees, build lightmaps, optimize mesh animations etc and store it in a cache directory.
Your method will work too. Just save a "cached" copy of the build octree and re-build it if the level data file changes.
That way you only have to build the tree once without the need for an offline preprocessing step.
I once made a game engine where you could input whatever and it would cache models, sounds, octrees, build lightmaps, optimize mesh animations etc and store it in a cache directory.
Author
Thanks everybody.
It's good idea absolutely that create Oct/Quad/BSP tree in creation process.
Then, Another question:
If it's a huge scene, the data created is colossal too. So, it's impossible to load all the data in memeory. How can we do?
If we have to load a certain part of the data created each once, how can we determine which one will be loaded? Depending on the frustum, isn't it?
I am uncertain about it.
It's good idea absolutely that create Oct/Quad/BSP tree in creation process.
Then, Another question:
If it's a huge scene, the data created is colossal too. So, it's impossible to load all the data in memeory. How can we do?
If we have to load a certain part of the data created each once, how can we determine which one will be loaded? Depending on the frustum, isn't it?
I am uncertain about it.
You could load only what is needed/visible. And then you only keep the last N used nodes in cache, the others will be banned from memory until needed again.
You could use a double-ended queue for that. Each node that is drawn will be reinserted at the front of the queue. After re-inserting, don't forget to re-insert the parent nodes recursively, so that no parent will be banned with active children (yay, I just had that idea, and I could need it for picogen). Say your quadtree is of level 13 (which is already quite massive), then this will add 13 computation steps in the worst case. It gets relatively cheaper if the time of drawing a node increases (e.g. more polygons, more complex shaders).
Another solution could be a garbage collector: Have a global frame counter and one for each node. Upon drawing a node, update it's own frame counter, so that you have a measure on how old a node is. Again, don't forget to update parent nodes.
Personally, I prefer the double ended queue, as this will give you or the user exact control about the maximum memory usage.
edit: Oh, and let me re-iterate how important LOD is. Basically, without LOD, I needed roughly 32GiB quadtrees, where I now only need 1 or 2 for the same quality. Not exactly comparable as the implementations largely differ, but gives a good taste.
You could use a double-ended queue for that. Each node that is drawn will be reinserted at the front of the queue. After re-inserting, don't forget to re-insert the parent nodes recursively, so that no parent will be banned with active children (yay, I just had that idea, and I could need it for picogen). Say your quadtree is of level 13 (which is already quite massive), then this will add 13 computation steps in the worst case. It gets relatively cheaper if the time of drawing a node increases (e.g. more polygons, more complex shaders).
Another solution could be a garbage collector: Have a global frame counter and one for each node. Upon drawing a node, update it's own frame counter, so that you have a measure on how old a node is. Again, don't forget to update parent nodes.
Personally, I prefer the double ended queue, as this will give you or the user exact control about the maximum memory usage.
edit: Oh, and let me re-iterate how important LOD is. Basically, without LOD, I needed roughly 32GiB quadtrees, where I now only need 1 or 2 for the same quality. Not exactly comparable as the implementations largely differ, but gives a good taste.
I never had problems fitting Octrees into memory? Is it very detailed geometry? A garbage collector is a good idea and occlusion culling is also a major improvement to the octree algorithm. Unless it's mostly countryside ;)
I never did use LOD on the octree level itself. Just objects/characters.
I never did use LOD on the octree level itself. Just objects/characters.
Quote:Original post by ozak
I never had problems fitting Octrees into memory?
Just a question of how much detail you have :)
In my case, I stored 32768*32768 height values, effectively yielding two billion triangles (clicky).
Quote:I never did use LOD on the octree level itself. Just objects/characters.
I did so, too. But as I wanted to reduce memory requirements for the same detail (I am talking of ideally a few triangle per pixel), I added LOD and lazy building. Note though that this is, at least at the moment, for still images (see also http://picogen.deviantart.com, and for high quality ones.
Quote:they dont use an octree, they use a grid as the main map organization.
So, a buge scene, like WORLD OF WARCRAFT, how do we manager the scene in Octree?
Octrees, just like probably all trees, are used for sparse data, that means, lot of 'empty' space with some dense area. It would be not smart in most cases to start dividing a world like WoW by an octree and it wouldn't be smart to end dividing it by an octree. So, every grid-cell might have an octree representation, but every leave of the octree has probably a big bunch of data. It might be also a grid, but probably it's just a "soup of triangles" called mesh, some soup of logic data and a bunch of references to textures.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
