Fillrate and VSD (Visible Surface Determination)by Ga'ash Soffer on December 10, 1998 7:43 PM EST
- Posted in
The portals I'm talking about aren't doorways which lead you to another world; even though they can be used rather efficiently to simulate these scenarios in 3D games. So what are portals? Well, the idea behind a portal rendering system is to divide the world into convex polyhedrons, with a bunch of polygons inside. There is then a 'door' leading to another convex polyhedron which stores another bunch of polygons. This 'door' is a polygon which is where the two convex polyhedra are connected. The rendering scheme is as follows:
Render a polygon
If polygon is a "door" (Portal?) then render the next convex polyhedron, clip the results to the clipping window.
Otherwise, just render it plain
Since Portal rendering starts in the current polyhedron the viewer is in, it renders the closest polygons (generally) first. This greatly reduces overdraw because when we finally reach the further polygons, chances are that something will be covering most of its pixels, so we don't draw them. When it comes down to overdraw alone, Portals is one of the most efficient methods of reducing overdraw.
As you can see from the above example, Portals work best in environments with many rooms with none, or very little detail inside the rooms. Descent is the perfect example of portals in action. That kind of environment is perfect for portals.
When it comes to overdraw in indoor environments, Portals are hard to beat. The average overdraw rate is about 50% for a portal based engine, while overdraw can reach up to 400% (meaning 400% of the necessary pixels needed are drawn) using BSP Trees. Not only are portals faster at rendering, they allow for fully (well, almost) dynamic environments. Also, there are many hacks involving portals which allow for cool teleportation effects (something like DmRadikus, In Unreal, even though Unreal doesn't use portals to render), as will be used in Prey. If portals are so great, why doesn't everyone use them. Well, it turns out that portals do have their downsides.
What can go wrong with portals?
The first problem with portals is that, if you want a fully dynamic environment, the polygons inside each portal cannot be arranged in any way (i.e. their orientations are completely arbitrary) there is no way to speed up raycasting and collision detection (plus a bunch of other stuff) other than checking every polygon in the portal. If the portals are small, this isn't much of a problem; however, large portals can cause significant slow downs. Speaking of large portals, remember when I mentioned that portals are best suited for enclosed type environments (rooms)? Well, the reason for this is that outdoor environments require either very large portals, or a bunch of portals with tons of "doors". Both of these approaches aren't very efficient.
Are there work arounds?
Well, currently, I don't believe there is a workaround which does not sacrifice something, namely the fully dynamic aspect. I am currently exploring possible organization methods which would not make any restrictions on the game world, and allow for fast raycasting/collision detection as well.
Let's hear about it...
As I search for a better acronym, the current one is ECP, or Equilateral Cubic Partitioning. The idea is quite simple, divide the world into a 3dimensional grid and then place each polygon in its appropriate location. (Some polygons, which are borderline go in the lists of a few cubes) Since the cubes should be made much smaller than portals, raycasting is much faster. Also, fully dynamic is possible because placing polygons inside their appropriate cube is an easy task which should be able to be done in real time (haven't tried it yet though... I'm too scared it won't work right :) The only restriction on this type of environment is that no polygon can have a radius which exceeds the 1/2 the length of an edge of a cube. (Polygons which can span more than 4 cubes will be a problem to classify speedily)