Jump Over Left Menu
A List Processing System for Effectively Storing Computer Animated Pictures
Sherwood E. Anderson, Syracuse University
The Efficient coding and identification of pictures in a computer animation program are of cardinal importance for the ease and economy of producing films. Consequently, a list processing technique was implemented in the movie language developed at Syracuse University. To save core storage, pictures are stored in variable length stacks. To allow a flexible picture specification system, subgroups of the stack, called arrays, are set up sequentially within the stack by the program user. Thereafter, either a specific array, or the entire stack may be manipulated by a single command. This allows one stack to hold a stationary background, another a moving figure, etc. Film clips generated by this technique will be shown.
This project was supported by Air Force Contract AF 30(602)+4283 through the Rome Air Development Center.
Syracuse University is conducting a computer animation project funded by the U.S. Air Force through the Rome Air Development Center. The objective is to develop a movie language for educational films, that is powerful enough to describe complex motions, yet simple enough to be easily learned by a non-programmer. While working on this project, the author wrote four graphic programs on an IBM 360/50. The.development and structure of the system upon which they are based was written up as a master's thesis.(1) The first program produces two-dimensional pictures on a Cal-Comp 565 digital plotter. It was given the acronym CALD (Computer Aided Line Drawings). An extension of CALD, named CAPER (Computer Aided Perspectives), produces perspective views of three dimensional figures. An instruction manual explaining their use was printed as a technical report by the Syracuse University Electrical Engineering Department. (2)
Both CALD and CAPER were adapted to produce 16 mm motion pictures by means of the Stromberg Carlson 4020 microfilm recorder. These programs were named CAMP (Computer Aided Motion Pictures) and CAMPER (Computer Aided Movie Perspectives), respectively. All four programs share the same list processing technique for storage of pictorial information.
DATA STORAGE BY LIST PROCESSING TECHNIQUES
Some earlier computers were designed with a variable word length (the IBM 1401 and 1460, for example). This scheme allows only as much space as is needed for each variable. If a value has a range from zero to nine, for example, only one decimal location is needed; likewise, if a variable is defined which can attain a value of 9,999 or less, then four digits of storage are set aside. For a slight increase in processing time, a very economical allotment of core storage is thereby achieved.
In a typical FORTRAN program, an area is defined to the maximal possible size of its intended use. If large storage areas were reserved for all figures, some memory locations would clearly be wasted when figures requiring fewer points were stored. A circle comprised of 36 line segments, for example, would require much more storage space than a triangle. To eliminate such waste, a list processing scheme was chosen that allows the figures to be loaded consecutively. This is analogous to the variable word length storage allotment mentioned in the paragraph above. The method is generally used to manipulate alpha-numeric symbols in groups called push-down lists. The name push-down alludes to the likeness of a spring loaded retainer of some item like bullets in a magazine; as each new bullet is inserted, it pushes down the rest of the group as an ordered unit. List Processing forms the basis of such programming languages as SLIP(3) or IBM's PL/1.(4)
STRUCTURE OF DATA LISTS
The variable length concept was used to advantage in all of the graphic programs described here. All pictures are constructed from combinations of basic figures (e.g. rectangles, circles, sine waves, etc.) which are set up in response to commands punched on data cards. The relative size and position of each one is fixed by parameters following the commands on the data card. Other figures not in the basic repertoire can be built up by giving the endpoints of the needed lines. Each new addition is placed at the end of a variable length list, called a stack, and each figure within the stack is called an array. The identity of each array is retained, and either a single array, or a whole stack may be handled with a single command. All pictures are thus retained in a three level grouping hierarchy: points, arrays, and the largest category, stacks. Care must be taken to generate the arrays in sequential order; e.g. a circle in stack 1, array 1, a triangle in stack 1, array 2, etc. Once generated, however, arrays can be processed in any order. A second figure can replace an existing figure, provided that it requires the same number of locations.
HEADER CELL DELINEATORS
The only peripheral storage locations used in this scheme are header cells, which precede each array within the stack. These header cells delineate the arrays and discriminate among the three different types of arrays which can be set up:
- a line array whose points are stored as pairs of X-Y co-ordinate sets to be plotted as separate lines; i.e. X1, Y1, X1', Y1', X2, Y2, X2', Y2', ... Xn, Yn, Xn', Yn' would plot n lines.
- a closed curve array, whose points are stored as sequential X-Y co-ordinate sets to be plotted as a continuous line; X1, Y1, X2, Y2, X3, Y3, ... Xn, Yn would connect n points.
- a hybrid array, which contains both of the above types.
A header cell is placed at the beginning of each array to serve as a pictorial data marker. Since data points are given in inches (for both plotted and movie output), the largest allowable co-ordinate is twelve inches or less; i.e. 0 ≤ X ≤ 12.0; 0 ≤ Y ≤ 9.0. A value of 10,000 or over is then easily distinguished from an X or Y value. Five numbers of this magnitude were arbitrarily chosen to serve as data markers. Two of them are header cells to designate array types 1 and 2 above. Two other values are used as sub-header cells to introduce an additional string of data onto the end of an existing array. One final value is used to terminate the data at the end of each stack.
- Header cell= 40,000 indicates the beginning of a line array.
- Header cell= 30,000 indicates the beginning of a closed curve array.
- Sub-header cell = 20,000 indicates the beginning of a line sub-array.
- Sub-header cell = 10,000 indicates the beginning of a closed curve sub-array.
- End-of-stack cell = 50,000 indicates the current end of a stack. At the start of the program run, the first location in each stack is initialized to this value. As new arrays are added, this cell is pushed down to the bottom of the stack.
By means of these five data markers, it is possible to construct a hybrid array, as illustrated below:
40,000., X1, Y1, X1', Y1', X2, Y2, X2', Y2', 10,000., X1, Y1, X2, Y2, X3, Y3, 50,000.
This array would plot first two lines, then connect three points with two straight lines. The end of stack cell indicates that this array is the last one in the stack.
Obviously, when a new array is set up at the end of a stack, an end of stack cell should be placed at the terminal location. However, if an existing array is altered within the stack (e.g. by calling the same command name to draw the same figure in a different position), the next cell will contain the header cell of the following array and should remain intact. To avoid changing this cell, a test is made upon the cell immediately following any new figure. If it is non-zero it must either be the header cell of a previously defined array, or an end of stack cell, neither of which should be altered. If it is zero, it must be the new end of the stack, and should be set equal to 50,000.
IMPLEMENTATION IN FORTRAN
The data storage area itself is a monolithic block dimensioned for 8,000 locations. Normally, each of the eight stacks begins at one more than an integral value of 1,000. The stacks were purposely chosen contiguously, so that an jndexing scheme was possible under FORTRAN to address any location within the block, using only one symbolic name, S. In this manner) S(1) is the beginning of stack 1, S(1,001) is the beginning of stack 2, etc. A valuable outcome of this arrangement is that the user can permit any stack (except 8) to run over into the next higher one(s). Stack 1 for example, can be 8,000 locations long if none of the other stacks are to be used. Stack 8, array 1 contains a 12 by 9 inch bordering frame loaded into it by the program, and is intended to be used as a guideline, showing the movie frame's size. This figure may be erased if it is desired to use stack 8 for another purpose. In addition, stack 7 is loaded with a set of 49 alpha-numeric characters, any of which can be transferred to provide lettering for a picture.
Because of the variable length of each array, an algorithm is needed for locating the beginning of any array within a stack. This is accomplished in the subroutine HDR by the relation:
I= [(SN - 1) * 1000] + K
where SN is the stack number, and K is the number of locations counted down from the top of this stack to the header cell of the array in question. This value of the subscript, I, is passed back to the calling subroutine, which begins processing the data at location S(I).
The four graphic programs each consist of a main program and a series of subroutines. Each data card calls a pre-compiled subroutine for a specific task such as generating, rotating, or plotting a figure. The glossary of commands actually forms a graphic language which eliminates what Kulsrud terms the meta compiler phase.(5) The main program merely monitors command loops and channels control to the proper subroutine.
EXTRACTION OF POINTS FOR PROCESSING
Once the stacks are set up, they must be accessible for processing. The flow chart for the plotting subroutine is given in Fig. l. The stack and array numbers are represented by STK and ARRY, respectively. The subroutine HDR uses these values to find I, the subscript of the variable S(I) that points to the top of array ARRY. The function PLOT(X, Y, IP) moves the plotter pen (or CRT light beam) to the point (X, Y). If IP= 2, the pen is down (light beam on); if IP= 3, the pen is up (light beam blanked). Since IP is initialized to 3, the first point of an array is reached in the DRAW INHIBIT mode.
For a closed curve array (header cell = 10,000 or 30,000), LC is set to zero and the pen stays down until the end of the array. However, for a line array (header cell= 20,000 or 40,000), LC becomes non-zero, and IP acts as a flip-flop between 2 and 3, which raises and lowers the pen for each new point. IST tests for a new header or sub-header cell.
AN EXAMPLE WITH TWO STACKS
To illustrate an effective use of the stacks, suppose a jackknife is to be shown, first opening up, then sliding off screen to the right (see Fig. 2 for selected views). The data cards that generated this sequence are listed in Fig. 3. The handle, which consists of two rectangles and two semicircles, is loaded into stack 3. The blade, which includes a triangular thumbslot, is placed in stack 2. The handle is simply drawn each time, but the blade is drawn with a rectangular inhibit mask (MDRAW command) over the handle as it opens. In the last phase, both stacks are offset to the right and drawn with the border serving as a rectangular window (WDRAW command). The economy of the stack system should be apparent. Only one command is required to rotate the whole blade, and another to draw selected parts of it.
EXTENSION TO 3-D FIGURES
A much more complex object is shown in perspective in Fig. 4. This might be entitled Self Portrait of a Mechanical Artist; The CAPER/ CAMPER data storage system was an extension of the planar programs with the addition of appropriate projection formulae.(6) A third co-ordinate for each point had to be introduced, but all other aspects of the programs are similar to CALD and CAMP.
Since a movie clip was to be made of this scene, the pictorial grouping was carefully planned. The cabinet and knobs of the plotter were loaded into stacks 1 and 2; the pen assembly into stack 3; the sprocket holes into stack 4; and the graph being plotted into stack 5. It was then relatively easy to program the pen to traverse axially as the sprocket holes revolved, and the graph rolled around the plotting drum.
This straight forward data storing technique has proved to be very effective for the creation of computer animated movies. It allows an unusual facility for creating and manipulating pictorial data under FORTRAN, and could serve handily in an on-line inter-active display system.
1. Anderson, S.E., "A Graphical Programming Language for Computer Generation of Incremental Plots and Animated Motion Pictures", Master's Thesis, Syracuse University, 1968.
'Anderson, S.E., C.A.L.D. and C.A.P.E.R. Instruction Manuals, TechReport TR-67-6, Syracuse University Electrical Engineering Dept., Syracuse, New York, 1967.
3. Weizenbaum, J., "Symmetric List Processor", Communications of the ACM, Vol. 6, No. 9, Sept. 1963, pp. 524-536.
4. PL/1: Language Specifications, Form C26-6571-2, IBM Programming Systems Publications, Poughkeepsie, N.Y. Jan. 1966.
5. Kulsrud, H.E., "A General Purpose Graphic Language", Communications of the ACM, Vol. 11, Number 4, April, 1968, pp. 247-254.
6. Noll, A.M., "Stereographic Projections by Digital Computer", Computers and Automation, Nov. 1965, pp. 20-23.
C DATA CARDS FOR C CAMP JACKNIFE MOVIE ERASE2 0 CLEAR STACKS 2,3, 4 ERASE3 0 ERASE4 0 C STACK2 WILL CONTAIN C THE BLADE C STACK3 WILL CONTAIN C THE HANDLE C STACK4 WILL BE USED C FOR WORK SPACE SETCV2 1 3.2 4.0 5.4 4.0 BLADE EXPAR2 1 5.3 4.27 5.14 4.48 EXPAR2 1 4.8 4.6 3.2 4.6 TRNGL2 2 4.4 4.1 .5 .08 THUMB SLOT CIRCL4 1 1. 4.3 .3 SET UP TEMP.CIRCLE ROTAT4 1 1. 4.3 90. TNSFR3 1 1. 19. 4. 1. TRANSFER CIRCLE LEFT C HALF INTO STACK 3 RECT 3 2 1. 4. 2.2 .6 RECT 3 3 2.4 4.2 .6 .2 TNSFR3 4 19. 37. 4. 1. TRANSFER CIRCLE RGHT C HALF INTO STACK 3 OFSET3 4 2.2 0. OFFSET RIGHT HALF OFSET2 0 2.8 OFFSET WHOLE KNIFE OFSET3 0 2.8 TO THE RIGHT SIZE 2 0 6. 4.3 1.8 1.8 INCRSE.SIZE OF SIZE 3 0 6. 4.3 1.8 1.8 WHOLE KNIFE ROTAT2 0 6. 4.3 180. CLOSE BLADE TO START SAVE SAVE COMMANDS IN C SC4020 FORM DRAW 3 0 DRAW HANDLE ALONE FRAME ADVANCE FILM ESAVE REPET 24. REPEAT FOR 24 FRAMES DO 90. BEGIN ROTATE LOOP ROTAT2 0 6. 4.3 -2. ROTATE BLADE MDRAW2 0 2. 6.01 3.76 4.85 DRAW BLADE WITH MASK DRAW 3 0 DRAW HANDLE FRAME ADVANCE FILM LOOP END ROTATE LOOP DO 44. BEGIN OFFSET LOOP OFSET2 0 .25 OFFSET BLADE OFSET3 0 .25 OFFSET HANDLE WDRAW2 0 0. 12. 0. 9. DRAW BLADE IN WINDOW WDRAW3 0 0. 12. 0. 9. DRAW HANDL IN WINDOW FRAME ADVANCE FILM LOOP END OF OFFSET LOOP STOP