Sign in to follow this  

Spatial Partitioning question

This topic is 4857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Yes, spatial partitioning algorithms are asked about all the time, but my question is a little different. I don't think anyone has asked this one before. Anyways, most all games I've seen that have well documented level formats use some version of the bsp format (half-life, quakes, dooms, so on and so forth). I haven't seen anyone using like an octree or a quadtree format or anything like that. Do people just always calculate this stuff at runtime like I've been doing, or do game programmers have a format set out to have this stuff compiled into a file like the bsp formats? I've seen alot of tutorials on how to construct an octree, but I really haven't seen any that show how to use them. It's a pretty simple thing to write a class that will decompose a set of vertices into an octree, but is that how it's done normally, at runtime I mean? What about huge scenes with very high detail? Wouldn't that take forever as the algorithm is recursive and all? If these data structures are saved into some sort of file format, does anyone have an example that's at least documented a little?

Share this post


Link to post
Share on other sites
Constructing the octree everytime you load a scene would be insane.That sort of are done off-line.You get a scene comprised of polygons(created in 3DMax for example),you construct the octree and save it to your own file format.In runtime,you just load that file and use the info to reconstruct the octree in memory.I don't know any official format,but it's not hard,it's just like saving any other tree structure.My choise would be to store in the file both the polygon soup and the tree nodes.First you will save the primary node,and then all the nodes below it.
What you have to do is traverse the whole octree,and save to the file each node you encounter.The terminal nodes will contain the indexes of the polys they contain.When you later load the file,follow the inverse approach(load the primary node,then its 8 children,the childrens of each children,etc...).

Share this post


Link to post
Share on other sites
Those formats you mentioned uses a BSP mainly for historical reasons. It made sense five years ago, and since they had lots of tools developed for working with a bsp, they stuck with it.

When it comes to building your spatial data struc6ture, don't do it at runtime. There's no point, since you can just do it at level creation time (the levels won't change) and that way you can spend more CPU to get a better data structure. Ideally, loading at runtime should just consist of blasting data off disk straight into memory.

Share this post


Link to post
Share on other sites
Quote:
Original post by mikeman
Constructing the octree everytime you load a scene would be insane.That sort of are done off-line.You get a scene comprised of polygons(created in 3DMax for example),you construct the octree and save it to your own file format.In runtime,you just load that file and use the info to reconstruct the octree in memory.I don't know any official format,but it's not hard,it's just like saving any other tree structure.My choise would be to store in the file both the polygon soup and the tree nodes.First you will save the primary node,and then all the nodes below it.
What you have to do is traverse the whole octree,and save to the file each node you encounter.The terminal nodes will contain the indexes of the polys they contain.When you later load the file,follow the inverse approach(load the primary node,then its 8 children,the childrens of each children,etc...).


That's what i thought, but I'm woefully inadequate in my knowledge of spatial partitioning algorithms and how they're saved. I'm not even familiar with how they do it with bsp trees, except superfically (I've read some of the bsp stuff from gametutorials.com). I suppose I should learn how they handle that first as an example to what I should be doing?

Share this post


Link to post
Share on other sites
I currently do everything at run time and it is really lousy. I am trying to move to a compiled format but haven't got the permission yet to do so. But my visualization is from external GIS sources and my company can't decide if they want to compile all external data to an interal format and take the storage hit.

Share this post


Link to post
Share on other sites

This topic is 4857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this