NetNews Usenet Archive 1992 #27

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / virtual / 3692 < prev next >

Wrap

Internet Message Format | 1992-11-15 | 27.5 KB

Path: sparky!uunet!ogicse!news.u.washington.edu!stein.u.washington.edu!hlab From: jpc@tauon.ph.unimelb.edu.au (John Costella) Newsgroups: sci.virtual-worlds Subject: SOFTWARE: Galcube--galilean antialiased cube Message-ID: <1992Nov16.030624.21708@u.washington.edu> Date: 15 Nov 92 04:43:23 GMT Article-I.D.: u.1992Nov16.030624.21708 Sender: news@u.washington.edu (USENET News System) Organization: University of Washington Lines: 505 Approved: cyberoid@milton.u.washington.edu 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.