|
Building a 3D Portal Engine - Issue 13 - More Portal Features by (26 March 1999) |
Return to The Archives |
Introduction
 |
|
Last week we discussed the 'pure portal algorithm', which required lots of clipping against arbitrary volumes, and datasets consisting of convex volumes only. At the end of the article I mentioned the difficulties with 'portalization', and presented a solution in the form of a BSP tree builder. The dataset that a BSP algorithm produces works, but it will contain lots of portals and convex sectors, resulting in rendering speeds below the speed that the average Quake clone achieves. So, this week we discuss some modifications to the 'pure portal algorithm' that allow much faster rendering. Eliminating Clipping The most expensive part of the portal algorithm is clipping. Clipping of polygons against a volume that consists of an arbitrary number of planes requires quite a lot of math, and this math is neccessary for each and every polygon. While this might be satisfying for the couple of polygons that a software renderer can handle, it's not acceptable for hardware rendering: You expect thousands of polygons from a 3Dfx or OpenGL game (you don't expect anything from a Direct3D game), so your portal engine better deliver. Somehow, we need to get rid of most of the clipping. Well, there's a way to do that. Consider this: While the portal structure and algorithm achieves the important 'zero overdraw' feature, that's not it's primary goal. The biggest advantage of a portal engine is that it allows worlds to be rendered at a speed that is independent of the total world size. Besides, there are better ways to deal with overdraw, if we really want it to be zero. So, let's not clip polygons against the view volume anymore. In fact, we should still clip portal polygons perfectly, since that's the key to limiting visibility. But, the other polygons can be handled better. Once we know that a polygon is at least partially visible, it's much faster to send it to an accelerator at that stage, rather than clipping it perfectly. The accelerator's z-buffer will take care of overdraw, in a much quicker way than our clipper could ever achieve. In software, a z-buffer is a disaster. So, we need something different here. How about an s-buffer? Go read the doc that I wrote about s- and c-buffers now, it's on Flipcode too. If we implement a portal engine that skips the polygon clipping for opaque polygons, we can thus send partially visible polygons to either the s-buffer, or the hardware accelerator. No more clipping man. :) Concave Sectors Another good way to get a portal engine up to speed is using concave sectors: Instead of using small sectors (or larger sectors with very little detail) we could also use larger sectors, if we would somehow find a way to handle the problems that this introduces. As you may recall, convex sectors have a big advantage: You can draw the polygons in any order, since they can't overlap eachother. When we introduce concave sectors, we'll also introduce overdraw, so we must somehow take care of that. There are a couple ways to do that. First, for the hardware dudes, simply use the z-buffer. It will take care of all your problems. Then, for software rendering: If you want to do it perfect, you need either software z-buffering (which is slow), or a BSP tree for the contents of each sector. Or, if you are willing to accept occasional glitches, you could simply use the painters' algorithm. Believe me, it works pretty well. So, what does the average concave sector look like? Well, for indoor areas it still is a room, or a hallway, or any other area that is intuitively a single space. You could still place portals in the windows, doors, and so on; it's just that the contents of the room doesn't have to be perfectly convex anymore. So, if you have a room with two doors and a table in the middle of the room, you might ignore the fact that the room is concave because of the table, and simply pretend that the room is convex. The table will be rendered OK because of the z-buffer, the BSP tree or the painters algorithm. This of course drastically reduces the number of portals, and thus the number of clips. If you combine it with the first method that I mentioned, you should now be able to render pretty complex scenes with your portal renderer. The Catch But there's a catch. If you want to use your portal engine to cast shadows, you need a perfect portal set, since the shadow algorithm depends on the zero-overdraw feature. I didn't yet explain how to do shadows, so here we go: The lit parts of polygons are in fact precisely what a light can see. So, if we could render the scene from the viewpoint of the lightsource with zero overdraw, the remaining polygons should be lit. So, we construct a 'frustum' (in this case we usually call that a 'lightbeam':), starting at the light source location, and we start tracing portals from the viewpoint of the light. First, polygons in the sector that the lightsource is in are illuminated. Of course, only polygons that face the lightsource should be lit, but in a pure portal set, this is always the case for the first sector. Then, we trace the portals that where encountered. Portals are clipped against the lightbeam, just like we did for the viewpoint rendering. If anything is left, the beam volume is adjusted, and the sector beyond the portal is entered. When there's nothing left to process, we've found every polygon that the light can see, so we're done... It's really that easy. How you do the actual 'illumination' of the polygon (parts) that you found, is up to you. At Lost Boys, we tried two techniques: At first, we clipped polygons in parts: The clipper emitted two parts during light rendering, a 'lit' part, and a 'shadowed' part. The 'lit' part was then illuminated by adding a color to it (the light source color). The remainder kept it's original color. Later on, we decided to use lightmaps. Instead of clipping a polygon in smaller parts, we only determined the lit part. The original polygon remained intact, with the same color and texture. The 'lit' part was abused to project a texture (the lightmap) over the original polygon. I started this section with a 'catch': For shadows you do need a perfect portal set, with all it's disadvantages. Shadows are therefore as slow as a pure portal engine would be, but I still believe that this is one of the most intuitive ways to deal with them... Besides, you can use a perfect portal set for your shadows, while you store your geometry also in a simpler format to enhance the visibility determination... Mixing is the key to success here, as always. That's all for this week. And here's your homework: For the next few days, repeat this to yourself: 'Mixing is the key to success... Mixing is...' Mix portals with BSP. Mix a complex pure portal set with a simpler one. Mix voxels with portals. Mix an s-buffer with hardware acceleration. Have success. :) |