System and method of processing digital terrain information

[0002] This invention relates to terrain map displays, and more particularly, this invention relates to a system and method for processing and creating digital terrain elevation data plan-view maps relying on a graphics application programming interface (API).

[0003] Digital map generation and display systems access and display digital terrain map images effectively in real time with the travel of an aircraft, helicopter or other object over terrain. One factor in the ability of the system to effect a real time display is to use the combination of scene memory for storing a portion of digital map imagery data from a mass storage device in a prescribed orientation, such as north-up, and a controlled addressing scheme for reading the data from scene memory for displaying the image in accordance with the heading information supplied by an aircraft's on-board navigation equipment. U.S. Pat. No. 5,299,300 issued Mar. 29, 1994 to Femal et al., the disclosure which is hereby incorporated by reference in its entirety, discloses a hardware embodiment of interpolation processing of digital map imagery data that retrieves full and half resolution data stored in half-resolution addresses.

[0004] The advent of commercial off-the-shelf (COTS) graphics hardware, such as driven by advanced and sophisticated PC game markets, has placed pressure on custom avionics market place to use COTS graphics hardware and software. The avionics community, however, requires high fidelity digital terrain elevation data map displays. Under a commercial off-the-shelf graphics application programming interface, such as the OpenGL, a terrain is modeled with a series of polygons and a lighting model is used to illuminate the terrain providing the relief image. For example, an OpenGL image, as an example, can use a half-a-million polygons in one image. The polygons could be triangles where the corner of each triangle includes an elevation post and particular coordinates for the post. Every triangle and its coordinates are sent through the OpenGL or other COTS application programming interface (API). A processor calculates the surface angle and slope based on the received coordinates and determines where the sun is located.

[0005] This use of a large number of polygons requires a large memory and processor bandwidth to create the imagery, which is also required to rotate, i.e., translate and zoom, at rates of a minimum of 20 Hz. Maintaining a plan-view digital terrain elevation data display via conventional, commercial off-the-shelf methods requires significant processing capability, as noted above. These terrain displays are generated via polygonal meshes and use the lighting model. They are bandwidth intensive and processor heavy, and are not as desirable if a more simple and efficient solution could be found.

[0006] The present invention is advantageous because it is now no longer necessary to create a polygonal mesh and lighting model that is used, in turn, to create a plan-view digital terrain elevation data display. The present invention advantageously uses a bit-mapped image, texture map, where each pixel value corresponds to a color in a color map, such as a gray scale image color map. By careful construction of these two items, it is possible to create a three-dimensional relief map that can have a moving sun-angle without expensive calculations. For every digital terrain elevation data post, a normal is calculated relative to the terrain surface. This value is encoded in a half-polar coordinate system with tilt and azimuth, which are represented as two fixed-point integers. A color (gray scale as one example) table is created and contains the illumination colors given a particular azimuth and tilt combination. The native two-dimensional color table array is “collapsed” into a single-dimensional array by concatenating (link together), the azimuth and tilt into a single integer, where azimuth will be in the most significant position.

[0007] The color index/color pallet mode of an application programming interface is used for the grid of single-value surface normals that become a texture. During rendering, the color table is used by the graphic subsystem to convert the “color index” into an RGB color.

[0008] When the heading angle of the map changes, the result is a simple change in azimuth. To avoid any optical illusion problem, the virtual sun must appear to remain in the upper left corner of the display. Because the map imagery is rotated, the illumination angle of the sun is counter-rotated, compensating for the map rotation. The counter-rotating movement of the sun-angle can be accomplished by shifting the values in the color table. Instead of using a hardware application, the present invention manipulates digital terrain elevation data such that the effect caused by some prior art hardware devices are performed with a graphics application programming interface, which lowers the bandwidth by orders of magnitude, freeing up resources for other features. The applications can include airborne digital maps, mission planning systems and geospatial/cartographic systems.

[0009] Other objects, features and advantages of the present invention will become apparent from the detailed description of the invention which follows, when considered in light of the accompanying drawings in which:

[0010] FIG. 1A is a block diagram of basic components of a memory/cache architecture, as an example of a system that is used in the present invention.

[0011] FIG. 1B is a plan-view of a typical digital terrain elevation data display taken from an aircraft.

[0012] FIG. 2 is an exploded view of a digital terrain elevation data plan-view showing various unstacked layers.

[0013] FIG. 3 is a composite digital terrain elevation data plan-view of a complete image of the unstacked layers shown in FIG. 2.

[0014] FIG. 4 is a texture mapping example of an image using a graphic application programming interface.

[0015] FIG. 5 is an example of an image of an extremely dense polygonal mesh created from many polygons.

[0016] FIG. 6 illustrates an image using a dense regular grid of triangles.

[0017] FIG. 7 illustrates an image for a triangulated irregular network that is flat-shaded.

[0018] FIG. 8 illustrates an image for a flat-shaded TIN (having a rougher approximation of surface).

[0019] FIG. 9 illustrates an average surface normal N_AVG.

[0020] FIG. 10 illustrates a TIN image with Gouraud shading.

[0021] FIG. 11 illustrates a large area TIN image with Gouraud shading.

[0022] FIG. 12 illustrates a diagram of a half-polar coordinate system used in the present invention.

[0023] FIG. 13 illustrates the computation of surface normal and the use of texture memory and a color map.

[0024] FIG. 14 illustrates how a color map table can be manipulated in accordance with the present invention.

[0025] FIGS. 15 and 16 are examples of azimuth/tilt values.

[0026] The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Like numbers refer to like elements throughout.

[0027] The present invention is advantageous and provides an enhanced and alternative method for creating digital terrain elevation data plan-view maps on an airborne digital mapping system. The system of the present invention uses a graphics application programming interface, such as a commercial off-the-shelf OpenGL API. Instead of creating a normal polygonal mesh, and using a lighting model to create the plan view digital terrain elevation data display, the present system and method uses a texture map in the form of a bit-mapped image. Each pixel value corresponds to a color in a color map, such as a gray scale image color map. By carefully constructing these two items, it is possible to create a three-dimensional relief map that has a moving sun-angle without expensive calculations.

[0028] For every digital terrain elevation data post, a normal to the terrain surface is calculated and encoded in a half-polar coordinate system. The tilt and azimuth are represented as two, fixed-point integers. A color table contains the illumination colors (such as the gray scale image colors) and are given a particular azimuth and tilt combination. The native two-dimensional color table array is “collapsed” into a single-dimensional array by concatenating (linking together) the azimuth and tilt into a single integer where the azimuth will be located in the most significant position.

[0029] The color index/color pallet mode of an application programming interface is used with a grid of a single-value surface normal becoming a texture. During rendering, the color table can use the graphics subsystem to convert the “color index” into a RGB color.

[0030] When the heading angle of a map changes, the result is a change in azimuth. To avoid the optical illusion problem, the virtual sun can appear to remain in the upper left corner of the display. Because the mapped imagery is rotated, the illumination angle of the sun must appear counter-rotated, compensating for the map rotation. This counter-rotating movement of the sun-angle can be accomplished by shifting the value in the color table.

[0031] The system and method of the present invention is advantageous over prior art hardware specific approaches. With the present invention, the data is manipulated such that the effect rendered by hardware devices is performed with a graphics application programming interface. The present system and method lowers the bandwidth by orders of magnitude, freeing up resources for other features and can be advantageously used for airborne digital maps, mission planning systems, geospatial/cartographic systems, and other systems known to those skilled in the art.

[0032] FIG. 1 illustrates a computer system shown at 20 that uses a unified memory architecture, as an example only. A graphics accelerator 22 accesses map data from a random access memory (RAM) 24. Data and control commands are input to the graphics accelerator from CPU 26. Two-dimensional images are displayed on an LCD 28 or other similar display. It is possible to use a texture or other cache 30 (indicated by dashed lines) where the fill rate could be higher from the cache and from the main memory of the unified memory system such as with the cache architecture.

[0033] Any graphics hardware architecture can be hidden by the software layer, called the graphics application programming interface (API). Although different programming interfaces can be used in accordance with the present invention, one preferred application programming interface is an industry standard API called OpenGL, which provides a common interface to graphics functionality on a variety of hardware platforms. OpenGL also provides a uniform interface to the various mapping capabilities, such as texture mapping capabilities, supported by system architecture. Further details of OpenGL programming are found in Neider, Davis and Woo, OpenGL Programming Guide, Addison-Wesley, Redding, Mass., 1993.

[0034] FIG. 1 is a plan view of a sun-sloped shaped digital terrain image where the sun is representative as shining from the upper left hand corner. This type of image could be used on many different types of displays 28, including flat panel displays and other similar displays, including active matrix liquid crystal displays that are both monochrome and color. Typically, the display 28 has real time smooth and continuous map updates at different speeds and motions and provides full anti-aliasing. It has elevation color band slight height above terrain (HAT) and slope shading digital terrain elevation data (DTED) overlays with full graphics generation with continuous zoom of 0.5 to 8× and auto zone boundary compensation. A digital map generator can store terrain data to generate moving train map displays and eliminate paper maps. The displays can be either digitized representations of standard aeronautical charts or topographical displays created from digitized elevation and cultural feature data. Symbology overlays can be added to show features such as wave points, flight paths and assist with terrain-aided navigation and ground collision avoidance. Typically, the displays could be 640×480 and 1280×480 sensor video modes that have fiber-optic video interfaces and RS-422 serial interfaces for command modes and status and use commercial display technology, as known to those skilled in the art. Various on-board processors, with both HSDB and SDDN functions, can exist on single SEM-E modules.

[0035] A plan view DTED display is typically composed of several “layers,” which build up the display. The underlying, sun-sloped shaded terrain map, the contour lines, the translucent tint colors (elevation banding, threat intervisibility), and symbology elements are also built. The symbology elements can be disregarded and these elements can be visualized if an image is flipped over and the layers unstacked (FIG. 2), showing a complete image is composed.

[0036] Historically, digital maps have been provided that have necessitated custom image rendering hardware in order to provide DTED images that can be rotated, translated and zoomed at rates past 20 Hz. With the advent of COTS OpenGL and other graphics API hardware, it is desirable to use a COTS graphics API, such as OpenGL software standard and COTS chips for the hardware. The DTED plan-view display uses the highest memory bandwidth and might prove to be the most difficult mode to provide in an OpenGL setting.

[0037] OpenGL and similar COTS graphics application programming interfaces provide a rich set of capabilities for rendering 3-D graphics. Typically, a scene is rendered out of polygons, which are then applied with a series of textures (i.e., photos). For example, in FIG. 4, an ocean surface is created with a polygonal surface and a texture.

[0038] In a typical sun-slope shaded display using OpenGL, it is possible to create a terrain surface and apply a shading model to illuminate the terrain. In order to have a fairly high fidelity image, a large number of polygons are used. In FIG. 5, a DTED display is rendered using approximately one million polygons. This polygonal mesh is created from a regular (equally sized) grid of triangles, directly created from the elevation mesh, similar to the example in FIG. 4. It should be emphasized that the data bandwidth necessary for this display is large because OpenGL and similar COTS graphics API's are required to compute a lighting calculation for every triangle. This calculation requires both the triangle coordinates and normal vectors.

[0039] It is possible to integrate in a Triangulated Irregular Network (TIN) optimization code into software to speed up a perspective mode. Thus, TIN can be used for a plan-view DTED mode. A TIN code is created for the purpose of a texture-mapped perspective display. TIN's reduce the number of triangles necessary to model the terrain surface.

[0040] FIG. 6 illustrates a dense regular grid of triangles (two per four elevation posts) that use an average surface normal at each vertex. FIG. 7 illustrates a TIN that approximates the same surface, but the polygons are flat shaded, i.e., a triangle has one single color, in order to visualize the triangle mesh. FIG. 8 illustrates a TIN that has a decreased number of polygons creating a less accurate surface approximation.

[0041] In a flat shading model, a single color is used for each facet of the terrain. This is derived from how that surface plane faces the light source, by using the normal vector to the surface. FIG. 6 shows the average surface normal, which is used for a Gouraud (smooth) shaded image. To provide an average surface normal, a normal from each surface plane incident upon the vertex is accumulated, averaged and normalized (FIG. 9). Colors, such as gray scale colors, can then be calculated at the vertices and bilinearly interpolated across the triangle facet.

[0042] When this technique was performed upon a TIN surface, the resulting image was much less than satisfactory (FIG. 10). This poor image results from several factors. First, each surface was weighted the same, yielding a disproportional normal. Second, the surface approximation itself leads to a smoothing effect (removing high frequency variations in the surface). When viewed at the larger scale (FIG. 11), it is evident that the smooth shading will have pronounced effects upon the larger triangles (representing large flat areas of terrain). Because human eyes are sensitive to the smooth linearity of the tessellated surface, this technique cannot be used even with a weighted normal approach, which can be calculated with moment arms.

[0043] One of the advantages of the plan-view DTED display of the present invention is the position of the virtual sun. When in a heading-up mode, the virtual sun always remains in the upper left corner of the display regardless of the map rotation angle. This ensures that the resulting image presents mountains as projecting out of the display and not in the opposite manner. If it were not for this difference, most systems would have little difficulty presenting a DTED display. The system can calculate the image once, then create a texture of that image using the feedback mechanism in OpenGL or other COTS graphics API, and rotate that texture appropriately. It is possible to accomplish something similar, eliminating the job of polygonal shading.

[0044] For each “loadable” terrain block, the software will, for each post, calculate a normal to the surface. This normal, in basically a half polar coordinate system, will be composed of two elements: a slope tilt and a slope azimuth as shown in FIG. 12. These two coordinates are represented as two fixed point numbers, which are then concatenated, i.e., linked together, into a single reference integer and into a “two” dimensional table. This single reference integer will become a color index into the azimuth/tilt table. The azimuth/tilt table will be a color table containing RGB values (FIG. 13). This valuation can be advantageously accomplished in hexadecimal notation.

[0045] The example shown in FIGS. 15 and 16 illustrate how to encode an azimuth/tilt into an 8-bit integer. FIG. 15 illustrates the individual bit positions within the 8-but integer. As shown in FIG. 15, azimuth is a 5-bit number (values 0 . . . 31) with a least significant bit equal to 11.25 degrees. Tilt is a 3-bit number (values 0 . . . 7) with a least significant bit equal to 7 degrees. Angles over 49 degrees will be represented as the fixed point value of 7.

[0046] Example: Azimuth=90 degrees, tilt=35 degrees $90\mathrm{Deg}=\frac{90\mathrm{Deg}}{11.25\frac{\mathrm{Deg}}{\mathrm{Azimuth\_LSB}}}=8$ $35\mathrm{Deg}=\frac{35\mathrm{Deg}}{7\frac{\mathrm{Deg}}{\mathrm{Tilt\_LSB}}}=5$

[0047] FIG. 16 shows how these two fixed-point numbers are concatenated into the single integer value (resulting value shown in both hexadecimal “h” and decimal “d” representation).

[0048] As illustrated in FIG. 13, terrain elevation posts 40 are processed via a surface normal computation where the software computes values such that the terrain is represented as surface normals 42. This data is sent to texture memory 44 and processed into the color map 46. This will allow the software to use the OpenGL or other API color index mode. After using color index mode for the underlying map image, the software can then command the API, such as OpenGL, to switch back to RGB mode to render any information in the RGB color system. It is possible that in some individual OpenGL and other graphics API implementations, using desktop machines, the software cannot switch color modes within a single window.

[0049] When the heading angle of the map changes, the result is a simple change in azimuth. By applying a single offset, the “proper” colors can be indexed into the azimuth/tilt table thereby generating the correct sun-angle color. By “shifting” or otherwise manipulating the color table, the effect of changing the offset can be accomplished, and hence, the proper sun-angle shading angle will be accomplished for a particular heading value (FIG. 14). Since the manipulation of the sun-angle is done via the color map table, the software only needs to instruct the OpenGL interface to render the terrain texture map on an appropriately rotated rectangular polygon.

[0050] This method is similar to what the modular map family has done with custom software/hardware, operates solely within the guise of the graphics API such as OpenGL. There will be a large decrease in computations necessary to render the image. Typically, this is covered by the COTS OpenGL hardware chips, but there are still limitations. The bandwidth between the software and the OpenGL interface drops significantly.

[0051] Many modifications and other embodiments of the invention will come to the mind of one skilled in the art having the benefit of the teachings presented in the foregoing descriptions and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed, and that the modifications and embodiments are intended to be included within the scope of the dependent claims.