Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Fistandantilus

Automatic portal placement

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

Advertisement
In my engine I import UnrealEd level data and automatically create cells with portals inbetween them. I while ago I discussed this on a thread called "Indoor vs Outdoor 3D engines". This is now about 4 pages back.

Anyway, here is some of what I wrote back then. Maybe it helps, I don't know. Let me know if you any more info

quote:


OK, where to start..?

Well, in UnrealEd, you have to select Export to save the level. If you look at this exported file, you'll see it's an ASCII file with a pretty simple format. In UnrealEd you build the level by first "subtracting" a primitive object (cube, sphere, cone, etc) from the initially solid world. You can then add additional objects inside this one, or subtract other ones as well. Objects can intersect. In any case, the exported file only contains the raw objects, not the intersected, processed objects. As it turns out, this is ideal.

Once I import the level data into my converter, I do the intersections on the objects, depending if it's an add or subtract object. I do it twice for each intersecting object. Once object A intersects object B, then the other way around. In each case I check to see which one produces the least amount of polygons that create the intersection part of the two objects. When an object intersects another object, the intersecting polygons are split and new polygons are added to "wrap" around the intersecting part of the second object. Later I simply add portals where two polygons are coplanar, intersecting and facing in opposite directions (two objects are touching). I don't add portals immediately because more than two objects can intersect each other.

For instance, let's say you have a cube and a cone. The tip of the cone is protruding into the cube through the floor. Both objects are of the "subtract" kind, so the end result should be a cube room with a hole in the floor where it connects to the second cone-shaped room. The two different intersections would result in one where the floor of the cube is cut up into many smaller polygons, and new polygons are added to "wrap" around the tip of the cone. Later the cube polygons touching the cone polygons will be replaced with portals, and as you can image, there would be many of them.

In the second case, the tip of the cone would be sliced off, and the end result would be a single portal, as you can imagine. So obviously the second test would be the one that will be used. BTW, both results would be functional, even the one with many portals that stick up from the cube's floor, it’s just not optimal.

I also do another pass that does stuff like combine portals that are co-planar and touching (multiple portals next to each other), but the final portal must be convex. Touching portals sometimes shows up with different combinations of intersections.

In any case, the end result is quite good. Probably not perfect, but pretty good. I have optimized the portal-walking algorithm, and I can process about 150-200 portals per frame before there is too much slowdown (drops to about 50fps). ([EDIT]: See my benchmark results later, as this was an incorrect guestimate). Even the complex levels that ship with Unreal Tournament can be rendered pretty well. I do have other rendering issues though, like some missing textures, transparency issues, etc, but this has nothing to do with the portal design itself, more how I import other data from the UnrealEd file, and the rendering part itself. My engine is far from complete.

The coolest thing about this is that I can use UnrealEd to create my levels, and I don’t need to care about dealing with placement of portals. Definitely worth the time I spent writing the importer.




In a later reply...

quote:


What I found is that I’m getting perfectly acceptable performance by using the z-buffer on the hardware and simply drawing the whole room, either convex or concave. Now the way my cells are set up (and this is partly because the way the UnrealEd objects are presented), each portal cell has a “main cell”, and any number of “sub cells”. Sub cells are usually features of a room, like stairs, chairs, etc. The main cell is always a “subtract” primitive object (a hollow object, faces pointing in), and sub cells are always “add” primitive objects (a solid object, faces pointing out), as described in my previous post. Each sub cell has a bounding box, and even if the main cell has been placed on the to-be-rendered list during the portal-walk test, each sub-cell can be culled out of the current view frustum (that might also have been clipped through portals). Only main cells have portals, sub cells do not. Anyway, I found that if I first draw the sub-cells, then the main cell, I get better performance. This is because the sub-cells are always in front of the main cell (the sub-cells are inside the main cell). This becomes more noticeable if a sub-cell is filling up most of the screen. BTW, a sub cell can have an embedded main cell, like when you create a solid cube with a hole cut out of it. In this case the portal would be added to the main cell, and it would lead to another main cell that just happens to be located inside the first sub cell.

Also, in most cases the main cell ends up being convex anyway (cubes, cones). It can also be concave, like if you create a room out of the stair brush, for instance. But most times it’s convex.

Your example of a room with a pillar would be a “subtract” cube, and inside there would be an “add” cube (the pillar). Note that both objects are convex. So in my engine the pillar would be drawn first (but only drawn if it’s bounding box is inside the view frustum), then the main room would be drawn. It’s a very crude front-to-back method, but it works due to fast hardware. You can also sort the sub-cells front-to-back by doing a distance-to-center-of-bounding-box test just before rendering the visible sub-cells in each main cell. I’m sure some people would disagree with my methods, but they work fine for me. So may main answer to you is: I don’t even bother too much with depth issues, other than some basics.




In that same thread I posted some benchmark results to get an idea how many portals can be visible and still get acceptable framerates. The way the test-level was laid out was an absolute worst-case scenario, and in no way will a real level have that many portals, but I did it to test purely the portal walking code. In a real level there would be well less than 100 portal visible at any one time. Here are those results:

quote:

0 portals, 1 cell, 272 fps (looking at solid wall)
50 portals, 38 cells, 239 fps
100 portals, 44 cells, 236 fps
150 portals, 48 cells, 238 fps
300 portals, 68 cells, 236 fps
600 portals, 89 cells, 238 fps
1 000 portals, 121 cells, 220 fps
2 000 portals, 196 cells, 122 fps
3 000 portals, 265 cells, 87 fps
5 000 portals, 384 cells, 55 fps
10 000 portals, 639 cells, 30 fps
15 000 portals, 939 cells, 21 fps



Hope that helps...

SS


Edited by - Axter on February 25, 2002 2:19:32 PM

Share this post


Link to post
Share on other sites

  • 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!