|
Building a 3D Portal Engine - Issue 09 - 2D Portal Rendering by (26 February 1999) |
Return to The Archives |
Introduction
 |
|
In this article we'll start the investigation of the portal technique for fast visible surface determination. We'll start again with the basics, and proceed to the darker corners of technology as we explore portal-related features like mirrors, shadows and warps... A few years ago, I wrote a little 3D engine in Pascal. It was more or less portal based, as I used a technique that I now call '2D Portals'. That isn't the perfect name to give it, I know, but suggestions are always welcome... Anyway, before I explain what '2D Portals' are, I will try to explain the basics of portal rendering in general. Imagine a large room. In the middle of this room there is a floating thing that looks like a mirror at first, but when you look closer, you can see that it actually shows a completely different scene... It's a link to another location, a window in space... Or, to be exact, a geometrical discontinuity. This is what Unreal (and I assume Prey also) calls a 'Portal'. In my opinion, a portal is much more. It can also link two rooms in a perfectly normal way, for example. So, what's its benefit in that case? Simple, if you return to the floating portal example. Everything that you can see through the floating portal is 'clipped' against the portal. And even better, it's very easy to determine if everything beyond the portal is visible, simply by determining if the portal itself is visible. The first thing I mentioned reduces overdraw to almost zero, if you would place portals all over your scene. The second cuts of whole parts of your world in an incredible efficient manner. Besides that, the algorithm is very simple and intuitive, and generally applicable. Just to be sure that you grasp the general idea of portals, one more example. Imagine you are in a room, with three windows, and a single door. Outside this room, there is a huge world, with lots of large polygons. In short, the exterior is a disaster for the average software renderer, because the walls will be drawn right over it, causing massive overdraw. But if you would place portals in the windows, and one where the door is, you could actually clip the exterior to these areas, and reduce the overdraw to zero. If you would turn away from the door, you wouldn't even have to consider the scenery beyond the door. So, no matter how many polygons you could see through the door, it's processed in no time. That's a 3D coder's dream: No extra penalty for geometry that is not visible. Visible complexity counts, not total complexity. The data structures needed for this stuff are extremely simple. There are two things that you need to know about: Sectors are areas in your geometry, completely sealed off by a combination of portals and solid polygons. So, in the example above, you have two sectors: The room the camera is in, and 'outdoor'. Portals link two sectors. So, each window links to the sector 'outdoor'. Now that the basic ideas are clear, I shall wet your appetite with some little ideas. A world is usually rendered by the following pipeline: The rotation of coordinates is usually performed using a matrix. Now wouldn't it be cool to use different matrices on different coordinates? (no, I hear you think) Yes! Imagine, you look out of one of the windows of the hypothetical room I mentioned before. All the coordinates in the room are rotated and translated using the usual matrix. But then you encounter a portal. The portal alters the matrix, and links to a different sector than the one that is physically behind the window, for example by changing the translation vector. All polygons that you see through the portal are rotated and translated by the new matrix, so effectively, you are looking at a different position... One window could for example link to another window, so if you try to look out of the window, you see yourself, looking out of a window, and so on... This way, a portal could also be used as a mirror: You can easily determine the mirror matrix for a viewpoint and a plane, and render the sector that the portal is in using that matrix. I'll get back on all those nice features later. So, how do you implement your portal engine? Here's some pseudo code:
Some comments on this code: It's recursive. You start with a view volume (called a frustum) as large as the screen. Each polygon in the sector that the camera is in is clipped to this frustum. When a portal is encountered, it's also clipped to the frustum, and if it's not completely clipped away, a new frustum is determined, but only AFTER the original frustum is stored. After all, we still need to do the rest of the polygons in this sector using this frustum. Then the sector that the portal links to is rendered with the new frustum, in exactly the same way. When it's done, the frustum is restored. So, how do you define a frustum? Well, here comes my 2D Portal engine... A portal is a convex shape. Therefore, you could describe the screen space that it covers with two arrays, wich contain for each screen line the left side of the portal polygon and the right side of the portal polygon. In fact, you could use exactly the same code that you use to find polygon outlines before drawing it to determine the outlines of a portal. You should also store two extra values: The first screen line that the portal covers, and the last one. The information in these arrays can then be used to clip polygons that are visible through the portal. To do this, simply clip the polygons against the bounding rectangle of the portal polygon. During the actual drawing of the spans, clip each span against the values stored in the arrays. This approach has some disadvantages. First of all, it can never be implemented for hardware accelerators, as you need access to individual spans to clip them against the portal. Second, there's an awful lot of clipping going on: Every polygon is first clipped against the bounding rectangle of the portal, then per line against the spans of the portal polygon. That's a lot of work. Third, portals behave bad when they come too close. If a portal polygon gets clipped partially away because it's partially behind you, you will get a black polygon instead of a portal. That's bad, since you HAVE to be able to walk through a portal. Despite these problems, this implementation is still very nice to start with, because it's so easy to implement. It's perfect for testing things, and the algorithm can always be replaced by something better, without wasting all the code. The 'better variant' is 3D Portal rendering. But that's something that we will discuss later... |