Digital map generator and display system

• US 6,023,278 A
• Filed: 10/06/1997
• Issued: 02/08/2000
• Est. Priority Date: 10/16/1995
• Status: Expired due to Term

• Current Assignee: Rateze Remote Mgmt. L.L.C. (Intellectual Ventures LLC)
• Original Assignee: Jed Margolin
• Inventors: Margolin, Jed
• Primary Examiner(s): Feild, Joseph H.
• Application Number:
  US08/944,366
• Time in Patent Office: 855 Days
• Field of Search: 345/418, 345/419, 345/425, 345/426, 345/427, 341/94, 340/995, 463/30-33
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A digital map system for displaying three dimensional terrain data uses terrain data in the form of polygons. The polygon database is produced from a database of elevation points which are divided into, for example, n×n (where n is a positive integer) squares which have an elevation point in the center of the square. The center point forms four polygons with the corners of the square. The elevation of the center point may be chosen to be the highest elevation point in the n×n square, the average elevation of the elevation points in the n×n square, the elevation of the actual center point, or other methods. The method chosen depends on how the data base is to be used. The size of the n×n square chosen also depends on how the data base is to be used since there is a tradeoff between the resolution of the displayed scene and the amount of data reduction from the original database of elevation points. The polygon database may be used in a pilot aid using a synthetic environment, a flight simulator, as part of the control system for a remotely piloted vehicle, or in a video game.

Claims

1. A method for compressing an elevation database, said elevation database comprising digital elevation points of terrain arranged in an array of rows and columns, said method comprising the computer implemented steps of:

selecting every mth column of said elevation database;

selecting every nth row of said elevation database;

determining a center elevation point within a cell bounded by intersections of said mth column and said nth row, wherein m and n are greater than 1, and wherein the elevation of the center elevation point is determined using an elevation of at least one point on a non-selected column or row; and

storing a compressed database that represents said cell using data that identifies said center elevation point and said intersections of said mth and nth row creating said cell.

2. The method as described in claim 1 wherein said center elevation point is assigned an elevation value by a method selected from the group consisting of:

a) assigning an elevation value equal to the highest elevation value of said plurality of elevation points in said cell;

b) assigning an elevation value equal to the average elevation value of said plurality of elevation points in said cell;

c) assigning an elevation value equal to the average elevation value of a subset of said plurality of elevation points in said cell proximate said center elevation point; and

d) assigning an elevation value equal to the elevation value of the elevation point near said center elevation point.

3. The method as described in claim 1 further comprising defining a plurality of three dimensional polygons in said cell and producing a display of terrain by displaying said plurality of polygons.

4. The method as described in claim 3 wherein said polygons comprise vertices comprising a first said intersection, a second said intersection and said center elevation point.

5. The method as described in claim 3 wherein said cell comprises vertices defined by four said intersections of said mth columns and said nth rows, wherein said plurality of polygons are defined by each adjacent pair of said vertices and said center elevation point.

6. The method as described in claim 1 wherein said database comprises a plurality of geographic blocks, each said geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.

7. The method as described in claim 2 wherein said database comprises a plurality of geographic blocks, each said geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.

8. The method as described in claim 3 wherein said database comprises a plurality of geographic blocks, each said geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block, wherein said resolution is varied by using a first value of m and a first value of n in said first geographic block, and a second value of m and a second value of n in said second geographic block, wherein said first value of m is different from said second value of m and/or said first value of n is different from said second value of n.

9. The method as described in claim 3 wherein at least one of said polygons is displayed such that at least one edge of said at least one polygon has a different appearance than a central portion of said at least one polygon.

10. The method as described in claim 1 wherein said database is used to produce a display for a video game.

11. The method as described in claim 5 wherein said database is used to produce a display for a video game.

12. A method of producing a display of terrain comprising the computer implemented steps of:

providing an elevation database, said elevation database comprising digital elevation points of terrain arranged in an array of rows and columns;

defining a cell having a plurality of non-adjacent ones of said digital elevation points as vertices;

calculating a center elevation point for said cell, wherein the elevation of said center elevation point is calculated using certain of said digital elevation points that are not vertices of said cell;

defining a plurality of polygons within said cell, vertices of each of said plurality of polygons being selected from said center elevation point and from said plurality of non-adjacent ones of said digital elevation points; and

displaying said plurality of polygons as three dimensional objects.

13. The method as described in claim 12 wherein said cell is defined by a method comprising:

selecting a plurality of columns;

selecting a plurality of rows;

defining said cell using elevation points at intersections of said plurality of selected columns and plurality of selected rows as vertices of said cell.

14. The method as described in claim 13 wherein said plurality of columns are selected by selecting every mth column and said plurality of rows are selected by selecting every nth row within a region of said terrain, wherein m and n are greater than 1.

15. The method as described in claim 12 wherein said plurality of polygons are defined by:

defining a line from at least one vertex of said cell to said center elevation point.

16. The method as described in claim 13 wherein said plurality of polygons are defined by:

defining a line from at least one vertex of said cell to said center elevation point.

17. The method as described in claim 14 wherein said plurality of polygons are defined by:

defining a line from at least one vertex of said cell to said center elevation point.

18. The method as described in claim 15 wherein said plurality of polygons are defined by:

defining a line from each vertex of said cell to said center elevation point.

19. The method as described in claim 16 wherein said plurality of polygons are defined by:

defining a line from each vertex of said cell to said center elevation point.

20. The method as described in claim 12 wherein said center elevation point is assigned an elevation value by a method selected from the group consisting of:

a) assigning an elevation value equal to the highest elevation value of said plurality of elevation points in said cell;

b) assigning an elevation value equal to the average elevation value of said plurality of elevation points in said cell;

c) assigning an elevation value equal to the average elevation value of a subset of said plurality of elevation points in said cell proximate said center elevation point; and

d) assigning an elevation value equal to the elevation value of the elevation point near said center elevation point.

21. The method as described in claim 12 wherein said database comprises a plurality of geographic blocks, each said geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block.

22. The method as described in claim 14 wherein said database comprises a plurality of geographic blocks, each said geographic block representing a geographic area, wherein a first geographic block may have a different resolution from a second geographic block, where said resolution is varied by using a first value of m and a first value of n in said first geographic block, and a second value of m and a second value of n in said second geographic block, wherein said first value of m is different from said second value of m and/or said first value of n is different from said second value of n.

23. The method as described in claim 12 wherein said method is used to display said terrain in a video game.

24. The method as described in claim 17 wherein said method is used to display said terrain in a video game.

25. The method as described in claim 12 wherein at least one of said polygons is displayed such that at least one edge of said at least one polygon has a different appearance than a central portion of said at least one polygon.

26. A machine readable medium having stored thereon sequences of instructions, which when executed by a processor, cause said processor to perform the steps of:

accessing a compressed version of a database storing digital elevation points of terrain arranged in columns and rows, said compressed version having been generated by storing intersections of only certain columns and rows from said database and by calculating and storing a center elevation point relatively in the center of each cell bounded by adjacent ones of the stored intersections, wherein the elevations of said center elevation points are calculated using elevations of digital elevation points that are not on said stored intersections and are not stored as part of said compressed database;

defining a plurality of polygons within each cell using as vertices the center elevation point and the stored intersections for that cell; and

displaying said plurality of polygons as three dimensional objects.

27. The machine readable medium of claim 26, wherein said step of defining said plurality of polygons further includes the step of:

defining said plurality of polygons in each cell as non-overlapping triangles having the center elevation point as a vertex.

28. The machine readable medium of claim 26, wherein each center elevation point is equal to the highest of elevation points in the elevation database that fall within the cell containing that center elevation point.

29. The machine readable medium of claim 26, wherein each center elevation point is equal to the average of elevation points in the elevation database that fall within the cell containing that center elevation point.

30. A method of displaying a representation of terrain over which an aircraft is flying, said method comprising the computer implemented steps of:

accessing a compressed version of a database storing digital elevation points of terrain arranged in columns and rows, said compressed version having been generated by storing intersections of only certain columns and rows from said database and by calculating and storing center elevation points relatively in the center of each cell bounded by adjacent ones of the stored intersections, wherein the elevations of said center elevation points are calculated using elevations of digital elevation points that are not on said stored intersections and are not stored as part of said compressed database;

defining a plurality of polygons within each cell using as vertices the center elevation point and the stored intersections for that cell; and

displaying said plurality of polygons as three dimensional objects.

31. The method of claim 30, wherein said step of defining said plurality of polygons further includes the steps of:

defining said plurality of polygons in each cell as non-overlapping triangles having the center elevation point as a vertex.

32. The method of claim 30, wherein each center elevation point is equal to the highest of elevation points in the elevation database that fall within the cell containing that center elevation point.

33. The method of claim 30, wherein each center elevation point is equal to the average of elevation points in the elevation database that fall within the cell containing that center elevation point.