Jump to content
  • Advertisement
Sign in to follow this  
leahayes00

BSP Trees and Portals

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

Hi All, I am currently in the process of creating my first 3D engine and its editors. My scene data is stored using classes, but basically is of the form: struct CVertex3D { float x, y, z; }; struct CEdge { CVertex3D *verts; int total_verts; }; struct CPolygon { CEdge *edges; int total_edges; }; struct CMesh { CPolygon *polys; int total_polys; }; I am completly new to the ideas of BSP trees and portal systems; how can I create a program which will automatically generate a BSP tree from this mesh data and then generate the portal system? Any help would be greatly appreciated! Best Regards, Lea Hayes

Share this post


Link to post
Share on other sites
Advertisement
Just a thought, and i'm sure people may disagree, but would it not be better to have an edge class that stores indexes to the vertices, just so in the future you dont risk transforming vertices more than once.

You could just run through all of the vertices associated with a model and transform them, then use your framework to control the rendering order.

Share this post


Link to post
Share on other sites
ermmmm... unless you want hell on your head, generate portals using CSG data, not BSP... I've gone through the BSP way and it'd be hard for me to recommend it to anyone (not that I've failed ;] )...

Share this post


Link to post
Share on other sites
Here's an article here on GameDev about automatic portal generation:

http://www.gamedev.net/reference/programming/features/apg/

Share this post


Link to post
Share on other sites
Hi,

A few questions about CSG data:
-> What is it?
-> Any advantages or disadvantages over BSP data?
-> Is it easily calculated from mesh data?

Thanks for all of the links!

Lea Hayes

Share this post


Link to post
Share on other sites
CSG stands for Constructive Solid Geometry. In CSG, each building block is defined by planes that intersect with each other forming a convex volume. For example, to define a cube, one would use six planes whose normals point away from each other.

Unfortunately, there's no way to generate CSG from arbitrary polygon/vertex data you are currently using -- it only works the other way around.

Share this post


Link to post
Share on other sites
Let me address these two:

-> Any advantages or disadvantages over BSP data?
-> Is it easily calculated from mesh data?

First of all, you don't want to calculate your portals using the mesh data. I though once I could, but the world geometry complexity quickly killed me. The point is that portals allow you to have highly detailed environments. Such detailed env arent a good material for BSP calculation. Ok, maybe for some sorts of BSP they are however you'd need a Solid-Leafy BSP tree that is very hard to calculate in the right way. If you have your BSP constructed for arbitary geometry, floating point errors can kill you, you'd have to use lots of small tricks and calculation validations (like I did) or resort to unlimited precission arithmetic. In either case you get mediocre performance.
So the key point is that the geometry is too complicated to make BSP out of it.

Here comes the other option: Use your favourite modelling program and make some boxes. Let these boxes define your rooms. You can later put any detail into them (they are the top-level volumes that represent conservatively your room data). Now if you perform CSG on these boxes, you'd get a very low detail representation of your level data. Now, you don't want to display it anywhere, so you build more detailed world and 'put it inside the boxes'. Now you have your hi-res world in the low-detail boxes. The CSG gives you portal and room data.

So, what are the advantages of CSG over BSP here ? well, basically, CSG can be done as a form of BSP, however first CSG'in the boxes and then applying BSP portalization on them would just be redundant. Instead, you calculate your portals using CSG. Like, you carve one box with another, you know which faces of the other box have been clipped out. Let these define your portals. You can then apply your favourite mesh simplification on them.

Another view at BSP portalization: using BSP portalization you can generate perfect portalizations (i.e. the case whene you couldn't have placed portals better by hand) if you want CONVEX rooms. That isn't possible for CONCAVE rooms, unless you can clearly define how perfect portalization on concave rooms look like.

Unless perfect portalization is the point, going with the CSG method is better because with it, you get good portalizations with concave rooms and that's often the desired case, otherwise you'd have to connect your concave rooms into convex ones using some heuristics, since convex rooms are cool, but only if you don't have excessive amounts of them :]

Anyway, search for Angel Popov, portalization and CSG here and on flipcode's Message Boards. Also, there's a dude who has done a nice editor that you can look at if you need some ideas. The link to an IOTD on flipcode is here:

http://www.flipcode.com/cgi-bin/msg.cgi?showThread=08-14-2001&forum=iotd&id=-1

If you're planning on doing a CSG compiler, I would strongly suggest thinking REALLY hard about proper polygon splitting. The splitters that ppl give code for in the net do not perform in the right way when it comes to floating point errors. You have to predict any error in your clipping routines and correct these errors. When you've done that poly splitting. Test it until you're COMPLETELY SURE that it's performing fine

If you want to learn BSP in the right way, I'd recommend looking at Mr.Gamemaker's tutorials. They used to be freely available on the net, though now they are only given as game institute courses so I don't know if the license allows ppl to freely distribute the version of the tutorials that used to be free. Some ppl should have those 'free versions' though ;)

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!