24

Inspired by this GameDev question.


3D rendering is expensive. With 2D games it's easy to not re-write the buffers every frame, like in Super Mario Bros where the PPU is instructed to render the level with an offset:


Image source.

With 3D games, it's harder to do this. However, this comment suggests that it was done:

@RussellBorogove Well, not all 3D games. It has to do with how constrained the camera is. FPS games usually do have to redraw everything (though early 3D FPSes still didn't - if you constrain the design a bit, you can save lots of pixels from being redrawn). A game with fixed camera, or a clever use of orthographic projection, can keep many things unchanged - there just isn't any reason now that we all have 3D hardware. And even if you redraw every pixel, it doesn't necessarily mean rendering the meshes again and again - they can be cached as 2D sprites. It's all about the constraints. – Luaan

What are these clever tricks that allowed some 3D games to be rendered so quickly on the hardware?

5
  • 3
    If this question is too broad, could anybody give some tips as to how to narrow it down without invalidating existing answers? It is a little broader than I intended but I don't forsee very many more techniques existing; the existing ones seem to cover all of the bases.
    – wizzwizz4
    Mar 6, 2018 at 16:38
  • In case you're curious I added some new stuff to my answer
    – Spektre
    Mar 7, 2018 at 11:24
  • @Spektre I noticed! :-)
    – wizzwizz4
    Mar 7, 2018 at 16:40
  • Maybe someone could add to their answer the Pie In the Sky engine which was used in a lot of early DOS games in some way? It's history and how it worked is written here It was really impressive for it's time. Apr 18, 2018 at 20:38
  • @LateralTerminal If the technique isn't already written about in an existing answer, you could write one.
    – wizzwizz4
    Apr 19, 2018 at 6:54

6 Answers 6

36

A very broad question, so a random dump of thoughts:

Elite approximates solid objects through convex objects. Because every game object (other than the missile) is convex that means by definition that every hypothetical ray of vision from your eye to the object other than generate edge cases must pass through it exactly twice: once through a front face and once through a back. So just eliminating the back faces makes any single object appear to be solid when set on its own against a black background. Back-face culling is a standard technique that remains in use as it cuts the work for any closed object, but in Elite the further requirement of object convexity helps to give the illusion of solidness.

Elite and many other games also use split-precision arithmetic. Individual objects are small but in a much larger space. So objects themselves have local geometry stored in 8 bits and rotated using 8-bit arithmetic. The object centre exists in a 16-bit (or larger) space and is subject to 16-bit arithmetic. Having located the centre in 16-bit space, sign extend and add the 8-bit results to get all intermediate results in 16-bit while having saved a lot on arithmetic. There are cheap and compact lookup-table approaches for 8-bit multiplication based on 8-bit lookup tables and simple addition so the saving is very substantial.

Plain vector games like Elite often do partial screen updates essentially by accident. It's too expensive to clear a whole frame buffer or to keep a spare and lines very rarely overlap. So they XOR objects in and then XOR them out again. As and when they can't keep up with the output frame rate, which is usually, that has the effect that objects across the screen are updated sequentially. When the screen becomes full you can see one move, then the next, then the next, etc.

Even as early as I, Of the Mask, animated scenes were being prerendered and replayed as a sequence of 2d draw calls, with some sprites added on top for gameplay. This presages interactive movies by about a decade.

Rescue on Fractalus probably begins the line for games based on a voxel heightmap, and does what it does on an Atari by leaving most of the surface details very implicit. It's drawing verticals of a uniform colour and just putting pixels on top because it's cheap to update a vertical of one height to another, and the pixels although sparse are enough to fire the imagination. Later games like Commanche could afford whole-buffer updates.

It might not be immediately obvious, but the 8-bit versions of Stunt Car Racer also assume they're filling a vertical space for faster solid graphics. They do not allow the car to roll beyond a certain amount, and when it does you can see the area underneath the track soft of rotate with you. So it's not really filling polygons so much as maintaining a 1d height map.

As almost everybody knows, Wolfenstein's optimisations are (i) to restrict walls to a single height and vertical location, collapsing the problem of drawing from 3d to 2d; and (ii) requiring them to be on grid boundaries, for a simple per-column test without prior knowledge. Restriction (i) also makes each column a line of constant depth. Which means no per-pixel divides. The limited number of potential outcomes also allows all per-column possibilities to be precomputed.

Doom keeps similar per-pixel optimisations for wall rasterisation but completely replaces the logic as to what should be drawn by using a structure called a binary-space partition ('BSP') tree that allows a very fast back-to-front sorting of level geometry and ensures geometry is arranged in advance so that sorting by depth is always sufficient for a correct drawing. Allowing geometry not to overlap vertically further collapses the amount of work necessary to decide which bits of walls remain visible after having sorted them.

Quake does a similar thing with a BSP tree but adds an additional structure for broad-phase elimination of sections of the world called a potentially-visible set. A side effect of putting a structure into a BSP tree is that you end up with a bunch of convex sectors that the player can stand in. Quake keeps a compact list in each sector of which other sectors could be visible. That allows huge parts of the BSP traversing and therefore of span comparison to be skipped entirely.

Games like Descent go a different way with convex sectors, rendering from that which the camera is in outwards and clipping each further sector to the portion of the display still unfilled by closer sectors. That's full-fat portal rendering: the surfaces that join sectors are 'portals' and the portals are the be all and end all for scene graph traversal and for visibility. Later but still retro games often use portals in a less strict manner as merely a broad phase for whether a section of the map might possibly be visible, particularly if they have a GPU that can report something like 'if I were to draw that polygon, [some/none] pixels would be drawn'. Games still do that, but I'm aware of it being implemented at least as far back as Mario 64 and twenty years passes my test for retro.

A different branch of games going back at least to Alone in the Dark prerenders the background and simply superimposes the moving objects. Some knowledge of the full-scene geometry is retained for collisions and clipping but most isn't retained at runtime. In Alone in the Dark pixel artists created the backgrounds. In Resident Evil they were CG rendered.

Little Big Adventure II is probably the most interesting branch of that system of thinking: it has the full 3d geometry of its outdoor world but presents it through fixed cameras. Each time the camera changes it pre-renders the background with depth information, after which only the main characters are redrawn in realtime. That causes a 0.5 second lag when changing camera, but that alone isn't jarring for the genre.

The Microsoft Talisman project from the mid-'90s tried something very close to what you're asking. It would start by rendering a frame as a sequence of tiles and submitting those to the GPU. It would approximate the next frame and possibly the one after that by having the GPU simply manipulate the original tiles based on the camera difference — rotate them, move them around, scale them, all of them independently of each other. Then when the CPU had prepared the next entirely-new frame, it would submit it. So you got perfect key frames plus approximate intermediaries. It was implemented and previewed, but missed its window for success as the ordinary 3d accelerators appeared on the market.

EDIT: also suddenly returning from the back of my the memory, a special word for Parsoft Interactive and the line of flight simulators up to 1996's 'A-10 Cuba!'. They were software developers that started on the Mac in the late-'80s, which means a massive display compared to processing ability. So they used a system of per-scan frame differencing to publish only the differences. Imagine a big green polygon that's rotating. The centre essentially remains the same so if you can figure how to redraw only the edges in less time than it takes just to redraw the centre then that's a win. Exactly how they did it seems to be vague but I'll bet it's just a matter of inserting spans into a structure that you can then traverse in x order (probably O(log n)) and performing a linear differencing of this frame and the previous at the end (in O(n)).

That's almost certainly why they were still pushing solid colour polygons as late as 1996, but also why they could do a pretty good frame rate at 1024x768x8bpp on a 68040, and a fantastic frame rate at 1280x1024 on my unaccelerated Pentium of 1996. Which was the best the monitor could display.

12
  • 1
    very nice summary +1 btw do you know anything about: more advanced 3D rendering on ZX? (not wireframe) not sure how the name of technique was something like freescape? or farscape? or something The first time I saw it was in Sentinel I think. The rendered polygons where not filled but also not fully empty. And there was also Caption Blood the descent onto planet was interesting but does not look like any advanced technique was used for it. Also Are you sure BSP was in DOOM? I taught Duke3D used it first
    – Spektre
    Mar 6, 2018 at 10:34
  • 1
    @Spektre Doom definitely came before Duke3D and they were lauded as the first to BSP Afaik.
    – Weaver
    Mar 6, 2018 at 13:21
  • 4
    @Spektre that's Driller, which uses the Freescape engine. It has some interesting limitations in that each room is entirely described in 8-bit precision using the combination of a small number of predefined primitives rather than meshes, and is way ahead of its time in being scripted. I've actually never seen Captain Blood before, despite being in a Spectrum family back in the day, but from eyeballing it looks broadly on the Fractalus scale of a 1d height map with topped pixels.
    – Tommy
    Mar 6, 2018 at 13:51
  • 1
    @Spektre Duke 3d uses a portal based visibility algorithm. The map is stored as sectors which contain walls as well portals to other sectors. The visibility problem is handled incrementally by drawing the walls in the current sector, and then recursively traversing each portal that's visible in the remaining un-filled screen space. Jan 4, 2019 at 22:23
  • 3
    @Spektre Duke does not use a bsp tree, it uses a portal graph, which accomplishes a similar goal, but in a different way. And whoever taught you about doom should be ashamed (^:. Doom does the same exact thing, but by traversing a bsp tree. Visibility is solved by the bsp naturally sorting the walls in distance order, and using a span-buffer to clip further walls by already drawn wall segments. Check out fabiensanglard.net/doomIphone/doomClassicRenderer.php and fabiensanglard.net/duke3d/build_engine_internals.php Jan 11, 2019 at 18:50
16

Many games that "looked" 3d simply placed pre-rendered 2d pictures of 3d objects onto the screen. For example, a typical first-person dungeon crawler might show a player a view something like:

\         /
|_       /
| |\ ___|
| | |   |
| | |___|
|_|/    |
|        \
/         \

If it would be possible to see a particular kind of wall surface at one of four different distances from the player on the left, four distances on the right, and four distances up ahead, a game would have twelve pictures of that wall surface--one for each of those circumstances where it might be shown. If the walls include 3d features like alcoves, different views would often be drawn or painted by a human artist, then scanned and scaled, and finally cleaned up by hand. At no point would any actual 3d rendering be involved (except by the human artist).

3
  • 2
    Even more advanced renderers used similar techniques. For example, in Wolfenstein 3D, all walls are constrained to exist on a right-angled grid, so even through the perspective can vary, for each frame every wall has one of only two possible precalculated angles that is easy to translate to screen coordinates.
    – Jules
    Mar 5, 2018 at 21:03
  • 3
    @Jules: Wolf3d and Doom rendered each wall every frame as a sequence of posts. Doom then rendered each floor as a sequence of horizontal spans. The facts that all posts were all in the same direction and that all spans were in the same direction greatly simplified rendering, but things still had to be rendered every frame. By contrast, in the older style of dungeon crawler the only "rendering" would be an unscaled bitmap copy.
    – supercat
    Mar 5, 2018 at 21:10
  • 3
    @Jules The question says "reduce" not "remove" so that would probably be a valid answer to the question. None of the answers so far are what I expected; the subject and this community rarely fail to surprise me in this way.
    – wizzwizz4
    Mar 5, 2018 at 21:14
16
  1. Tile based 2.5D render

    Any isometric game can reuse an already rendered frame. As there is no real perspective the movement of camera/player is really just panning/scrolling the x,y.

    Isometric render:

    isometric

    And usually by one or fraction of one tile so the render could be highly optimized.

    Also 3D polygons where sometimes rendered as sprites into isometric engines – see Diablo1 (at least I suspect they use it) as an example. It's hard to say if they do it on game runtime (during init) or during game development or at all (an all is pixel art instead).

  2. Pseudo 3D render based on 2D ray casting techniques

    Pseudo 3D raycasting Wolfenstein3D and Doom3D techniques are rendered whole each frame. The only thing that could be speed-ed up by scrolling is the ray cast intersection list acquisition (map in top left) but that makes no sense as the added code will not gain anything (unless very large map is used with high visibility depth) and probably would even slow things down due to branching.

    Wolf:

    Wold3D

    Doom:

    Doom3D

  3. Paging effects

    But if we got any specific constraint of movement we could use this "scroll/pan/combine" technique and usually was used in Demo scene for things similar to this:

    DMA

  4. Polygonal 3D render

    Sadly for real unconstrained 3D engines is this not an option. Instead if speed is not good wireframe techniques where used to speed up. Or even combined with sprites.

    ZX advanced polygon rendering

    Caching meshes as sprites is possible only if the view has no real perspective or the rendered object is in the "same" distance (like background) or very far so its relative distance does not change too much.

  5. 3D Ray tracers

    When talking about 3D graphics do not forget that there are also 3D (back) ray tracing techniques which are fully perspective but they can reuse already computed rays (if light/shading model allows it and lights and scene are static). If those requirements are met than does not matter where camera was if ray lies on the same axis and there is not obstacle between them than they results in the same color regardless of camera orientation and position. This can be used by caching rays of last frame and reusing them ... +/- some accuracy rounding. That might speed up a lot of the entire frame raytrace like:

    Mesh back raytrace:

    mesh

    Volumetric back raytrace:

    volumetric

    but I never saw implementing this in a real application. The current gfx HW is not suitable for these techniques however. There are attempts to build special ray tracing processors (for now they based on FPGAs) which could handle Snell's law and Fresnel's natively. Hopefully they will be added into GPUs someday...

    Apart of all this there is one technique used for 3D raytracer to speed up the rendering that is unique to these renders. It is using stochastic approach for branching. Basic ray tracers works like that you cast ray when it hit something it either reflects or both reflect and refract and this is recursive up to some layer. This can be speeded up by using pseudo random approach where the split of ray is not happening. Instead the ray has 50% chance to reflect and 50% to refract. And on top of that usually few frames are merged together. This way we can have much higher speed for the same recursion layer at the cost of quality (the image is a bit noisy like from CCD camera). This technique is fairly common in GLSL as it allows to use the underlying architecture in similar manner than polygonal rendering which is not the case for recursive ray split.

4
  • 2
    I removed the edit summary from the top of your post because there is one built in and Stack Exchange posts are supposed to appear as a "final draft" (most readers won't care about the edit history, and those who do can look at it by clicking the link to it).
    – wizzwizz4
    Mar 7, 2018 at 16:51
  • 1
    @wizzwizz4 oki btw thx for the spelling correction my English is rusty and lacks grammar.
    – Spektre
    Mar 7, 2018 at 18:18
  • 2
    ("oki btw thx" Hmm...) I'm just doing my job! :-)
    – wizzwizz4
    Mar 7, 2018 at 18:21
  • 3
    This is a good post, but one correction, Doom did not use raycasting techniques (though you could mimic how it looks with them). It's closer to a Polygonal renderer, but the polygons are restricted to being perfectly vertical wall segments (which allows drawing them per-span with constant depth). The walls are projected into screen space and drawn, and the floors/ceilings are incrementally built from the empty screen-space in between where the walls where drawn. Jan 4, 2019 at 22:19
12

One technique that has not been mentioned (well, it kind-of has, but not under its actual name) is the "impostors" (or "imposters") technique.

It consists in drawing some 3D objects of the scene with a very rough approximation of their angle to the camera, and updating this angle only when really, really needed (by that we mean: only when the human eye would start noticing that this object doesn't seem to be "turning" as it should).

This technique has two flavours:

  • Rendering small objects. The extreme version of this technique is the billboard, when every object is constantly facing the player, and the game designer decides that the objects should never turn (their angle to the camera is forever fixed). It can be made more permissive by deciding that the object can have 4 fixed angles to the camera (front, sides, back) or even 8 (for example, in Doom, barrels and lampposts always face the player – that means only one fixed angle to the player, while enemies can be seen from 8 angles).

    Please note that this can be achieved in two ways: either the object is a sprite previously drawn in 2D (as in Doom), or it's just re-rendered at the required angle. Having just a few allowed angles makes the following optimisations available:

    1. You can cache the few renderings of the object seen from each angle, as 2D images.
    2. Since the angles have discreet values, you can restrict the calculation space (for example if you pre-calculate and store in memory all the cos and sin values for these angles).
    3. If you have many objects to display, most of the will be seen under the same angle, so you can use the same cached rendered version many times (for example if you draw trees you can copy and paste the same tree seen from a handful of angles many times, by just scaling down the sprite depending on the distance). That's also sometimes used to render a crowd (like the stadium's audience in old sports games or the people on the side of the road in car racing games).
  • Rendering large, complex, distant objects. The key here is that these objects are distant. It means that their angle with the camera will change very slowly (even if the player/camera moves sideways for a long time, the mountain in the distance will look almost the same. therefore, the payer doesn't notice if you don't redraw it as much as it should).

    If the player/camera turns, then the distant object is just moved sideways on the screen (or just projected onto a skybox that gets rotated, as described below), but doesn't change, so it is not redrawn. From time to time, if the camera moves to much, then simply re-render the complex object as seen from the new angle. Since that doesn't happen often, it's not too costly. it can be processed in a parallel thread. That technique is used in open-world games, like Skyrim, GTA, etc.


Another technique: the skybox.

You could consider it as an impostor pushed to the extreme: the object (the sky, the sun, the clouds...) is so distant that its angle to the camera will never, ever change. So all you have to do is render it once and for all onto the screen and move it accordingly to the player looking up/down/left/right. As always, you can decide to render it from a 3D model (if you're rendering a complex, slowly-changing object such as a cloud) or from an actual 2D drawing.

You never need to scale it because it always remains at infinite distance. In order to rationalize that lateral movement (up/down/left/right) of the 2D rendered object that occupies the entire field of vision (like the sky), you project it onto a very large cube created around the scene (the player is inside the giant cube). You might want to apply a slight distortion of your 2D-rendered sky at the limits between each face of the cube, so that it's not too obvious that the sky is actually a cube. And voilà.

2
  • 1
    This is more the sort of technique I expected when I asked the question. However, now that I think of it, Doom does seem to have used the "imposters" technique. I've noticed that having an animation of an object rotating was often used in the "billboard" variation to disguise the fact that it's a pre-rendered 2D sprite and not a full 3D object.
    – wizzwizz4
    Mar 6, 2018 at 16:35
  • 2
    Thought so ;-) However in Doom it's so scarcely used that you can barely call it impostors. Impostors is really used when you want to render many times the same 3d object OR one object only once in a while. In Doom it's just a few sprite on the screen that don't even try to pass as 3D. Mar 7, 2018 at 20:59
5

It helps to understand what the main limitations of 3D graphics where back in the day. Memory bandwidth was very limited, and early computers often stored graphics in a format that made changing individual pixels or spans of pixels expensive (e.g. Amiga bitplanes).

As such it often helped to move 3D rendering away from graphics RAM and into some faster RAM which lessened the effect of overdraw. This was common on the Amiga in later years, and was often combined with a conversion from a convenient graphics format to the Amiga display format which made use of the otherwise dead time between memory access cycles.

Also, floating point mathematics were very expensive due to most CPUs not having an FPU, and even FPUs being fairly low performance by modern standards.

As such it was common to used fixed precision floating point, or simply use integer maths scaled up by say 10,000x. Operations like division, multiplication and sine/cosine were expensive too so optimizations such as using binary shifts and lookup takes were necessary.

3
  • This technique of rendering in "faster RAM" doesn't make sense to me. Surely you'd have to write it into graphics RAM eventually, and so it would be better to write it there in the first place... unless you mean something different to what I'm interpreting it as meaning.
    – wizzwizz4
    Mar 7, 2018 at 17:12
  • 2
    On the Amiga there was two types of RAM. Chip RAM and Fast RAM. Chip RAM was 16 bit 3.58mhz. Fast RAM, when attached to an accelerator card, was like 32bit 25mhz. Plus, Chip RAM was used also by the chipset to fetch gfx data to feed the raster. So the CPU had half or even less of the bandwidth. Amiga chipset needed gfx in planar format too. Since gfx had some degree of overdraw, it was faster to render in Fast RAM and only at the end copy in Chip RAM doing the chunky to planar conversion contextually. Mar 7, 2018 at 19:40
  • All the answers above and even this comment about faster RAM can be summed up in one general trick : reduce the calculations spaces (whether be color space, coordinates space, angle space, discrete numbers, etc...). When it comes to memory reducing calculations space can mean reduce addressing space (through some platform-dependant assembly tricks). The "closer" the memory you need to read/write, the less data needs to be moved around. And that can fasten things up. Mar 16, 2018 at 16:29
4

A more abstract answer : speeding up the computations always relies on narrowing some of the data spaces.

  • Narrowing the color space : Simplifying any kind of alpha transparency or remove it entirely. Simplifying / factorizing the RGB encoding by using indexed colors.

  • Narrowing the rendering space : Don't redraw the whole scene at each cycle, instead buffer the "dirty" parts and redraw only those ones. In #d, use a BSP tree or culling to render only the faces that can be seen by the player.

  • Narrowing the 3d space : don't use floats for coordinates. Round everything up all the time. Use parallax instead of real 3d.

  • Narrow the angles : Instead of 360 degrees, only allow stuff directly facing the camera (pure 2d) or only at 45 degrees angle (isometric), or fake the height (doom-like raytracing engine). Pre-buffer the values of the cos and sin for the most used angles.

  • Even narrowing the computer code space : Use assembly language to disregard a lot of failsafes in loops or potential input/output values, and instead go straight to the point. Sometimes, copy and paste the same code 10 times rather than having a for..next loop

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .