3D Coding TAT - Introduction/Waffle
Who is it for ?
These code & tricks are intended for 80x86 assembly-language coders (all 10 of us) who choose not to use a high-level language but enjoy getting our hands dirty with the low-level nitty-gritty stuff. Although many of the techniques can be applied to other languages without too much fuss (many if not all of the examples are in pseudo-code) coding 3d stuff should demand the fastest methods to give the greatest level of detail at the lowest possible hardware requirement.
"A programmer who is scared of assembly....
is like a pilot who is scared of flying.."
No matter how fancy your compiler optimzation options are they cannot really compete with pure 80x86.
"Using a high-level language for games
is like driving with the hand-brake on."
Typos & mistakes
I am sure that a great number of mistakes and spelling errors can be found in this document. Possibly some of the methods I have described won't work because of 'em or there are no doubt flaws in the given psuedo-code which prevents it from working. This document is NOT meant to be a source-code-library, but as an incentive to spark off your own improvements and code ideas. Personally I reckon that using someone else's 3d library is a backwards step and does nothing to advance the state-of-the-art goal posts because let's face it, the 3d engine is already 2nd hand and past it's sell by date.
Does this stuff work ?
Well, maybe. Some of the ideas are still too vague or perhaps too flawed to be implemented directly, so a variable amount of development time will no doubt be needed to fully realise them. Many of the methods and tricks included in this document are merely extensions of my own observations about 3d objects, projection and data classification. When I first programmed some 3d code way back in 1989/1990 I had VERY little resources and almost zero access to the well known clipping, line drawing and polygon drawing techniques so about 90% of this was learnt the hard way. Many (all) of these techniques are only intended to be motivation for either improving traditional algorithms or to be the spark of a yet-to-be-discovered method. The text was written in a mostly jargon free way, but now and again a phraze pops in for a quick visit.
Wording and Definitions
Some of the wording of subjects and ideas may be incorrect to some extent and my mathematical knowledge is basic, so the reader is asked to overlook some small errors or mistakes. Many of the trendy buzz-words have been explained in a brief way so that a basic understanding can be quickly gained without too much maths jargon or techo-babble (which some 'professional' programmers seem to get their rocks off on) personally I think that a simple, easy-to- understand describe helps create an easy-to-code algorithm because you can spend more time on optimizing and development rather than remembering what a "4d quasi-jerp" or "nonrational-polar-hyper-exponent" actually does.
I have tried where possible to describe things in a logic and easy to read structure with many iffy ASCII diagrams to illustrate. The same technique is sometimes described in a number of ways and the wording of one element might be exchanged with another, this will hopefully help any confused readers by giving a different approach to a subject.
At the end of this quickly growing document I have included a short glossary of terms which should help the baffled.
Mentality of a coder
I find that going right back to the basic definitions and re-reading some of the most primative code & algorithms can help inspire me develop new ways of looking at complex problems or new techniques. These days many new programmers seem to skip past most of the fundamental programming techniques. With floating-point instructions and 32-bit registers some argue that the older stuff like division algorithms or mult-byte precision using ADC etc. is obsolete. But I strongly disagree because many of the primative techniques were developed on slug-like processors and so were optimized far more than most of today's offerings. Even the classic "repeated-subtraction to-do-a-division" is important, not to replace the CPU's IDIV and DIV instructions but it is the hidden technique behind the Bresenham line drawing (although no-one has ever mentioned this, it IS repeated subtraction for DIVISION and NOT like most books like to call it DECISION based.)
If you try to code a game/3d engine from a mathematical point then I reckon you have chosen the wrong starting point. Think from a CPU view-point and what instruction it likes and dislikes, choose those which it likes (MOV, ADD etc.) and minimize those it does not (FSQRT etc.).
LUT (Look-Up Tables) can not only be a good source of speed-up but they have two other bonuses, 1. they normally free up more registers than by the calculation approach. 2. they do allow a certain amount of flexibility at initialisation time. So very complex rules and optimizations can sometimes be built in the look-up tables when they are created this removes some tests which the calculation approach needs.
3. disk space is usually saved, depending on whether your program builts the tables or they are included at assembly time.
If you are really serious about writing lightning fast 3d code then I would first suggest thinking about the overall view of your engine, what it needs to do (and most importantly what it DOES NOT need to do), scribble down all the restrictions and the amount of flexibility you want in your engine. This way the places where a corner can be cut will hopefully be seen at the beginning. Sometimes it is very easy to get bogged down in the instruction optimization. Trying to shave another 1 CLK cycle off that pixel drawing routine might be a small reward and can be misplaced if your line drawing is still sluggish. A trap which I have fallen in many times when writing code is attempting to optimize the code as you write it. As you type instructions you may realise a better way, so you go back and delete the previous few lines for a better method and then you see another optimization, before you know it your source code is shrinking in size rather than growing! So just get the rough outline of your code typed in and then you can optimize it much more easily because you can see the program flow a lot more clearly and you will end up with working code MUCH sooner.
Sometimes it is very easy to fall into the low-level trap (not seeing the forest for the trees), this is where I believe a more global, "group" approach can give the best gains. Instead of rejecting a single polygon, try and reject entire objects, rooms, even sub-levels if you can. This way a vast amount of calculation and processing can be avoided without counting each CLK cycle. And then when you do groom your code for tweaks and optmization tricks, your engine will leave all the rest standing! Sometimes an entirely new/different way of approaching the same old problem (like using some not-so-obvious algorithms) can produce better optimization than following the traditional rendering method path as written in most books.
The fastest way to draw something .... is NOT to draw it!
I know the above phrase looks stupid, but it is the actual goal for all programmers when they optimize. The goal is not to use the fastest instructions but NO instructions at all.
The problem of "overdraw" can seriously reduce performance. I remember once reading an article written by a team from a games software house who had written a number of 3d games and they stated "trying to calculate what can be seen would make the games run at an unplayable rate... so we simply draw the most distant objects first and then overdraw with nearer ones." But I reckon this situation has now been reversed due to the vast increase in polygon and textures workload which is now demanded for an "average" 3d engine. As the levels have doubled and doubled in terms of polygons and complexity, the need for pre-processed level and more fanciful storage/sorting techniques has become a much more important issue than ever before and will be vital in the near future.