Sign in to follow this  

Determining Sectors from portals

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

Zemedelec:

You know which sector each BSP leaf belongs to by walking the connectivity information like I described in an earlier post (The previous AP). Essentially, it's just a flood fill of the convex leafs produced by the BSP process. When you come across a portal, stop filling. The process will end when you have classified each leaf as being part of a sector.

Share this post


Link to post
Share on other sites
Quote:
Original post by DigitalBlur
You know which sector each BSP leaf...


Yeah, the BSP-era solution. Did you tried it?
I have troubles back when I tried to build BSP from relatively complex and non-convex environments - except the *tons* of leafs, numberic errors tend to cause nasty bugs... I guess it was just me.

Then I thought about CSG-ing all the geometry, and walking the faces, starting from a portal - a similar method, but with far less subdivisions (-> more stable) and imho faster.
Didn't implement it, however.

Share this post


Link to post
Share on other sites
Interesting. I had thought of trying something like that but could never quite figure out how it would work. Could you give a more in-depth description of how you would implement it.

I tried implementing a similar algorithm to the one I described a few years back. However, it wasn't really successful. But that was due to problems in my maths/BSP code which caused it to fail on all but the most basic two room approach. Errors in the BSP itself couldn't be too much of a problem as engines have used this sort of pre-processing for years. However, I am concerned about making polygon splits which are not required for both performance & a fear of introducing floating point errors. I guess I'll have to find some time to implement it and see what happens.

There was also an old IOTD posted on flipcode (before it died :() where a guy was using a completely automated system for generating portals. In that system, his editor was CSG (like unreal rather than the quakes). When two subtract brushes intersected, a portal would be generated. I can understand how this sort of geometry would make this task easier, but there a so many good quake style editors available (with source too!). Performing sectoring on a poly soup also allows you to be editor agnostic which can only be a good thing.

Anyone else have any alternative approaches to the sector/portal problem? What about ways to reduce numberical errors or redundent splits?

Share this post


Link to post
Share on other sites
Quote:
Original post by DigitalBlur
Interesting. I had thought of trying something like that but could never quite figure out how it would work. Could you give a more in-depth description of how you would implement it.

Subdivide the world by itself, i.e. there shouldn't be polygons that cross each other. BV hierarchy will do the job - subdivide the world into a tree, til a N polys group together in the leaves. Do O(N^2) intersection in the leaves and keep everything indexed. After that compute adjacency, using simple hash-table, by inserting each edge indices to find neighbour faces.
Then start to choose portal faces and walk their neighbours using flood fill and creating sectors. After all portals are used as starting points OR are already walked AND there are unmarked faces - walk these faces too, then cast a ray until something marked with other value is hit.
That's it.

Quote:
Original post by DigitalBlur
There was also an old IOTD posted on flipcode (before it died :() where a guy was using a completely automated system for generating portals.

Angel Popov, a neighbour of mine actually... :)
He however uses a relatively low-poly world AND he detects portals itself. Which is completely another problem imo...

There was another idea (which is faster to program and more stable).
Photon trace the triangle soup, using simple hierarchy (kd-tree) for collision with a bounding ray. Shoot from portals, mark geometry.
After some shooting, start to shoot backwards from unmarked polys to the world hoping to hit something marked... :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zemedelec
There was another idea (which is faster to program and more stable).
Photon trace the triangle soup, using simple hierarchy (kd-tree) for collision with a bounding ray. Shoot from portals, mark geometry.
After some shooting, start to shoot backwards from unmarked polys to the world hoping to hit something marked... :)


Cool, I like that Idea... No splitting & alot more stable. Did you come up with that idea? Or did you read a paper (if so, where can I get it?). I can't imagine that it would be as fast as using a BSP, although I'm sure it would scale alot better as the scene becomes more complex.

Essentially, the tracing is used to decide what is visible from a given point (a portal in this case). Graphics hardware uses the Z-Buffer to achieve this, I wonder if you could perform the tracing in hardware. It would certainly speed up the pre-processing! You would render the scene from the portals perspective and then use the results to figure out which polygons were visible. Very accurate & fast, now just to figure out how to check which polygons were rendered in the first place! Maybe Hardware Occlusion Queries? (Don't know much about this, so it maybe completely out of the question or even overkill).

Any thoughts?

Share this post


Link to post
Share on other sites
Quote:
Original post by DigitalBlur
Cool, I like that Idea... No splitting & alot more stable. Did you come up with that idea?

Sorry, no paper, come up with it myself.

Quote:
Original post by DigitalBlur
Essentially, the tracing is used to decide what is visible from a given point (a portal in this case).

Yes, and if we continue this idea, we can shoot and save bouncing faces into a group. Later, if we bounce into a already grouped face, its whole group get marked. That way we can propagate much faster the connectivity (this is not visibility!) information through the world.

Quote:
Original post by DigitalBlur
Graphics hardware...
Any thoughts?


Thought of that myself - one can render polygons with unique colors (like index <-> color conversion), only flat shaded, solid geometry. Get the back buffer, scan the rendered pixels for id-s of polygons. Nice and fast.
The problem here, is the placing of the camera. But since it can be fast, we can do that way the grouping - just place the camera in every point of a 3d grid, render into 6 cubemap faces the world and group all visible polygons into sectors.
If anything didn't marked - place camera in-front of those polys and render again.

Actually, this procedure can be done to compute bruteforce PVS by GPU - fast and easy (PVS cells - 3d grid blocks).

Share this post


Link to post
Share on other sites
Couldn't you just walk your face array neighbor-by-neighbor using shared triangle edges until you've reached all neighbors? Whenever your "iterator" has reached a portal edge, you can look to see what next face shares an edge with your the previous face and and an edge with the portal. (Would have to be two discreet edges; the same edge would mean your looking at the two faces split by the portal.) This way you can wind your way around the portal and not worry about traversing to the wrong side of the portal.

If you have your artists design the buildings in a modelling app - (Maya, Milkshape, Blender) and manually place portal polygons (just normal faces tagged somehow) such that the model is cleanly sectioned off, the "sectorizer" shouldn't have any issues, methinks.

Seems like it should work to me... any thoughts?

Share this post


Link to post
Share on other sites
Quote:
Original post by spartanx
Seems like it should work to me... any thoughts?

It should work, IF the geometry has no flying edges, T-junctions, etc.
It is an odd requirement, because if one must triangulate a roof with a chimney because of the software that computes sectors...
Well, it IS an options - it just depends more on the input geometry.
Making CSG is a solution to that, but it is far from trivial.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zemedelec
It should work, IF the geometry has no flying edges, T-junctions, etc.


Yep, your spot on Zemedelec! Infact, there was a guy over on Ogre3d which did just that for the Goole's Summer of Code. You can download the pre-processor he wrote from one of the forums. It seems to work (and at a good speed), but it imposes too many constraints of the Geometry in my opinion.

As calculating visibility information on the GPU. I really like the idea of using unique colours to identify polygons/polygon groups. I too had thought of the grouping that you mentioned. Would you really need a cube map? You could almost use techniques from Shadow mapping to skew the perspective. Resolution isn't really a problem as you just need to know that a poly is visible, not exactly how much of it is.

Share this post


Link to post
Share on other sites
To avoid this tons of problems and work, I just allow the artist to assign objects to zones. it's very easy to use and to implement.
it has even a very nice advantage beyond the algorithms you suggested here, u can make portals like in Prey, you place just onesided portals and define the zone it maps to, this way you can let people go into a room without a way back.

Share this post


Link to post
Share on other sites
Quote:
Original post by DigitalBlur
Quote:
Original post by Zemedelec
It should work, IF the geometry has no flying edges, T-junctions, etc.

Yep, your spot on Zemedelec! Infact, there was a guy over on Ogre3d which did just that for the Goole's Summer of Code. You can download the pre-processor he wrote from one of the forums. It seems to work (and at a good speed), but it imposes too many constraints of the Geometry in my opinion.


Interesting - any links? What it did, that code - walking the geometry, or the CSG thingy?

Share this post


Link to post
Share on other sites
I don't know if this is the latest code but here is a link i found in the forum:

http://www.geocities.com/wael_el_oraiby/basic_app_2.zip

This method takes a polygon soup and creates two bsp trees. One tree is of the geometry without the placed portals, the other is just the portals. The portal BSP is CSG subtracted from the poly BSP. After this process, a poly which has not been assigned a sector is chosen and assigned a new sector number. Then all polys with shared verts are also tagged as part of the same sector. This process continues until there are no more polys sharing verts which are not assigned a sector. You now have a complete sector. Another unassigned poly is chosen and the system continues.

I haven't tried it myself, but the reports on this forum:
http://www.ogre3d.org/phpBB2/viewtopic.php?t=20546&postdays=0&postorder=asc&start=50

seem to indicate that the process is quite fast. However, there cannot be any T-junctions or floating geometry for this to work which is too restrictive. The geometry that this seems to be used with also seems very simple, so i'm not convinced that this would scale well to complex scenes.

More info can also be found here:
http://www.ogre3d.org/wiki/index.php/SoC2006_SceneManagement

Share this post


Link to post
Share on other sites

This topic is 4084 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.

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