From: jpc@tauon.ph.unimelb.edu.au (John Costella)
Newsgroups: sci.virtual-worlds
Subject: SOFTWARE: Galcube--galilean antialiased cube
Date: 15 Nov 92 04:43:23 GMT
Article-I.D.: u.1992Nov16.030624.21708
Organization: University of Washington
Originator: hlab@stein.u.washington.edu



/------------------------------------------------------------------------\
|                                                                        |
|                       Announcing the release of                        |
|              / \                                     / \               |
|             |\ /|           G A L C U B E           |\ /|              |
|              \|/                                     \|/               |
|                                                                        |
|    a proof-of-concept software simulation of Galilean antialiasing     |
|                                                                        |
|                                                                        |
|                  Copyright (C) 1992 John P. Costella                   |
|             School of Physics, The University of Melbourne             |
|                                                                        |
\------------------------------------------------------------------------/

Overview
======== 
   GALCUBE is a program written by the author, for IBM PCs and compat-
ibles, that simulates in detail the methods propounded in the recent 
paper "Galilean Antialiasing for Virtual Reality Displays".


Description
===========  
   To verify that the technique of Galilean antialiasing, as outlined 
in the abovementioned paper, is indeed practically feasible, the author 
has written a simple program, GALCUBE, that simulates in detail all of
the operations that would be carried out by display hardware equipped 
with minimal G^(2) antialiasing.

   GALCUBE pre-computes a number of frames of view of a 3-D cube, ro-
tating at a rate of one-quarter of a revolution per second, against a
stark black background, that would be shown by a minimal G^(2) display 
device, for a given shading model and frames-per-update speed. These 
pre-computed images are stored in RAM and blitted onto the screen at a 
rate of 25 frames per second, using the standard MS C blitter, to show 
what would actually be seen by a viewer of a 25 frame-per-second G^(2) 
display device showing such a scene; the equivalent display for a 
conventional G^(0) device, for the same update rate, can be toggled in 
or out, for a direct comparison. Unfortunately, however, the use of 
Galilean antialiasing for the gross *translational* motion of the cube
---which is the most effective aspect of the technique---could not be 
implemented, due to the hardware limitations of the IBM PC, which was 
used as a lowest common denominator platform.

   The GALCUBE program itself has not been optimised for speed; it is 
simply a proof-of-concept tool. The size of the cube is, on fast 
machines, about 80 by 80 pixels on the VGA 640x480 16-colour display 
mode; this is reduced on machines that are not fast enough to blt such 
images (using the MS C blitter) at a rate of 25 frames per second. The 
cube is rendered in one of several simple shading models, selectable 
from the command line; the frames-per-update speed is also selectable. 
 
   GALCUBE computes update frames using an unoptimised and simplistic 
scan-converter written for this purpose, the output of which would
resemble closely the output of a practical (but highly optimised) poly-
gonal G^(2) scan-converter. Between update frames, GALCUBE propagates 
the Galilean image from frame to frame using the methods outlined in 
sections 2 and 3 of the abovementioned paper. The propagation compu-
tations simulate (in software) *EXACTLY* the computations that would 
be carried out in the hardware devices, including the full effects of: 
finite arithmetic; truncation of fractional bits, for storage purposes; 
finite evaluation of the Poisson test; 1-, 2- or 4-way averaging in 
the expansion algorithm when dictated by the results of the Poisson 
test; propagation of both debris and galpixels from frame to frame. 
Each galpixel in the image is rated for N_{prop} = 16 frames propagation 
time; the x- and y-components of motional and fractional positional 
information are stored in 32 bits each; the z-buffer is 8 bits wide; 
the motional and fractional positional information of the z-component 
is stored in 16 bits; and the grey-scale value, fractional value and 
derivative is stored in 8 bits; totalling 96 bits, or twelve bytes, 
for each pixel.

   It should be noted that the author has improved on the "G^(2), then
G^(0) fallback" debris-generation algorithm outlined in the above-
mentioned paper; the new algorithm is---unlike the old---invariant 
under Galilean transformations (as well as under accelerative trans-
formations); it works by simply retarding galpixels by a single frame, 
marking them as debris, and then overdrawing the propagated galpixmap; 
debris is now capable of being propagated from frame to frame. This 
removes the last remnants of the G^(0) display philosophy (which is, 
of course, non-invariant under Galilean transformations); it means that 
the treatment of unobscuration depends *only* on the *relative* vel-
ocities and accelerations of the obscurer and obscuree, and not the 
apparent "absolute" motion of these objects with respect to the display 
device. This new algorithm, which may be described in more detail in
Sci.Virtual-Worlds shortly, is both implemented and documented in the 
GALCUBE source code (yet to be released).

   On the other hand, the further enhancements outlined in section 4 
of the abovementioned paper are *not* implemented in GALCUBE; these 
would be more amenable to testing once actual hardware implementations
of the minimal system described in sections 2 and 3 become available.
Thus, the simulation provided by GALCUBE represents only a very
*simplistic* demonstration of the minimal capabilities of G^(2) anti-
aliasing. The use of a rotating object, without translational motion, 
further stresses the algorithm maximally, since successive views of 
faces are continually being presented; more realistic practical 
scenarios, where motion of the displayed scene is due primarily to 
the motion of the participant (rather than the objects themselves), 
would look much better than the results shown by GALCUBE.

   In all this, it must be borne in mind that GALCUBE is only a very
primitive attempt by the author to demonstrate proof-of-concept of
Galilean antialiasing by software simulation. It was not originally 
intended that GALCUBE be released for public scrutiny; the rather sim-
plistic and unsophisticated programming behind it reveals these original 
intentions; but nevertheless it may be useful to VR G^(2) display de-
signers as a first crude step---who, it is hoped, will overlook the 
sloppiness of the programming itself.


System Requirements
===================
GALCUBE has the following system requirements:
   - an IBM PC, PS/1, PS/2, or compatible machine
   - a version of the MS-DOS or PC-DOS operating system; or, failing that,
       MS-OS/2 or IBM-OS/2 version 1.1 or later, or Windows NT or later
   - a VGA or higher graphics adapter
   - a monochrome or colour VGA-compatible monitor (GALCUBE only runs
       in 16-grey-shade mode, regardless of monitor type)
   - 640 kB of conventional RAM

The following specifications are not required, but ARE desirable:
   - "real" MS-DOS or PC-DOS, rather than a DOS box under Windows 3.x,
       Windows NT, or OS/2
   - MS-DOS 5.0, loaded high, with device drivers also loaded high
   - a machine clock speed of at least 16 MHz
   - at least an 80386SX processor          
   - an 80x87 maths coprocessor, for 8088, 80286 or 80386 machines
               
The following hardware and software is NOT used by GALCUBE:
   - a mouse
   - extended or expanded memory
   - Microsoft Windows
   - Super-VGA or XGA capabilities
 

Instructions for Use
====================
   GALCUBE is supplied in the following posting, in UUENCODEd and PKZIPped
format. The following procedure should be used to extract GALCUBE:

   (1) Save the following posting to a file.

   (2) Strip any mail- or Usenet-header from the start of the file, with
       a text editor.

   (3) UUDECODE the text file; the binary file galcube.zip should result.

   (4) PKUNZIP the binary file; this should yield GALCUBE.EXE. A suitable
       version of PKUNZIP is available from the Sci.Virtual-Worlds
       anonymous-ftp archive site, and which at the time of this document
       was located in the cheap-vr directory.

   (5) Transfer GALCUBE.EXE to a machine satisfying the requirements
       listed above.

   (6) Ensure that the machine is completely BACKED UP to secure 
       media. While GALCUBE has been tested extensively on the author's
       and a few other machines, Murphy's Law says that it must fail on 
       someone's machine, somewhere, some time; while such a failure is 
       unlikely to corrupt files, such a possibility can never be ruled 
       out.

   (7) Boot DOS. For best results, do NOT run GALCUBE from a multitasked 
       DOS session under Microsoft Windows or under OS/2; the program is
       timing-dependent; its unoptimised form makes it a cycle hog. 

       If, however, due to factors beyond your control, it is NOT 
       possible to run pure DOS, then do the following:

          - Under Microsoft Windows 3.0 or 3.1, in Standard Mode: 
              (i) Only use a full-screen DOS session to run GALCUBE.

          - Under Microsoft Windows 3.0 or 3.1, in 386 Enhanced Mode:    
              (i) Close as many background programs as possible.
             (ii) Only use a full-screen DOS session to run GALCUBE.
            (iii) Set the Exclusive check box in the Settings for the
                    DOS session that is used.
                    
          - Under Microsoft Windows NT (still currently in beta):
              (i) Optimise the DOS session following the general
                    guidelines listed for OS/2 versions 1.x and 2.x

          - Under MS-OS/2 or IBM-OS/2 versions 1.1, 1.2 or 1.3:
              (i) Close as many background programs as possible. 
             (ii) Run GALCUBE from the DOS box.

          - Under IBM-OS/2 version 2.0 or higher:
              (i) Close as many background programs as possible.  
             (ii) Only use a full-screen DOS session to run GALCUBE. 
            (iii) Edit the DOS Settings for the program object to
                    maximise the speed of the session (in the same way
                    as is done for DOS-based games).

       Note that processor focus should NOT be switched away from
       GALCUBE while the message "Testing machine animation speed..."
       is being displayed; however, focus CAN be switched away while
       frames are being computed, or while the rotating cube is being
       shown, if necessary.

   (8) Run the program GALCUBE.EXE, with the command line arguments 
       listed below. NOTE: No other files are required for GALCUBE to 
       run; therefore, it is *not* necessary to first CD to the directory 
       that GALCUBE.EXE resides in, nor to include that directory in 
       the PATH environment variable.

   (9) To quit the program during the pre-computation of frames, press
       CTRL-Q; this may take up to one frame's worth of computation to
       be recognised.

  (10) To toggle between the normal G^(0) (sample-and-hold) simulated
       display mode, and the Galilean G^(2) antialiased mode, while the
       rotating cube is being shown, press the spacebar.

  (11) To quit the program while the rotating cube is being shown, press
       the ESC key.


Command-Line Arguments
======================
GALCUBE.EXE should be invoked from the command line as follows:

galcube <frames-per-update> <shading-model>

The arguments are described below; examples will follow:

<frames-per-update>: An integral number between 1 and 25, specifying
                     how many frames it takes for the (simulated)
                     display processor to generate a new update.
                     In between these exactly-computed frames, GALCUBE 
                     emulates exactly the G^(2) Galilean propagation 
                     algorithm that would be applied by a minimal
                     hardware G^(2) video controller, to compute 
                     intermediate frames. (When showing the "normal" 
                     simulated display, only the exactly-computed 
                     updates are displayed, for <frames-per-update> 
                     successive frame periods each.)

<shading-model>:     The shading model used by GALCUBE. The following 
                     shading models are currently supported:

                 w   Wireframe: The cube is drawn in wireframe only, with
                       rear edges removed.

                 a   Ambient: Each face of the cube is shaded with the
                       same constant shade of grey. To delineate edges, 
                       the wireframe rendering of model w above has 
                       also been added, in a slightly brighter shade 
                       of grey. This mix-and-match of shading models 
                       is for illustrative purposes only, and intro-
                       duces artifacts; the diffuse model below should 
                       be used as a better guide.

                 d   Diffuse: Each face of the cube is shaded with a 
                       shade of grey which is flat, but which depends 
                       on the orientation of the face with respect 
                       to a light source at infinity. The light source 
                       direction passes through a point to the right 
                       of the viewer; a small amount of ambient light
                       is added to reduce the starkness of receding
                       faces that are facing away from the light 
                       source. GALCUBE assumes that one bit of frac-
                       tional grey scale is added to the four bits 
                       displayable, and that two integral bits plus 
                       one fractional bit are allocated to storing 
                       the first derivative of the grey level; this 
                       is used for temporal convective antialiasing 
                       of the grey level. Second derivatives are not 
                       computed in the current version of GALCUBE.


Sample Invokations of GALCUBE
=============================
The following examples illustrate how to run GALCUBE from the command
line, as well as providing a rough "guide" to the features of the
demonstrations that are of note. 

Command line      Effect
------------      ------
galcube 4 w       Runs GALCUBE, in wireframe mode, computing every
                  fourth frame as an update (exactly), and then
                  Galileanly propagating for the next three frames. 
                  The "normal" mode display shows the cube with an
                  inter-update time of 160 milliseconds (i.e. 4/25
                  of a second). Note that it is difficult, with this
                  "non-immersive" demo, to get an idea for the
                  *latency* in the "normal" display; i.e., it is up
                  to 160 ms "behind the play" at any one time. 
                  However, sometimes, when one toggles (via the
                  spacebar) between the two displays, the "normal"
                  display actually jumps *backwards*. This is *not*
                  a program error: it reflects the fact that the
                  sample-and-hold display can have bad latency 
                  problems. The Galilean-antialiased display, on the
                  other hand, *extrapolates* the motion (*not* inter-
                  polation) using velocity and acceleration infor-
                  mation, and is thus not delayed.

GalCube 6 Wire    As above, but with an inter-update time of 6/25 of 
                  a second, or 240 milliseconds; only one frame in
                  every six is actually computed, the other five being
                  derived by the (simulated) video controller using
                  Galilean antialiasing. Note that capitalisation of
                  the command line is irrelevant, and shading-model
                  parameters are checked for their first letter only.

galcube 12 w      As above, but now the inter-update time is 480 ms,
                  or one-eighth of a revolution (one revolution occurs
                  roughly every four seconds; here it is rounded off
                  to 8 x 480 ms = 3.84 s to allow a continuous-play of
                  the pre-computed frames). Note that, at this low an
                  update rate, the "normal" display is completely
                  ambiguous: it is not possible to tell whether the 
                  cube is rotating clockwise or counterclockwise; it
                  is also delayed by up to half a second, although this
                  is not obvious from this non-immersive demo. The
                  antialiased display is still holding up well.

galcube 24 w      As above, but now propagating over a 90 degree
                  rotation of the cube. The "normal" display doesn't
                  rotate at all, since the symmetry of the cube means
                  it is always "seen" in an equivalent orientation.
                  The antialiased display is still moving; but it is, 
                  however, "falling apart", as described in the above-
                  mentioned paper; this is an inherent property of 
                  rotating objects: their "use-by date" is about 45 
                  degrees of rotation (i.e. the example above). The
                  one-second inter-update time is, of course, much
                  longer than is praticable for a minimal global-update
                  system in any case.

galcube 1 a       Ambient shading model used, as described earlier,
                  with every frame computed exactly. Note that when 
                  <frames-per-update> equals 1, the two toggleable 
                  modes of view are identical; no Galilean anti-
                  aliasing is performed. The edges are equivalent to
                  the above wireframe display, added to make the faces
                  delineable. A better shading model is given below.

galcube 4 a       As above, but now using an inter-update time of 
                  160 ms. Note that the added wireframe edges of 
                  this shading model cause some "smudging" on the 
                  emerging ("critical") face; the methods of section
                  4 would remove this problem. The "Enterprise effect"
                  of the corners are the result of unobscuration of
                  the background; with unobscuration caching (section
                  4), this effect would also be removed. In this 
                  simplistic demo, the rotating nature of the cube 
                  lays a lot more of this "debris" than would be 
                  encountered, most of the time, in most real-life 
                  situations. 

galcube 8 a       As above, but now increasing the inter-update time
                  to 320 ms. Note that build-up of debris, for this
                  rotating case, is quite noticeable on a black 
                  background; apart from this, however, the cube 
                  itself is propagating well. In practice, the effects 
                  of (i) non-stark backgrounds, and (ii) less critical 
                  motion of objects (i.e. due mainly to viewer motion,
                  rather than rapid intrinsic rotation) will reduce 
                  the amount of noticeable debris. To properly deal 
                  with an inter-update time of 320 ms, however, the
                  methods of section 4 should really be employed.

galcube 1 d       Diffuse shading model used, as described earlier,
                  with every frame computed; this is the *BEST* that
                  GALCUBE can do with this model, even without in-
                  voking Galilean antialiasing at all. Note that there
                  are two sources of "flickering": Firstly, the low
                  number of grey-shades (16) means that some colour 
                  "jumps" are visible. Secondly, the lack of syn-
                  chronisation between the blitter and the video
                  adapter leads to occasional visible horizontal 
                  lines appearing out of nowhere, on most displays.
                  Note that these are artifacts of GALCUBE; ignore
                  their presence in the following.

galcube 6 d       Diffuse model, as above, but now with an inter-
                  update time of 240 ms. The "normal" display is
                  almost ambiguous, and is (in reality) delayed.
                  The antialiased displayed cube's *motion* is quite
                  clear, and it is not delayed; however, the quality 
                  of the image cannot, of course, be perfect. The 
                  debris comments of the above also hold true here; 
                  with unobscuration caching, the edges would not 
                  "smudge". There are, however, further causes of
                  image degradation. Note that the "critical" emerging 
                  face is shaded more-or-less reasonably, but with 
                  some blotchiness due to the low information content 
                  of the original rendered update for this face. 
                  However, these "blotches" increase in brightness
                  along with the rest of the face, and are gradually
                  averaged out during the propagation procedure.
                  Likewise, all faces of the cube have "shading 
                  inertia": they continue to change shade between
                  updates; this smoothness is a marked improvement 
                  over the "normal" display, which jumps and flashes
                  quite badly. The G^(2) display would be much smoother 
                  again if it were not for the very limiting 16-colour 
                  VGA mode being used, and if correspondingly more bits 
                  were allocated to storing colour derivatives. This
                  "quantisation error" is, in fact, responsible for the
                  occasional vertical lines in faces that have a slightly
                  different shade to the face; this would not occur
                  if greater colour resolution were used.

galcube 12 d      As above, but now lengthening the inter-update time 
                  to 480 ms. The antialiased display is still holding 
                  up reasonably well; the "normal" display is again 
                  ambiguous. The "Enterprise effect" for debris is
                  now the most noticeable effect; unobscuration caching
                  would remove it.

galcube 24 d      Ditto, with an inter-update time of 960 ms. Again, 
                  the cube falls apart; it is past its use-by date.
                  The "normal" display is useless (fully ambiguous).

galcube 3 d       We have returned to an inter-update time of 120 ms.
                  This corresponds to an update rate of 8.3 hertz.
                  If this were hardware-implemented on a system with
                  a frame rate of 83 Hz (and better shading capabil-
                  ities), then an order of magnitude improvement will
                  have been achieved, even for this small propagation
                  time. It should be noted that the "normal" display
                  at 8.3 updates per second would look much worse were
                  it to be linked to a head-position device (as would
                  be obvious to anyone with experience with a 8.3 Hz
                  VR system), since the gross motion of the cube as a
                  whole would also be jumpy, and would be delayed by
                  an average of 60 ms.

The reader is invited to play further with the command-line arguments
and see the effect that they have on the simulation; and to develop
more sophisticated software simulations that are closer to the real
requirements of a VR system. Due to the nature of Galilean antialiasing,
it is, in practice, essentially ephemeral; for this reason, software 
simulations, and frame-by-frame "browsing" capabilities, will remain a 
feature of development in this area, *even after* hardware implement-
ations come into general use. A much more sophisticated set of utilities
is therefore clearly required. The author, however, must leave the
development of these utilities to the designers of hardware implemen-
tations, who will tune the software to their own needs and goals.
                 

Acknowledgments, Disclaimer and Copyright Requirements
======================================================
Helpful discussions with D. Stampe, R. E. Behrend and A. R. Petty 
are gratefully acknowledged. This work was supported in part by an
Australian Postgraduate Research Allowance, provided by the 
Australian Commonwealth Government.

IBM, PS/1, PS/2 and OS/2 are registered trademarks of International 
Business Machines Corporation.                   

Windows and NT are trademarks, and Microsoft and MS-DOS are registered 
trademarks, of Microsoft Corporation.

386 and 387 are trademarks of Intel Corporation.

DISCLAIMER: This software is provided AS IS; no responsibility 
            is taken by the author for any damage, either direct 
            or consequential, caused by its use. Use of the 
            software on any computer is undertaken at the risk 
            of the user; if this is unacceptable, all copies of 
            the software should be erased. While every attempt 
            has been made to ensure the accuracy of this document, 
            no legal responsibility is taken by the author for 
            any errors, typographical or otherwise, contained 
            herein.

Copyright (C) 1992 John P. Costella. Copyright to both this document,
and the accompanying software, is retained by the author. However,
permission is hereby given for the unlimited duplication of both
this document and the accompanying software ONLY for the purposes of
research or development, provided that both are copied in their
entirety, and unmodified in any way. Neither this document, nor the 
accompanying software, may be included in any commercial package; nor 
can they be sold for commercial profit. 

The document "Galilean Antialiasing for Virtual Reality Displays"
was e-published in LaTeX form in Usenet Sci.Virtual-Worlds on 
4 November 1992, and may be retrieved, in LaTeX, DVI or PostScript 
format, from the archives of the newsgroup. The document was also 
issued, in paper form, as a University of Melbourne School of Physics 
preprint, number UM-P-92/105, on 28 October 1992; as a last resort, 
a paper copy of the preprint may be requested by post, either from 
the author, at the address listed below, or from the Physics Branch 
Library of the University of Melbourne.

Queries and suggestions are welcome, and should be directed to the
author; preferably to the e-mail address jpc@tauon.ph.unimelb.edu.au;
or, failing that, via post, to the following street address:

John Costella, 
Particle Theory Group,
School of Physics,
The University of Melbourne,
Parkville, Victoria 3052,
AUSTRALIA.

Printed in Australia on acid-free unbleached recycled virtual paper.