Jump to content
  • Advertisement
Sign in to follow this  
ZQJ

Automatic portal generation

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

Does anybody know of any good algorithms to automatically generate a cell/portal decomposition of a triangle soup? The triangle soup is guaranteed to be closed and non-self intersecting, i.e. generally well behaved. I'm just trying out the Lefebvre-Hornus method somebody posted on here recently but after the initial step my test level only had 7 remaining portals! I haven't finished implementing it yet but I was wondering if there's a better way that doesn't involve constructing a BSP first. I'd also be really grateful if anybody's got any really big maps lying about in the Quake 1/2 .map format I can have because that's what I'm using for testing.

Share this post


Link to post
Share on other sites
Advertisement
here's a small idea (not yet tested or finished but can be a starting point)
how about building kd-tree out of whole scene?
then walking the tree front to back and using bitmap to resolve visibility.
you test node bounding box against frustum and if it's visible test it against
bitmap (same resolution as screen) if it's visible you either recurse or if it's leaf, draw it's contents and also draw it on bitmap.
i know , it will be slow for high poly scenes but could be use with antiportals.
now. i think it can be modified to support cell/portal decomposition
when splitting a node of kd-tree
you make big rectangle on the split plane and bounded by nodes bounding box
then perform CSG with all polygons in current node and this rectangle
at the end you'll get set of polygons that define portals. you add them to the list and add pointers to those portals to left and right subnode that will be result of splitting current node. then you split your nodes polygons by split plane and move them to children, then recurse.
when splitting nodes polygons you also split portal polygons.
after you are done you should get a set of leaves with lists of portals connecting them to other leafs. then you can try to optimize it. use optimization similar to that of that paper you mentioned. or just try to remove large portals first (instead of removin them just set a flag that tells that portal is always visible).

of course there are problems to be solved.
- how to find good splitting plane (that generates smallest portals??)
- how to optimize output
- axis aligned split planes are far from perfect.
so maybe it's better to use general split planes, of course then how to find best split plane?

Share this post


Link to post
Share on other sites
Quote:
Original post by biki_
...


That method have a bunch of problems - as you said, AA planes are far from perfect, but can be used on many maps, since walls generally tend to be AA too. But then, splitting criteria is very important - does it use actual AA polys to produce a plane, or no and so on. BSP itself is better suited for approximation of polygon soup boundaries, and so for subdivision into cells and portal generation. Not even close to perfect, but better.

Share this post


Link to post
Share on other sites
Quote:
Original post by ZQJ
Does anybody know of any good algorithms to automatically generate a cell/portal decomposition of a triangle soup? The triangle soup is guaranteed to be closed and non-self intersecting, i.e. generally well behaved. I'm just trying out the Lefebvre-Hornus method somebody posted on here recently but after the initial step my test level only had 7 remaining portals! I haven't finished implementing it yet but I was wondering if there's a better way that doesn't involve constructing a BSP first.

I'd also be really grateful if anybody's got any really big maps lying about in the Quake 1/2 .map format I can have because that's what I'm using for testing.


I have in mind one method, that involved building a connectivity graph for a level, between all open spaces.
First, subdivide the level with quad-tree, to get the 'free'-space of the level, where no poly exists. Then, connect that nodes into a graph, and optimize it (remove close-by nodes, that have same neighbours). That way portals will be smallest polygons, that cut some path in this graph and cause a path from a node in front of a portal to the node in the back of the portal to be a lot longer (even infinity long).
How to find portals? For each graph edge, find a list of first N closest polys (use favorite proximity test for that, like bounding sphere around edge - get all faces, found nearest ones). Then find the actual points on the edge, which are closest to those polys, make a plane and test that plane if it forms a portal - this one is tricky, because you'll need to build maybe a full BSP tree, to get plane<->world intersection fast.
Collect all such portals, then optimize them.
This is again a non-trivial task (imho), and various solutions can be applied. Like finding for each portal its closest, and deciding which one is better (like who sees more *different* geometry, or the number of points from which the portal is visible must be minimal and so on).
Some of visibility computation can (and must :) be made with the GPU, avoiding slow (and buggy) geometrical CPU solutions.
And I am very interested in large MAP files for testing too.. ;)

P.S.: There was a paper on portal computation a while ago, can't remember the name but will search for it. It uses some sorth of deconstruction the level into grid, then trying to extend the walls until somewhere the connectivity is lost - and build a portal there... Seems not very good to me, but will search for link anyway.

Share this post


Link to post
Share on other sites
Here's another one that looks interesting: Generating portals for indoor scenes using a 3D watershed transform.
http://www.ulb.ac.be/polytech/sln/team/dhaumont/mcp.pdf

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!