KR20100074845A - Method and apparatus for visualizing digital elevation model - Google Patents

Abstract

The present invention relates to a method and apparatus for visualizing a digital elevation model, the method for visualizing a digital elevation model (DEM), the process of receiving the terrain data divided into at least one grid, and each of the Calculating and comparing a first altitude difference and a second altitude difference with respect to the lattice; dividing the lattice into two triangles according to the difference between the first altitude difference and the second altitude difference; and forming a triangular strip from the divided triangles. The method comprising the step of generating.

Description

METHOD AND APPARATUS FOR VISUALIZING DIGITAL ELEVATION MODEL

The present invention relates to a digital elevation model (DEM) visualization, in particular to provide a method and apparatus for improving the rendering image quality by reflecting the curvature / altitude / height value of the terrain.

Navigation is mounted on the vehicle by means of a vehicle navigation system. The basic function of the navigation device is to accurately track the location of the vehicle on the road and accurately display it on a road map. The secondary function is to identify traffic conditions of other roads or provide information on gas stations.

However, the driver must be well visualized to find the desired location on the map of the navigation device. This is because when driving a vehicle at high speed, searching for a map with three-dimensional visualization rather than searching for a map of the plane provides convenience and safety to the user. That is, when a feature such as a surrounding building or terrain is viewed in a three-dimensional shape, it can be intuitively recognized.

Digital Elevation Model (DEM) is used as a method to give two-dimensional map data to give a three-dimensional feel. The DEM collectively refers to data represented by three-dimensional coordinates used to build a Geographic Information System (GIS), and records the numerical values of heights (or elevations) of points distributed at regular intervals on the surface of the computer. It is processed using.

In addition, DEM has a merit of easy calculation and easy implementation. Store height / altitude values in an array at the intersection of each grid. In general, when visualizing three-dimensional DEM terrain data, each grid is divided into two triangles in a consistent / constant direction without rendering the terrain's curvature and rendered as triangles. In this case, it is difficult to properly reflect the curvature of the terrain.

Therefore, there is a need for a method and apparatus for dividing two triangles in consideration of the unevenness / curvature / height of the terrain in each grid of the DEM.

An object of the present invention is to provide a method and apparatus for effectively visualizing the 3D DEM terrain data used in the navigation device.

Another object of the present invention is to provide a method and apparatus for dividing two triangles in consideration of the unevenness / curvature / height of the terrain in each grating in the navigation apparatus.

Another object of the present invention is to provide a method and apparatus for generating and rendering triangle strips for quickly rendering three-dimensional DEM data in a navigation device.

According to a first aspect of the present invention for achieving the above object, a method for visualizing a digital elevation model (DEM), comprising the steps of: receiving terrain data divided into at least one grid; Calculating and comparing a first altitude difference and a second altitude difference with respect to the lattice of; and dividing the lattice into two triangles according to the difference between the first altitude difference and the second altitude difference; It characterized in that it comprises a process of generating.

According to a second aspect of the present invention for achieving the above object, in the apparatus for the visualization of the digital elevation model (DEM), receiving terrain data divided into a grid consisting of at least one four elevation points A DEM data generation unit, an altitude difference comparison unit for calculating and comparing a first altitude difference and a second altitude difference with respect to each of the lattice, and dividing the lattice into two triangles according to the difference between the first altitude difference and the second altitude difference And a triangular strip generator and a triangular strip generator for generating a triangular strip from the divided triangles.

As described above, by triangulation by reflecting the curvature / altitude / height of the terrain, there is an advantage that the image quality can be improved because it reflects the curvature of the terrain. In addition, the rendering image quality may be improved by reflecting the curvature of the terrain.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the following description of the present invention, detailed descriptions of related well-known functions or configurations will be omitted if it is determined that the detailed description of the present invention may unnecessarily obscure the subject matter of the present invention. The following terms are defined in consideration of the functions of the present invention, and may be changed according to the intentions or customs of the user, the operator, and the like. Therefore, the definition should be made based on the contents throughout the specification.

Hereinafter, the present invention will be described a method and apparatus for visualizing a digital elevation model (hereinafter referred to as "DEM") in navigation.

FIG. 1 illustrates an example of generating DEM data from contour topographical data and visualizing the DEM data in three dimensions.

Figure 1 (a) is a view showing the contour of the general terrain, Figure 1 (b) is divided into a grid of a certain size of the terrain represented by the contour of the Figure 1 (a), separated by a grid Represents a terrain as a set of triangular pieces connected by three elevation points. In other words, as an efficient and convenient expression method of approximating the surface of the terrain, the digital elevation model (DEM) uses the elevation level (x, y, z) (arbitrary elevation points connected by regular grids or triangles). Hereinafter referred to as DEM data).

FIG. 1 (c) is a diagram of visualizing two-dimensional terrain into three-dimensional terrain by rendering the DEM data in FIG. 1 (b). A method of rendering the DEM data will be described with reference to FIG. 2.

2 shows an example of rendering DEM data according to the present invention.

Referring to FIG. 2, some terrains are divided into nine grids, and each grid is triangulated in a predetermined direction and rendered.

For example, rendering is performed with a first triangle made up of elevation points (0, 4, 1) counterclockwise (200), and then rendering is performed with a second triangle made up with elevation points (1, 4, 5) counterclockwise. (210). After the triangles of each grid are rendered in this order, the triangle information expressed in the rendering language is transferred to hardware such as graphic acceleration and visualized in three dimensions. At this time, some elevation points forming the triangle may overlap and the rendering speed may be slow.

3 shows another example of rendering DEM data according to the present invention. In order to reduce the overlapping of the elevation points in FIG. 2, rendering is performed using a triangle strip in FIG. 3. The triangular strip is one of the ways in which the coordinates of the triangle are represented, and each elevation point added forms a new triangle.

Referring to FIG. 3, in the triangle consisting of the elevation points 0, 4 and 1, when the elevation point 5 is added, the triangle consisting of the elevation points 4, 1 and 5 is added. After the elevation point 2 is added, a triangle consisting of elevation points 1, 5 and 2 is added. Similarly, when the elevation point 6 is added, a triangle consisting of the elevation points 5, 2, 6 is added, and when the elevation point 3 is added, a triangle consisting of the elevation points 2, 6, 3 is added. When elevation point 7 is added, a triangle consisting of elevation points 6, 3, 7 is added.

Subsequently, when the elevation point 8 is added, a triangle consisting of the elevation points 3, 7 and 8 should be added, but since the surface consisting of the elevation points 3, 7 and 8 is not a triangle, the elevation point 7 is overlapped. Add it. Since the surface consisting of the elevation points (3, 7, 7) is also not a triangle, add an elevation point (4), and since (7, 7, 4) is also not a triangle, and add again the elevation point (4). Since (7, 4, 4) is also not a triangle, it adds an elevation point (8), and (4, 4, 8) is also not a triangle, so it is added to an elevation point (5) to create elevation triangles (4, 8). Add elevation point until 5) is displayed.

That is, when configuring a triangular strip, a triangle is added every time an elevation point is added, thereby reducing the overlapping elevation point than FIG. 2.

4 is a view comparing a rendering example using a triangle in the prior art and the present invention.

Referring to FIG. 4, the terrain is divided into grids having the same size, and DEM data is generated for the terrain divided by a double grid. Conventionally, triangles are formed in a predetermined direction to form triangles for generating DEM data.

For example, when some terrain 400 separated by a grid is composed of four elevation points 500, 520, 500, and 490, a triangle is conventionally formed in a predetermined direction to form a triangle for generating DEM data. Assume that a triangle is formed as shown in FIG. In this case, when the elevation point 520m and the elevation point 490m are connected to form a triangle, and the remaining elevation points 500 and 500 of the triangle do not have an altitude difference, the middle portion of the grid generates altitude. Looking at the drawing of the contour line on the left, the middle part of the grid 400 of some terrains do not have altitude, but when the triangulation is performed, the altitude is generated in the middle part. Therefore, it is impossible to accurately reflect the altitude.

Therefore, in the present invention, in order to accurately reflect the altitude as shown in FIG. 4 (b), a triangle is formed in a direction without an altitude difference. For example, 30m (520m-490m) when the triangle is connected by 520m above sea level and 490m above sea level (called the first altitude difference), and 0m (500m-500m when the triangle is formed by connecting 500m above sea level and 500m above sea level When a triangle is formed in a direction in which the altitude difference is small by comparing)) (called the second altitude difference), as shown in the contour line on the left side, the altitude does not occur in the middle portion of the grid and rendering is performed.

FIG. 5 is a diagram illustrating a case where the altitude is not reflected and the altitude is reflected in FIG. 4 according to an exemplary embodiment of the present invention.

Referring to FIG. 5B, when an elevation point 520m and an elevation point 490m are connected to form a triangle, the altitude is not reflected. In other words, there is no altitude in the actual middle part, but altitude is generated in the middle part after rendering.

This is a rendering example in which the altitude is reflected when the elevation point 500m and the elevation point 500m are connected to form a triangle. That is, there is no altitude in the actual middle part, and no altitude occurs in the middle part even after rendering.

6 illustrates a navigation device for visualizing DEM data according to an embodiment of the present invention.

Referring to FIG. 6, the navigation device includes an input unit 600, a GPS module unit 602, an output unit 604, a control unit 606, a DEM visualization unit 608, a map data DB 610, and terrain data. The input unit 630 and the DEM data generator 640 are generated and configured.

According to an embodiment, the functions of the terrain data input unit 630 and the DEM data generator 640 may be preprocessed by a general computer. When the generated DEM data is stored in a database, the navigation device maps the data 610. By accessing the DEM data can be read and used.

The input unit 600 provides a user interface, receives an input value from the user, and the GPS module unit 602 receives location information from the satellite and provides the received location information to the controller 606.

The controller 606 is responsible for the overall control of the navigation device. For example, DEM data reflecting location information from the GPS module unit 602 and altitude from the map data DB 610 is provided to the DEM visualization unit 608.

The DEM visualization unit 608 performs rendering using the location information provided from the control unit 606 and the DEM data reflecting the altitude, and provides the result to the output unit 604.

The output unit 604 displays status information, a limited number of characters, and terrain information generated during the operation of the navigation device. That is, the terrain is displayed in three dimensions by using the DEM data rendered by the DEM visualization unit 608. The output unit 604 may use a color liquid crystal display (LCD).

The terrain data input unit 630 provides the result of the contour data obtained from the satellite photograph or map to the DEM data generator 640 in an ordered pair consisting of coordinates on a two-dimensional plane of a sample point and an altitude value at that point.

The DEM data generator 640 divides the terrain data from the terrain data input unit 630 into a predetermined grid size, reads an elevation value (or height value) of four points in the grid, and reflects the altitude of the DEM. Generate data. To this end, the DEM data generator 640 includes an altitude difference comparison 642, a triangular divider 644, and a triangular strip generator 646.

The triangle dividing unit 644 reads information about an elevation value, and when triangle strip generation is impossible, a triangle is generated by overlapping triangles or a strip not overlapping triangles. For example, in the case of forming a triangle using an altitude difference, first, as shown in FIG. 10 (b), triangles are overlapped with 0, 4, 1, 5, 6, 1, 2, 6, 3, and 7 Strips may be created, in other embodiments 0, 4, 1, 5, 6, 6, 1, 2, 2, 6, 3, 7 strips may be created without overlapping triangles, and in another example triangles When the strip is formed and no triangle is formed, another strip is added. For example, create a first strip using triangles up to 0, 4, 1, 5, 6, then subtract 1, 2, 6, 3, 7 when no triangle is formed (5, 6, 2). 2 Create a strip.

The altitude difference comparison 642 compares the first altitude difference and the second altitude difference by calculating a first altitude difference and a second altitude difference from an elevation value of four points. For example, as shown in FIG. 5, four elevation values 500, 520, 500, and 490 forming one grid among terrains divided into a plurality of grids are provided from the terrain data input unit 630. The first elevation difference is the difference between the elevation points 520m and 490m on the diagonal, and the second elevation difference is the difference between the elevation points 500m and 500m on the other diagonal.

When the first altitude difference is greater than the second altitude difference, the triangular divider 644 divides the grid by connecting the elevation points forming the second altitude differences, and the triangular strip generator 646 sets the elevation points forming the second altitude differences. Generate DEM data from triangles made up of connections. On the other hand, when the first altitude difference is smaller than the second altitude difference, the triangular divider 644 divides the grid by connecting the elevation points forming the first altitude differences, and the triangular strip generator 646 divides the first altitude differences. DEM data is generated from a triangle consisting of connecting elevation points.

The map data DB 610 stores the DEM data generated from the DEM data generator 640 and provides the DEM data to the controller 606 when requested.

7 is a flowchart illustrating visualization of DEM data according to an embodiment of the present invention.

Referring to FIG. 7, the DEM data generator 640 reads an elevation value (or height value) of four points in the current grid in step 700, and in step 702, the first altitude difference LTRB and the second altitude difference RTLB. Calculate

For example, as shown in FIG. 5, four elevation values 500, 520, 500, and 490 forming one grid among terrains divided into a plurality of grids are provided from the terrain data input unit 630. The first elevation difference is the difference between the elevation points 520m and 490m on the diagonal, and the second elevation difference is the difference between the elevation points 500m and 500m on the other diagonal.

In operation 704, the altitude difference comparing unit 642 compares the first altitude difference with the second altitude difference. If the first altitude difference is greater than the second altitude difference, the triangular division unit 644 divides the grid by connecting elevation points forming the second altitude differences in step 706, and the triangular strip generator 646 divides the second altitude differences. DEM data is generated from a triangle formed by connecting elevation points. On the other hand, when the first altitude difference is smaller than the second altitude difference, the triangular divider 644 divides the grid by connecting the elevation points forming the first altitude differences in step 708, and the triangular strip generator 646 the first altitude difference. DEM data is generated from a triangle formed by connecting elevation points.

For example, FIG. 9 shows an example of triangulation according to the comparison of the first altitude difference and the second altitude difference. The difference between altitude 1 and altitude 4 and the difference between altitude 2 and altitude 3 is obtained from a grid consisting of altitude 1, altitude 2, altitude 3, and altitude 4 (Fig. 9 (a)).

If the difference between the altitude 1 and the altitude 4 and the difference between the altitude 2 and the altitude 3 is smaller, the grid is divided into two triangles by connecting the altitude 1 and the altitude 4 (Fig. 9 (b)). On the other hand, when the difference between the altitude 1 and the altitude 4 and the difference between the altitude 2 and the altitude 3 is greater, the grid is divided into two triangles by connecting the altitude 2 and the altitude 3 (FIG. 9 (c)).

Thereafter, the DEM data generator 640 checks whether there is a grating to be triangulated in step 710, and if so, proceeds to step 712 and reads information about the next grating (four elevation points). In addition, steps 700 to 710 are performed to generate a triangular strip.

The procedure of the present invention is then terminated.

8 is a flowchart for generating a triangular stream for visualizing DEM data according to an embodiment of the present invention.

Referring to FIG. 8, the triangle divider 644 adds three elevation values forming a starting triangle to the stream in step 800.

In operation 802, the triangle dividing unit 644 determines whether a strip can be generated by adding a next elevation value.

If it is possible to generate a strip for the next vertex, the DEM visualization unit 608 proceeds to step 810 and proceeds to step 810 to read information about the next elevation value.

On the other hand, if it is impossible to generate a strip for the next vertex, the triangle divider 644 proceeds to step 804 to generate a strip by overlapping triangles or a strip without overlapping triangles.

Thereafter, the triangle dividing unit 644 checks whether there is a next elevation value in step 806, and if there is a next elevation value, the flow proceeds to step 810 to read information about the next elevation value.

For example, when the terrain is divided into three grids to form a triangle in a predetermined direction (Fig. 10 (a)), the terrain is divided into three grids to form a triangle to reflect the altitude difference (Fig. 10). (b)), a triangular strip is produced.

As shown in FIG. 10 (a), when triangles are formed in a constant direction, strips are generated at 0, 4, 1, 5, 2, 6, 3, and 7.

According to the present invention, in the case of forming a triangle using an altitude difference, first, the triangle is overlapped with 0, 4, 1, 5, 6, 1, 2, 6, 3, 7 as shown in FIG. To generate a strip, in another embodiment 0, 4, 1, 5, 6, 6, 1, 2, 2, 6, 3, 7 to create a strip without overlapping triangles, as another example When a triangle is formed and a strip is formed, another strip is created by adding another strip. For example, create a first strip using triangles up to 0, 4, 1, 5, 6, then subtract 1, 2, 6, 3, 7 when no triangle is formed (5, 6, 2). 2 Create a strip.

If the next elevation value does not exist, the DEM visualization unit 608 proceeds to step 808 to perform rendering using triangle strip data.

The procedure of the present invention is then terminated.

Meanwhile, in the detailed description of the present invention, specific embodiments have been described, but various modifications are possible without departing from the scope of the present invention. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be determined not only by the scope of the following claims, but also by the equivalents of the claims.

1 is an exemplary diagram of visualizing the DEM data in three dimensions after generating DEM data from the contour terrain data according to the present invention;

2 is an exemplary diagram of rendering DEM data in three dimensions according to the present invention;

3 is another exemplary diagram of rendering DEM data in three dimensions according to the present invention;

4 is a rendering example using a triangle in the prior art and the present invention,

FIG. 5 is a rendering example when the altitude is not reflected and the altitude is reflected in FIG. 4 according to an embodiment of the present invention; FIG.

6 is an apparatus diagram for visualizing DEM data according to an embodiment of the present invention;

7 is a flowchart for visualizing DEM data according to an embodiment of the present invention;

8 is a flowchart for generating a triangular stream for visualizing DEM data according to an embodiment of the present invention;

9 is an exemplary view of triangulation according to a comparison between a first altitude difference and a second altitude difference;

10 illustrates an example of creating a triangular strip.

Claims (16)

In the method for visualizing the digital elevation model (DEM), Receiving terrain data divided into grids composed of at least one four elevation points; Calculating and comparing a first altitude difference and a second altitude difference for each grid; Dividing the grid into two triangles according to the difference between the first elevation difference and the second elevation difference; Generating a triangular strip from the divided triangles. The method of claim 1, And wherein the first elevation difference is a difference value between two elevation points existing on a first diagonal line, and the second elevation difference is a difference value between two elevation points existing on a second diagonal line. The method of claim 1, And when the first altitude difference is greater than the second altitude difference, connecting two elevation points of the second altitude difference to divide one grid into two triangles. The method of claim 1, And when the first altitude difference is less than the second altitude difference, connecting two elevation points of the first altitude difference to divide one grid into two triangles. The method of claim 1, The process of generating a triangle strip from the divided triangle, When one elevation point is added, if the triangle is not formed, the triangle is overlapped by overlapping the previous elevation point. The method of claim 1, The process of generating a triangle strip from the divided triangle, When one elevation point is added, if the triangle is not formed, the current elevation point is overlapped so that the triangle is not overlapped. The method of claim 1, The process of generating a triangle strip from the divided triangle, When one elevation point is added, if a triangle is not formed, generation of the triangle stream currently generated is stopped, and a new triangle stream is generated. The method of claim 1, The method further comprises the step of rendering using the generated triangular strip. In the apparatus for the visualization of Digital Elevation Model (DEM), A DEM data generation unit for receiving terrain data divided into grids composed of at least one four elevation points; An altitude difference comparison unit for calculating and comparing a first altitude difference and a second altitude difference with respect to each of the grids; A triangular divider for dividing a grid into two triangles according to the difference between the first elevation difference and the second elevation difference; And a triangular strip generator for generating triangular strips from the divided triangles. The method of claim 9, Wherein the first altitude difference is a difference value between two elevation points existing at a first diagonal line, and the second altitude difference is a difference value between two elevation points existing at a second diagonal line. The method of claim 9, The triangular divider And when the first altitude difference is greater than the second altitude difference, connecting two elevation points of the second altitude difference to divide one grid into two triangles. The method of claim 9, The triangular divider And when the first altitude difference is smaller than the second altitude difference, connecting two elevation points of the first altitude difference to divide one grid into two triangles. The method of claim 9, The triangular strip generator And when one elevation point is added, if no triangle is formed, the previous elevation point overlaps the triangle. The method of claim 9, The triangular strip generator When one elevation point is added, if the triangle is not formed, the current elevation point is overlapped so that the triangle is not overlapped. The method of claim 9, The triangular strip generator When one elevation point is added, if a triangle is not formed, the current triangle stream generation is stopped and a new triangle stream is generated. The method of claim 9, The apparatus further comprises a DEM visualization unit that renders using the generated triangular strip.

Images