CA1206260A - Image processing system - Google Patents

Abstract

ABSTRACT OF THE DISCLOSURE

The disclosure relates to a computer controlled imaging system involving a digital image processing and display system which hasthe abilitytocompose and construct a display scene from a library of images with sufficient processing speed to permit real-time or near real time analysis of the images by a human operator or a hardware/software equivalent thereof. An unique method of mapping a digital input image to a viewing plane in both linear and perspective modes is disclosed.

Description

IMAGE PROCESSING SYSTEM
BACKGROUND OF THE INVENTIO~
Field of the Invention The in~ention relates generally to a computer controlled imaging system and, more particul~rly, to a digital image processing system which has the ability to compo~e and construct a sequential stream of scenes for a display from a library of images with sufficient processing speed to permit r~al-time or near real time analysis of the images ~y a human operator or~a hardwarejsoftware equivalent thereo.
One ex~mple of the many possible applications of such a system relates to the field of vehicle simulation such as aircraft flight simulation. In such a system a visual su~sy~tem within the aircraft flight simulation system receives flight data from a fligh~ simulationcomputer and terrain data from a defined or "gaming area" data base. A data processing system within the visual simulation system organizes the flight data and terrain data to produce a simulated visual display as i~ would appear to an observer in the cockpit of the aircraft.
The visual system of a vehicle simulator which may be, for example, a helicopter simulator, involves a "window view of the simulated surroundings'i and controls for guiding the "vehicle" in any desired dixection relativ~
to such surroundings. The term "window view" of the system herein i~ a display, normally in video ~orm, of a simulated environment which corr~ pond~ to a terrain covering a large area which m~y be on the order of 25 to lOO square miles, ~.

for example. The simulated environment is referred to herein as a defined area or gaming area.
The operation of the controls of the vehicle guides the vehicle in, around and through th0 gaming area and it is the system response to the vehicle controls which determines what is seen in the window, that is, the video display. What is seen in the "window" is referred to as the field of view or FOYo DESCRIPTIO~ OF THE PRIOR ART
One system in the prior art known as "Computer Generated Imagery" 5CGI) system utilizes a computer system to generate video displayable imagery from a data base.
In the CGI system objects and suraces for constructing video displ ayabl e scene arederived from purelymathematical models stored in the form of points whi~h define the lLmits of the objects and surfaces.
The strength of CGI is in its surface rep-resentation~ A real or artificial surface can be measured to get elevations at specified points, usually at intersections of a uniform grid. The surface can be reconstructed in a computer by connecting sample elevations.
In addi~ion to realistic !3urface representation, CGI offers control over the placement of objects on the surfac~.
5ince the data of elevations is usually provided with a uniform grid, the placement of other objectscan be specified on this same grid. Typical o~jects such as trees, rocks, shrubs, houses and roads can all have their positions defined in the data base grid system.
Correct illumînation and pPrspective are also major contribu~ions from CGI. Correct illumination is achieved by finding the surface normal for each pixel ~12~Ei~

displayed. This normal is used along with line-of-sight and the normal from ~he illumination source, plus an ~mbient intensity and haze factors, to compute an intensity for a pixel. Correct perspectivP is achieved because the distance from the observation point t.o each s~rface point is known.
This distance is a significant variable in the perspective transformation.
A weakness of CGI is lack of realism. Although an object can be accurately po~itioned, correctly ill~minated and displayed in correct perspective, the object it~elf cannot be realistically presented. The current state of the art in CGI object presentation is such that objects appear overly cartoonish. Some scene elements, such as barren terrain, sand and clouds can be represented more realistically than highly structured objects like trees and grass or detailed man-made ob~ects. ~uchdetailed objects simply lack reali.sm.
Another imaginsl system is conveniently referred to as "Computer Synthesized Imagery" or CSI. The CSI
technology also generates images such as, for example video displayable images, from a data base ~ut ~he objects and surfaces stored n its data base are represented a~
real-world electromagnetic media images of objects and surfaces rather than mathematical moaels thereof as in CGI.
Thus, whereas CGI uses a oo~puter to generate imagery from a purely mathematical data base, CSI uses a computer to ~ objects ~ a scene based on stored real-world images. Although CGI provides excellent control of a scenP to be constructed and displayed for interaction in an environment, the fidelity is l~w and thus realism in the displayed scene is poor~ C5I is ~us~ the opposite.

. 4 Whereas fideli~y is excellent, the control over scene construction is restrict.edO
The st~ength of CSI lies in its use of real images such as photographs in the scenes. With currently available video equipment the photographic data can be readily manipulated. Literally thousands of individual photographs can be stored on video disks, and access to them may be controlled by an indexing system just as is the case with digital data stored on magnetic disks.
Moreov~r, the fid~lity of the image is true and the outputted image is precisely the same as thP inputted, stored image.
A weakness of CSI is that its scenes are limited to the view point of the "camera". That is, one cannot d~amically navigate a scene unless a series of through-the-scene photographs i5 used. For any reasonable size gaming area, the number of through-the-scene pho-tographs may be prohibitive~
UMMARY OF T~E lNVEN~IO~
By means of the present in~ention the CGI system

2~ has been merged with newly developed CSI technology to form a "Ccmputer Generated Synthesized Imagery" system which is referred to herein as a CGSI sys~em, The inYention herein involves combining the be~t of both technologies, CGI and CSI, to form CGSI~ A scen~ is constructed by placing individual, normally detailed, objects with high fidellty ~CSI) on a specified surfac0 or background which may be CGI or CSI generated. A CGSI scene may beconstructed much in the m2nner of a CGI scene with the surface elevations and object locations laid out on a uniform grid. The indivldual objects used in ~he scene are ~ailored for perspec~ive, location and ~ransformation including size~
~4~ ~Y~ rotation, warp and intensity ar performed on P~ v ~

each image as required. The surface may be CGI textured or a series of CSI surface inserts. The scene is normally constructed by beginning with the objects most remote from the observation or scene recognition means and placing objects un-til the nearest objects have been placed. The CGSI scene may be constructed with imagery from any portion of the electromagnetic spectrum including visual, IR, MMW, radar, or the like.
~ n accordance with the present invention, there is provided a method of mapping in a 3D coordinate system of 2D
input images of views of objects stored in a data base to output images in a moveable rectangular viewing plane having a rectangu-lar column and row pixel matrix, said sy~tem having a main axis extending normal to said viewing plane and having a viewing point thereon in spaced relation to said viewing plane, said method comprising the steps of: representing each of said 2D images as a rectangular matrix of pixel intensity values arranged in columns and rows of pixels and having corner coordinates;
establishing a rectangular pixel matrix of each of said stored 2D images; computing four corner coordinates for an output image in said viewing plane corresponding to said corner coor-dinates of any selected one of said 2D images; making two ortho-gonal passes wherein said first pass is over said input image to form an intermediate image having columns and rows of pixels and corner coordinates determined by said computed four coordi-nate corrlers of said output image, and wherein said second pass is over said intermediate image to form said output image with columns and rows of pixels and corner coordinates determined by said compu-ted four coordinate corners of said output image;

making line transformations in said first pass wherein said input image columns are converted to said intermedia-te image " ~ , - 5a -columns with said intermediate image columns havin~ lengths derived from said input image columns establishing xespective ratios defining the lengths of said input image columns relative -to said intermediate image columns; making line transformations in said second pass wherein said rows of said intermediate image are converted to said output image rows on said viewing screen with said output image rows having lengths derived from said intermediate image rows establishing respective ratios defining the lengths of said intermediate image rows relative to sai.d output image rows; calculating and forming for each of said line transformations from said ratios~ -the number of input pixels required respectively from said columns of said input image and said rows of said intermediate image -to create output pixels respectively for said intermediate image columns and for said final image rows; mapping said input pixels sequentially and fractionally to said output pixels for each of said line transformations; and summing and averaging said intensity values of said input pixels corresponding to ~ach said ou-tpu-t pixel and respectively accruing composite values so obtained to said ZO output pixels~
In accordance with another aspect of the invention, there is provided a method of linearly mapping a rectangular digital input image having columns and rows and corner coordinates, and represented as a pixel matrix of intensity values, to any predetermined quadrilateral having columns and rows and corner coordinates, comprising the steps o~: perform-ing sequentially two orthogonal scanning passes of said input image wherein said first pass forms from said inpu-t image an intermedi.ate image having columns and rows of pixels and corner coordinates and said second pass forms an output image having columns and rows of pixels and corner coordinates from said intermediate i.mage; performing line transformati.ons during said 6~

first pass whereby said columns of said intermediate image correspond to said columns of said input image and have lengths and positions determined from said coordinates of said quadrilateral; performing line transformations during said second pass whereby said rows of said output ima~e correspond to said rows of said intermediate image and have lengths and positions determined from said coordinates of said quadrilateral;
calculating for each of said line transformations (1) the vertical ra-tios of the respective lengths of said columns of said input image relative to said columns of said inte.rmediate image and (2) the horizontal ratios of the respective lengths o~
said rows of said intermediate image relative to said rows of said output image; calculating a pixel ratio for each of said l.ine transformations from said verti.cal and horizontal ratios -to determine respectively, for each of said line transformations, the number of said input image pixe].s required to create said inte.rmediate image pixels and the n~Imber of said intermediate image pixels required to create said output image pixels and calculating, for each o:~ sai~ created intermediate and output pixels, an average intensity value from the intensity values of said input and intermediate pixels respectively; and mapping said input pixels sequentially a.nd fractionally to said inter-mediate pixels and mapping said intermediate pixels sequentially and fractionally to said output pixels for each of said line transformations.
In accordance wi.th a further aspect of the invention, there is provided a method of mapping a digital input image to a viewing plane which is moveable in a 3D coordinate system and wherein said image comprises elements arranged in columns and rows of pixels representing a matrix of pixel intensity values in said system, said system having an o~servation point on a main axis thereof and a viewing plane having a format wi.th ~J

~ 5c -columns and rows extending normal to said axis and spaced from said observation point, said system defining a reference plane parallel to said main axis and extending normal to said viewing plane, comprising the steps of: projecting, sequentially the orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane;
processing each line of said first pass o~ject lines by project-ing divergent lines from said observation point -to said each line of said first pass, object lines through said viewing plane to define an :intermediate image line coincident with said viewing plane having equal line segments of at least one pixel, said divergen-t lines intersecting said each line of said first pass object lines resulting in corresponding line segmen-ts between said divergent lines having respective lengths equal to the number of said pixels separating said divergent lines;
calculating pixel ratios of said line segments o~ each line of sa:id firs-t pass object lines to corresponding line segments of said intermediate image line; mapping said elements of each of said columns of said digital input image sequentially and fractionally to said line segments of a corresponding line of said first pass object lines; projec-ting divergent planes from said observation point through said rows of said viewing plane, said divergent planes having a separation of at least one pixel in said viewing plane, each of said divergent planes intersecting sa.id viewing plane to form a final image line and intersecti.ng said input image to form a second pass object line;
processing each said second pass object line b~ extending second pass divergent li.nes from said observation point through said columns of said viewing plane having a separation of at least one pixel in said viewing plan~ and through said second pass ob~ct line to form segments thereof, said second pass divergent lin.es intersecting said viewing plane to form horizon-tall~

'~

- 5d -extending correctly positioned final image rows with each of said final image rows having segments with lengths proportioned to the number of said pixels of corresponding ones of said segments of said second pass object lines; calculating pixel ratios of said line segments of each line of said second pass object lines to corresponding line segments of said final image row; and mapping pixels to a row of said final image rows sequentially and fractionally from said segmen-ts of a corres-ponding said row of said final image.
In accordance with another aspect of the invention;
there is provided a method of mapping a digital image in a 3D
coordinate system to a viewing plane which is moveable in said system, said system having a viewing point and a main axis extending normal to said viewing plane and through said viewing polnt, said system having a reference plane con-taining said main axis and extending normal to said viewin~ plane, said method being applied to a digital input image arranged in columns and rows and represented as a matri~ of pixel intensity values, said input image being on the opposi.te side of said viewing plane from sai.d viewing point, said method being applicable to map said input image to said viewin~ pl~ne and comprising the steps of. projecting, successively and orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane; processing each of said firs-t pass object lines in sequence by extending radiating rays in said reference plane from said viewing point through said vi.ewing plane and said first pass object line, said radiating rays (1) intersecting said viewing plane to form an intermediate image line with segments each having the length of one pixel and (2) intersecting said first pass object line to form segments; processing said input image rows with respect to - 5e -said first pass object line segments to obtain a pixel ratio for each of said first pass object line segments relative to each corresponding one of said in-termediate image line segments;
mapping said pixels of each of said input columns sequentially and fractionally to said line segments of each corresponding one of said first pass object lines; summing and averaging for each said segment of each of said first pass object lines said intensity values of said pixels mapped thereto to obtain a composite value and applying said composite value to correspond-ing ones of said intermediate image line segments; processingsaid intermediate image by extending radiating planes from said viewing point through said rows of said viewing plane having one pixel separation and through said input image, each of said radiating planes intersecting said input image to form a second pass object line; processing each of said second pass object lines by extending second pass radiaLting rays from said viewing point through said columns of said viewing plane having one pixel separation and through said second pass object line; said second pass radiating rays intersecting said viewing plane to form a horizontally extending correctly positioned final image line witl~ segments each having the length of one pixel and intersectin~ said second pass object line to form segments each having a different length; processing said intermediate image rows with respect to said second pass object line segments to obtain a pixel ratio for each of said second pass object line segments relati.ve to a corresponding one of said final image line segments; mapping said pixels of each of said intermediate image rows sequentially and fractional:Ly -to said line segments of each corresponding one of said second pass object lines;
s~nming and averaging for each said segment oF each of said second pass object lines said intensity values of said pixels ,~

mapped thereto to obtain a composite value corresponding to each of said final image pixels and applying said composite value to corresponding ones of said final image line segments.
In accordance with a further aspect of the invention, there is provided a method of mapping in a 3D coordinate system havi.ng a viewing point on a main axis thereof and a viewing plane extending normal to said axis and spaced from said viewing point, said system having a reference plane containing said main axis and extending normal to said viewing plane, said method bei.ng applied to a digital input image arranged in columns and rows and represented as a matrix of pixel intensity values, said input image extending obliquely relative to at least one of said planes, said method being applicable to map said input image to said viewing plane, and comprising the steps of: projecting, successive]y and orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane; processing each of said first pass object lines in sequence by extending radiating rays in said refer~nce plane from said origin through said viewing plane and said fixst pass object line, said radiating rays (1) intersecting said viewing plane to form an intermediate image line with segments each having the length of one pixel and ~2) intersecting said first pass object line to form segments; processing the total number of said input image rows with respect to said first pass object line segments to obtain a pixel ratio for each of said first pass object line segments relative to a corresponding one of said intermediate image line segments; mapping said pixels of each of said input columns sequentially and fractionally to said line segments of each corresponding one of said first pass object lines; sur~ning and averaging for each segment of each of said first pass obj~ct lines the intensity values of each pixel mapped ~.2~
- 5g -thereto and applying the composite value to corresponding ones of said intermediate image line segments; processing said intermediate image by extending radiating planes from said viewing point through rows of said viewing plane having one pixel separation and through said input image t each of said radiating planes intersecting said viewing plane to form a final image line and in-tersec-ti.ng said input image to form a final image line and intersecting said input image to form a second pass construc-tion line; projecting each of said construction lines to a plane which is normal to said viewing plane and contains said main axis to form second pass object lines; processing each of said second pass object lines by extending second pass radiating rays from said origin through said columns of said vie~7ing plane having one pixel separation and through said second pass object lines, said second pass radiating rays (1) intersecting said ~iewing plane to form a horizontally extending correctly positioned final image line with segments each having the length of one pixel and (2) intersecting said second pass object line to form segments each having a different length; proce~sing said intermediate image rows with respect to said second pass object line segments to obtain a pixel ratio for each of said second pass object line segments relative to a corresponding one of said final imase line segments; mapping said pixels of each of said intermediate image rows se~uentially and fractionally to said second pass object line segments of each corresponding one of said second pass object lines; and summing and averaging for each segment of each of said second pass object lines said intensity values of said pixel~ mapped thereto to obtain a composite value corres-

3~ ponding to eacn of said final image pixels and applying saidcomposite value to corresponding ones of said final image line segments.

- 5h ~L~

In accordance with another aspect of the invention there is provided a method of mapping input pixels from an input pixel llne in an input image to output pixels in a corre-sponding output pixel line in an output image, comprising the steps of, determining pixel transformation starting points for said input and said output pixel lines, and mapping from said input pixel line to said output pixel line by beginning at said starting points and assigning se~uentially and contiguously on a fractional basis, the number of said input pixels required to generate each of said output pixels.
It is, therefore, a main object of the invention to provide a new and improved computer generated imagery system involving the use of real-world images in the data base. Other objects of the invention will become apparent from the following specification, drawings and appended claims.

BRIEF DESCRIPTIONS OF THE DRAWINGS
In the drawings:
Figure 1 is an aerial view of a battlefield area shown as an example of a defined or gaming area which could be rep-resented in a data base in accordance with principles of the invention;
Figures 2A and 2B illustrate scenes which might be somewhere in the deEined area of Figure 1 as it would appear for an instant on a video display simula-ting a window in the cockpit of a helicopter simulator;
Figure 3 is a b]ock diagram outline of the CGSI system which embodies the invention;
Figures 4 to 12 illustrate steps in the construction of a typical CGSI scene;
Figure 13 is a system block diagram of hardware used for data base construction;
.,~

- 5i ~ 6~

Figure 14 illustrates a method applied to a house for generating three dimensional objects by breaking the objects down into subsurfaces;

,~

Figures 15 and 16 illustrate a process for obtaining high fidelity objects and surfaces to an optical disk which retains the object "library" of the data base;
Figures 17 to 20 illustrate the treatment of 5 translucent objects such as smoke, dust and shadows which are referred to as "special effects" objects;
Figure 21 illustrates the use of a sector masX
for producing glint and glare effects with a CGSI system;
Figure 22 illustrates IR imagery in a CGSI data 10 base;
Figure 23 illustrates a flight path around a large object, i.e., a tank, which is stored as a series o two dimensional views in an opti~al disk in one degree increments in azimuth and elevation;
Figures 24 to 27 illustrate the occulation capability of the CGSI system;
Figure 28 is a schematic representation of the field of view (FOV) function;
Figure ~ is a list of the equations which deine ~he positions o an observation or scene recognition system relative to the terrain coordinate system of the gaming area;
Figure 30 i5 a graphic representation ofa two-pass image warping technique:
Figure 31 is a blocX diagram which illu~trates ~ channel or "pipe line" for processing object, sur~ace and special effects data from the aata base library with the use of a warp t~chnique;
Figure 32 illustra~es implementation of the -intensely control function of the look-up-table card of the channel shown in Figure 31;
Figure 33 is a simple block diagram illustrating two identical object processors for two-pa~s processing of an input image in p~r~orming the warp tech~ique;

Fig~re 34 illustrates two-p~s~ warping organiæed in a pipeline configuration;
Figure 35 shows a flow chart for a continuous interpretation technique for the process indicated in Figure 30;
Figure 36 shows a pixel interpretation processor for carrying out the process indicated in Figure 30;
Figure 37 illustrates spiral mapping of an image into memory for pixel processing;
~ 10 FigureS38 - 40 show exc~mples of how the image address ~o memory address is mapped;
Figure 41 illustrates both serial and parallel objQct, surface and special effe~t c~annel processing;
Figures 42 and 43 illustrate the warping ofimages 15 in both linear and perspective in acoordance with techniques of the present invention;
Figures 44A and 44B illustrata the re~pective vertical and horizontal mapping of object lines on a screen relative to an observed E~int of view;
Figure 45 depicts the intercep~ion equation associatin~ with the mapp:ing of an image line on the screen as illustrated in Figure 44;
Figure 46 depicts a hardware pipeline performing t~e equations of Figure 45, Figure 47 illust:rate~ a first p~ss vertical object line projection;
Figure 48 illustrates a second pass hori70n al ob j ec t l in ~ pro j ec tion;
Figure 49 illustrates an output pi~el corre-30 -sponding to an alternate processing algorithmJ
Figure 50 is a block diagram of a s~ene construction module for assembling ~he indivi~ual objects ~or processing into a single scene;

Figure Sl illustrates a channel combiner for combining video data from multiple sources on a pixel-by~pixel basis to form the final composite scene:
Figure 52 shows a blc~k diagram of the special effects function performed by the special efects unit l~
indicated in the block diagram of Figure 3;
DESCRIP~IO~I OF A PREFERRED EMBODIMENT
Referring to the drawing~, Figure 1 is an aerial view o a battlefield area which may be fictitious or may be an actual place anywhere in the world. 1`he area shown by way of example has been referred to as a gaming area or defined area and, within the limits of practicality, would normally be an area covering on the order of 25 to 100 square miles.
If by way of example, the video display imagery system ofthe present inventionwere tobeused for simulating ~he operation of a helîcopter, a si;nulated gaming area such as that shown in Fig~re 1 might be devised or selected as an environment for the operakion of th~ helicopter.
The visual system of the helicopter simulator would provide a continuous "window view" of the gaming area which could be a video display of a stream of pilot eye-view scenes in the ~aming areacorresp~nding to thelocation and attitude of ~he helicopter relative khereto. The helicopter simulator would be equipped with contr~ls for guiding or navigating it in any directivn in, around and through the gaming area in the manner of free fligh~. The system response to uch ccntrols determines what is seen in the video display "window".
Figure 2~ illustrates a scene which miyht be somewhere n the gaming area o Fi~ure l, pos~ibly behind a grsve of *rees, as it would appear for an instant on a video display simulating a window in th~ cabin of the helieopter simula~or. The continued operation of the controlsby a pilot trainee would define the dynamicmovement of the helicopter in the gaming area and the ~cene on the video display would be in ac~ordance with the instant-to-instant location of the h~licopter.
Figures 2A and 2B are actual copiesofphotographic reproductions of screened video display scenes in a gaming area which were produced in accordance with the principles of the present invention. m e deci~ed realism in the detail o the objects despite the ~act that the scene images have been through several processing steps which tend to reduce detail should be noted. In addition, the smooth transition from object to b~ckground illustrates the elL~ination of the cartoonish representations in the scene.
Figure 3 is a block diagr~ outline of the CGSI
system and such diagram will be referred ~o frequently herein.
Figures 4 to 12 demonstrate steps in the ~0 construction of a typical CGSI scene which would culminate in the block 12 of the diagram of ~igure 3. These figures are also photographic reproductions of screened images.
The construction of a CGSI scene normally begins with the placement of land, water and sky surfaces. The 2S sequence continues with tlhe addition of objects, both small and large. The objects may be tree , rocks, bushes, houses, xoads, lights, ~ehicles, helicopters~ airplanes, animals, girls, etc. Finally, specia~ effects may be added, if desired, and these may include ~moke, dust, clouds~ shadows, 3~ etc~ To demonstrate how CGSI works~ a sample srene is assembled in opera~ions depicted in Figures 4 to 12.
Beginning with Figure 4, sky is added in egments over a distant background. Breaking the sky into segments, allows peaks and valleys to fvrm the skyline as shown.

^ 10 In this example, the sky was broken into five segments.
In general, the lower edge of the segment does not need to be straight, but may be curved or jagged to simulate rolling or sharp hills or mountains. An explanation of how the individual segments are warped based upon minimum and maximum data based elevations and ~pon viewpoint is described in detail later.
In Figure 5, textured surfaces are added, also in segments, to orm foreground and foothill surfaces.
Ihe untouclled region between the foothills and the sXy ~?~ appears as mountains in the distant background. In ensuing ~ a.
~igures, stored, textured surfaces, warped to fit the screen coordinate~ of the surface pol~gons, are then added to the scene. The intensity of each surace may be varied based upon range or other desired parameteræ~
Figure 6 illustrates a planned road segment for which a road representation in the data base surface library is w~rped to fit the screen coordinates. The surface library may containdifferent road surfacesand other special surfaces suoh as r~treams and ponds.
Figure 7 shows examples of planned, relatively small two-dimensional (2D) objects which occupy less than a predetermined frac~iorl of the total screen. In one embodiment objects occupying less than 1/16 of the scene's area were represented in 2D. This is because it has been demonstrated that .in the majority of applications, s~ch relatively small n~tural obj~cts such as trees, bushes and rocks may be re~resented from one side, i.e., as 2D
objects, with lit~le loss of realism7 Objects which cannot be represented from one side such as larger buildin~s, or item~ of special interest such as tanks~ ships, etc. are referred to and represented as three-dimensional objects ~3D~. It will be appreciate~ ~hat rela~ively small 2D
objects may be processed by le~s extensive processing r ll hardware/software than 3D objects and surfaces. During ,~ ~h~ flight through a scene, the 2D object may be handed offto a 3Dprocessor when it occupiesmore than a preselected amount of the area of the scene.
Figure 8 illustrates a tank as a multi-view or 3D object. Multi-views of the tank are stored and ths correct view, based upon the tank path, elevation and observer's viewpoint, is used in constructing the scene.
The tank may be moving and may be very large.
Figure 9 illustrates a house which is an example of a mul~ surface or 3D building. T~e house is separated into several surfaces, several roof segments ~one if both sides are identical), two ends, and two sides. The individual suraces of -the house can be warped from a norm21ized view to form the perspective dictated by the screen coordinates and then joined together.
Figure 10 illustrates large 2D objects which can occupy more than the predetermined amount of the area of the scene. When required, these objects may be expanded so that an object may ble larger than the entire surface of the ~creen.
Figure 11 illustrates a special effects technique used for translucent media which include clouds, dust, smoke and shadows. A mask controls the tra~smi~sion functions a~d a second input word co~trols the intensity a~a color.
Figure 12 illustrates a co~plete CGSI scene which might also appear somewhere in the ga~ing area illustrated in Figure 1.
The block diagram of ~igure 3~ will be addressed next. Each item thereof rom the data base constructlon to the special effects insertion is described briefly immediately below and in greater detail in the ensuing text.

. 12 BRIEF DESC~IPTIONS OF ITEMS OF BLOCK DIAGR~M OF FIGURE 3 DATA BASE CONSTRUCTION
The data base comprises two very different types of data which relate to the object library and the gaming area, respectively. The object library hardware produces and stores imagery with 'high fidelity on optical disks.
The gaming area hardware is used to load the locations of objects, surfaces and specia] effects.
The flexi~ilityof the object libraryisvirtually unlimi~ed. It may contain images of objects and sur~aces, and transmissivity masks of special effects each of which mayberepresented inone ofmanybandsofthe electromagnetic radiation spectrum~ m is allows the simulation'of not only the visual domain but also input/output based on sensed IR, MMW, radar, etcO The object libary may also contain a mixture of 2D and 3D images. The images may represent a variety of day/night and diurnal conditions.
The visua1 object libxary normally c~mprises photographic matter. In constructing high-fidelity objects from the object library, images from individual real-world ele~ents, highly accurate models, artist drawings, photo~raphs, etc., sto~ed in the library are restored to form "near-perfect"
images. ~his is achieved by restoring edges, separating objects from their backgrounds, correcting intensity and ~5 color, generating realistic color, positioning object from system reference points generating high-fidelity CGI
objects, and generating graphic data, i.e., light sources.
Ground contact and height reference poin~s are also added.
I~e "neax-perfect" objects, surfaces, and special effects are stored on a rapid ~cces and high-speed data rate media. "~ear perect", means high fidelity with respact to the quality of the input image.

The gamung area database providesthe~nformation necessary for the placement of the contents of the object library, surfaces, and special effects on a grid or gaming area. The objects may be placed by an operator or in a random manner ~y the computer. The ob~ects in the library may be either stationary or capabl~ of movement. The output o this function determines contents of the scene.
VEHICLE SIMULATION COMPUTATIONS
The vehicle simulation computations, based upon the vehicle math model and control inputs, determine the locations and viewing direction of the visual or sensor system for the prLmary vehicle. In addition,the computation may be performed on secondary vehicles based upon-vehicle moclels and selected paths. The output of this determines the location of the observer.
COMMU~ICATIO~S SUBSYSTEM
Of course, the input¦output or I/O of the vehicle simulation system and I/O of the CGSI system must interface in an efficient manner. The communication subsystem can ~e a bi~directional link and bufer interfacing the two systems. This function is the "handshake" and data flow between t.he systems. -FIELD OF ~EW A~D COORDII~ATE TRANSFORM COMPUTATIO~S
A FOV processor determines the presence of objectsc surfaces, and special effects in the scene ~mder construction. The output of a transformation matri~ ~V) converts real-world coordinatesto screen coordinates~ This data from the transormation matrix permits rapid testing and determines ifall of arlyportion ofthe objects,surfaces and ~pecial effects are present in the scen~. To avoid testing for the presence of all the objects in the data base, a "smart" algorithm test~ only those objects or ^ 14 surfaces which are in the proximity of the scene. The FOV processor maintains a list of objects in the FOV and their object, surface o~ special-e~fect channel assignment.
The function of the FOV computer is to determine w~at can be seen by the observ~r.
CO~TROLLERS FOR OBJECT5, SURFACES A~D SPECIAL EFFECTS
The controllers "fan out" and prbcess the control functions generated during the FOV computation. The processed control functions are passed to the object/surfacestspecial efects processing channels. The main functions performed by the contxollers include the transformation of gaming area coordinates to screen coordinates, processing range data from the operator-controlled vehicle to each obiect in FOV, determining the intensity of each object based upon range and object identification, and commanding to the object library base for the retrieval of the correct image data.
The function of the controllers is to " fan out" FOV data and g~enerate precise co~trol data for the scene.
LIBRARY FOR OBJECTS, SUR]?ACES A~D SPECIAL EFFECTS
The library stores the images used to construct a scene. The Controllers command the selected images which are passed to the processing channels. The only function of the library i5 to store images and provide the correct image upon ccmmand.
PROCESSING OE~NNELS FOR OB~ECTS, SURFACES AND SPE~IAL
EFFECTS
The individual processing channels or "pipeline processors" normallyprocess one lar~e item (object, surface or special-effect) per channel at one ~ime~ me processing channels may have the capability of processing a plurality of smaller items in parallel. All the processing channels - 15 ~

operate in an identical manner on each sllch item because it is the nature of the item which designates the function of the channel. In one embodiment each processing channe:L modifies one large or sixteen small items from the object library by the transformation specified by the control functions.
That is, the object, surface, or special-effects processing channels function to change a stored image in normal straight-on perspective to scene conditions based on scene coordinates by changing image, position, size~
rotation, and warpO Image intensity is modified based upon a range and object type. The function of these parallel pipeline processing channels then is ~o modify each object, surface and special effect used in a given scene as required.
SCENE CONSTRIJCTION
A scene construction module takes the individual image from each processing channel, separates the image from the background, and assembles the scene based upon range. In this manner, near objects occlude more distant objects. Ihe high-frequency edges generated by assembly a scene from individual images may be smoothed by a Gaussian function. This opera-tion matches edge and internal frequencies.
The scene construction module receives range information from the object and surface controllers. The range is used to determine whether or not a particular object is in front of, or behind, other objects in the sceneO If the particular object pixel is the closest occupied pixel in the scene, then it will be the pixel displayed. This may be ter~.ed a "nearest"
treatment.
The scene construction function accepts video inputs from each video channel and from a background-level source defined by the FOV computer.
III this function the outputs may be real-time video signals to the special effects insertion module.

.:

The digital scene construction function contains the following subfunctions- 13 object channel combination, 2~ scene value adjustment to accommodate scene-wide intensity corrections, and 3) smoothing to compensate for object-to-object and object-to-background boundaxies.
SPECIAL EFFECTS
I~e translucent special effects ~re added after the generation of the scen~. me sp~cial-effects module adds the special effects based upon range. Special effects, such as smoke, or dust, may occur ahead of, or behind images in ~he scene. The intensity masks s~ored in the object library and processed in ~he special effects processing channel control ~he transmissivity ofthe-special effects. The intensity value input controls the intensity/color of the special effects such as black smoke and white clouds.

D~TAILED DESC~IPTIONS OF ITEMS OF BLOCK DIAGR~M OF FIGURE 3 .~

DATA BASE
The data base hardware, like the data base itself, may be separated into t~wo separate subsystems comprising object library and defined or gaming area hardware. The object lib:rary hardware produces and stores the imagery with high fidelity on optical disks. The gaming area hardware is used to load the l~cations of the objects, 25 surfaces, and special efects. The data base hardware then operates non-real time to produce high-quality images on controlled backgrounds which are transferred to optical di~ks for storage.
The library hardware consi~s of a disk con~
troller, disk drive, signal conditioning module and optical disk. Either a video ~analog~ or digital disk ~ay be 9~

used for ~toring the images. A video disk provides about 6 to 8 bits, or 64 to 256 gray shades. A digital disk can provide up to 12-bit data. In all cases, except for very high resclution sensor images, the industrial 525-line non-contact video disk appears to provide images ofadequate fidelity~
The use of a video disk is well known. The image is scanned by sequential rows which in effect constitutes a column scanning of the frame. As will be ~escribed later, however, it is normally more efficient lS to start any of the warp processes described herein with a first pass column prccessing of the output of the video disk. Wikh this in mincl, it is thus desirable to store the images on the video disX with ninety degree~ offset orientations so that the disk output will in effect ~e in column form to facilitate the first pass column processing.
Of cour5e~ if for some reason it is desired to store the frames on the v:ideo disk with a normal or upright orientation, this may readily be accomplished and a front end processing means may be provided for the processin~
channels which will serve to properly orient the data in a buffer to accommodate the processing characteristics of the warp sequence being utilized.
Althou~h other devices will occur to those skilled in the art, in conjunction with an optical disk, the CGSI
concept has been found to work quite well and has not been particularly difficult or expen~ive to implement.
~he video disk offers the following advantage :
a) High-density storayeO about 54~000 frames per single side of a 12-inch disk.
b) Relatively low data storage costs.
c~ Excellent random access: with somemodification, it appears that an industrial disk will readily skip plus or minus 50 to 100 rames every 60 ,',.. ,. ~n cycle field time or in 16 2/3 ~illiseconds. The actual j~mp occurs during the blankin~ interYal, therefore~ no image data is lost.
d) High data rates: provides data at video rates.
e~ Long life and securedata: the disk i5 non-contact and read only, the data can not be damaged by head crashes or operator errors.
f) Ra~id replication.
A system block diagram of non-real time data base hardware is shown in Figure 13. In this system edges are restored, the background is separated from the objects, intensity ard color are corrected, real istic color is generated, objects are positioned for system reference poi.nts, non-~eal time high fidelity CGI objects are generated, and graphics data ~light sources~ are generated.
DATA BASE - GAM ING AR:EA
The gaming area contains the reference poin~s for locating surfaces, objects and special ef~ects. The gamin~ area may be set up in ei~her of two manners, a manual mode or an automa1:ic mode.
In the manual mode, the operator may search the object library and select which objects to place in the gaming area. The object files may be individual objects such as bushes, tre~s, surfacesr mountains, roads, lakes, or yroups of small obje~ts on one file. To place a 2D
Qb ject in the ga~ing area, the operator selects an X, Y, Z
surface reference point in gaming area 3-space wherein X, Y and Z, respectively, represent horizontal, vertical an~
rang~ axes. A ~econd X,Y,Z reference point determines tha height and position. Thus~ if the ob ject is standing in a true vertical position, the X and Z raerences will remain constant, and the Y reference will change by tha height o th~ object. If the object is tilted in one of the axes ~le X and/or Z axis r~ference points w~ll change.

~2~
1~

5urfaces may be defined by four X,Y,Z reference points, one for each corner. This includes, for example, the side of a house, a laXe, a road, a river, etc. To produce greatdetail accuracy, threedimensional multi-imageobjects may be stored in a series of images which represent l-degree increments both azimuth and elevation~ These may bedefined by three refer~nce points which represent the center ground contact point, the c~nter height, and a directional vector or pointing angle.
~he automatic placement m~de operate~ in much the same manner as ~he manual mode. The computer processes and places he objects in a controlled manner as will be discussed. The objects are placed by type and density.
DATA BASE ~ OBJECT LI~RARY
The object library contains images which, f~rb convenience,maybedivided into threebasic classes, name y,~
surfaces, and special effects.
In thecase ofobjects and surfaces,~olid-surface objects may bQ further classified into two-dimensional, three-dimen~ional one axis, three-dimensional two axis, and light sources. A process for getting obiects and ~urfaces to the optical aisk with near perfect high fidelity is shown in Figures 15 and 16. Each o~ these will now be treated in more detail.
OBJECTS - TWO DIMENSIO~AL
A previously stated t it has been found that mos~ object~ found in nature such as rock~, trees, bushes, shrubs, etc., may usually be presented in two dimensions with sufficient realism. A picture is taken of the objects 3~ rom the averag@aspectangle used in t~e deslred simulation.
As the elevation changes, ~he objec~ is transformed between the reference points which re~ul~s in an increassd or decreased height, depending upon the perspective. In the 20 ~

case of trees and bushesg an object surface remains perpendicular to the viewer as during the flight path. Experiments have indicated that this efEect is not noticeable. The relationship of objects to other objects and the rate at which the relationships change, in addition to the size and size changes, provide the depth cues. For two-dimensional objects, a single picture may be stored on a track of the optical disk and processed through a warp opera-tion to obtain the proper rotation, size and position.
OBJECTS - T~EE DI~ENSIONAL - ONE AXIS
If an object is tracked as during a flyover, the perspective changes by 90 degrees. In this case, the simulation may require a series of additional pictures in the vertical axis.
OBJECTS - TH~EE DIMENSIONAL - TWO AXIS
Three-dimensional/two-axis objects or surfaces may be handled by three approaches. The first is by storing a series of pictures in as small as l-degree increments in both azimuth and elevation. This is a powerful presentation technique which works extremely well when objects contain fine details which require high surface fidelity. The precise increments may be obtained by rotating models of large objects such as helicoptersg tanks, and houses on two very precise rotary tables, and photographing the objects at each setting. A second method of generating three-dimensional objects is by breaking the objects down into subsurfaces such as the house shown in Figure 14. A house such as this could be seen on the video disp:Lay in various perspective views in a sequence of scenes but would never be asse~bled as a total object image except by the computer. The sides are separated and assembled by a warp technique. This approach permits , , t~e use and construction of many objects from several pictures and approximate dimensions. A third method adaptable to large objects, such as ~ills, is to photograph an object at a series of fixed elevations with a relatively large spacing such as a 30-degree spacing in azimuth completely around an obj~ct. As an example for most ~imulations one elevation can be used, typically 15 degrees, and a series of pictures around the object in 30-degree increments has been found to be adequate.
1o OB~ECTS - LIGHT SOURCES
The light sources are laid out from a string of points stored in m~mory and a warp algorithm warps the surface from a normal view to the vehicle perspective.
Thi5 approach worXs very well and h~s been used to produce a demonstration landing tape.
SPECIAL EFFECTS
With respect to special effects, these translucent objects or images add further realism to the scene by providing smoke, fog,dus1:, shadows~ and haze. These ob~ects may be stored as a masX which defines the outline, shape and transmissivity factor. The mask determines the combining percent of object and special effects. A secon~
variable controls the intensity or color of the special-effect object. The mask determines the mixing ratio o the special effect with the bacXground fixed variable-control intervals, This technique may ke used, for example, to generate dust clouds rolling up behind a moving tank. A warp operation may also be applied to distort the special effect and a series of sequential frames used to generate the motionO
Thus, the translucen~ vbjects may be static or d~namic. The special effects objacts have been defined in terms of transmi9sion ma~ks in the object library~

3~ 3 ~- 22 ~hiq means that the data in the obje~t library determines the percent of background ob~ects present and the percent o~ special effects present ~y the follGwing equation:
r `
Pixel Value (gray level) = (l-MASK)*~ KGROUND (graylevel)~
+ (~ASK) *(SPECI~L EFFECTS V~LUE-(gray value)) The special effects value determines the gray shade o~ the special effects. Thi is shown in Figure 17. The masks for static special ~ffects are easy to draw as on white pape~ using gray tone markers. In this manner t~e relatively unsXilled or non-artist can readily sketch many general or specific clo~ds, dus~, smoke, fog and haze configurations. The special effects objects are typically treated as 2D ob~ectsO An assortment of masks may be s~ored in the library.
Four specific special effects have been implemented as follows:
1. DY~AMIC SMOKE
A smoke mask defining the ou~line and transmission factors is generated by an artist ~ased upon picture and mathematical characteri~;tics ~f the smoke. The top and bottom should be in the same location and have the same width as shown in A of Figure 18. ~e~t a series o~ frames, perhap~ 480, are generated~ Each pi~el may be incremen~ed one or more pixels in ~he Y axi5 w~en the frames are played back to produce a continuous ~irculatory loop. This is shown in B o~ Figure 18. Next, t~e top of the smoke cloud in each frame i5 feathered as shown in C of Figura 18 to match the dispersing of the smoke in atmosphere.
~he frames are stored in sequenre on a video disX as shown in C of Figure lB and a warp fuQction in the special e~ects processor is used to expa~ the top to sim~late diffusion, shear the image to acco~odate wind velocity, size the cloud based upon range, and position the cloud in the ~cene.
An initial condition parameter ~e~s the color or intensity of the c]oud. The rate at which the smoke fumes are played back determines the rate of 10w.
2. DYNAMIC DUST
By way of example, ~ive to ten dust transmission masks may be ~reated. A series of linear interpola~ions betwaen the various masks ~1-2, 1-3,...,1-10,...,9-10~
produce a series of fxames which are stored on a video disk. A warp function in the speci~l effects processing channel places the mask at the correct p0rspective, size and position in the scene and an initial set condition determines the color or it:ensity. Thi~ i~ shown in Figure 19.
3. SHADOWS
Shado~s may be treated as translucent o~jects like dust and smoke. The transmission masks for shadows are generated from imag~3s in the object library. ~he transmission mask, a shadow, may be crea~ed by ~etti~g all the pixelsin an objectto onegray level whichdetermines the transmission of the ~hadow. In t~e gaming area, the foux reerence points of an object are projected to ~he surface. ~he new points on the surface are the shadow reference pointsO The shadow, transmission mask, is warped to fit the scene based upon the eha~w~s reference points.
This procedure is shown in Fig~re 20.

4. G~I~T A~D GLARE
Typically, glint and glar~ are sur~ace normal data. However, in a CGSI sy tem, unless the obj~cts are ~2~6~
~4 developed from CGI noda'. data, the surace normal data i~
not avallable. To produce glint and glare, a sector mask is developed based upon the glint and glare bright areas produced by diferent sun angles as sho~n in Figure 21.
The sectors in the mask are gray level. That is, when stored in the object library, sector 1 may have a luminance value of 8, sector 2 a value of 16, etc. The sun angle table data sets the look-up tables in the object processor.
If the sun is in s~ctor 2, the input value of 16 in the look up table sets the output glint and glare values to a predetermined level. The remaining output ~alues in the look-up table are zeroO The result is a bright spot in sector 2. As the ~urret moves or the sun moves, the I;h 7' 5 ILJ~ ~
sector changes. In~-~h~ay b~4ee~r~, dynamic gIint and ~5 glare may be based upon sun and vehicle movementO

~ATA BASE - GE~E~L DISCUSSION
The CGSI datal base is extremely versatile, consisting of real objects and simulated special effects.
The r~alism achieved dependson the ingenuity of theoperator se~ting up the particular simulation. The data base does not require skilled progr~nmers~ and lends itself to subject matter expert~ for -the particular applications. If a cJroUp be working in a certain domain~ , visual, millimeter wave, or radar, imagery :Erom that sensor is load~d in ~he ob~ect file~ ~his imagery simulates the sensor because it comes from ~he sensor. In addition, the parameter of the i.ma~es or s~nsor may be modified when building the li~r~ry or in the setting of intensity values during real-time processing. An IR exampl~ is shown in Figure 30 220 In this illustration the selected emissivity may be changed to simulate changes to the sensor or a host of other paxame~ers. If a specific area or ~pe o terrain is under inv~stigation, that imagery may be loaded into the objact file without requirin~ the skilled services of a computer programmer or an elaborate, expensive data base change. In opposition to the state-of-the-art CGI systems, the C~SI data base is very w211 suited for rapid setup and rapid training over a range of complex human factors situGtions. The versatility i~ demonstrated by the fact that time of year, time of day, weather conditions and most other parameters may be selected and easilyimplemented by the experimenter withcut skille~ software knowledge.
1~ DATA BASE - DISCUSSION OF ~D AND 3D SYSTEMS
2D Natural Objects The classifi~ation "2D ~atural Objectsl' includes trees, bushes, and small rocks. ~s previously stated, it has been ound that one image taken at a depression angle of say 15 degrees will suffice for depression angles from O to 40 degrees and all views in azimuth. The dominant visual efects apparently are the geometric relationships and size change~ of any object with respect to other natural objects in the scene. ~e stationary internal detail of an object enhances the scene by adding much needed detail.
If a helicopter flies in a circular path around a tree the fact that the foliage does not change is imperceptible tQ the average observer~ Trees with no leaves, however, when used ~y helicopter pilots for a hovering g~ide, are ~5 perceived differently and may require the 3D multi-image.
2D Man-Made Objects Man made objects have definite orien~ations such as the front or side o~ a vehicle. To test these issuPs, however, a simulation of a tank driving down a road with man-made or oriented objects (an old truck, a car, a tombstone, etc.) has been developed. In this simulation, the objects alway~ remained normal to the viewer, but the 6~

2D nature of the objects is not detectable when one watches the tape. It appears that small to medium objects may be presented in aspect for an angle of plus or minus 15 degrees in azimuth and elevation without any noticeable degradation in image quality. For complete fly-around conditions, however, a 3D approach is required.
2D Patch Techniques Clumps or small patches may be warped and layed ~' out to ~orm a continuous high te~ture large surface~. In the tank dri~e sequence, for example, a ile of cattails was represented very successfully by a collection of many small patches of cattails each si~ed and positioned individually to produce a high degree of realismJ In a helicopter sequence of a demonstration video tape, the helicopter initially takes off and flies over detailed grass constructed from a series of patches. The use of patches repr~sents another very powerful technique for adding highly detailed su:rface information. This technique can also be used for water, rocks~ roads, railroad tracks, etc.
In addition, each patch can have dynamic motion~
That is, the wind or r~tor blast co~ld be blowin~ the grass or water. This effect is simulated b~ storing a series of dynamic frames on the optical disk and ~eeding the frames through the surface processors analogous to the simula~ion billowing smQke ~bove.
This technique also may be used to represent groupsof objectsat a distance. In the helicopter sequence, a cornfield shown during a "pop up" ~as constructed using several identical patchesofa cornfiela. ~his sameapproach may be used for dense trees, background, or any highly detailed textured surface.

3i~

E~tire areas of textured imagery may be warped to produce textured surfaces. This concept may be extended to long narrow "o~jects", such as runwa~s, railroad tracks, roads, creeXs, streams, etc. Linear warping techniques may be used on near square "objects," but a true perspective warp should be used for realistic representation of long narrow "objects" to avoid ima~e distortion.
A 2D surace need not be limited to sides but may include light sources (points or strips of light~, small rolli~g hills, mounds of sand, ponds, or small lakes.
A city simulated using CGSI techniques can be configured from surfaces, streets, sidewalks and building frontsO
3D Multisurfaces Most man made objects can be broken down into multisurfaces such as the sides of a building or truck.
By treating each side as a 2D surface and by allowing the computer to construct ihe visible sides of the o~ject in ~he scene, the ~D objects can be created from a small data base of individual !ides. As an example, consider a house with two sides, two ends, and two roof sections.
Each section is determined byfour (X,Y,Z) reference points.
Therefore, four corners x three reference points x six side~qq equals 7~ coordinate number~. They are required to locate all of the house detail in tha gaming area. The many views of objects required by the CGSI technique may be obtained from models, generated from estimate size data~
or digitized fr~m actual photographs o real objects.
3D ~ul~i-View Complex high fidelity object images lose fidelity ~hen ~hey arP reduced to a flat or curved surface. Two e~amples are a tree with branches, but without leaves, and a tank having many irregular surfaces. These obj~cts, 2~

which may occupy more than a third of the screen's area, may be stored as a long serie~ of ZD views taken in as little as l-degxee increment~ in azimuth and elevation.
This multiple view approach requires about (90x360) 32,400 frames or about 60 percent of a video disX holding 54~000 frame~ per object. The most demanding flight path, as shown in Figure 23, is one which encompasses the ob~ect at a changing elevation. If the frames be indexed on the disk in l-de~ree incrementals fr~m 0 to 90 degrees in elevation, for each l-degree incremental change in azimuth, the disk needs to jl~p about 100 frames to reach the next rame of interest even i the fiight path is almost level.
~he disk must be capable of jumping approxLmately plus or minus 100 frames during the vertical retrace of each TV
field. Thi5 allows flight around an object at various elevations i~ 6 seconds (360 degrees/60 field/sec). Thi~
is a realistically adequate limit as even a 6-~econd tight 360-degree turn would ma}ce the pilot dizzy. Other ideas, `~ involving linear and nonlinear interpolationJ have been explored for 30 multi-view objects, but to date none h~s equalled the fine detail.
Special Effects The special effects are processed like 2D objects and surfaces except that a transmission ma~k is used.
The mask may be dynamic ~changing at each frame as for dust and smoke). Also, the color and intensity of material may he controlled. All of these special effect techniques have been demonstrated in a CGSI video output mode~
~cculation The CGS~ concept allows objects to have holes or win~ows in them. That is, for example, one may see through a clearing in the branches ~o the nex~ object or backgro~ld with decided realism~ Features or parts of 6~

features nearer the viewpoint al~ays properly occult features or parts of features farther away. As explained elsewhere herein, the scene construction module uses range data to selecteach pixel in the final scene. To demonstrate the occulation capability which utilizes the range data, three examples will now bepresented. These areillustrated by Figures 24 - 27.
In the first example, shown in Figure 24, occulation of three trees may be based on range data to the gaming area reference points. In this manner, T
occults to T2-- and T3 ; T2 occults T3.
In the second example, a long slender vehicle i~ moving about a tree. As shown in Figure 25, the use of ~ingular range points for the vehicle will provide inaccurate cccultation. In both A and B, th0 vehicle is in front of the tree. However, in B the vehicle is placed behind the tree because RV is greater than RT . Thi5 approach does not suffice. In Figure 26, two range data points, a maximum and minimum, are maintained for the vehicle. Note that the ve-hicle range now may be determined by using the vehicle range vector closest to the range vector of the tree. Sec;ments A through D of Fiyure 26 demonstrate successful placement of a vehicle driving around a tree.
The third example addresses the problem of two vehi~les as shown in ~igure 27. Again, the range may properly be selected by using the closest vehicle vectors.
In ~his manner any number of objects may be addressed.
2D/3D Conclu ions The preceding sections have outlined several 2D
and 3D approaches to t~e plac~men~ of ob~ects and special effects i~ the scene and their imple~entation guides. By means of these techniques, it is feasible to simulate most objects and conditions encountered in the real world.

~pplications ofthe appropriate ZD/3D technique asnecessary will occur to those skilled in the art.
Vehicle Simulation The hardware and software for generating the ;`''`~ ~'~ f~ ~ O q ~ J r~
location of the ~rainee's vehicle or other scene r~ee~nti~
means relative to the g~ming area and the location of movinq objects in the gaming area are not themselves a partofthe CGSIsy~tem inventiondisclo~ed herein. However, the X,Y,Z, roll, pitch and yaw signals indicating l~ instantaneous locations of such vehicles are sensed by the CG5I system hereof and, in response thereto, the video di~play scenes of the simulated gaming area are developed.
Co~unications Subsystem ThP hardware to interface the CGSI system to the vehicle simulator ~ppears to be unique for each application. Each user has an established vehicle simulation computer and ~he CGSI system can have a standard input. It is the interface hardware that converts the digital output signal fro~m the vehicle simulation computer to match the input ~o the CGSI FOV computer. This hardware interfacemayrange from asimplecableto acomplex interface containing buffers and microprocessors~
FI~hD OF VIEW AND COORDINATE TRA~SFORM COMPUTATIONS
In Figure 28 there is shown a schematic representation of the FOV f~nction relative to ~e gaming area. The origin o~the gaming area coordinate system is represented by point 20 and the eyes of the observer may be at an~ point 21 in the gaming area. The screen or CRT
immediately in front of the observer or trainee has ~he outline 22 and the origin of ~he screen coordinate sys`tem is at point 23. The four corners of 2 terrain patch are projected t~rough the CRT whichmay represent the windshield ~2~oæ~0 of the aircraft and an outline 24 thereon represents the projection o~ the terrain patch on the screen which i5 seen by the operator.
Two types of vehicle simulation computations supplied to the FOV processor are (1) position vectors which define the changi~g positionsof the aircraft relative to the origin 20 of the terrain coordinate system and (2) rotational data (yaw, pitch and roll ~ which defines the changing attitudes of the aircraft relative to the origin 20 ofthe terrain coordinate system. ~luationsrepresenting thi~ data are set forth in Figure 29.
In accordance with known prior art principles the vehicle data in the form of the- equations set forth in Fi~ure 29 can be procPssed to yield the distance or 15 range of any object or surfac~, such as the terrain patch, from the screen 22 and the screen coordinates for the four corner points or ve.rtices of the proj ection of the o~ject or surface on the screen. In fact, the prior art capability is such that the terrain patch or any object or surface may have the shape and si~e of any form of convex polygon and the scIeen coordin tes of the plurality o vertices thereof can be computed.
I~e necessity of utilizing this advanced capability of the prior art, however, i5 not required in the present inventionbecaus~ of the manner in whichobjects, ~urfaces and special effects are ~tored i~ the data has~.
A~ previously mentioned and as illustrated in Figure 30, photographs of objects and surfaces are stored on a video disk and access to them is controlled by an index co~trolled by the FOV processor. Each object or surface has its input image in a frame which is the same si2e as the video screen which may be 512 line~ having 512 pixels per line.

~lz~

The data base has a list of all the objects, surfaces and special effects (indivi~ually denoted by the collectiveacronym OSSE) in thegaming area. Their locations therein are designated ~y gaming area coordinates. Also, the data base contains inormation regarding the height of each object therein. The FOV so~tware allows real-time determinations o the OSSEs in the field of view and the respective distances of the OSSEs from the video screen.
In Figure 30, the frame 25 containing the input image of an object has a shape which depends on the true shape of the object and the YOV processor uses that height in the transform equations of F~gure 29 to determine corresponding screen coordinates 1 to~4 of the video screen 26. The intermediate image 27 is an integral part of a linear warp algorithm which facilitates the mapping of the image from the input Erame 25 to the screen frame 26 and will be discussed in detail further on herein.
In summary, relative to the FOV function, the processing of the data from the vehicle simulation computations results in (1) the determination of osse' 5 in the field of view, (2) the distance of each OSSE from the location of the observer, and (3~ the determination of the screen coordinates of the ~our vertices to the enclosed space of which the input image of each OSSE is to be mapped. The above da~a for ea~h 05SE is directed to an OSSE pro~essing channel as will be described below.
OBJECT/SURFACE/SPECIAL EFFEC'rS ~OSSE) CH~NELS
The processing channels or OSSE channels process Ob~ect, Surface and Special Effects data from the data base library. As stated above, identical channel hardware is s~itable for all three unction~. -The OS5E channels are im~rtant and essentialto 2 CGSI system~ A possible hardware implementation of an OSSE channel is shown i~ Figure 31.

In order to obtain the correct intensity, color, imase, size, location, rotation and perspective, several functions are perormed on library data by an OSSE channel as follows:
a) A high-speed (approximately 100 nanoseco~d sampl~s) analog-to-digital converter 30 converts the objec~ Lmage to a dlgital format.
Conventionally, the digital format has 512 pixels per line, 480 active lines (525 total) and eight bits per pixel (256 gray shades).
b) A high-speed memory card 32 accepts the digital data in either th~ X or Y axis. The axis and direction of loading depencls on the xotation of the image~ The data is loaded to minimize pixel compression during the processing passes. For example, instead of rotating an image60 degrees, which may result in some Lmage loss, th~ data isloaded in the perpendicular axis(at90 degrees) and rotated 30 degrees. The memory card also holds the object image for processing when ~he optical disc controller i5 selecting a new track (image). This card may be omitted if the objects are stored on the disk in gO degree increments or if the rota~ions are less than ~ 45 degrees.
c~ A lookup table or lut 34 modifies the int~nsity v~lues of images for range and contrast effects.
This operation requires a delay of only a few pixels~
d) A warp card 36 transorms the image in the Y
axis on a line-by-line basis. ThP starting point (offset~ and magnification factors shift and compress or expand the pixels ofeach line. This operation delays the flow of pi~els by one line.

e) A second identical high speed read/write X and Y axis memory card accept~ and stores the transformed Y data for an odd and even field to form a frame. After ~he Y axis field is loaded in the Y axis, the X axis data is read out by line, and even and odd fields. This buffer operation requires one video frame.
f ) A second warp card 40 identical to card~ 36 processes X axis data by shifts and expands or compresses lines. Again, this operation delays ~he image by approximately one video line~
INTE~SITY CO~TROL
The intensity control of the look-up-table or LUT includes a memory controller 50 and an object LUT 52.
During ths active part of the display tLme the input video is used to address the LUT and the data output of the LUT
is passed on to the warping function .implemented by cards 36, 38 and 40 for further processing. This procedur effectively maps input intens~ty values into output intensity values via the data stored in the LUT. During ~he vertical blanking interval, memory controller 50 can assume ~ddressing control of the LUT 52 ~if so commanded by the object controller) and load a new set of values into the LUT for the purpose of deining a new object, or modiying the appearance of the previously selected object.
The intensity control can be properly broken down into two separate functions which provide intensity corrections related to a specific object as perfo~med by card 34 and intensity corrections related to the en~ire scene as will be re-ferred to below.
Memory controller 50 may be implemented by a single chip microcompu~er and LUT 52 may be implemented aq a RAM with multiple~ and con~rol circuitry to allow access from both the video data and data in memory controller 50.
LINEAR WARP TECHNIQUE
O~e linear warp technique associated with the invention is impl~mented by cards 36, 38 and 40 and involve a procedure to perform spatial transfonns on a digital image represented as a matrix of intensity values. Given a rectangular input image accessed from an optical disk data base, the technique in operation will map linearly to four corner points of the output image on a video screen. As illustrated in Figure 30, this is accomplished wit~h two orthogonal passes as indicated. Each passlinearly interpolate.s each input line to a diferent size and positions it in the output image. The size and position parameter for each interE~lation are determined from the input image corner coordinates and the output corner coordinates. The interpo]Lation consumes consecutive input pixels and generates consecutive output pixels. ~he two passes inte~act to perform siæe, translate and rotate tran6forms plus nonstandard mappings.
The process is independent of the FOV equations which calculated the four output corners on the video screen. It is computationally invariant for all transforms once the four output corners are ~sta~lished. It operates on line and column orien$ed streams of conserutive pixel valuesand is therefore ideally suited for real timehardware implementation.
Each pass simply sizes ~enlarges or reduces) ~he input line and positions ~offsets) it in thP output video image~ Both of the~e operations are accomplished by con~inuous intexpolation over ~he discrete field of pixels. This allows the continuous line sizing and subpixel positioning o output lines and columns which completely eliminates aliasing of diagonal edg2s. m e heart of the technique is an method w~ich allows the system to continuously ~ize a discrete input lin and phase its position in re].~tion to the discrete output grid.
I~TERPOhATION
Figure 35 depicts a flow chart for a continuous interpolation operation for the process indicated in Figure 30 in which SIZFAC is the "Size Factor" applied to ~he input image line and I~SFAC is the inverse of SIZFAC and has the additional significance of indicating what portion of input pixels is required tG create an output pixel.
INSEG is the portion of the current i.nput pixel available to contribute to the corresponding output pixel and OUTSEG
is the portion of the output pixel yet to be completed.
With the above definitions well in hand, th~
process begins by comparirlg the values of I~SEG and OUTSEG.
If OVTSEG is smaller thzln INSEG it means that there is sufficient input pixel available to complete an output pixel. Conversely, if ]:~SEG is smaller than OUTSEG it means that there is not sufficient input pixel l~ft to 20 complete the output pixelThus, th~ current input pixel will be used up and a new pixel must be fetched to complete the output pixel~ Only under these two conditions will an input pixel be used up without finishing an output pixel or an output be completed without using up the input pixel.
I an output pixel remains to be completed the current pi~el value is multiplied by OUTSEG and added to an accumulator. INSEG i5 decremented by the value of OUTSEG to indicate usage of that portion of the input pixel then OUTSEG i~ initialized to I~SF~C indicating that a complete output pixel remain~ to satisfy. The contents of the accumulator are scaled by SIZFAC and the result is the valuP of the nexlt output pixel. m e procass .then re~urns to compare the new values o I~SEG and OUTSEG.

If an input pixel remains to be used up the current pixel value i5 multiplied by I~SEG and added to the accumulator. OUTSEG is decremented by the value of I~SEG to indicate that the portion of the output pixel has been satisfied. Then I~SEG is reinitialized to 1.0 and the next input pixel is fetched. I~e process then returns to co~pare the new values of I~SEG and OUTSEG.
The heart of the process is the interplay between I~SEG and OUTSEG scaling input pixels to output pixels.
The effect is cne of pixel scaling and migration from one discrete grid to another discrete grid through a continuous interpolation process. Of course, the success of this continuous scaling process depends on the fractional precision of I~SEG and OUTSEG. With sufficient precision the effect is of perfectly smooth pixel migration between the two discrete grids.
Subpixel phasing is accomplished by initializing OUTSEG to some percentage of INSFAC to create a partial first output pixel. The last output pixel may not be completed when input pixels are exh2usted, resulting in a partial last output pixel. This allows continuous positioning of the output with relationship to the discrete pixel grid and elLminates edge aliasing.
With the capability to contin~ously size and p~ase a discrete input line in relation to a discrete output grid, the warp to the quadrilateral becomes a matter of determining the si~e, phase, a~d output location parameters for each column of the first pass and each line of the second pass.
The irst pass~ (Figure 30) reads th~ inpu~ image and writes the intermediate image vertically left to right.
The object is to migrate all pixels into their correct vertical axi~ orientation. This is accomplished by mapping ~he first col~mnbetween Yl and Y4and linearly interpolating ~%~

over all other col~ns such that the last column begins at Y2 and ends at Y3.
The second pass reads rows from the intermediate image and writes rows to the output. Since all pixels are now in their correct row, the rows can be processed independently in any order such as a two to one field interlace. The object of the second pass is to migrate all pixels into their correct horizontal axi~ orientation.
The second pass mapping must be considered in three processing regions a~ indicated by the dotted lies of the intermediate image. There is a different output.
location delta for each region and the size factor is updated with its delta onlyduring middle region processing.
With the correct initial values and deltas each corner is mapped into its output X coordinate and the rest of the imclge follows in proper relation.
The initial output location is the intersection ofthe 1-4 edge with the horizontal line through the uppermost corner. The location delta for the upper region is tha slope of the 1-4 edge if corner 1 is uppermost or the slope of the 2 3 edge if corner 2 is uppermost. The location d~lta for the middle region is the slope of the 1-4 edge. The location clelta for the lower region is the 1-4 edge slope if cor~er 4 is bottommost or the 2-3 edge slope if corner 3 is bottommost. The initial size factor is t~e leng~h of ~he horizontal line segment ~rom the second highest corner to ~e horizontally opposi~e edge.
The slze delta is t~is value subtxacted fxom the similar value of the third highe~t corn~r and divided by the vertical distance between the second highest and third highest corner~.
In ~hi~ manner, corners 1,2,3,4 of the input image are mapped to corners 1,2,3,4 o the output image.
This mapping may require ~ 90, 180, or 270 degree ~2~

preorientation of th input image prior to the mapping discussed here. This orientationis determined bycomputing the area of the four possible intermediate images and choosing the orientation that results in the largest area.
Ater preorientation the corners of both the input and output images are relabeled such that corner 1 is the extreme upper, left corner.
The warping function, then, implements a process using both column-by-column and line-by-line passes. Fiyure 33 repxesent~ the top-level block diagram for the warping function with three sub-functions defined. Two identical object processors 60 and 62 disposed o~ cards 36 and 40 are defined, each capable of performing a one-dLmensional warp. The Y object processor 60 performs the column~b~-columr-warp,and the Xobjectprocessor62p~rforms the line-by-line warp. A frame buffer 64 is used to store the intermediate image (warped in Y but not X~ to allow the X object processor 62 access to row data rather than the column oriented data in the sexial data stream used up -to that point.
Magnitude and offset parameters, for both Y a~d X passes, essential to the implementation of the algorithm are passed to the Y and X a~is processors 60 and 62 -Erom the appropriate object controller at the frame rate.
2~ Line-by-line (column-by-column) computations of magnitude and ofsPt mustbe handled bythe axis processorsthemselves.
IMPLEMEMTATIO~ OF LINEAR WARP TECHNIQ~E
The two-pass technique is organized, as shown in Figure 34, in a pipeline confi~ur~tion as input memory 70, irst-pass processor 60, intermedia~e memory 64 and second-pass processor 62. ~he intermedia~e m~mory is a double buffer so that the first-pass processor 62 can wri~e it~ results in one bufer w~ile the second-pass processor is reading its input from ~e other buffer.
Both processing stages may be of identical h,ardware design.
There are three points of externa:1 coT~munication in the subsyste~n. The input image memory 70 .'LS loaded

5 from an image data base and is a lO-MHz, 8 bit I/O port.
The host has to pass sub-image coordinat:es and output cornex cooxdinates to a controller 72~ ~liS, may be a fast RS232 or a shared DMA portO The th.i.rd port is the outpu~ image deliv~red as a lO-MHz, 8-bit, synchronized 2-l interlace stream of pixels.
The host must set up the input image as shown in frame 25 of Figure 30 and deliver the image corner points 1 to 4 indicated in the scree~ frame 26 of Figure 30. The subsystem ~hen performs the ind~cated transorm on the supplied image until the host changes one or the other.
The control and proc~ssing inside the subsystem naturallypartitions into threehierarchical stag~s,namely, the frame, line and pixel stages. The frame and line processing is lower bandwidth than pixel processing and can be accomplished with available l6-bit microcomput~rs.
The pixel processing is very high data rate and requires custom designed hardware.
The frame level control involves setting up the ~5 memorie~, communicating with the host and initiating the line processors. Several comput2tional tasks are carried out at the frame level. The access orientation of the input image is deter~ined by finding the oxie~tation which generates the larges~ intermediate image. This is indica~ed by the rame 27 o~ Figure 30. There are our possible orientations and an output position and a size fac~or and associated deltas must be calculated and passed to the line processor of Figure 34. For the second pass these calculation~ are somewhat more complex ~h~n for the first pass and, in addition, some screen clipping calculations must be carried out.
There are 33 milliseconds available to carry out the fxame oriented calculations and, by using double integer arithmetic operations, these tasks require only about 15 milliseconds on, for example, a M68000. Thus, there is ample processing power in a single microcomputer to carry out these calculations and control the subsystem.
ThP line level processing increments the output position and size factor, perform clipping calculations on th~ output position, sets the address in the input and output memory and signals the pixel processor to begin processing. There are 63 microseconds available for ~his processing. It is estimated that at lea~t 50 microseconds are re~uired. This is close to the limit and two microcomputers may be required to assure performance of line computations for each pass.
A separa~e line level proc2ssor is required for each pass but only one frame processor is required. A
.o total of five microcomputers may thus be needed. Thexe is very little data storage requîred and programs are short for each processO Therefore ~ery little memory iB
required and all ive processors can be fit on a single board~
Figure 36 illustrates a typical pi~el inter-polation processor for carryin~ out the interpolation process of consuming input pixels and generating output pixels~ It impl~ment~ th~ two-state loop o~ the int~rpolation tec~nique which can be readily pipelined in 3~ hardware. Output pixels must be readily generated at a maximum xate of one evexy 100 nanoseconds. The algorithm may require two cycleR to generate an output pixel;
therefore, the pipeline must be capabls of 50 nanosecond ~2~

cycles. The processing will fit into a fast pipeline with minimum hardware.
There is a recursive coupling in the process which i~ accounted for in a single pipeline stage. This is the comparison of I~SEG and OUTSE~. The use of one to scale the input pixel (INSEG~ and the subtraction of one from the other based on the comparison generating a new value for one which is then compared aga.in. The factor chosen for the scaling can be clocked into a register of the next stage and preserv~d; but the compare and subtract must occur in a single cycle in a single stage. This is illustrated in Figure 36.
First-Stage Operation If the image is being reduced in size, OUTS~G
is smaller than INSEG and an output pixel is being completed.
OUTSEG is stored into the factor register of the next staye and is subtracted from INSEG. The new value of I~SEG is stored in its register. OUTSEG is reinitialized from INSFAC and the compare is set for the next cycle~

Conversely, if I~SEG is smaller than OUTSEG, an input pixel is depleted~ INSEG is stored into the factor register of the next stage and is subtracted from OUTSEG.
Th2 new value OUTSEG is ~tored in its register and INSEG
is reinitialized ~o 1~0 and the pipeline stage is set for the next cycle. The remaining stages then ~ollow in a straightforward manner~
SecGnd Stage The second stage multiplies th~ input pixel value by the selected scale factor. If an input pixel is ~epleted the next input pixel is cl3cked into the pixel register.
The resul~ of the multiplication i~ delivered to the next or third ~ta~e of the pipeline.

Third Stage me third stage accumulates the scaled values ofinput pixels. If an input pixel is used up,the processing ends. If an output pixel isbeiny completed, the accumulated value i~ delivered to the next stage and the accumulator is cleared to zero.
Fourth Stage The fourth stage shifts the accumulator value to normalize the declmal position for input to the output scaling multiplier. This normalization is discu sed in the subsection on arithmetic precision.
Fifth Stage In the fifth stage, the accumulated value is multiplied by SIZFAC which is the inverse of I~SFAC. This creates the value for the next output pixel. l~is value is then delivered to m~mory to be stored in the nex~
output pixel location.
Arithmetic Precision The interpolation is sensitlve to arithmetic precision in bot~ the output intensity values and their spatial orientationO Cornputer simulation has shown that values of I~5EG and OUTSEG with 8 bits of fractionation are sufficient to ensure very high output image fidelity over a large range of transforms.
The value of INSEG is never greatex than l.0 and thus requires but 9 bits o representation. OUTSEG
can be represented as 16 bits with 8 bits of fractionation.
bitsO It is readily observed that the smallest of the two values is always chosen a9 the scale factor for the n~xt stage. This means that ~here will be only scale factors of 1.0 or an 8-bit fraction thereof. A factor of l.0 can be detected and treated as a special case by

6~3 bypassing the scale multiplication and presentin~ the pixel value directly to the accumulator~ Thiis leaves only scale factoris with 8 fraction bits. An 8x8 multiplier will suffice for the scaling and the product, then, is a 16-bit -~alue with 8 fraction bits.
The accumulator accumulates these values. Again, there are two possibilities. I INSFAC is less than l.O
,~ the relevant pixel bits migrate into the fractional portion of the product and ~e~u~e only one accwmulatiQn occurs.
On th other hand, i I~SFAC is greater ~han l.O the relevant pixel bits will migrate into high-order bits and there may be several accumulations. The accumulator must therefore b~ 24 bits wide and contain 8 fraction bits.
The accumulator value is eventually sc-aled to the final output value by SIZFAC. ~nly 8 bits of this final scaling are needed. The 8 bits to the left of the decimal point are the desired bits. The possible values th~t can accumulate are clirectly related to the value of I~SFAC and SIZFAC. Therefore, the value of SIZFAC is directly related to the range of possible values in the accumulator and the rele~ant bits of both SIZFAC and the accumulator which produce the desired 8 bits can be determined.
SIZFAC can be normalized so that its high-order bit is a 1. I the value is truncated to its 8 high order bits and the position of the resulting decimal point noted, the resulting value might, for instance, hav~ 6 fraction bits. Based cn the valua of SIZFAC then the relevant bits are picked out of the accumulator value which has 8 fraction bits. The value picked is the value wit~ enough fraction bits to bring the total of fractlon bits between it and SIZFAC to 8. When the two numbers are multiplied toge~her the 16-bit product has 8 fraction bits and the 8 high -order bits are the desired bits left of the decimal point for the output pixel value.

TWO-AXIS FAST MEMORY
The memory serves the pixel processors by delivering and receiving streams of consecuti~e pixels of a specified row or column. ~he line microcomputer will load the image row and column address into the memory address counters. It specifies wh~ther ~he address is to be incremented as a row or column and wh~ther read or write operations are to be performed. The memory respond~
to requests for the next pixel from the pixel proces~or.
For each new line the memory i5 reset to a new row and column address by the line microcomputer.
The m~mory must respond to requests at a maxLmum rate of one eve~y 100 nanoseconds. This speed is achieved more easily by a technique which involves orga~izing the memory in four banks of 8 bits each. In this manner, four pixels can be delivered or stored in a ~ingle memory cycle and pixels can be moved four times faster than the basic memory speed allows. As shown in Figure 37, fast access in both rows and columns of the image is achieved by mapping the image into the memory spirally such that any four co~secutive pixe~ls of any row or column resides in separate memory banks.

IMAGE ADDRESS TO MEMORY ADDRESS MAPPI~G
Figures 38 - 40 show examples of how the image address ~o memory address is mapped. The row and column image address is stored in up/down counters and mapped internal.~y to a memory address~ ~he mapping entails incrementing either the row address for column-oriented access or the column address for row-oriented access. The determination of the lower order 2 bits of the 16-bit memory address and the control o the rotating address orientation of the input and output registers for each m~mory bank are the more esoteric aspect~ of the address mapping.
The upper 7 bits of the 16 bit memory address comprise the upper 7 bits of the 9 bit column addr~ss.
The next seven bits of the m~mory address are the upper 7 bits of the 9 bit row addressO The lower 2 bits of the memory address are a function of the lower 2 bits of either the row or column address based on the row/column flag. For the row~oriented access mode the lower two bits of each bank are identical and are the lower two bits of the row addressO For column-oriented access the lower two address bits are different for each m~nory bank and are rotated according to the lower two bits of the column aadress.

Lower 2 BanX A BanX B Bank C Bank D
Column Bit~

Ql 11 OO Ol lQ

Ccntrol ofthe input-output registers i5 identical for bo~h row and ~olumn a~cess modes and is a functi~n of ; the lower two bit of both row and column. The register address assignment rota~es depending on the row or column being accessed. Considering only the lower two bits the zero pixel for a zero column i5 in Bank C, etc. The same is true for rows. Th s rota~ing register address can be Lmplemented by assigning Q ts Bank A; 1 to Bank B, etr., and by adding modulo 4 the lower two bits of row and column addresses.
For each request from the processor the proper rowor column address is incremented. Pixelsaremultiplexed out of output registers or into input registers~ When the lower 2 bit~ of the incremen~ing address change from 11 to 00 a memory cycle is initiated to store four input pixels or read the next four pixels.

LAROE/SMALL CH~NNEL PROCESSORS

As previously stated to construct a CGSI scene each object, surface, and ~pecial effect (OSSE~ image pass through a processing channel. The siz~ of each OSSE may range from a pixel to the! entire screen. In most scenes, small (e.g. an area less than 1/16 of the screen3 objects out number large objects (e.g. an area greater than 1/16 of the screen~. The processing channels are designed with the capability to operate on an entire frame. These are called large channel processors. The use ofa small fraction such as only 1/16 of a frame i9 very inefficient. Three choices e~ist: run inefficiently with parallel large fr~me processors, build a special purpose small OSSE processor, or pass a plurality of, sa~ 16 OSSE's ~hrough a large 4~ .

channel proc0ssor. The last choice, of course, is by far the most practical.
A plurality of small OSSES may be passed through the large channel processor in either a parallel or serial manner as shown in Figure 410 In the parall~l appxoach, 16 small OSSE's are loaded in one memory plane. For each line (column) pass, the processor changes factors four times. The output of the proce~sor is loaded in an output memory plane. The OSSEs are positioned wi~hin their cell of the memory plane. An X and Y screen address of the c.ell and the positions of the OSSE within the c:ell d~termines the position of the image for the scene con~truction module.
The serial approach passes entire small images ~hrough the processor first in Y then X. The serial method uses 16 small input and output: memory planes.
As previously stated, one inherent prior art CGI imaging problem involves edge aliasing or the lack of edge feathering or smoothing in the transition from object to bacXground whic~ leads to cartoonish repres~ntations, 20 One distinct advantage of the continu~us interp~lation system o~ the present lnvention is the elimination of edge aliasing in the edge detalls of the pictorial Lmages.
The pictorial images produced, as by photography~ are realistic reproductions of objects where the boundary ~ransitions between each object and i~s background are ~ nGt step function~ or ~udden changes but rather gra~ual ~lf~ $~

or feathered transitions. The interpolation character-istics of the present invention faithfully xeproduce these precise intensity changes w~ich occur between the object and the background so as to portray softened or smoothed 5 edges which enable high fidelity. This is in sharp contrast to the decidedly large jumps in intensity levels between adjacent pixels which characterize the sharp edges and yield the cartoonish effect referred to above.

PERSPECTIVE WARP TECHNIQUE

In the case of linear warping, the advantage of the in~erpol2tion technique is that most of the highly variable calculations can be performed at the frame level where there is plenty of time avaiLable. The line calculations are very simple and the pixel interpolator need be set up with but a few parameters and turned loose on a line of pixels. ~le linear interpolation approach achieves the correc~ ou~line for perspective transform but ~he mapping o the internal data is not c~rrect because it is nonlinear.

This nonlinearity is manifested in the continuous interpolation process in the form of a continuouslychanging size factox for each new output pixel. 1~us, wi~h -the linear transform the valuP of I~SFAC i~ constant o~er an entire column or line;wher~as wi~h the p0rspectivetranso~m t~e value of I~SFAC may be different for each output pixelO

3~

It is desireable that the function for the changing value of INSFAC or the changing size factor be characterized with simple enough computations that they may be embedded in low cost real time hardware. This may be accomplished by a two-pass operation in which the vertical and horizontal passes are considered in terms of vertical planes and horizontal planes instead of just rows and columns. The first pass utilizes a series of projections of each object column onto a vertical plane and the second pass utilizes a series of intersections of the object with planes projected from the origin through each line on the screen.
The computation related to the plane is illustrated in Figures 44A and 44B. The origin eye of the observer at 0 becomes the origin oE a coordinate system. The line AB represents the viewing screen. The line CD
is a line representing an object in space behind the screen. The lines emanating from the origin depict line-of-sight rays intersecting the screen AB at one pixel increments. These rays also intersect the object line CD.
The point where a ray intersects the object line maps onto the screen at the point where that same ray intersects the screen.
Therefore ~he portion of the object line between any two ray intersections is the portion o~ the input image that maps to ~he screen pixel be~ween the intersection of those two rays and the screen. The length of the segment of CD between any two rays is the number of input 2~i~

pixels, that contribute to the corresponding output pixel, or the value of INSFAC.
To obtain the value of I~SFAC for each output pixel for the interpolation power processor it is necessary 5 only to trace rays from ~he beginning of the object line to the end, solve for the intersection of each ray, and ind the distance between in~ersec~ions.
The interception equation (Figure 45) is quite simple and contains constant terms, ~or the most part.

The ray line passes through the origi~-and is characterized ~y its slope which depends on the screen distance and the screen coordlnate. The screen coordInate is the snly value of the equation that changes as the ray is traced.
~he object line ~quation i5 characterized in term~ of its end points. MOBJ is defined as the slope of the line. The interception equation solves or the Z
coordinate of the intersection of ~he two lines~ A
subtraction of Z coordinates of the previous intersection yields the horizontal clistance bet~een the iwo inter-sections~
It is seen in Figure 44A that the object lineCD forms a right triangle within the coordinate system and each intersec~ion segment ~ormsa similar righttrian~le.
The ratios of tha leng~h CD to the horizontal distance betw~en C and D is the same as ~he ra~io ofeach intersec~ion segment to its horizontal distance. ~his constant ratio 6~
^ 52 RATIO may be determined directly from the endpoints of the line CD and the length of the input line and may be applied to the hori~ontal distance between intersections to determine the lengths of the segment and the next value 5 of I~SFAC.
The computation conslsts of applying the changing screen cooordinateSpropagating through the equation. As shown in Figure 46, this readily lends itself to pipelining in hardware.The pipeline delivers a new value of INSFAC
to the interpolation processor for each new output pixel.
The correct object line C~ for each column and each row may be characteri ed by projections and inter~ections of the ob~ect in 3 space onto planes. This i5 accomplished by a two~-pass procedure.
The first pass which is illustrated by Figure 47 utilizes a vertical YZ plane and projections of columns of the o~ject onto this plane. This may be accomplished by determining ~he YZ coordirlates o the tcp and bottom 3f each column of pixels in ~he object image in 3 space.
The YZ coordinates of these two point~ in each relevant column are the endpoints of the object line in the YZ
plane ko be traced with rays in the in~erpolation process as represented in Figure 44~
~s~ra~el i n The second pass~Figure 48 and Figure 44B utilizes planes projected ~rom ~he origin through each successive line on ~he ~creen. The intersection o~ that plane and the object again defines the line for the ray tracing process. This line i5 determined by it~ endpoints in the plane and these endpoints are found by finding the intersection with the plane of the two 3-dimensional lines defined by the edges of the object in 3 space.
The two pass procedure utilizing the ray traciny along projected object lines to drive the continuous interpolation process achie~es a mathematically correct and high fidelity perspective transform of a plane image onto a viewing screen. This is ill~strated for both the linear and perspective situations in Figures 4~k ~e~ and The treatment of images in perspectiYe has been described in ~echnical terms. As a furt~er aid to more fully understanding ~he perspective warping of images, the following explanation is provided.
It will be remembered that any frame, w~ether it is to be portrayed on the screen either in linear or perspective form, is stored in memory in the same way.

The data for the frame is a 512x512 row and column pixel array with associated intensity values.
For the perspective portrayal t~e FOV program calculates the coordinates of the ~our coxners of the fr2me in 3~space which is the coordinate system which has the receptor of the scene recognition system, which may be an observer, as the origin. ~l example of a rame lO0 in 3-space is shown in Figures 47 and 480 Referring to Figures 44~ and B and Figures 47 and 48, the screen AB in front of origin or the eye O of the observer is an XY
plane a predetermined distance from the origin.
As shown in Figure 47, the 512 columns o the fram~ 100 are sequentially projected to a line CD in the YZ plane which plane does not have an orientation relative to the X-axis~ In each case the line CD ~referred to as an object line~ is a leg of a right triangle for which tl~e respective frame column is the hypotenuse~ The characteristics of interest of each object line CD are its end coordinates in the YZ plane in which it appears and æuch coordinates are calculated and stored.
Each of the 512 object line~ CD is subjected to an~ 47 a vertical pass opera~ion as indicated in FigureS44~,,which is in a YZ plane, which contains the origin 0. Scan or ray li~es 101 e~tend from the eye or origin 0 through screen AB, there being one pixel ~acing between each pair Gf adjacent rays. The rays 101 also interect the : ~o o~ject line CD as indicated.
Object line CD was derived fro~ a frame column having S12 pixels and for purposes of calculation is considered to hav~ a corres~onding leng~h scalea to 512 units . The segment~ 102 o the 1 ine CD :~ormed by .the intersecting rays 101 are of unequal lengths and such leng~h~, based on a total l~ngth o 512 uni~s for line ~L2~3~

CD, are calculated by equations as reEerred to above and as set forth in Figure 45.
With the lengths of the segments 102 known, the total assumed length of 512 units for the :Line CD are prorated relative to the individual segments. This step provides a pixel ratio between each segment 102 and the corresponding line segment of screen line AB and this ratio is the INSFAC value for each segment 102. As the lengths oE segments 102 vary relative to each other, the values of INSFAC for the respective segments varies correspondingly.
Using the stored pixel intensity values of each frame column, the sizing and interpolation process explained above in connection with the linear warp is used to obtain the corresponding line 105 in screen AB for the intermediate image.
Repeating the above process Eor each of the 512 object lines CD
results in an intermediate perspective image as illustrated in Figure 42 in which 512 vertical lines corresponding to the columns of Erame 100 com prise correctly sized and positioned vertical components of the final image.
In the second pass, illustrated in Figures 44B and 48, planes 103 radiating from the origin extend through rows 104 of the screen AB which rows are spaced one pixel apart. Planes 103 intersect frame 100 in lines of intersection PQ which are indicated in Figures 44B and 48 and to some extent are analogous to the lines CD of the vertical pass.
The lines PIQ' may be considered second pass construction lines because each of them is projected -to the horizontal X7. plane which contains the origin or eye 0 of the observer. This is the plane XZ shown in Figures 44B and 48 where the projected construction lines P'Q' are identified as lines PQ and are referred to as second pass object lines.
The width of the intermediate image corresponding to each construction line P'Q' is (or is assumed to be) equal to the length of the ~,'1 , ,i ~; r 36~

second pass object line PQ. The line 104 of screen AB, which is a projection back from line P'Q', is a final output line. A line through the intermediate ima8e at the same level as a line P'Q' will have to be mapped onto the corresponding screen line lO4.

,1 , ~A

Referring to Figure 44B, vertical planes 106 through the origin and screen AB (spaced one pixel apart), and one of the second pass object lines PQ, divide the line PQ into a series of segments Xl, Xl, X3, etc., which inherently are of different sizes.
The length of line PQ corresponds to the width of the intermediate image at the vertical level of line 104 (FigureS48). The pixel columns of the intermediate image are equally spaced because the first pass operation did not disturb the horizontal spacing of the columns of the input frame 100.
The segments Xl, X2, etc. of each second pass line PQ each represent a number of intermediate image pixels corresponding to their respectiv~ lengths such that the pixels are pro rated wi~h respect to them. As the spacing of the rays 106 through line 104 is at a one pixel wid~h, the ratio of the number of pixels represented by each of the sPgments Xl, X2, etc. relative to the corresponding one pixel spacing in line 104 of screen AB

is equal to I~SFAC which may have a different value for each of the segments Xl, X2 etc. of line PQ.
U~ing the s~ored pixel inten ity values of each line in ~he intermediate image, the sizing and interpolation process explained above in connec ion with ~e linear warp algorithm is used to obtain the corresp~nding line 104 in screen ~B and all the other lines thereof for the final image~

ALTER~ATIVE ALGORITHM
An alternative system may be employed wherehigher resolution must be retained as objects approach the viewer.
This approa~h assumes that the input image resides in a memory addressable as a grid in which the grid intersections are the points at which input i~age intensities are known.
Ea~h output pixel may then be proj ected into the grid of the input image. The relative intensity o the output pixel is computed from t~e region occupied by the projected output pixel. In Figure 49, a projected output pixel is represented by the polygon formed by t~e dashed lines.
The intensity computed for an outpu~ pixel may be an area weighted average of the smaller regions forming the inside of the projected output pixel.
This procedure will ba explained for one typical pr~jecte~ output pixel iLn terms of Figure 49. In t~e figure, the rows of the input image grid are identi ied 2~ by the letters A, B, C, D, and the column5 by the letters a, b, c, d~ e smaller grid regions forming the inside of the projected output pix21 are identified by the n~nbers 1, 2~ 3, 4, 5, 6, 7, 8, 9. Each smaller region is bordered by solid and/or dashed linas. Region 1, for example, is bordered by the upper and letmost ~L2062~0 dashed lines and by the ~olid lines forming ~he bottom of row A and the right adge o column b.
The inten~ity of the output pix el is the area weighted average, in which output = ' 1 ( intensityj 3 ( areaj) where intensityj= ~ (corner intensities for each smaller region j), and area j is the area of a smaller region expressed as a percentage of the total pro~ected output pixel's area enclosed by the dashed polygon.

The corner int~ensities for a small region ~re bilinear interpolations f:rom the four nearest grid corners of the input image. Using Region 1 as an example, the intensity at the upper left corner of Region 1 is computed as the bilinear interpolant of the four corners of tXe sq~re formed by Row A and Column b.. The inten~ity of the upper right corner of Region lis the bilinear interpolant ~0 of the four corners of the square formed by Row A and Column c. The intensity of the lower right corner of Region 1 is the bilinear interpolant of the foux corners of the square formed by Row B and Column CD The intensity of the lower l~t corner of Region 1 is the bilinear : 25 interpolant of the four corner~ of the square formea by . 60 Row B and Column b. Th,_se intensities or the Region 1 corners are averaged to form intensityj where j=l. ~his is the value multiplied with area; to form the fi-st of the nine products summed to compute the projected output pixel's intensity. In this manner, the corner intensities for each small region are similarly interpolated then averaged to produce a single value to multiply with each region' 5 area expressea as a percentage of the large region.
These products may then be summed to compute the output pixel intensity.
SCENE CONSTRUCTIO~
A scene construction module is pro~ided which assembles the individual objects be:ing processed into a single scene or frame with each object positioned appropriately and viewed according to whether or not it is occluded by other objects.
The block diagram ofthe sceneconstructionmodule shown in Figure 50 indicates ~hose subfunctions necessary to implement all of the generic tasks required of this function. The following sections will describe each of these subunctions in more detail.
Channel combiner 80 forms the heart of the scene construction module, for it is here that ~he video data from multiple sources or channels is combined on a pixel~by-pixel basis to form the final composite scene or picture. The term "channel" i~ used here to refer to a source of video d ata . Of cour se, e ach o f the se sources may be expanded to include one or more colors. As shown in Figure Sl, the channel combiner 80 accepts video fro~
the surface and object channels. The channel combiner also accepts range information for each displayed object from the object and software controllers as indicated in the block diagram of Figure 3. The channel combiner outputs a channel of video data and a "trigger" ~ignal to a smoothing input 82 which performs the smoothing subfunction.
A channel combiner implementation is presented in Figure 51. Three basic elements are defined to implement channel combinations which are the object switch, the serial-to-parallel interface ~S/P -I/F), and a trigger generator 84.
As shown in Fic~ure 51, the final object switch element 85 accepts video data from two channel sources, and range information from either the surface and object controller Ivia the serial to-parallel interface) or the previous object switch. m e object switch then outputs on a pixel-by-pi~el basis the selected video channel and the appropriat:e range of that channel. The selection basis can be termed "nearest occupie~" in that the video output is that of the object closest to the viewer that actually has non-z~ro pixel data. One single range value is used to describe bot~ two-dimensional objects and three-dimensional objects. Object daka is assumed to be ~3 ~- 62 embedded in a "field of zeroes." Each ob ject switch in the array also outputs a "switch select ~ignal" which is input to ~he trigger generator B4.
As shown in Figure 51~ trigger generator84accepts the "switch select" signals (the gating network output which also controls the range and video select muxes in the switch) from all of the object switches in the array.
The output of the trig~er generator is a single "trigger"
signal which is used by the smoothing function 82 to control start ofsmoothingr Characteristicsof the signal generator include (1) all changes in "switch select" signal inputs which affect the video output to the display must cause the "tri~ger'~ signal to activate, and (2) the throughput delay occasioned by the number of pipeline stages of the trigger generator must match the delay of the video path to the ~moothing subfunct:ion.
Scene value ad~ustment is performed by 2 ~cene value aajus~ment unit 86 which is used where scene-wid~
intensi~y corrections are required. 5uch corrections may be appliea to compensate for day/night lighting, haze, 2G rain, etc. These are ~ypically initial conditions, or very slowlychanging ¢onditions. The scenevalue adjus~ment accepts video data from the channel combiner80 and intensity correction values from ~he FOV compu~er. Outpu~ video from this subfunction is applied to the smoothing subfunction.

~2~ 6~

The smoothing subfunction performed by the smoothing unit 82 is used to simulate edge characteristics o the sensor. ~n edge refers to any adjacent pixels on a display lin~ where a boundary exists. Such boundaries include those defined by objects overlaying other objects, or the transition from background to ob~ect While several different typ~s of edge smoothing algorithms may be used, a two~to-eight pixel process using Gaussian plxel weighting is prefexred.

SPECIAL EFF~CTS
The special effects function performed by the special effects unit 12 may add translucent smoke, haze, or dust into the scene. These effects also have a range and may appear ahead of or behind other objects in the scene. A block diagram of the special effects function is shown in Figure 52. Two subfunctions are necessary to implement thi~ function" n~nely, a serial-to-parallel interface (S/P~I/F) and a special effects switch 88.
~he S/P~I/F performs its function by accepting serial data ~in this case from th~ FOV computer) and loadiny parallel range data into the range r~gister of the special eects switch.
The special effects switch 88 is quite similar to an object switch. A "nearest occupi~d" algorithm may ~till be used to select the range value passed on to th~

next stage and influences how the channel i and channel i+l videos are combined. The actual co~bination is not a simple switch implemented by a mux in khe object switch but is an arithmetic combination which is influenced by the "ne~rest occupied" channel decision and a conkrol or select signal from the FOVcomputer. The actua~ combination method is probably similar to the equation Y = ai ~ b(1~2) or bi + a~i~l).

Claims (23)

THE EMBODIMENTS OF THE INVENTION IN WHICH AN EXCLUSIVE
PROPERTY OF PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:

1. A method of mapping in a 3D coordinate system of 2D input images of views of objects stored in a data base to output images in a moveable rectangular viewing plane having a rectangular column and row pixel matrix, said system having a main axis extending normal to said viewing plane and having a viewing point thereon in spaced relation to said viewing plane, said method comprising the steps of:
representing each of said 2D images as a rectangular matrix of pixel intensity values arranged in columns and rows of pixels and having corner coordinates;
establishing a rectangular pixel matrix of each of said stored 2D images;
computing four corner coordinates for an output image in said viewing plane corresponding to said corner coordinates of any selected one of said 2D images;
making two orthogonal passes wherein said first pass is over said input image to form an intermediate image having columns and rows of pixels and corner coordinates determined by said computed four coordinate corners of said output image, and wherein said second pass is over said intermediate image to form said output image with columns and rows of pixels and corner coordinates determined by said computed four coordinate corners of said output image;
making line transformations in said first pass wherein said input image columns are converted to said intermediate image columns with said intermediate image columns having lengths derived from said input image columns establishing respective ratios defining the lengths of said input image columns relative to said intermediate image columns;

making line transformations in said second pass wherein said rows of said intermediate image are converted to said output image rows on said viewing screen with said output image rows having lengths derived from said intermediate image rows establishing respective ratios defining the lengths of said intermediate image rows relative to said output image rows;
calculating and forming for each of said line transformations from said ratios, the number of input pixels required respectively from said columns of said input image and said rows of said intermediate image to create output pixels respectively for said intermediate image columns and for said final image rows;
mapping said input pixels sequentially and fractionally to said output pixels for each of said line transformations; and summing and averaging said intensity values of said input pixels corresponding to each said output pixel and respectively accruing composite values so obtained to said output pixels.

2. A method of linearly mapping a rectangular digital input image having columns and rows and corner coordinates, and represented as a pixel matrix of intensity values, to any predetermined quadrilateral having columns and rows and corner coordinates, comprising the steps of:
performing sequentially two orthogonal scanning passes of said input image wherein said first pass forms from said input image an intermediate image having columns and rows of pixels and corner coordinates and said second pass forms an output image having columns and rows of pixels and corner coordinates from said intermediate image;
performing line transformations during said first pass whereby said columns of said intermediate image correspond to said columns of said input image and have lengths and positions determined from said coordinates of said quadrilateral;
performing line transformations during said second pass whereby said rows of said output image correspond to said rows of said intermediate image and have lengths and positions determined from said coordinates of said quadrilateral;
calculating for each of said line transformations (1) the vertical ratios of the respective lengths of said columns of said input image relative to said columns of said intermediate image and (2) the horizontal ratios of the respective lengths of said rows of said intermediate image relative to said rows of said output image;
calculating a pixel ratio for each of said line transformations from said vertical and horizontal ratios to determine respectively, for each of said line transformations, the number of said input image pixels required to create said intermediate image pixels and the number of said intermediate image pixels required to create said output image pixels and calculating, for each of said created intermediate and output pixels, an average intensity value from the intensity values of said input and intermediate pixels respectively; and mapping said input pixels sequentially and fractionally to said intermediate pixels and mapping said intermediate pixels sequentially and fractionally to said output pixels for each of said line transformations.

3. A method of mapping a digital input image to a viewing plane which is moveable in a 3D coordinate system and wherein said image comprises elements arranged in columns and rows of pixels representing a matrix of pixel intensity values in said system, said system having an observation point on a main axis thereof and a viewing plane having a format with columns and rows extending normal to said axis and spaced from said observation point, said system defining a reference plane parallel to said main axis and extending normal to said viewing plane, comprising the steps of:
projecting, sequentially the orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane;

processing each line of said first pass object lines by projecting divergent lines from said observation point to said each line of said first pass, object lines through said viewing plane to define an intermediate image line coincident with said viewing plane having equal line segments of at least one pixel, said divergent lines intersecting said each line of said first pass object lines resulting in corresponding line segments between said divergent lines having respective lengths equal to the number of said pixels separating said divergent lines;
calculating pixel ratios of said line segments of each line of said first pass object lines to corresponding line segments of said intermediate image line;
mapping said elements of each of said columns of said digital input image sequentially and fractionally to said line segments of a corresponding line of said first pass object lines;
projecting divergent planes from said observation point through said rows of said viewing plane, said divergent planes having a separation of at least one pixel in said viewing plane, each of said divergent planes intersecting said viewing plane to form a final image line and intersecting said input image to form a second pass object line;
processing each said second pass object line by extending second pass divergent lines from said observation point through said columns of said viewing plane having a separation of at least one pixel in said viewing plane and through said second pass object line to form segments thereof, said second pass divergent lines intersecting said viewing plane to form horizontally extending correctly positioned final image rows with each of said final image rows having segments with lengths proportioned to the number of said pixels of corresponding ones of said segments of said second pass object line;
calculating pixel ratios of said line segments of each line of said second pass object lines to corresponding line segments of said final image row; and mapping pixels to a row of said final image rows sequentially and fractionally from said segments of a corresponding said row of said final image.

4. A method of mapping a digital image in a 3D coordinate system to a viewing plane which is moveable in said system, said system having a viewing point and a main axis extending normal to said viewing plane and through said viewing point, said system having a reference plane containing said main axis and extending normal to said viewing plane, said method being applied to a digital input image arranged in columns and rows and represented as a matrix of pixel intensity values, said input image being on the opposite side of said viewing plane from said viewing point, said method being applicable to map said input image to said viewing plane and comprising the steps of:
projecting, successively and orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane;
processing each of said first pass object lines in sequence by extending radiating rays in said reference plane from said viewing point through said viewing plane and said first pass object line, said radiating rays (1) intersecting said viewing plane to form an intermediate image line with segments each having the length of one pixel and (2) intersecting said first pass object line to form segments;
processing said input image rows with respect to said first pass object line segments to obtain a pixel ratio for each of said first pass object line segments relative to each corresponding one of said intermediate image line segments;
mapping said pixels of each of said input columns sequentially and fractionally to said line segments of each corresponding one of said first pass object lines;
summing and averaging for each said segment of each of said first pass object lines said intensity values of said pixels mapped thereto to obtain a composite value and applying said composite value to corresponding ones of said intermediate image line segments;
processing said intermediate image by extending radiating planes from said viewing point through said rows of said viewing plane having one pixel separation and through said input image, each of said radiating planes intersecting said input image to form a second pass object line;
processing each of said second pass object lines by extending second pass radiating rays from said viewing point through said columns of said viewing plane having one pixel separation and through said second pass object line;
said second pass radiating rays intersecting said viewing plane to form a horizontally extending correctly positioned final image line with segments each having the length of one pixel and intersecting said second pass object line to form segments each having a different length;
processing said intermediate image rows with respect to said second pass object line segments to obtain a pixel ratio for each of said second pass object line segments relative to a corresponding one of said final image line segments;
mapping said pixels of each of said intermediate image rows sequentially and fractionally to said line segments of each corresponding one of said second pass object lines;
summing and averaging for each said segment of each of said second pass object lines said intensity values of said pixels mapped thereto to obtain a composite value corresponding to each of said final image pixels and applying said composite value to corresponding ones of said final image line segments.

5. A method of mapping in a 3D coordinate system having a viewing point on a main axis thereof and a viewing plane extending normal to said axis amd spaced from said viewing point, said system having a reference plane containing said main axis and extending normal to said viewing plane, said method being applied to a digital input image arranged in columns and rows and represented as a matrix of pixel intensity values, said input image extending obliquely relative to at least one of said planes, said method being applicable to map said input image to said viewing plane, and comprising the steps of:
projecting, successively and orthogonally, said columns of said input image to said reference plane to form first pass object lines in said reference plane;
processing each of said first pass object lines in sequence by extending radiating rays in said reference plane from said origin through said viewing plane and said first pass object line, said radiating rays (1) intersecting said viewing plane to form an intermediate image line with segments each having the length of one pixel and (2) intersecting said first pass object line to form segments;
processing the total number of said input image rows with respect to said first pass object line segments to obtain a pixel ratio for each of said first pass object line segments relative to a corresponding one of said intermediate image line segments;
mapping said pixels of each of said input columns sequentially and fractionally to said line segments of each corresponding one of said first pass object lines;
summing and averaging for each segment of each of said first pass object lines the intensity values of each pixel mapped thereto and applying the composite value to corresponding ones of said intermediate image line segments;
processing said intermediate image by extending radiating planes from said viewing point through rows of said viewing plane having one pixel separation and through said input image, each of said radiating planes intersecting said viewing plane to form a final image line and intersecting said input image to form a final image line and intersecting said input image to form a second pass construction line;
projecting each of said construction lines to a plane which is normal to said viewing plane and contains said main axis to form second pass object lines;
processing each of said second pass object lines by extending second pass radiating rays from said origin through said columns of said viewing plane having one pixel separation and through said second pass object lines, said second pass radiating rays (1) intersecting said viewing plane to form a horizontally extending correctly positioned final image line with segments each having the length of one pixel and (2) intersecting said second pass object line to form segments each having a different length;
processing said intermediate image rows with respect to said second pass object line segments to obtain a pixel ratio for each of said second pass object line segments relative to a corresponding one of said final image line segments;
mapping said pixels of each of said intermediate image rows sequentially and fractionally to said second pass object line segments of each corresponding one of said second pass object lines; and summing and averaging for each segment of each of said second pass object lines said intensity values of said pixels mapped thereto to obtain a composite value corresponding to each of said final image pixels and applying said composite value to corresponding ones of said final image line segments.

6. A method of mapping input pixels from an input pixel line in an input image to output pixels in a corresponding output pixel line in an output image, comprising the steps of, determining pixel transformation starting points for said input and said output pixel lines, and mapping from said input pixel line to said output pixel line by beginning at said starting points and assigning sequentially and contiguously, on a fractional basis, the number of said input pixels required to generate each of said output pixels.

7. A method according to claim 6 wherein said input pixels have intensity levels and said intensity levels of said input pixels of each said number of input pixels are summed and averaged to provide the intensity level for the correspond-ing one of said output pixels.

8. A method according to claim 6 wherein said input pixels have intensity levels and said intensity levels of said input pixels of each said number of input pixels are summed and averaged to provide a related intensity level for the corresponding one of said output pixels.

9. A method according to claim 6 wherein said number is a constant for said line.

10. A method according to claim 6 wherein said number is a variable.

11. A method according to claim 6 wherein said lines are rows.

12. A method according to claim 6 wherein said lines are columns.

13. A method according to claim 6 wherein said output image is an intermediate output image.

14. A method according to claim 6 wherein said input image is an intermediate input image.

15. A method according to claim 6 wherein a plurality of input pixel lines and output pixel lines are mapped sequentially.

16. A method according to claim 15 wherein said input pixels have intensity levels and said intensity levels of said input pixels of each said number of input pixels are summed and averaged to provide the intensity level for the corresponding one of said output pixels.

15. A method according to claim 15 wherein said input pixels have intensity levels and said intensity levels of said input pixels of each said number of input pixels are summed and averaged to provide a related intensity level for the corresponding one of said output pixels.

18. A method according to claim 15 wherein said number is a constant for said line.

19. A method according to claim 15 wherein said number is a variable.

20. A method according to claim 15 wherein said lines are rows.

21. A method according to claim 15 wherein said lines are columns.

22. A method according to claim 15 wherein said output image is an intermediate output image.

23. A method according to claim 15 wherein said input image is an intermediate input image.