ftp.gamers.org/ftp.gamers.org.zip/ftp.gamers.org/pub/games/uwp-uml/game-dev/docs/rgp-faq

Text File | 1993-07-04 | 41KB | 1,077 lines

Revision 0.0.5  of REC.GAMES.FAQ

This document will be made available by mail request at a later
date (mail server difficulties).  You may attempt to see if this
mail server works by sending to:

    [e-mail]

I cannot be sure it's working yet,  please leave feedback on what
state it is in.

There are currently 3 FAQ's

RGP.FAQ - rec.games.programmer General FAQ
RGP.IBM - rec.games.ibm relevant FAQ
MAZE.FAQ - FAQ about MAZE's (more of a compilation of articles)

This was done so that someone who is looking for more general
information will be able to find game programing information
without being inundated by IBM, other computer-SPECIFIC
information, or the topsy turvey world of maze generation.

The current Editor is [e-mail]

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     Contents
--------------------------------------------------------------------------------
LEGAL

This document is FREE!  It is for your self enlightenment.  No
warranty is provided nor implied with this information. The
accuracy of the information contained herein is subject to
conjecture.  Therefore the editor and contributers will take NO
liability for improper use, misuse, or abuse of this information,
and any damage to ANYTHING or ANYONE whether physical, financial,
etc. in no way, shape, or form can be attributed to this
document. Use this information at your OWN risk.

The above statement is to keep those who contributed and the
editor free from personal injury for being nice.

Special thanks to:
[e-mail] (Andre A. Nurwono)
[e-mail] (Dave Roberts)
[e-mail] (Sean Barrett)
[e-mail] (Cyberman)
(and anyone else I forgot to mention for that matter)

If you wish to contribute CODE be sure it's something you DO NOT
wish to COPYRIGHT!

All contributions and suggestions should be sent to me at:
[e-mail]
place in subject header

RGP.FAQ.*
where * is any of the following
    SUGGESTION      - to suggest Adding an area (I recommend that
                        you send the information if you want it
                        added)
    ADD             - an addition (ie TBA's [see KEY for what TBA
                        means])
    EDIT            - for a correction somewhere (it is suggested
                        contributers do there own editing)
    FLAME           - complaints - I'll read these but be sure to
                        be tasteful in you commentary.  You may or
                        may NOT get a reply.

For now I'm going to use my personal mail account.  So please be
careful.

Format:
There are several categories and each category contains it's
relevant questions as suggested.

Key:
TBA - To Be Added

[Frequently Asked Questions about terminology]
Q1.1    What are .MOD files?
Q1.2    What is a pixel?
Q1.3    What is a bitmap?
Q1.4    What is flicker?
Q1.5    What is snow?
Q1.6    What is a frame buffer?
Q1.7    What is a Sprite?
Q1.8    What is vertical/horizontal retrace?

[Frequently Asked Questions about Animation]
Q2.1    How do I make sprites on my xxx?
Q2.2    What about collision detection?             TBA
Q2.3    What about bitmap scaling?                  TBA
Q2.4    What is perspective mapping?                TBA
Q2.5    What about 3d objects and manipulation?

[Frequently Asked Questions about Map Generation]
Q3.1    How do I generate a maze?
Q3.2    How do I generate a landscape/terrain?      TBA
Q3.3    How do I generate a hex map?                TBA
Q3.4    What about random number generators?

[Frequently Asked Questions about Libraries and support software]
Q4.1    What is there for the IBM compatible?
Q4.2    "    "  "     "   "   Amiga?                TBA
Q4.3    "    "  "     "   "   Atari?                TBA
Q4.4    "    "  "     "   "   Macintosh?            TBA
Q4.5    "    "  "     "   "   Sun/Sparc?
Q4.6    "    "  "     "   "   X?                    TBA

[Frequently Asked Question about Where is ...]
Q5.1    Where is Joshua Jensens famous Perspective Mapping Code?
Q5.2    Where else should I read?
Q5.3    Where can I find out about ray traceing?

Note 1: Fixing snow and flicker
Note 2: 2 Part Tutorial on 3d graphics

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     Terminology
--------------------------------------------------------------------------------

Q1.1    What are .MOD files?
    A .MOD file is a file generated for the Amiga.  A tracker is
    used to play the MOD.  A mod consists of digitized sound and
    sequencing information to play music.  Here is a BRIEF and
    incomplete text file that is somewhat informative on the
    subject.

    Note - Joshua Jensen has written a mod player that can be
    linked into your code.  So has the author of mod play.

    SEE ALSO - Mod Format specification file.  (Modform.zoo)

Q1.2    What is a Pixel?

    Pixel is short for Picture Element.  It is a single dot
    address on a grid used to display images on a monitor (Tv
    included).

Q1.3    What is a bitmap?

    A bitmap aka bitimage is the representation of an image in
    the form of a sequence of bits.  For example most graphic
    modes on computers represent the pixels using a BITMAP.

Q1.4    What is flicker?
    Flicker is a noticeable pulse or change in an image.  This
    can be on a CRT (Cathode Ray Tube) or other type display
    device.  The cause is that the refresh rate of the CRT is
    lower than the persistance of vision of the person observing
    it.

    Another form of flicker is due to rapid drawing of data on
    the screen.  What happens is that the data is drawn out of
    syncronization with the horizontal and vertical scan.  So
    your image apears to fade in and out of visability.

    SEE ALSO fixing snow and Flicker

Q1.5    What is SNOW?

    Snow are small specals on the screen that appear like SNOW
    falling on the screen (hence the name).

    Snow is caused by a number of things.  One of which is when
    one is writting to the screen while the display card is
    scanning that address of the screen, this causes a conflict
    and can produce random specals.

    Another cause of snow is an improperly connected monitor.
    This can damage the monitor.  Yet another source is noise
    from an electro magnetic source, if indeed it's not from
    anything you own the FCC might need to be notified.

    SEE ALSO fixing snow and Flicker

Q1.6    What is a frame buffer?

    Memory that contains image data that is translated to the image
    on your screen.  A frame buffer does not have to be
    "visible".  Also the methode of this tranformation is not
    always the same, so no effort here will be made to explain
    further.

Q1.7    What is a Sprite?

    A sprite is an image usually moveable about the screen.
    Common information stored in a sprite are, width, height,
    position, and image data.  A sprite ussually does not effect
    the screen background, this is of course dependant on
    implementation.

Q1.8    What is vertical/horizontal retrace?

    Most monitors are what is called a RASTER display.  This
    means that an image is represented by setting the intensity
    of a grid of dots on the display.  Each dot is called a
    pixel.  In order to display the grid a CRT sweeps an electron
    beam across the display surface sending pulses corresponding
    to the intensity of the pixel.  However the stream of video
    information is almost always represented left to right top to
    bottom.  This mean that the beam must scan across the screen
    and then move BACK to start a line.  This is called
    Horizontal retrace.

    Vertical retrace is when the beam finishes painting the
    screen from top to bottom again the beam must be moved to the
    top of the screen.

    The horizontal sweep is controlled by an electric field the
    vertical sweep is controlled usually magnetic field.

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     Animation
--------------------------------------------------------------------------------

[Frequently Asked Questions about Animation]
Q2.1    How do I make sprites on my xxx?

    This, unfortunately, is a rather complex problem and its
    implementation is often computer-specific, however some of it
    can be addressed in the general FAQ.

    Sprites require one to copy pixels to the display in a
    certain area of the screen.  There are various issues that
    must be addressed about this.

    Getting and Putting an image: getting means you copy a
    section of a screen (bitmap) to a buffer, putting means you
    dump a buffer of data (bitmap) to a screen location.  These
    are often used for less sophisticated sprite animation.

    The problem with this technique is put destroys the
    background information.  So if you want a background at all,
    there must be a way to "overlay" an image onto it without
    causing a large area around the sprite to disappear. An old
    way of "fixing" this is to copy the background of an image
    before you destroy it, then put the background back after you
    move it.

    Another methode of sprite creation requires custome hardware
    (Amiga C64 Atari 8bits).

Q2.2    What about collision detection?                 TBA
Q2.3    What about bitmap scaling?                      TBA
Q2.4    What is perspective mapping?

    What is it?  Basically it takes an image and "pastes" it in
    3d perspective onto a surface.  This is much faster than
    rendering surfaces in real time.  Article 7716 of r.g.p
    written by Joshua C. Jensen ([e-mail]) is an example
    of this technique (implemented in Turbo Pascal).
    Unfortunately this article # may not corespond to anything in
    usenet! :)  However the date it was posted was 1 Aug 92
    01:36:51 GMT.  SO you can grab the coresponding articles
    there! :)

Q2.5    What about 3d objects and manipulation?

    Note 2 is a pair of tutorials on this subject.

    Another suggestion is to check comp.graphics FAQ and the
    comp.graphics resources guide as well.

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     Map Generation
--------------------------------------------------------------------------------

Q3.1    How do I generate a maze?

    This is a VERY frequently asked question in rgp so we have
    a unoffical maze FAQ.  It's is now posted WITH the RGP Faq.

Q3.2    How do I generate a landscape/terrain?
    Another fun filled FAQ it has too many answers.  A suggestion
    is to read sci.fractals.  Now if someone would conribute some
    information on this I would be happy to construct the
    "land.faq".

Q3.3    How do I generate/use a hex map?
    Well this has discussed considerably on rgp.  We haven't a
    FAQ for it until I get permission to use something I
    captured.

Q3.4    What about random number generators?
    These are mandatory for making a "new" universe each time a
    program loads.  Usually the ones included in a C compiler
    library are sufficient for most needs.  However sometimes one
    must go the extra mile and use there own random number
    generator.  Currently we have no FAQ on random number
    generators.  (sorry)

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     Libraries and support software
--------------------------------------------------------------------------------

Q4.1    What is there for the IBM and Compatibles?

    There is a lot.  I suggest scrounging around wuarchive
    personally, but here is a terse UNOFFICIAL list!

    contributed by
[e-mail] (Andre A. Nurwono)
==========
 --------
 Graphics
 --------

*.  Executable
    File(s) : TWEAK06.ZIP
    Who     : Robert Schmidt ([e-mail])
    When    : 1992
    What    : A program to experiment w/ VGA registers, very useful
          if you want to define new modes (like mode X & 360x400 modes)
    Where   : simtel & mirrors

*.  Executable, (source code)
    File    : SPRITE.ZIP
    Who     : Billy Dalrymple
    When    : 1989
    What    : A sprite editor, produces sprites w/ mask in files.
          info available for $10
          source code available for $25
    Where   : I forget

*.  Executable, Source Code
    File(s) : VGA.ZIP
    Who     : [e-mail]
    When    : 1992
    What    : A sprite editor, includes full source (.ASM & .C)
    Where   : I forget

*.  Source Code, Library
    File(s) : DDJ****.ZIP, XSHARP**.ZIP
    Who     : M. Abrash
    When    : Aug-Dec 1991, Jun-Aug 1992
    What    : Mode X introduction. Sources to do animation,
          polygon plotting, anti-aliasing, etc, on Mode X.
    Where   : SIMTEL and mirrors,
          ftp.mv.com (Official DDJ site) in pub/ddj

*.  Source Code
    File(s) : article 7198 of rec.games.programmer
    Who     : Frederick J. Haab ([e-mail])
    When    : 26 Jun 92 00:17:52 GMT
    What    : Scrolling in mode 13h, C program
    Where   : USENET archives

*.  Source Code
    File(s) : article 7716 of rec.games.programmer
    Who     : Joshua C. Jensen ([e-mail])
    When    : 30 Jul 92 00:02:36 GMT
    What    : Bitmap manipulation (scaling + perspective), Turbo Pascal
          source w/ inline assembly.
    Where   : USENET archives

*.  Source Code
    File(s) : VESAVGA.ZIP
    Who     : Randy Buckland
    When    : 6/18/92
    What    : .ASM & .C source to provide fast routines for VESA VGA modes.
    Where   : garbo

*.  Sprite Library, Code
    File(s) : STK110.LZH
    Who     : Jari Karjala
    When    : 1991 (v 1.1)
    What    : Sprite library & toolkit for Hi-Res EGA, BW
          includes C source, demo & good docs.
    Where   : simtel & mirrors

*.  Sprite Library, Source Code
    File    : SPRITES.ZIP
    Who     : Marius Kjeldahl
    When    : 1991
    What    : Sprite library for VGA mode $13
          includes TPU, .PAS source.
          (shareware, $69 ?)
    Where   : garbo

*.  Sprite Library, Toolkit
    File(s) : WGT_SPR2.ZIP, WGT_TC21.ZIP, WGT_TP2.ZIP
    Who     :
    When    : 1992
    What    : Shareware Sprite toolkit for VGA mode $13
              includes TPU (WGT_TP2.ZIP), example programs for usage
          Nag-shareware program
    Where   : wuarchive, if somebody hasn't erased it yet

*.  Library (Pascal)
    Files   : EGOF10.ZIP, EGOF10P.ZIP, EGOF10M.ZIP,
              EGOF10B.ZIP, EGOF106.ZIP
    Who     : Logi Ragnarsson
    When    : 1993
    What    : 256-colour graphics library for Turbo/Borland Pascal 6.0
              and 7.0, VESA SVGA, Mode-X (and more), VGA/MCGA 320x200,
              example programs, manual, shareware ($20).
    Where   : garbo

*.  Library Source
    File(s) : Xlib04c.zip
    Who     : Themie Gouthas (and company)
    When    : 11 Mar 93
    What    : mode X library for game, to many feature to mention
    Where   : pub/[e-mail]

 -------------
 Sound & Music
 -------------

*.  Documentation
    File(s) : Article 6077 of rec.games.programmer
    Who     : Jeffrey S. Lee ([e-mail])
    When    : 25 Feb 92 15:02:02 GMT
    What    : Programming the AdLib/Sound Blaster FM Music Chips
    Where   : usenet archives, also at the SB project site
          (tybalt.cco.caltech.edu), & SB mailserver
          ([e-mail])

*.  Executable, Runtime Library
    File(s) : MODTECH.ZIP
    Who     : Mark J. Cox ([e-mail])
    When    : 1991
    What    : TSR Library to play .MOD files in the background
          Supports PC Speaker, SB, DisneySS, LPT DACs, etc
    Where   : ftp.brad.ac.uk in /misc/msdos/mp

*.  Library
    File(s) : MODOBJ.ZIP
    Who     : Mark J. Cox ([e-mail])
    When    : 1992
    What    : .OBJ file w/ routines to play .MOD files in the background
          Supports PC Speaker, SB, DisneySS, LPT DACs, etc
          Includes examples in TC & TP
          (shareware, $30)
    Where   : ftp.brad.ac.uk in /misc/msdos/mp

*.  Source code
    File(s) : NH10SRC.ZIP
    Who     :
    When    :
    What    : Eliminate noise on sound samples, incl. .C source
    Where   : SB project site & mailserv site

*.  Source code, Executable
    File(s) : SB_OSC.ZIP
    Who     :
    When    :
    What    : SB input scope / oscillator. Incl. .ASM source
    Where   : SB project site & mailserv site

*.  Source code, Executable
    File(s) : SBDAC.ZIP
    Who     : Jeff Bird ([e-mail])
    When    : 12 Feb 92
    What    : SB DAC programming using DMA. Incl. .ASM & .C source
    Where   : I forget (probably on SB project sites too)

==========

Q4.2    "    "  "     "   "   Amiga?                TBA

Q4.3    What is there for the Atari?

from [e-mail]

    AMS library - Atari Machine Specific library
      - C++ classes for Sprites, Screen, Joysticks, Double buffering, etc.
      - beta testing now
      - contact: [e-mail]

Q4.4    "    "  "     "   "   Macintosh?

from [e-mail]

*. Source code
    Files   : Arashi_Source.cpt.bin
    Who     : ???
    When    : ???
    What    : source code for an arcade quality game, vector
        graphics, multichannel sound, (no sprites)
    Where   : pub/mac/think-c/[e-mail]

Q4.5    "    "  "     "   "   Sun/Sparcs?

    contributed by
[e-mail] (Andre A. Nurwono)
==========
 --------
 Graphics
 --------
*.  Library
    What    : Standard PIXRECT library
          Bitmap manipulation routines for frame buffer.

 -------------
 Music & Audio
 -------------
*.  Source code
    File(s) : tracker.tar.Z
    Who     :
    When    :
    What    : .MOD file player through the audio device. Works on SPARCS
          w/ audio devices.
    Where   :

*.  Source code
    File(s) : csound.tar.Z
    What    : FFT & signal processor

*.  Source code
    What    : MixView
==========

Q4.6    "    "  "     "   "   X                     TBA

    Additions are welcome.

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     FAQ's about Where is ...
--------------------------------------------------------------------------------

Q5.1    Where is Joshua Jensens famous Perspective Mapping Code?

    Beats me no one has found it yet (or at least hasn't told me
    they have and where to get it!) in one of the many usenet
    archive sites.  Places to look are gatekeeper.com and
    wuarchive.wustl.edu.  Both of these ftp sites archive usenet
    news.  I suspect all the rec.games.programmer articles are on
    these sites and maybe (heavem forbid) the original FAQ even.

Q5.2    Where else should I read?

    Here are SUGGESTED places you get information for things like
    perspective mapping programming the SB etc.

        comp.graphics
        comp.graphics.animation
        comp.sys.ibm.pc.soundcard

    I suggest before posting you read ALL newsgroups a minimum of
    1 week.  Ussually you will see the FAQ or where to get it.

    places suggested NOT to look for information

        comp.graphics.research

        if you want to get famed for posting off topic do it
        there.  That group is for research IE new frontiers.

Q5.3    Where can I find out about ray traceing?

    Ask about POV in comp.graphics should be good for about 30 to
    40 replies in your mailbox.  There are several packages
    available for free and comercially.  I suggest POV because
    it's free and actually quite good.  Vivid, Rayshade are just
    a few of the others.  POV seems to be the most popular (and
    portable also), with the most handy utilities.

--------------------------------------------------------------------------------
END OF FAQ

--------------------------------------------------------------------------------
REC.GAMES.PROGRAMMER     General FAQ     NOTES
--------------------------------------------------------------------------------

--------------------------------------------------------------------------------
NOTE 1: contributed by
--------------------------------------------------------------------------------
[e-mail] (Sean Barrett)

There are two things that qualify as flicker.  Well, hell, to make it
simpler, let's call it three.  At the end of this list I'll give a
rough definition of the problem.

1)    You move a shape by erasing it and plotting it in a new position,
and there is a screen refresh during the time it is erased, resulting in
the background showing through.

2)    You're using CGA and you try to write anywhere on the screen
during retrace, causing "noise" (due to DMA problems, I guess?).

3)    You're moving a shape by some sort of "one-pass" technique in which
the screen memory is never set to the background temporarily, so (1)
can't happen, but the screen area the shape is in is refreshed during
the draw, so half of it gets displayed at the old location, and half
at the new.

I think a general rule would be that flicker occurs when a pixel on
the screen is displayed with a color other than the "correct" or
"intended" pixel value, as compared to an ideal "intended" case.  (Thus,
if you're simulating something moving, you shouldn't see the
background; if you're trying to simulate something moving and
turning on and off simultaneously, then you should see it; it's
all a question of intent.)

Back to the above problems.

Now, so far as I know, there are only two solutions to #2.  Only redraw
during the vertical retrace (blank), or don't support CGA.  So I'm going
to forget about this problem.

You can handle #1, as I suggested in #3, by simply making sure you never
write to the screen a value you don't want displayed.  Below I'll put a
list of ways I can think of to do this for bitmapped graphics--i.e.,
how to avoid the erase-redraw cycle.

If you really want to handle #3, then things get funky, and more power
to you.  I don't personally believe it's a problem.  If it's periodic,
so this one shape when you move it horizontally in the middle of the
screen is always split with the top half leading the bottom half by
a pixel, it's a problem; but if it just happens randomly once in a while
I doubt it's noticeable.  In general, though, the solutions require
paying attention to where the screen refresh is in some way.  My main
point, the reason I'm posting this whole thing, is that *solving problem
#1 does not require messing with knowing what section of the screen
is being refreshed.*  As far as I know, the methods to combatting #3
are to redraw everything during vertical refresh (same as #2, but
overkill) or drawing your shapes from top to bottom lagging about half
the time of a screen refresh behind the refresh, or some such.

Solutions to #1 that don't require timing considerations, e.g., how
never to write a wrong pixel to the screen.

  o    Don't use raw bitmaps, use sprite hardware.

  o    Use hardware page flipping: display one screen, draw a new
    screen "off-screen" and when it's finished, direct the
    display hardware to display the new one.  This can get messy
    for fast animation because you have to keep track of where
    sprites were the last two frames to erase and update them.

  o    Use software page flipping; display one screen, draw a new
    screen "off-screen" and when it's finished, copy the new
    screen into screen memory.

  o    Use techniques such as "store" sprites which overwrite the
    background.  Generally an out-of-date technique now, though;
    only works for mono-color backgrounds.  You simply write the
    sprite onto the screen; the sprite has enough border around
    it to overwrite its previous image.  This is gross, very
    fast, and flicker-free except when shapes get on top of each
    other, at which point you get massive flicker.

  o    Use scratch-pad calculations, a variant of software page flipping.
    Copy the section of the screen off that you need to update,
    update it offscreen, and put it back on the screen.  A lengthy
    time ago I posted a discussion of how to do this effectively
    for XOR-style graphics for 8-bit type machines--you can xor
    a single image onto the screen that both erases and replots
    in a new place the old sprite.  And you can calculate the
    image to do it on the fly, without additional memory, if you
    set up your shape tables, and it's faster than the normal
    draw shape with XOR to erase, draw shape with XOR to plot cycle
    because it only reads and writes screen memory once.

Performance enhancements for bit blitting:

  o    Unroll loops.

  o    Write a custom bit blit for each shape, dedicated to that shape.
    Cuts your memory accessing down if the machine has an
    "immediate" operand mode that's faster than an index-addressed
    one.

Memory performance enhancements for techniques that require many copies
of shapes or large routines (such as pre-shifted shape tables):

  o    If you're only using some of your shapes at any point in time
    (e.g. if you can divide your display up into "scenes"; for a
    certain period of time only these shapes are used), calculate
    the "larger" derived tables on the fly when the scene starts
    up.  For large games (this is rec.games.programmer, not
    rec.graphics.programmer, right?) that have to access the disk
    anyway to change scenes, this is no big time loss.  Also, if
    you write the code right then while you're idling the processor
    before starting work on the next display, you can do this stuff
    then.

--------------------------------------------------------------------------------
NOTE 2: contributed by
--------------------------------------------------------------------------------
[e-mail] (Sean Barrett)

3D graphics: Using matrices and vectors        Part 1


-  Allows you to independently rotate objects and move the camera
   anywhere.
-  Does not discuss clipping.
-  Algorithm uses 9 multiplies, 2 divides, and 9 additions per point,
   plus overhead per independently located object.
-  Part 2 gives the derivation for these formulas.


Assume a right-handed universe, with x horizontal, y
depth, and z vertical, and a screen display unit with
x horizontal to the right and y vertical downward.


The following are the rotation matrices:

    Rx(t)            Ry(t)            Rz(t)
__                  __  __                  __  __                  __
| 1    0      0    0 |    | cos(t) 0 -sin(t) 0 |    |  cos(t) sin(t) 0 0 |
| 0  cos(t) sin(t) 0 |    |    0   1    0    0 |    | -sin(t) cos(t) 0 0 |
| 0 -sin(t) cos(t) 0 |    | sin(t) 0  cos(t) 0 |    |    0        0    1 0 |
| 0    0      0    1 |  |    0   0    0    1 |  |    0      0    0 1 |
--                  --  --                  --  --                  --
   rotate about x       rotate about y       rotate about z


The following is the translation matrix:

  T(a,b,c)
__       __
| 1 0 0 a |
| 0 1 0 b |
| 0 0 1 c |
| 0 0 0 1 |
--       --

Let each object be a collection of points or lines.  If lines, they
are drawn as lines connecting two 3D points, which can each be
individually transformed.  So this derivation just handles converting
individual points in three-space into pixel coordinates.

---- BEGIN FORMULAS ----

If d is the distance from the eye to the window, h is the width
of the window, v is the height of the window (use the sizes
of the actual display if you don't know what else, but this is
actually referring to the virtual camera's window); num_x
is the number of pixels on the display in the x direction, num_y
the number of pixels in the y direction, and (center_x,center_y)
the location of the center of the display;

let scale_x = d/h*number_of_x_pixels, scale_y = d/v*number_of_y_pixels.

Then let S be defined as
__                           __
| scale_x center_x    0     0 |
|   0        1        0     0 |
|   0     center_y -scale_y 0 |
|   0        0        0     1 |
--                           --

Let the camera be located at (cx,cy,cz).  Let the vector E be pointing
in the direction the camera is facing, the vector D be pointing to
the right (along the camera's x axis), and the vector F be pointing
up (along the camera's z axis); and let D, E, and F be of length 1.
Then define the following matrices:

   matrix J        matrix C
| Dx Dy Dz 0 |  | 1 0 0 -cx |
| Ex Ey Ez 0 |  | 0 1 0 -cy |
| Fx Fy Fz 0 |  | 0 0 1 -cz |
| 0  0  0  1 |  | 0 0 0  1  |

and let N = S*J*C.


Let each object i be at location cix, ciy, ciz, and let the matrix
which holds the current rotation for that object be O(i).  To rotate
the object around the q axis by n degrees, let new O(i) = Rq(n) * O(i).
To rotate the object about *its* q axis, let new O(i) = O(i) * Rq(n)
(I think.  I haven't looked at this closely, so it's probably wrong).

Let Otemp(i) be O(i) with the rightmost column of zeros replaced by
cix, ciy, and ciz, or in other words, the product of Temp(i)*O(i) where
Temp(i) is
__         __
| 1 0 0 cix |
| 0 1 0 ciy |
| 0 0 1 ciz |
| 0 0 0  1  |
--         --

Now, for each object i let M = N * Otemp(i).

Now, for each point P in i, let V = M * P, that is:

    Vx = M[0,0]*Px + M[0,1]*Py + M[0,2]*Pz + M[0,3];
    Vy = M[1,0]*Px + M[1,1]*Py + M[1,2]*Pz + M[1,3];
    Vz = M[2,0]*Px + M[2,1]*Py + M[2,2]*Pz + M[2,3];

Then the pixel to plot to is:

    If Vy>0
        (Vx/Vy, Vz/Vy)

Done.

-- 2 --

3D graphics: using matrices and vectors        Part 2

-  Allows you to independently rotate objects and move the camera
   anywhere.
-  Does not discuss clipping.
-  Algorithm uses 16 multiplies, 2 divides, and 12 adds for each point,
   plus overhead per independently located object.  Also shows how some
   of the calculations are wasted, and reduces it to 9 multiplies and 9
   additions.


The folowomg is a derivation of some of the math for using 3D
graphics with matrices and vectors.  I don't see any way of
explaining how to use the matrix formulas without all the extra
context, so you'll have to wade through it.  In general, you can
simplify things by multiplying out the matrices and similar
techniques.

You have a world described by three dimensional coordinates--it
could be lines or points or polygons, whatever.  You have an
imaginary camera in this world, and you want to draw exactly
what this camera would see.

We represent the camera as a point where an "eye" is and a window
through which it's looking--that is, a point for the eye, a vector
from the eye to the center of the window, and another vector to tell
us which way is the up direction on the window.  We can figure out
the sideways direction of the window by taking a cross-product, but
it may be better to represent it explicitly, as discussed far
eventually below.

What we want to know is where on our screen we should plot a
particular point.  The solution is to figure out where on the
imaginary window the point would appear to be, and then to map
the window onto our screen.

Suppose the eye is at the origin, facing along the X axis, and
the point is in the XY plane so we can only look at two dimensions
for illustration purposes.

Y axis
 |                ___---
 |          ___---
 |    ___--- |           Point
 | ---       |
eye----------+------------------  X axis
   ---___    |
         ---_|_
        window ---___
                     ---___

Suppose the window ranges from (d,h/2) to (d,-h/2) and the point is at
(a,b).  We want to know where the line from the point to the eye
intersects the window line.  Well, the point is only visible if
it's in front of the eye, so assume a>0.  Now, the two lines are

    y = (b/a)*x        (from Point to eye)
and    x = d            (line window is on)

So the location of intersection is (d,(b/a)*d).  In other words,
the point appears on our imaginary window with horizontal position
d*b/a if |d*b/a| <= h/2.

Thus, the quick and dirty 3d graphics formula for assuming an eyepoint
at the origin, X horizontal, positive to the right, Y vertical, positive
up, and Z depth, positive going into the distance (this is a left-handed
universe, whereas the rest of the derivations will be for a right handed
universe), and screen coordinates sx horizontal, positive to the right
sy vertical, positive down, is:

    if (Z>0) then
        sx = x_scale * X / Z + x_center;
        sy = - y_scale * Y / Z + y_center;
    endif

where x_center, y_center is the pixel address of the center of the
screen; x_scale is d/h*number_of_pixels_horizontally and y_scale is
d/v*number_of_pixels_vertically; d is the distance between the eye
and the window in the imaginary camera, h and v are the height and
width respectively of the imaginary window.

Ok, back to the messy stuff.  Since our eyepoint won't necessarily
be at the origin and facing in the right direction, we need to be
able to handle arbitrary translations and rotations.  In general,
to rotate (a,b) into (a',b') based on a given angle t, we do

    a' = cos(t)*a + sin(t)*b;
    b' = cos(t)*b - sin(t)*a;
(or switch the signs depending on which way you want to define as
the positive direction of rotation).

Now, to cleanly handle multiple rotations, we want to use matrices
to handle this.  This is the same as

    | cos(t) sin(t)|  |a| _ |a'|
    |-sin(t) cos(t)|  |b| - |b'|

that is, a 2x2 matrix times a 2x1 matrix gives a 2x1 matrix.  Now
to handle an arbitrary 3D rotation, we need to rotate on any axis:

   rotate about x       rotate about y       rotate about z

| 1    0      0    |    | cos(t) 0 -sin(t) |    |  cos(t) sin(t) 0 |
| 0  cos(t) sin(t) |    |    0   1   0     |    | -sin(t) cos(t) 0 |
| 0 -sin(t) cos(t) |    | sin(t) 0  cos(t) |    |    0        0    1 |

Now, to rotate about a particular point, we have to translate to that
point.  Say we want to rotate about (d,e,f).  Then we subtract (d,e,f)
from our point, rotate, and then add (d,e,f) again.  It would be nice
if we could do that automatically with the matrices, and there is a way
to, a cute trick.  We switch from 3x3 matrices to 4x4 matrices, and use
4-vectors.  For the rotation matrices, the new elements are all zero,
except the bottom right one which is 1; for example:

|  cos(t) sin(t) 0 0 |
| -sin(t) cos(t) 0 0 |
|    0      0    1 0 |
|    0      0    0 1 |

Also, all of our vectors have a fourth element, which is always 1.
(In programming this, you can just continue to use three-vectors and
program the 'multiply matrix by vector routine' to pretend there's
one there.)  Now, to do a translation we want:

    x' = x + k1;
    y' = y + k2;
    z' = z + k3;

It turns out that this does the trick:

| 1 0 0 k1 |  | x |
| 0 1 0 k2 |  | y |
| 0 0 1 k3 |  | z |
| 0 0 0 1  |  | 1 |


Now, let's define some matrix terms so we can compress our notation.
Let Rx(t), Ry(t), and Rz(t) be the 4x4 rotation matrices, and let
T(k1,k2,k3) signify the appropriate matrix as above.  To rotate a point
(a,b,c) theta around the y axis at point (d,e,f), we do the following
in sequence: T(-d,-e,-f), Ry(theta), T(d,e,f).  Now, one nice thing
about matrices is that we can get the effect of sequential application
by multiplying matrices; that is, if U = (a,b,c,1) and V=(a',b',c',1),
then do  T(-d,-e,-f)*U, and take that and do Ry(theta)*that, and take
this and do T(d,e,f)*this, giving V, then this is:

    T(d,e,f) * ( Ry(theta) * ( T(-d,-e,-f) * U ) ) ) = V

Since matrix operations are associative, this is the same as

    T(d,e,f) * Ry(theta) * T(-d,-e,-f) * U = V

or, in other words, let M = T(d,e,f)*Ry(theta)*T(-d,-e,-f), then
M is a matrix which performs the rotation we desire.

Ok, now to wrap it all up.  Suppose we have a bunch of objects in
3D we want to display, and the aforementioned camera.  The camera
is at (cx,cy,cz), and we have a vector E pointing in the direction
the camera is aiming, a vector D which shows which way the window
is pointing to the right, and a vector F which points along the window
upward.  These vectors form an orthonormal basis, so to rotate into
the frame of reference for them we use the matrix

| Dx Dy Dz |
| Ex Ey Ez |
| Fx Fy Fz |

also, we want to use 4x4 matrices and first we want to translate
to cx..cz, so we use

   matrix J        matrix C
| Dx Dy Dz 0 |  | 0 0 0 -cx |
| Ex Ey Ez 0 |  | 0 0 0 -cy |
| Fx Fy Fz 0 |  | 0 0 0 -cz |
| 0  0  0  1 |  | 0 0 0  1  |

So for an arbitrary point (a,b,c) in three space, the screen coordinates
for it sx, sy are:  let U = (a,b,c,1); let V = J*C*U.  Then

    if (Vy>0) then
        sx = scale_x * Vx/Vy + center_x;
        sy = - scale_y * Vz/Vy + center_y;
    endif

Generally, we want to store J and C separately.  It is pretty simple
to move the camera, now; if the camera is always moving in the direction
its facing, use the E vector and factor direction in by hand, and
put this into C.  To rotate the camera, just multiply a rotation
matrix on the left by J.

Now, to rotate objects properly, keep a separate rotation matrix
for each object.  Then for each point in that object, rotate it and
translate it.  It's simplest to store each object with the origin
as the center of the object.  Then to calculate a point, you multiply
by the rotation matrix and then by the translation to put the objects
center where it should be in world space; because you're doing the
translation second, it's easy to put it into one matrix:

translation    rotation
| 1 0 0 l |   | a b c 0 |   | a b c l |
| 0 1 0 m |   | d e f 0 | _ | d e f m |
| 0 0 1 n | * | g h i 0 | - | g h i n |
| 0 0 0 1 |   | 0 0 0 1 |   | 0 0 0 1 |

Call this matrix O(q) where q is the object number.

Then, for each point in object q, the final multiply is
V = J * C * O(q) * U.

Finally, we can move some of the final calculation into a matrix.
We have:
    sx = scale_x * Vx/Vy + center_x;
    sy = -scale_y * Vz/Vy + center_y;

If we factor out Vy, we get
    sx = (scale_x * Vx + center_x * Vy)/Vy;
    sy = (-scale_y * Vz + center_y * Vy)/Vy;

Suppose from V we calculate V':
    (scale_x*Vx + center_x*Vy, Vy, -scale_y*Vz + center_y*Vz, 1)

Then
    sx = V'x / V'y;
    sy = V'z / V'y;

Well, to get V', we just multiply V by the matrix

| scale_x center_x    0     0 |
|   0        1        0     0 |
|   0     center_y -scale_y 0 |
|   0        0        0     1 |

Let us call this matrix S.  Remember, scale_x = d/h*number_of_x_pixels,
scale_y = d/v*number_of_y_pixels, d is distance from eye to window,
h is width of imaginary screen, v is height of imaginary screen.

So, now, the basic idea is this.  To minimize calculation, let
N = S * J * C.  For each object q, let M = N * O(q).  For every point
U in q, let V = M * U.  If Vy>0, then that point is at (Vx/Vy,Vz/Vy)
on the screen.

In pseudo-code, that's

/* matrix_multiply (destination, left_multiplicand, right_multiplicand) */

for each time slice do
    if camera has moved then
        matrix_multiply ( N, J, C);
        matrix_multiply ( N, S, N);
    endif

    for q an object do
        matrix_multiply( M, N, O[q]);
        for p a point in object q do
            matrix_by_vector_multiply( V, M, U[q][p]);
            do something with  ( V[0]/V[1], V[2]/V[1] );
        endfor
    endfor
endfor

In truth, the matrix_by_vector_multiply wastes a bit of time, if you're
trying to tune the code, it'd be worth tuning it.  Normally, it does
this:

V0 = M00*U0 + M01*U1 + M02*U2 + M03*U3;
V1 = M10*U0 + M11*U1 + M12*U2 + M13*U3;
V2 = M20*U0 + M21*U1 + M22*U2 + M23*U3;
V3 = M30*U0 + M31*U1 + M32*U2 + M33*U3;

However, we know that the bottom row is never used, since V3 is always
1; furthermore, we know that U3 is 1, so we can just do

V0 = M00*U0 + M01*U1 + M02*U2 + M03;
V1 = M10*U0 + M11*U1 + M12*U2 + M13;
V2 = M20*U0 + M21*U1 + M22*U2 + M23;

This uses nine multiplies and nine adds, plus the two divides required
to calculate the screen coordinate.  I believe this is the minimum
possible for arbitrary 3D graphics.  (You can turn the two divides into
one divide and two multiplies by calculating 1/Vy and multiplying by
that, which may be a win on some machines.)