Sign in to follow this  
Hatori

How to define portals and zones in a level editor

Recommended Posts

Hi this is a question that has been puzzling me for a long time. Perhaps someone has a solution or ideas on how this can be fixed. In a level editor I can have an artist place portal geometry that is the easy part. So I now know where the portals are in the level and can store them in my exporter as I find them. However and this is the BIG question. How do I break the level up into zones after I have these portals? The only idea I have is to have the artist do this manually. For example take the walls of a room and designate that as a zone. Therefore I can use the AABB of this artist designated room as a zone. But this involves having the artist do this manually. Is there and automated process one could use? Also a potential problem is that there could be overlapping zone AABBs which would cause problems in the engine when it comes time to determine what zone the camera is in for example. Also some zones do not lend themselves to having a tight fit with AABB for example circular or oval geometry. I would greatly appreciate any help anyone can give me. So far I have been unable to automate this process. Thanks,

Share this post


Link to post
Share on other sites
Just some thoughts you can choose to completely ignore if you want...

#1 - I would trash the AABB concept, it defeats the purpose of a portal/sector based engine. That would be more appropriate in an oct-tree scheme.

#2 - Having artists place portal geometry manually is not necessarily the "easy part" as you have assumed. It is easy conceptually, yes, but in practice could prove otherwise. If the artist is going to create a watertight mesh, a single "portal" may end up being several triangles that may not be coplanar. Your engine might need to do an OBB approximation of that raw geometry. Testing for collision with the view frustum against the OBB would be faster than, say, 30 individual triangles.

#3 - Depending on the 3d editor being used (and the file format for that matter) you may be able to attach arbitrary information to geometry. Your artist could use this feature to designate geometry that belongs to a sector or zone. If not, map a material name or ID from the file to indicate its sector in your engine. As long as your convention is consistent it will work just fine.

#4 - You may be able to get away with not having to determine your camera's zone in real time as long as you always know the starting zone. From there, every time your camera passes through a portal, you can update the "current zone" of the camera from the info stored in the portal itself. If you don't know the starting zone, or absolutely need to solve for it on the fly, you could precompute a binary tree using all of the portals in your level, and use this to guide your lookup. Then you would only need a number of dot products to solve for your zone. Remember your camera's zone is not necessarily the zone in which you need to test for collisions. Your player's "bounding volume" can occupy many zones at the same time. A collision response could push your camera across a portal boundary. Just make sure you determine the camera zone after collision handling and it'll work out.

Share this post


Link to post
Share on other sites
Hi I very much like your idea for constructing a binary tree out of the portals. However what I do not have clear is how one would go about selecting the splitting plane. Also with this idea would the zones have to be convex for this to work? What if I select a portal for the split plane and it cuts another portal in two? Also when would I stop building the nodes? ie. How do I go about building this type of tree so that at the end of recursing into it I am at the correct zone? Many thanks for your suggestions. Especially the binary tree for the portals I am currently trying to implement this method in my code.

Share this post


Link to post
Share on other sites
Hi again. Usually the root node of the tree should be a plane that splits the level geometry in a relatively balanced way, so about half end up on one side and half on the other. Usually this is somewhere near the center spacially. If your level is centered at the origin of world space, then you could simply choose the portal closest to the origin and go from there. There are papers out there about constructing BSP trees that explain things a lot better than I ever could.

Yes sectors would have to be convex, and static, for this to work... one of the downsides I suppose. More work for your artist. You can still create non-convex rooms by sticking convex sections next to each other.

You would end construction of the tree when you run out of portals to process. I imagine that as you build the tree, you will keep a list of portals that you have already visited, and a list of those that have been eliminated from the particular branch being processed. All remaining portals would be fair game.

If a split plane intersects another portal, I think you would include that portal in both branches of the node. All you're doing, after all, is giving the engine a hierarchy of tests to perform. Just include provisions to ensure that you never cross the plane of the parent node on subsequent tests. I think if you eliminate portals *fully* on the opposite side and consider those that are same side and those that cross the plane, it should work out.

Share this post


Link to post
Share on other sites

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