Jump to content
  • Advertisement
Sign in to follow this  
KevinCoyle

Determining Sectors from portals

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

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

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Yay! I've remembered my login!

That makes sense Kevin and it's one of the ideas I was looking at. Personally, I'm not keen on it cause it's going to take a while to process with all those splits. Apart from that, I can't see why that approach wouldn't work.

Another way I've been thinking about lately tries to avoid any splitting during the BSP generation phase altogether. Instead of splitting the polygons, push them down both sides of the tree (as a pointer, not a copy). This would cause the same BSP to be created without the extra overhead of splits and each polygon would have a list of all sectors they belong to.

Once the tree is generated and you know what sectors each leaf belongs to, you could store some form of value at each parent node indicating what sectors you could reach from this node. To split polygons which are in multiple sectors, you send them down the BSP again. When a polygon straddles a splitter, you could check if you can get to all the sectors that the poly belongs to. If you can push down both sides (like the first time) and continue. If you cant, split (making sure you keep track of what sectors the new polygons belong to) and continue.

I've only started thinking about this recently so I'm not completely sure how (or how fast) this could be implemented. Nor am I convinced that this would yeild the correct results.

Any thoughts?

Share this post


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


How do you know that?

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!