Jump to content
  • Advertisement

Archived

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

BlackScar

BSP - Am I getting this right?

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

Ok, this goes out to all of the ones with the golden ticket (programmers that have mastered the art of BSP trees) Am I understanding this correctly? You take all the planes and split them down the middle to make a root. This root, is it a plane? How would you go about storing this root into a file? Just write the plane''s points on the first line? You''re also suppose to split the planes that go across the root too aren''t you. After you do that then what? I''m totally confused about this whole subject, but I do think I''m nibbling at it. Please can anyone show me some light? This thing is totally crucial to my game... Justin Eslinger

Share this post


Link to post
Share on other sites
Advertisement
Take a look at these urls. I also have a leafy BSP tree demo on my webpage with source that you could look at.

http://reality.sgi.com/bspfaq/
http://www.cs.cornell.edu/cs410-fa99/Handouts/BSP.htm
http://www.cs.buffalo.edu/~whitley/research/graphics/bsp/tutorial.html
http://web.mit.edu/napoli/www/6.838/bsp.html
http://www.exaflop.org/site/frames.cgi?HREF=http://www.exaflop.org/docs/naifgfx/naifbsp.html
http://members.xoom.com/3dcoding/tom_h/bsp.htm

When you look at those sites remember that there are many ways to handle BSP trees. There isn''t a single solution for generating a BSP tree, so don''t be alarmed when you read information that seems to conflict with other info. If you need anymore help just email me and I can try to explain things more.

Nate
http://nate.scuzzy.net

Share this post


Link to post
Share on other sites
ok... for a node based BSP (the one most commonly described and probably the most commonly used), here''s what you do.
1. copy all polygons in the scene to the top node
2. pick a polygon in the node (more on how to pick the polygon later).
3. take the plane that the polygon lies on, find all the polygons behind it and move them to the back list, find all the polygons in front of it, move it to the front list and store all polygons that are co-planar to the splitter, including the splitter, at the current node. polygons that straddle the splitting plane have to be split.
4a. if the back list isn''t empty, recurse into it starting at step 2
4b. if the front list isn''t empty, recurse into it starting at step 2

that''s all there is to it. in order to find the best splitter, try every polygon in the current node and find out how many polygons it splits (the less the better) and what is the difference between the number of front children and back children it generates (the less the better).
i''m sure you know the math behind classifying polygons as behind a plane, in front of it, etc, and if you don''t, there are plenty of texts on this on the web or your local math library.
hope this helps.

-goltrpoat


--
Float like a butterfly, bite like a crocodile.

Share this post


Link to post
Share on other sites
one quick question here.

go ahead and call me stupid, but why can''t you just sort all polygons according to thier z value? (I don''t fully understand everything about 3d). I realize that it wouldn''t sort them from left to right correctly, but couldn''t you sort the x value to do that?

- Moe -

Share this post


Link to post
Share on other sites
Because of the relativistic nature of 3D programs (polygons are in space relative to the camera, etc), sorting using a set z-value will not work.If you turn sideways, all the polygons suddenly have the same "depth" and must all be processed. Not a pretty picture. BSP trees provide a method of easily culling half of the possible polygons at a time. Culling polygons in calculation is very good, because it means your 3D card isn''t doint needless rendering and overdraw.

Share this post


Link to post
Share on other sites
But i thought in a 3d world, the world moved around you, not the camera moving around the world?

Share this post


Link to post
Share on other sites
Moe,
BSP trees are mostly used for back to front drawing.
You could sort the polygons according to the average z value (the painter''s algorithm), but then one or more polygons would have the same z value and you would get visual artifacts. Also if two polygons intersect in a peculiar way - for example:
+++ - +
+ -
-+ - - you can never draw then correctly without splitting them up.
(sorry for the ASCII graphic but I still haven’t learned how to put up a picture. How do you put up a picture up here, anyway?)

have fun,
Pascalix

Share this post


Link to post
Share on other sites
Anyone have code/tutorial for loading/displaying standard bsp map files.
Like quake map files?

MCSE, MCSD, Sun Certified Java Programmer
Pimp Daddy ;)

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!