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

Do you have any resources to do with BSP trees?

Hi,

I have the following link:

http://members.net-tech.com.au/alaneb/main.html

Regards,
Lea Hayes

Try Gamedev's BSP Tree Frequently Asked Questions

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 ;] )...

Here's an article here on GameDev about automatic portal generation:

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

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

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.

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 ;)