Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Zipster

BSP Trees, etc.?

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

Ive been reading this forum and i see a lot obout "BSP engines", and "portals" and "leafs"... WHAT THE HELL ARE THOSE THINGS? I know they have to do with 3D and stuff, since i did a little HL map editing in WorldCraft and those terms popped up often. I read somewhere that BSP are simply binary trees, but about portals and cells, im just confused. I looked around the net but had trouble finding comprehensive sites. Im sure you all know about all this since I live in a cave , so can anyone refer me to a REALLY good site on BSP Trees and potals thats easy to understand, etc., or maybe explain them here? Thx. Maybe THEN I''ll start a 3D engine . PCMCIA - People Can't Memorize Computer Industry Acronyms ISDN - It Still Does Nothing APPLE - Arrogance Produces Profit-Losing Entity SCSI - System Can't See It DOS - Defunct Operating System BASIC - Bill's Attempt to Seize Industry Control IBM - I Blame Microsoft DEC - Do Expect Cuts CD-ROM - Consumer Device, Rendered Obsolete in Months OS/2 - Obsolete Soon, Too. WWW - World Wide Wait MACINTOSH - Most Applications Crash; If Not, The Operating System Hangs

Share this post


Link to post
Share on other sites
Advertisement
You can find the BSP FAQ at: http://reality.sgi.com/bspfaq/index.shtml

BSP stands for "binary space partition." The "space partition" means that you are breaking up space (ie, your game world) into partitions (ie, small chunks). There are numerous reasons you would partition your space. For example, let''s say you need to check for collisions between the player and the walls. Using a BSP, you would check only those partitions in or near the player, rather than checking the entire world. Saves a lot of time.

The "binary" part of BSP is, as you heard, BSP is represented as a binary tree. Basically, the top of your tree is the entire world. Split it into two pieces somewhere: one partition goes on the left of the tree, the other partition on the right. Then recursively apply this process to the left and right sides, creating a tree as deep and wide as you need or want.

The big question in creating a BSP is where you divide your space at each level. For the BSP tool I wrote, I choose a plane (ie, a plane divides 3d space into two 3d partitions) aligned with a polygon that cuts the fewest polygons. This is a typical choice.

But I refer you to the FAQ at the top of this reply, since it will explain things better than I can.


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!

Share this post


Link to post
Share on other sites
thx man, that site was great! I think i have it now (well, at least BSP Trees, I still don''t know about portals, etc.)/
Thanx again!!

Share this post


Link to post
Share on other sites
HOLY SHIT! (excuse my language and my excitement) i was using BSP all this time without even knowing it! (i thought i had developed it by myself (well, i discovered it by myself at least) and as i was "developing" it, i said, hey, i think DOOM worked this way..... anyway, it''s nice to know that i can say, "i''m using BSP" now.

a2k

Share this post


Link to post
Share on other sites
A portal is simply a (usually transparent) polygon that connects two sectors (rooms, in Quake''s case). Quake 2 uses what is called an area portal system, which works like this:

1. find the room the player is in
2. add the BSP for that room to the "needs to be drawn" list
3. if there are any "open" (as in doors raised) portals, add the BSP''s of their sectors to the list.

That''s a pretty simplified description, but it should be enough to get the point across. Also, the Flipcode column WitchLord was referring to is:

http://www.flipcode.com/portal/

which has more than you''d ever want to know about portal rendering techniques and even some BSP stuff too.

-Liquid

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!