wolfenstein 3d

  unrolling loops
  c2p part I (st)
  c2p part II (st)
  avoiding c2p (st)
  interlacing (st)
  fat mapping
  3d pipeline
  portal rendering
  8bpp color mixing
  fixedpoint math
  blitter (mst/ste)
  sample replay (st)
  blitter gouraud (falc)
  blitter fading (falc)
  arbitrary mapping
  frustrum clipping etc.

  mc68000 math lib
  32 bytes sin-gen
  24 bit tga-viewer
  blitter example
  lz77 packer
  lz78 packer
  protracker replayer
portal rendering

rendering textured indoor scenes such as in games like doom or quake (atari ports of these id-classics can be found at patrice mandin's site) usually involves a large number of polygons.
hence and even if you use the most hardcore optimized poly-filler you will have to think about reducing the number of polygons to be rendered per frame, as long as considering a realtime application. so, to optimize the task of rendering such an indoor scene, which of course can be expanded to an outdoor scene with bit of creativity (by mapping a sky instead of a ceiling etc. :), it is *strongly* recommended to move away from the ordinary depth-sort & painters algorithm which would result in a worst case situatuin since you'd end up mapping many more polygons than actually visible - mind, your screnes might count up to thousands or even millions of polygons.

now how can you reduce the amount of rendered polygons ? - the obvious solution is to render and clip just the visible polygons depending on the viewer's position and facing. as, maybe with some restrictions, your world will remain static it's possible to compile a sort of hierachial structure giving a sorted order of polygons, beforehand. there are several ways to build those kind of structures such as bsp-trees that divide a scene into front and backspaces recursively, for instance.

in my opinion another common method known as "portal rendering" is a technique to be understood and implemented, quite easily. it works by subdividing your scene into convex sectors that may be connected with other sectors through invisible walls, so called "portals".
as each single sector is convex, which means that no matter how a straight connection between any two points belonging to it will pass along inside of it, no sorting is needed before rendering it.

additionally, portals have a great advantage over most of the other subdivision methods because you won't have to program an additional tree-compiler dividing your screne. instead, just define the convex sector as smallest atom used to compose your scene in your scene-editor.

consider this 2d layout of a simple room to be rendered in 3d:

using portals it could be divided into convex subspaces:

you'll obtain a data structure that could look like this:

sector1 -> sector2 -> sector1
                      sector3 -> sector4 -> sector3

each of the arrows represents a portal, marked as green connection-lines in fig. 2. imagine your sectors to be composed of any number of walls (lines with start and endcoordinates on a 2d layout, respectively). then portals just would need to be flagged as special walls to contain an additional pointer linked through that "imaginary wall".
here's some pseudocode that show how one could render a scene from a data-structure like above in a recursive front-to-back traversal:

RenderSector (*sector)
 if sector->rendered return;

 sector->rendered = true; // avoid infinite recursion

 walls = sector->num_walls;
 for current_wall = 0 to walls-1 {
    if visible(sector[current_wall]) {
      if !sector[current_wall]->portal RenderWall(sector[current_wall]);
      RenderSector(sector[current_wall]->next_sector) // cast into next sector


i think you get the idea. every sector gets plotted by transforming and mapping all its visible walls. as soon as you run into a portal you render the sector joined through it instead by recursing the "RenderSector" procedure.
let's trace it with a little example. imagine the player standing in the middle of sector 3 facing nw-wards:

1. sectos 3's only wall will be culled as well as the portal linking sector 4 as they lie
   outside of the players frustrum. you'll encounter the next and only visible portal to
   cast into sector 2.
2. having clipped and mapped the walls of sector 2 you still have to process 2 portals. one
   of them would result in a recursion to sector 3 but as that one isn't facing the player
   viewed from sector 2 it'll be culled upon this facing.
   the other portal lets the "RenderSector" procedure jump into sector 1 this time.
3. after sector 1's walls have been rendered (clipped against the ones that have been drawn
   yet, of course) the traversal would stop as each screen coulmn has been filled with
   a texture slice, which means that everything visible inside the frustrum has been

to get a correct result you can use something like a column-depth buffer in order to clip new walls against other ones that have been rendered before. along with a free rotateble or a true 3d scene which inevitable results in non-columnoriented mapping using a so called s-buffer is recommended since it is much quicker than a conventional z-buffer (nothing for a realtime application on a "slow" machine).
as you don't want to end up traversing the whole sector-structure - this tutorial should be about reducing the amount of processed polygons, ain't it ? - you should keep track of the number of filled columns/pixels to stop recursing as soon as the whole screen is filled.

performing hidden surface removal before determining if the current wall needs to be mapped or if it's a portal has a great advantage:
if a portal is hidden then everything visible through it (a large number of other sectors, maybe) will be invisible and hence not be processed, too which seems reasonable. furthermore you need to pass the player's current sector to the "RenderSector" procedure. this can be achieved by logging the sector from your collision routines, as soon as the player crosses a portal, which is easy to test if you can clip against ordinary walls already, just change the player-sector to the one just entered.

i'm gonna make up a little portal example source in the future if there's enough sparetime and feedback.

- 2002 ray//.tscc. -