Digital map rendering method

• US 10,019,835 B1
• Filed: 10/02/2014
• Issued: 07/10/2018
• Est. Priority Date: 03/05/2010
• Status: Active Grant

• Current Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Skoog, Mark, Hook, Loyd, McWherter, Shaun, Willhite, Jamie Wiley
• Primary Examiner(s): Zeender, Florian M
• Assistant Examiner(s): Amsdell, Dana
• Application Number:
  US14/504,614
• Time in Patent Office: 1,377 Days
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2210/61 Scene description
• CPC Class Codes: G06T 2215/16 Using real world measurements to influence rendering
• CPC Class Codes: G08G 5/04 Anti-collision systems

Abstract

The invention is a system and method of compressing terrain data to be used to render a three-dimensional map representation of the terrain data. In general, the invention operates by first selecting the boundaries of the terrain data and to be compressed and dividing the terrain data into regular geometric areas. Next, a type of free-edged, planar geometric surface is defined which is used to approximate the terrain data for each regular geometric area. The approximations are checked to determine if they fall within user selected tolerances. If the approximation for a specific regular geometric area is within the user specified tolerances, the data is saved for that specific regular geometric area. If the approximation for a specific regular geometric area falls outside the user specified tolerances, the regular geometric area is divided and a free-edged, planar geometric surface approximation is made for each of the divided areas. This process is recursively repeated until all of the regular geometric areas are approximated by free-edged, planar surfaces. Finally, the compressed terrain data is used to render a three-dimensional map.

Claims

1. A method for rendering a three-dimensional map using terrain data, comprising the steps of:

accessing the terrain data on a computer system;

selecting the boundaries of the terrain data to be used to render the three-dimensional map;

dividing the boundaries of the terrain data into regular geometric areas;

defining a type of free-edged, planar geometric surface;

approximating terrain in each regular geometric area, using the defined free-edged, planar geometric surface, as an independent free-edged, planar geometric surface;

checking the terrain approximation for each regular geometric area to determine if the terrain approximation is within user selected tolerances;

dividing the regular geometric areas outside the user selected tolerances into smaller regular geometric areas and approximating terrain data as described above for each of the smaller regular geometric areas;

recursively repeating the checking and dividing steps until all terrain approximations for regular geometric areas fall within user-selected tolerances; and

,

outputting a final compressed three-dimensional map using final terrain approximations data to a map rendering device.

2. The method for rendering a three-dimensional map of claim 1, wherein the regular geometric areas comprise one degree by one degree cells.

3. The method for rendering a three-dimensional map of claim 1, wherein the approximating step includes using a method selected from the group of max thinned and biased linear regression.

4. The method for rendering a three-dimensional map of claim 3, wherein the approximating step includes using the method of max thinned and the terrain approximation for each regular geometric area is determined by setting the free-edged, planer geometric surface to a constant elevation which is equal to the highest elevation terrain within the regular area.

5. The method for rendering a three-dimensional map of claim 3, wherein the approximating step includes using the method of biased linear regression for each regular geometric area is determined by performing a linear regression through the digital elevated terrain data to obtain an orientation of each free-edged, planar geometric surface and biasing the free-edged, planar geometric surface so that no terrain is higher than the free-edged, planar geometric surface.

6. The method for rendering a three-dimensional map of claim 1, wherein the checking step further comprises:

selecting global error tolerances for the boundaries of the three-dimensional map;

selecting error tolerances for specific zones; and

,

checking the terrain approximations for each regular geometric area against the global error tolerances and the error tolerances for specific zones.

7. The method for rendering a three-dimensional map of claim 1, wherein the dividing the type of regular geometric area comprises a recursive division resulting in a tree structure selected from a binary tree or a quad tree.

8. The method for rendering a three-dimensional map of claim 7, wherein the outputting step further comprises outputting:

header information correlating to the boundaries of the three-dimensional map, the type of free-edged, planar geometric surface defined, the tree structure selected for dividing the regular geometric areas, a size of the regular geometric areas, and a data byte format;

table information that indexes data along regular geometric area boundaries; and

,

compressed data.

9. The method for rendering a three-dimensional map of claim 8, further comprising the steps of:

determining a specific regular geometric area associated with a position area of interest;

decoding the compressed data associated with the specific regular geometric area to identify the geometric location of each free-edged, planar geometric surface within a two-dimensional representation of the specific regular geometric area; and

,

using the decoded data to output a height associated with the position area of interest to a display.

10. The method of rendering a three-dimensional map of claim 9, wherein the decoding step further comprises converting each data element of the compressed data into four floating point numbers that define a location of the boundaries of a square-shaped representation of the free-edged, planar geometric surfaces within the specific regular geometric areas.

11. The method of rendering a three-dimensional map of claim 10, wherein a size of the square-shaped representations of the free-edged, planar geometric surfaces relates to a number of times the free-edged, planar geometric surface was divided pursuant to checking the terrain approximation step.

12. The method of rendering a three-dimensional map of claim 11, wherein the using the decoded data step further comprises outputting decoded data associated with edges of the position area of interest and all edges of the square-shaped representations of the free-edged, planar geometric surface representations within the position area of interest.