I'm working on setting up my engine for portal rendering. I understand the concepts behind portals fine, what I'm having difficulty with is figuring out how to take a map and divide it into sectors based on hand placed-portals. I realize it would be easier to define the sectors by hand as well but the map editor I'm using doesn't have a good solution for that, and it will be faster, once-implemented, to have the sectors generated automatically based on the portals. I would appreciate any help anyone can offer thanks

your map is a closed mesh?
any information about connectivity, or just triangle soup?

I guess you could walk from one triangle to the next, capping off at portals, to get a continous area that can be said to have those portals associated with it...
sounds... painfully expensive though

Break up the world into aa 3d grid, and flood fill algorithm?

Just triangle soup, but it is a closed mesh.

I read somewhere (may be unreliable), that Doom 3 used a BSP to determine the sectors based on hand placed portals (using the portals as the splitting planes?). I explored this option but ran into the problem of some sectors getting split wrong. Has anyone had success with this approach?

If not I will look into the flood-fill approach. from what I've read it sounds like the next best approach with what I have to work with.

Does anyone have any idea how this might have been handled in Doom 3? The seperation between sectors seems very clean in doom 3, no tris ending up in more than one sector like the aa grid flood-fill approach might result in. I think they use bsp to determine what the sectors will be based on artist placed portals. I've been looking through the .proc file that contains the compiled data and the tree for a doom 3 map (A very simple rectangle room divided by a portal). But without more information it's hard to figure out what I need to do.



If anyone has any ideas how this was done or can point me towards any good articles or books on the subject I would appreciate it. Most of what I've been able to find myself focuses on the concept of portals, which I understand fine, most assume the sectors are placed by the level designer like the portals.

My impression is that the best portal/sector designs are either due to manual setting of what belongs to what sector...or by map editors who's tools automatically imply this information...

For example, perhaps your editor might be 'brush based'(geometric primitives that can be combined to make architecture) and the act of attaching a new brush automatically creates a portal where it is joined up to existing stuff...
or maybe each new 'room' must have a simple bounding hull created as the sector before any detailed triangle meshes are added...

That gives me an idea, I might be able to find a way to build the sectors during the process of creating the geometry from brushes, instead of building the geometry first then trying to figure out which polygons belong in which sector which is what I'm doing now. I already have portals, all I need is the sectors.

Hi Kevin,

I'm not sure if you have come up with an alternative solution to this problem, but this is my approach (Although, I still haven't implemented it yet. Need to find time/motivation).

Generate a leaf based BSP using both polygons & portals as possible split planes. Every time you split, ensure you save BSP connectivity information (for examples of this, look at the bsp compiliers for Quake 1-3). If the split plane is on the same plane as a portal, flag the connectivity information so you can refer to it later.

The final BSP leafs will contain both polygons and connectivity info. If you were doing software rending, this structure would be ideal as every leaf is convex. However, this is far from perfect for today's hardware so you need to merge connected leafs back together by walking the connectivity info. If the connectivity info connecting two BSP leafs indicates that this split was caused by a hand placed portal, then don't merge. This approach will leave you with a level correctly split into sectors.

The main draw back of this approach is that the BSP generation will create alot of additional geometry because of the splitting. I'm currently looking into ways to split polygons only when they sit between two sectors. One way is to avoid splitting until after we have generated the BSP and figured out which leafs belong to which sector.

Hmmm, this has turned into a very long response... I hope this hasn't been too much of a mess to try and understand.

Thanks for the reply. I'm going to try that approach. I'll let you know if I have any success.

On the issue of the extra geometry, I had an idea on that, but it may be a little convoluted and I may find a reason it won't work when I get to implementing it, but I could save the original geometry seperatly to reference later, then go with your approach generating the bsp and splitting the polygons, ending up with new geometry divided appropriatly into sectors. As I split the polygons, I can save an ID with the split polygons pointing to the index of the original polygon they came from. Once I have the split geometry divided into the sectors I want, I can go through each polygon, and say, if all polygons originaly split from polygon 20 are in the same sector, then replace those polygons with the original polygon 20 since there would be no need for that polygon to be split. But, if some polys which came from poly 20 are in sector 4 and the rest are in sector 5, then take the original poly 20, and use the plane of the portal between sectors 4 and 5, to split the original poly 20, into two new polys, that will replace the split polys belongs to both sectors 4 and 5.

Did I make any sense? forsee any problems with this approach?

Quote:Original post by DigitalBlur
...Once the tree is generated and you know what sectors each leaf belongs to,...

How do you know that?