Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-02-27
2001-01-23
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06177943
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to a method for compressing a digital elevation database for a system for displaying three-dimensional terrain data.
2. Discussion of Prior Art
Copending patent application “Digital Map Generator and Display System”, Ser. No. 08/944,366 filed Oct. 6, 1997 by the present inventor, describes a digital map system for displaying three-dimensional terrain data using terrain data in the form of polygons. The polygon database is produced from a database of elevation points which are divided into m×n cells which have an elevation point in the center of the cell. The center point forms four polygons with the corners of the cell. The elevation of the center point may be chosen to be the highest elevation point in the m×n cell, the average elevation of the elevation points in the m×n cell, or the elevation of the actual center point.
Other systems using elevation data directly have been developed that present an apparent three-dimensional effect as well as some that present a mathematically correct texture-mapped three-dimensional projected display. Both of these systems require a very large amount of storage for terrain data.
The 1987 patent to Beckwith et al. (U.S. Pat. No. 4,660,157) compresses terrain data using the Discrete Cosine Transform and stores it on a tape. The compressed data is read from the cassette tape in a controlled manner based on the instantaneous geographical location of the aircraft as provided by the aircraft navigational computer system and reconstructs the compressed data by suitable processing and writing the reconstructed data into a scene memory. Further processing of the data provides a 3D perspective on the display. The aircraft's heading is accounted for by controlling the way the data is read out from the scene memory. Different heading angles result in the data being read from a different sequence of addresses. Since addresses exist only at discrete locations, the truncation of address locations causes an unavoidable change in the map shapes as the aircraft changes heading. Beckwith's method displays only discrete points. This is made very apparent in Beckwith's use of a ‘column max memory’ in order to eliminate hidden points. The present invention mathematically rotates terrain polygons as the aircraft changes attitude. The resolution is determined by number of bits used to represent the vertices of the polygons, not the number of storage addresses. Further, the present invention displays three-dimensional projected polygons, not discrete points as produced by Beckwith.
The 1989 patent to Chan et al. (U.S. Pat. No. 4,884,971) teaches a method of interpolating elevation values using polynomials. The interpolated values are used in a radar simulator.
The 1990 patent to Beckwith et al. (U.S. Pat. No. 4,970,682) teaches a database consisting of rows and columns of digital elevation points, which is first compressed using the hybrid discrete cosine transform (DCT) compression algorithm, with differential pulse code modulation (DPCM) being used to transmit the DCT coefficient differences between each row of grid points. During operation the compressed data are read from the cassette tape, reconstructed, and stored in a scene memory with a north-up orientation. A read control circuit then controls the read-out of data from the scene memory with a heading-up orientation to provide a real-time display of the terrain over which the aircraft is passing. The display provided by this system is in the form of a moving map rather than a true perspective display of the terrain as it would appear to the pilot through the window of the aircraft. Note also that the display does not reflect the roll or pitch angles of the aircraft, only the aircraft's heading. Because the Beckwith patent accounts for the aircraft's heading by controlling the way the data is read out from the scene memory, different heading angles result in the data being read from a different sequence of addresses. Since addresses exist only at discrete locations, the truncation of address locations causes an unavoidable change in the map shapes as the aircraft changes heading.
The 1993 patent to Dawson et al. (U.S. Pat. No. 5,179,638) shows a a method and apparatus for providing a texture mapped perspective view for digital map systems which includes a geometry engine that receives the elevation posts scanned from the cache memory by the shape address generator. A tiling engine is then used to transform the elevation posts, where each square cell is divided into two three-dimensional triangles.
The 1994 patent to Femal et al. (U.S. Pat. No. 5,299,300) teaches an improvement over the Beckwith '682 patent. Where Beckwith teaches database compression by using the Discrete Cosine Transform, Femal achieves database compression by omitting every other row and every other column of the original database. In both Beckwith and Femal, during operation the compressed data are read from the cassette tape, reconstructed, and stored in a scene memory with a north-up orientation. A read control circuit then controls the read-out of data from the scene memory with a heading-up orientation to provide a real-time display of the terrain over which the aircraft is passing. However, whereas in Beckwith the addresses are truncated, causing an unavoidable change in the map shapes as the aircraft changes heading, Femal uses bilinear interpolation to create a plurality of interpolated addresses to create a smoother appearance as the data are read out.
Accordingly, one of the objects and advantages of my invention is to provide a digital map system that produces a mathematically correct three-dimensional projected view of the terrain, using polygons, while reducing the amount of storage required for the database. The invention can be used in a flight simulator or in a video game or in other systems where it is not necessary to exactly reproduce the terrain.
Further objects and advantages of my invention will become apparant from a consideration of the drawings and ensuing description.
SUMMARY OF THE INVENTION
The present invention is a method for compressing a digital elevation database to produce a compressed digital map database which is used by a digital computer system for displaying three-dimensional terrain data in the form of polygons. The compressed digital map database is produced from a database of elevation points by selecting every mth row and every nth column, thereby resulting in a reduction of database storage requirements. During program run-time the intersection of rows and columns forms cells with four corners. The elevation value of a center elevation point for each cell is formed by various methods, thereby creating a cell made up of four three-dimensional triangles. One method for creating the elevation of the center elevation point uses the elevations of the four corners of the cell. Another method uses extrapolated elevation values from the cell's extended diagonals. The three-dimensional triangles formed from the center elevation point are then transformed and projected using standard computer graphics methods to produce a three-dimensional projected display.
REFERENCES:
patent: 4660157 (1987-04-01), Beckwith et al.
patent: 4884971 (1989-12-01), Chan et al.
patent: 5140532 (1992-08-01), Beckwith et al.
patent: 5179638 (1993-01-01), Dawson et al.
patent: 5299300 (1994-03-01), Femal et al.
patent: 5781195 (1998-07-01), Marvin
patent: 5809179 (1998-09-01), Marimont et al.
patent: 5850226 (1998-12-01), Nagasawa et al.
patent: 5917495 (1999-06-01), Doi et al.
patent: 5923329 (1999-07-01), Beale
patent: 5943057 (1999-08-01), Ohba
patent: 5945976 (1999-08-01), Iwamura et al.
patent: 5963209 (1999-10-01), Hoppe
patent: 5970682 (1990-11-01), Beckwith et al.
patent: 5974423 (1999-10-01), Margolin
patent: 6020893 (2000-02-01), Freeman
patent: 6023278 (2000-02-01), Margolin
patent: 6057849 (2000-05-01), Haubner et al.
Description of USGS Digital Elevation Model Data, Earth Resource Observati
LandOfFree
Digital map compression and display method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital map compression and display method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital map compression and display method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464210