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
edge buffering / an optimized 3d rendering pipeline

most people's 3d engine works like this:

- rotate normals (used for shading, envitonment mapping etc.) and
  vertices, transform vertices - perform hidden surface removal and depth-sort visible
- clip faces against frustrum (3d clipping)
- render faces from the back to the front while clipping
  against screen boundaries, alternatively (2d clipping)

each of those tasks can be optimized to the maximum by using techniques like a 9 mul. rotation, a radix-sort, a 5 instruction mapper (or a 1 or 2 instruction mapper for triangles) and the sutherland-hodgeman algorithm in order to clip your scene's faces.
some programmers take advantage of a 6 mul. rotation combined with a bsp-tree which is recommendable if you decide for a static scene that doesn't morph or deform in any other way.

nonetheless, even if all those points have been applied and your engine seems to be optimized to the limit there's still a neat trick that can be used to streamline the whole job of rendering a 3d scene. it works by trying to eleminate a bottleneck that occurs when using a generic mapper which gets fed by screen and texture coordinates passing information about the face to be mapped.
today face mapping isn't a speed issue, anymore as it'll be done by special 3d hardware that implements accelerated fillers, on many "modern" machines. and so it should be the case on the upcoming, in my opinion very interesting, atari coldfire computer.
though, on the 16/32 bit range provided by atari itself we'll have to care about a quick filler as it has to be done via the cpu. although i never coded the dsp, i'd recommend you to use this chip on the falcon after having watched avena's astonishing "sonolumineszenz" and escape's awesome "hmmm...." demo :).

the problem with the method of a common mapper is that it works face oriented while in a 3d engine taking surface structures, that may be composed out of many more faces, into account makes much more sense as the faces' edges touch each other.
this fact doesn't mean anything else but that the texture and screen coordinates along those touching edges will be reused by other faces, which is why there is no reason for reinterpolating them each time a new face containing that edge has to be mapped, in the first place.

now, working surface oriented instead means that you should buffer those coordinates while interpolating them once so that as soon as that edge reappears in another face you can skip a time consuming interpolation loop and just reuse the coordinates from the buffer. imagine a wireframe to get the idea...
sure, it means that your engine needs to be extended by additional edge- and buffer-management overhead, but it should be worth the effort and as long as you feed your face mapper with edge numbers instead of point coordinates it shouldn't be too hard to implement if you stick to this pipeline:

- rotate and transform vertices
- remove hidden surfaces, sort visible ones
- render visible faces by interpolating a wireframe:

   -> for each object you need to have compiled
      additional tables that store edge numbers to each face and
      vertice assignments for each of thoes egdes

      with these tables it can be very easy to keep an edge pointer
      list which makes your mapper work as follows:

      before scan-converting an edge determine if its pointer equals 0.
      if so interpolate its coordinates while buffering them onto a long
      stack and save a pointer to the apropriate stack-frame into the
      edge pointer list.
      otherwise if the pointer is set yet just get the coordinates from
      the stack-frame addressed by this pointer.

finally, there's bit of a drawback in using this method as your face clipping gets limited to a 2d clipping algorithm if you want to keep things simple. but again, an edge buffer is able to optimize the clipping part by a great deal, as well in case you clip your edges before buffering them.
this way there isn't any need to reclip an edge upon reuse, naturally.

- 2002 ray//.tscc. -