See what's going on with flipcode!




 

Building a 3D Portal Engine - Issue 01 - Introduction
by (01 January 1999)



Return to The Archives
Introduction


Welcome to the first episode in a long series of articles about state-of-the-art 3D coding, written by the Phantom. In this first article we are not going to code anything (you're not supposed to touch anything yet), but we will merely dive into the subject and get our mind focused on what we want. Then, starting next week, this will be your guide to achieving that final, great goal: Learning to program 3D stuff yourself. And not just the average 3D stuff like the spinning wirecube that your uncle once showed you when you where a kid; but rather mouth-watering, fast and realistic cubes. Maybe even spheres. Believe me, it's better than driving lessons. It gives more pleasure than... well, ehm, can't think of anything right now, and ultimately, you can make this world a better place. Or, you can make your own world, and make it a better place.

Let's get a few things clear:

I am going to focus on software rendering only. That does not mean that you can stop reading now because you own a Voodoo. Two reasons: 1. Most techniques presented here are needed for hardware rendering too, except for the raw metal rasterizing optimization, and 2. You need to know how real rasterization works to get the most out of accelerated 3D graphics.

A few months ago I spoke to someone who asked me: "Why is it so difficult to make something like Quake? Can't you just toss all the polygons to the card, and let it display them?" - That's what I mean. Keep reading. Second thing I want to make clear right now is that I am not going to do your homework. There might be a snippet of code here and there to clarify stuff, but at the end of the series there will be NO full blazing 3D engine. That's your job. You're supposed to take the ideas, add some intellect, and produce something better. Remember, you wanted to turn your world into a better place. One last thing: I hate Micro$oft. So, if you feel offended by that, remove yourself. I will not mention this in every article, but sometimes I can't hold myself.

OK, on to the real stuff.

This series of articles will ultimately teach you how to develop a 'Portal Engine'. That's just my choice, I could as well have taught you how to do a BSP engine, or whatever, and most information is also useful if you want to do something completely different.

So, what's a portal engine anyway?

Basically, a portal based engine is a way to overcome the problem of the incredible big datasets that usually make up a world. A good 3D engine should run at a decent speed, no matter what the size of the full world is; speed should be relative to the amount of detail that is actually visible. It would of course be even better if the speed would only depend on the number of pixels you want to draw, but since apparently no one has found an algorithm that does that, we'll go for the next best thing.

A basic portal engine relies on a data set that represents the world. The 'world' is subdivided in areas, that I call 'sectors'. Sectors are connected through 'portals', hence the name 'Portal Engine'. The rendering process starts in the sector that the camera is in. It draws the polygons in the current sector, and when a portal is encountered, the adjacent sector is entered, and the polygons in that sector are processed. This would of course still draw every polygon in the world, assuming that all sectors are somehow connected. But, not every portal is visible. And if a portal is not visible, the sector that it links to doesn't have to be drawn. That's logical: A room is only visible if there's a line of sight from the camera to that room, that is not obscured by a wall.

So now we have what we want: If a portal is invisible, tracing stops right there. If there's a huge part of the world behind that portal, that part is never processed. The number of polygons that are actually processed is thus almost exactly equal to the number of visible polygons, plus the inserted portal polygons.

By now it should also be clear where portals should be inserted in a world: Good spots for portals are doors, corridors, windows and so on. That also makes clear why portal engines suck at outdoor scenes: It's virtually impossible to pick good spots for portals there, and each sector can 'see' virtually every other sector in the world. Portal rendering can be perfectly combined with outdoor engines though: If you render your landscape with another type of engine, you could place portals in entrances of caves, buildings and so on. When the 'normal' renderer encounters a portal, you could simply switch to portal rendering for everything behind that portal. That way, a portal engine can even be nice for a 'space-sim'...

OK, that's enough about portals, I guess. :) More about those later.

Before we can start thinking about portals however, we first need some knowledge about matrices, perspective, polygons, and all the other things that you need for a good 3D engine. Here's a short list of the subjects that I intend to write about in the next couple of months:
  • 1. Introduction (you're reading it)
  • 2. Basic stuff: Getting something on the screen in windows
  • 3. Matrices; translating, rotating, inverting...
  • 4. Some words about data structures for 3D
  • 5. A wire cube (OK, possibly some code there:)
  • 6. Hidden surface removal (two ways)
  • 7. 2D and 3D clipping; Sutherland-Hodgeman
  • 8. Polygon filling
  • 9. Portal rendering revisited: 2D frusum adjusting
  • 10. Intermezzo: 8/15/16 bit and transparency
  • 11. More portals: 3D frustum adjusting
  • 12. Portal features (discussion)
  • 13. ...
  • That should keep you reading for about 3 months. After that, we might look into things like lightmaps, bumpmapping, sprites, collision detection, sound propagation and so on.

    That's all for today. Oh yeah, one last thing: Please give me feedback. About my english, about my bad math, about ideas that I forgot to mention, and so on. And another thing: I am not going to do accelerated graphics, but that doesn't mean however that YOU shouldn't do it. In fact, I would really like to see a parallel thread of articles or 'ammendments' to my articles discussing how my stuff could be converted to Glide or whatever. I would also like to create a collection of links on the subjects I write about. So, if you have a cool link for me, send it in! I'll tell the web dude to adjust the articles with those.

    Let the 3D coding begin!


    Article Series:
  • Building a 3D Portal Engine - Issue 01 - Introduction
  • Building a 3D Portal Engine - Issue 02 - Graphics Output Under Windows
  • Building a 3D Portal Engine - Issue 03 - 3D Matrix Math
  • Building a 3D Portal Engine - Issue 04 - Data Structures For 3D Graphics
  • Building a 3D Portal Engine - Issue 05 - Coding A Wireframe Cube
  • Building a 3D Portal Engine - Issue 06 - Hidden Surface Removal
  • Building a 3D Portal Engine - Issue 07 - 2D & 3D Clipping: Sutherland-Hodgeman
  • Building a 3D Portal Engine - Issue 08 - Polygon Filling
  • Building a 3D Portal Engine - Issue 09 - 2D Portal Rendering
  • Building a 3D Portal Engine - Issue 10 - Intermezzo - 8/15/16/32 Bit Color Mixing
  • Building a 3D Portal Engine - Issue 11 - 3D Portal Rendering
  • Building a 3D Portal Engine - Issue 12 - Collision Detection (Guest Writer)
  • Building a 3D Portal Engine - Issue 13 - More Portal Features
  • Building a 3D Portal Engine - Issue 14 - 3D Engine Architecture
  • Building a 3D Portal Engine - Issue 15 - Space Partitioning, Octrees, And BSPs
  • Building a 3D Portal Engine - Issue 16 - More On Portals
  • Building a 3D Portal Engine - Issue 17 - End Of Transmission
  •  

    Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
    Please read our Terms, Conditions, and Privacy information.