• Advertisement
Sign in to follow this  

space partitioning questions

This topic is 4242 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

i have been doing some research on bsp and octrees and have some questions: 1. which would be best for levels that alternate between indoor and outdoor areas? 2. which is better for collision detection? 3. which better suits conditions where characters (npc and player) and some objects may be moving in and out of nodes? 4. do display lists work for bsp or octrees? if so, would i just have to create a display list for each node? (on the topic of display lists -- can normal or paralax mapping be done with display lists or should i use vbos?) 5. does anyone have a good tutorial that discusses the theory and also has example code for your prefered method? 6. do these methods lend themselves to LOD algorithms? thanks for the help! disclaimer -- please do not tell me to download quake's source because i have, and following it is, to me, fairly difficult. also, i have read papers on the methods to do the partitioning, but i really don't know how to do it myself without seeing an example. i did search the forums but i am adverse to disecting someone's code that didn't specifically put it up as a tutorial or example.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
So basically you are telling us you are a lazy noob. Why should someone waste their time helping you when you can't even look through code that works or do a search on the internet?

Share this post


Link to post
Share on other sites
no, more accurately i don't understand how you would divide polygons and i was never very good with linked lists. which is what octrees and bsp trees seem to be. furthermore, the papers and topics i have read seemed to say different things for instance -- it seems to me that most people use bsp trees for indoor environments and octrees for outdoor, but does one behave better than the other when used in both situations?

also, if the quake3 source is so easy to follow, where does one start in the quake3 source to understand how they build their bsp trees?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by supercat1
i was never very good with linked lists.


Yer in trouble.
Seriously

space partitioning, and heck, games in general are the least of your concerns if you don't have the basics yet.




P.S.
I use Portal Systems for all my space partitioning.

Share this post


Link to post
Share on other sites
well, i'm just not very good at developing them myself. when i was working with them in class it made sense (and i have multiple data structure books i reference when working with linked lists and hashes and what not) but i'm not the greatest at sitting down and thinking them up right off the top of my head.

anyways, i guess this is a good time for an update --

i found a tutorial that had a great explanation of what is going on and essentially answered my questions on how to do it, collision detection, and display lists. however, i'm still wondering about which is preferable for LOD and moving objects.

Share this post


Link to post
Share on other sites

There is no reason why you couldn't implement system which uses Octrees for outdoor environments and BSPs for indoors.

You'll need to run tests to see which one suits best for collision detection etc. The answer isn't that simple.

Also, consider that drawing a BSP tree might not be the most efficient way of drawing things with a GPU. Pushing a lot of static triangles once results usually better performance.

All the spatial partitioning trees work in a similar way. Doesn't matter if it was BSP-tree or quadtree or octree ... The idea of having some 2d-3d space and the dividing it accordingly by the desired method. You should be able to figure out the way of splitting by drawing some geometric shapes on a paper.

Share this post


Link to post
Share on other sites
when looking at bsp i noticed that the papers were saying stuff like "now pick a polygon to use as the splitting plane" and i wasn't sure if they ment manually or what. i just remember in school when working with binary trees we worked with ways to make them and then resort them so that they were ballanced, and that just wasn't fun. is this something that many bsp implementations use?

while i was reading the demo/tutorial i mentioned in my previous post it occurred to me that searching a large octree probably wasn't the best way to actually render the scene. so i was thinking i would use it only for collision detection (know what node an object is in and then only check collisions in there, or surrounding nodes if it is that big) and then keep a single display list as the rendering method.

thanks for the input!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by supercat1
when looking at bsp i noticed that the papers were saying stuff like "now pick a polygon to use as the splitting plane" and i wasn't sure if they ment manually or what. i just remember in school when working with binary trees we worked with ways to make them and then resort them so that they were ballanced, and that just wasn't fun. is this something that many bsp implementations use?

YES

Quote:
Original post by supercat1
while i was reading the demo/tutorial i mentioned in my previous post it occurred to me that searching a large octree probably wasn't the best way to actually render the scene. so i was thinking i would use it only for collision detection (know what node an object is in and then only check collisions in there, or surrounding nodes if it is that big) and then keep a single display list as the rendering method.

Depends how big the world is. If there's like 5 *sarcasm* triangles in your scene then sure, a single display list is fine.
If theres a whole lot, say 5K triangles, Octrees are Excellent for determining which one's can be skipped to save render time.

Share this post


Link to post
Share on other sites
I'm currently developing a graphics engine to deal with very big outdoor environements and indoor scenery (e.g. landscape with cave systems and other sorts of dungeons in it). There is acutally no such thing like levels, there is only one big world. For the terrain itself i use octrees because frustum culling and lod implementation is fairly easy and effective. For the indoor scenes, I basically use a Portal system within the octree nodes.

As you can see, it's not too hard to combine those techniques. Just stick whith whatever thing you believe to be effective for the specific task and then merge the algorithms.

PS: you should definitely stick with such simple datastructures like linked lists, till you get them clear, before starting on BSP or Octrees...


t0}{!c

Share this post


Link to post
Share on other sites
again, thanks for the input!

i'm afraid i might have downplayed my knowledge. linked lists just weren't my favorite part and so took a little more time to grasp. that isn't to say i never did, i just don't believe they are my strongest point. which is exactly why i was looking for a tutorial/demo that would go through and explain what was going on. :)

toxic -- do you have links to any papers or discussions that helped you get the portal system into your engine?

well right now i'm using a display list to draw about 13k triangles and on my geforce4 mx440 i'm getting an average of 85 fps while on newer hardware it is about 1k. i know this isn't very indicative because there currently isn't any collision detection, shaders, or such stuff but my initial interest in the octree/bsp tree was for collision detection.

thanks again!

Share this post


Link to post
Share on other sites
BSP really doesn't work that well for outdoor rendering, and with the power of graphics cards these days, a good octree implementation can render indoor enviroments nearly as quickly. Octrees are also vastly simpler to implement, if that is a deciding factor.
Another good aproach to pursue is a combination; Octree for outdoors and portals for indoors.

Anonymous Poster: You are acting like an absolute pain in the *********, and really you are not providing any useful information. Would you mind finding somewhere else to be an ass?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by swiftcoder
Anonymous Poster: you are not providing any useful information.



What I've said so far is True.
It is useful information, just lacking a full background explanation, he just has to take my word for it.
Not everyone has the time or patience to write out long detailed answers.

Do you want me to elaborate?
Fine, I'll give even better advice than yours:

Quote:
Original post by supercat1
when looking at bsp i noticed that the papers were saying stuff like "now pick a polygon to use as the splitting plane" and i wasn't sure if they ment manually or what. i just remember in school when working with binary trees we worked with ways to make them and then resort them so that they were ballanced, and that just wasn't fun. is this something that many bsp implementations use?

YES

-a balanced BSP tree is very important for optimal rendering. Take for example the case where the root of the tree is a polygon that happens to be at the very edge of the map, and the next one is right next to it, and so on in order to the other side of the map.
In this case, when checking for areas for visibility you'd end up doing a transversal across on average half the polys in the map.
Ideally, you want the first polgon in the BPS to be near the middle of the map so it creates two equally sized regions (with equal polys in each)
Each subsequent BPS level should similarly attempt to do an even split for it's area.
This reduces the overall height of the BSP tree and increases it's efficency at rendertime.
So YES, you will need to do that annoying BSP balancing stuff from school, sorry but you have to deal with it.

Quote:
Original post by supercat1
while i was reading the demo/tutorial i mentioned in my previous post it occurred to me that searching a large octree probably wasn't the best way to actually render the scene. so i was thinking i would use it only for collision detection (know what node an object is in and then only check collisions in there, or surrounding nodes if it is that big) and then keep a single display list as the rendering method.


Depends how big the world is. If there's like 5 *sarcasm* triangles in your scene then sure, a single display list is fine.
If theres a whole lot, say 5K triangles, Octrees are Excellent for determining which one's can be skipped to save render time.

-It's a tradeoff really between CPU and GPU workload. the video hardware is quite fast, so for small (getting bigger as new cards come out) numbers of polygons, doing brute force rendering of them all can be effective.
To go beyond this limit however, we genrally do a visiblity check on CPU to decide if large numbers of polygons are not going to be seen anyway (from the camera's position). Octree happens to be a very effective way to do this. However it does require work on the part of the CPU as well as you the programmer.
Your display list proposal might very well work(I cant tell since i dont have enough info on your project), but if it does turn out to be slow consider using an Octree.



You seem to be considering mainly BSP and Octrees at this time. May I ask what kind of environment you wish to use in your game?
For outdoors, a simple variant of Octree: the Quadtree (basically a flat 2d octree) is usually best.
BSP is better for indoors, however it is rather antiquated, and you might consider learning about Portal Systems instead, since many of the benefits offered by BSP have since been superceded. It's not exactly a bad choice tho, I belive as recently as Halo it has been used to some extent (within a hybrid system). and If you want depth sorted polygons for special transparancy effects it will give you this...

Basically BSP is good for decideing what polygons (walls) are infront of others. This lends itself naturally to indoor environs.
Oct/Quadtrees are good for visibility rejecting large areas of space at a time. thus very useful for large open outdoor areas.

Share this post


Link to post
Share on other sites
Quote:
What I've said so far is True.
It is useful information, just lacking a full background explanation, he just has to take my word for it.
Not everyone has the time or patience to write out long detailed answers.

Do you want me to elaborate?
Fine, I'll give even better advice than yours:

*quote removed*
YES

-a balanced BSP tree is very important for optimal rendering. Take for example the case where the root of the tree is a polygon that happens to be at the very edge of the map, and the next one is right next to it, and so on in order to the other side of the map.
In this case, when checking for areas for visibility you'd end up doing a transversal across on average half the polys in the map.
Ideally, you want the first polgon in the BPS to be near the middle of the map so it creates two equally sized regions (with equal polys in each)
Each subsequent BPS level should similarly attempt to do an even split for it's area.
This reduces the overall height of the BSP tree and increases it's efficency at rendertime.
So YES, you will need to do that annoying BSP balancing stuff from school, sorry but you have to deal with it.


it seemed, if i remember correctly, when i did it in school (and this is definitely far from perfect) we started with learned by just using the first value that was passed in. then we moved to methods of randomly choosing a number that was passed in (these are just basic binary trees for sorting numbers and such, but obviously the idea was to expand them for later projects). and then we moved to making a tree then finding a value in there that would produce a better tree and resorting it. however, with the bsp tree, since all the static poly data is known, couldn't you find the center point of all the data, locate the poly closest to it and then use that as the starting point for the bsp? then you wouldn't have to build it once, check to see if it is mostly ballanced and then if not resort it.

Quote:

*my quote removed*

Depends how big the world is. If there's like 5 *sarcasm* triangles in your scene then sure, a single display list is fine.
If theres a whole lot, say 5K triangles, Octrees are Excellent for determining which one's can be skipped to save render time.

-It's a tradeoff really between CPU and GPU workload. the video hardware is quite fast, so for small (getting bigger as new cards come out) numbers of polygons, doing brute force rendering of them all can be effective.
To go beyond this limit however, we genrally do a visiblity check on CPU to decide if large numbers of polygons are not going to be seen anyway (from the camera's position). Octree happens to be a very effective way to do this. However it does require work on the part of the CPU as well as you the programmer.
Your display list proposal might very well work(I cant tell since i dont have enough info on your project), but if it does turn out to be slow consider using an Octree.


that was another reason i was looking into bsp/octree systems -- they seemed to be an adequate way to do frustum culling.

Quote:
You seem to be considering mainly BSP and Octrees at this time. May I ask what kind of environment you wish to use in your game?
For outdoors, a simple variant of Octree: the Quadtree (basically a flat 2d octree) is usually best.
BSP is better for indoors, however it is rather antiquated, and you might consider learning about Portal Systems instead, since many of the benefits offered by BSP have since been superceded. It's not exactly a bad choice tho, I belive as recently as Halo it has been used to some extent (within a hybrid system). and If you want depth sorted polygons for special transparancy effects it will give you this...

Basically BSP is good for decideing what polygons (walls) are infront of others. This lends itself naturally to indoor environs.
Oct/Quadtrees are good for visibility rejecting large areas of space at a time. thus very useful for large open outdoor areas.


well, the environment will be changing for each scene/level, though it probably will be about 50% indoor and 50% outdoor. i don't envision or expect it to be a halo like game where you move from one to the other, but rather much more in the manner of games like silent hill -- indoor and outdoor environments that are distinct. speaking with a friend of mine in the video game industry who has written a book, he suggested using a quadtree also. i'm guessing this would probably work fine since i don't predict there will be any flying elements (though there may be some gravity shifting going on, ala prey). in that case, wouldn't it be similar to an octree only, instead of dividing the space into stacked boxes, everything just has the height of the base node and then the area of the footprint on the xz plane is what is being divided?

thanks for the info!

Share this post


Link to post
Share on other sites
This realy depends on what you actually want to do. If you want to go the oldschool way with having several different levels/maps (just like half-life quake, ...) you should consider implementing both, a octree (or quadtree) and a portal sytem and decide on a per level basis what to use. This may be rather unflexible but should definitely suffice for such types of games.

If you rather want to make a game like halo or Morrowind to name just some, it would be more flexible to combine some of the techniques.

Like mentioned before you could also just stick with octrees/quadtrees for indoor, but they ar rather ineffective, because you can most of the time only use them for frustum culling and lod with good cost/efficiency tradoff. I personally like the combined octree/portal implementation very much for indoor rendering, because you can easily imagine the portals as near-planes of little view frustums in your actual camera view frustum, and use them to cull more data behind your occluders with just the same technique you already implementet. And this is where the octrees come into play: rather than brute-force culling singe triangles or single objects, you can cull nodes of a tree structure which makes it very efficient.


Using Quadtrees or Octrees once more depends on the stuff you want to do with them. For example if you haven't got much layers of height, like a normal terrain engine or lets say an indoor-level with not much more than one structural level, you can savely use quadtrees, which are also faster in this case.

On the other hand, if you want to create a city that is buit up in the air for example, with some terrain stuff beneath it, you would for example get problems implementing an LOD system with Quadtree, because the city would be in the same Quad as the camera which could stand on that terrain stuff. ;) They would now be treated with the same LOD and although it could be kilometers away, it would be rendered with a complexity, as if it was right in front of you.

I think you get the point ...


Quote:
toxic -- do you have links to any papers or discussions that helped you get the portal system into your engine?


Sorry, I just read a view things about the basic ideas of portals, and some implementation detail, but I didn't realy save them anywhere, since I can think the rest up myself, but you won't have too much trouble finding a lot of papers an discussions on portals, because portal-engines were hyped (just like the xml , python, lua, ... stuff nowadays) just a few years ago.


t0}{!c

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement