Jump to content
  • Advertisement
Sign in to follow this  
supercat1

space partitioning questions

This topic is 4425 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!