Sign in to follow this  
leahayes00

BSP Trees and Portals

Recommended Posts

leahayes00    122
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
davidx9    184
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
h3r3tic    228
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
Arkion    122
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
leahayes00    122
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
Arkion    122
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
h3r3tic    228
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
Guest Anonymous Poster   
Guest Anonymous Poster
Well, here is a link you should take a look at...
I havent implemented this method yet, but it looks very interesting, I'll try to do it sometime...

http://w3imagis.imag.fr/Publications/2003/HDS03/mcp.pdf

Enjoy

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Hi,

h3r3tic: Thanks for your detail, it has changed my views on the subject.

Anonymous Poster: Thanks for the interesting concept.

Thanks for all of your help, it is much appreciated!

Best Regards,
Lea Hayes

Share this post


Link to post
Share on other sites
h3r3tic    228
omg... you want me to get mouth watering ? that method seems VERY promising :] Havent read the whole document yet but if they aint lieing then this method IS a killer :] thanks for the link

Share this post


Link to post
Share on other sites
ketek    132
I was silently following this thread when i came about the watershed method, i've implemented this code , so i can give
some thoughts about it , the code i've done is built upon
different stages, i have to admit that the idea is very clever
*but* it is very sensitive about the topology of the surfaces
i've encoded some quake 3 levels and went very well, while other
have very large 'unbounded' areas, further more the memory required is very large ( 4 buffers for a 3d grid of 256 voxels in my case ) so i've moved everything from memory to file. When i 've coded the Watershed method i thought i had the 'phylosofal stone' for 3d graphics, i was wrong, vey wrong, first the contact point beetween 2 different labels are the 'portals' very often the contact surfaces are complex, very difficult to group, i've done a convex hull
for enclosing that surfaces, large parts were still missing, causing the visibility code to bypass very large visible areas , more over the results were different between different maps.
So i've added stages upon stages to refine the portal computation
After struggling for few months, i've decided that this method is good for a very coherent map, full with othogonal walls,
the document never talks about patological conditions very difficult to avoid in my opinion and very common with complex levels.
So, now i'm now sticking back with k-d trees.

Share this post


Link to post
Share on other sites
h3r3tic    228
thank you, ketek. i was really gonna code that portalization method... now you've brougth me to the reality

so... the problem is that the portals between 2 different regions get very complex because geometry isn't that simple at the connections ? do i understand you right... sorry, but you don't write enough '.' and ',' in my opinion ;)

you're sticking back to k-d trees ? ermm... portal generation using k-d trees ? could you give some more detail/links ?

i'll try to investigate where i can get the bsp / csg portalization method... i'm hoping to find the holy grail as well ;)

Share this post


Link to post
Share on other sites
ketek    132
Sorry english is not my native language, i know sometimes
my posts are hard to understand, anyway , watershed method comes from image analisys , adapting to 3d isn't a joke i've worked
very hard for 3 months, an incredible numebrs of problem popped
up , when translating the concepts from a 2d image , which the document talks about , to a 3d world , first, memory footprint
isn't a thing you can underestimate , watershed method uses 4 buffers , say you want an accurate voxelisation of the world ,
you need 256x256x256x4 buffers of float this takes up several mb of memory , so the first problem was moving read and write operations from memory to file, slowing the creation process very considerably , second , the nightmare was understading
the way to consider labels , that were aoutsied the geometry of the same level , i mean watershed method labels everything,
you end up with large labels connected to 'nothing' i have used an heuristic to determine such areas , but sometimes it fails,
regions connecting different labels forms surfaces , you need to
separate each surfaces and find a plane for computing a convex hull for this surfaces projected on the plane , these are the
"portals" you look for, the code was not trivial, see, i had to
add stages upon stages to have an unstable algorithm not so robust as the paper states, i think that the author avoided some
cases which arise very quickly in a real level map.
moreover, little regions were scattered upon the map, another heuristic to cull them away, at least i was frustrated by the
several "noise" labels popping here and there, portals were too many to threat them quickly by the frustum check function dealing with many sides portals.
I 'm not saying that watershed isn't usefull, it is a well known
method in 2d image analisys and working very well even in image recognition , but i think its hardly adaptable for a 3d environment.
Just my thought.
Sorry for my english

Share this post


Link to post
Share on other sites
leahayes00    122
Hi,

ketek - would you be able to send an example of the implementation of the watershed-style method which you have implemented please?

Best Regards,
Lea Hayes

Share this post


Link to post
Share on other sites
ketek    132
Sure i will send you the 2d watershed method with source code fully functional , i've implemented as stated in the document, it works flawlessy for a 2d image, studyng the generated map
you will see how many problems will pop up to define which are the 'rooms' and what is the 'outside' of the room, anyway this code is still a simpler version, but it is usefull to study if you wnat to grab the watershed principle.
If you want to know more, just ask , but i think that for starting this code is ideal because it is not bloated with other function not relating to the proper method.
Send me an email and i will zip the project for you.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this