Method and apparatus for three-dimensionally transforming two-dimensional linear data in accordance with three-dimensional topography data in real time and method and apparatus for three-dimensionally visualizing two-dimensional linear data together with three-dimensional topography data in real time

• US 20060129320A1
• Filed: 08/10/2005
• Published: 06/15/2006
• Est. Priority Date: 12/14/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Shinjun, Lee, Heesae, Kim, Dokyoon, Ahn, Jeonghwan, Lee, Keechang
• Granted Patent: US 7,411,587 B2
• Time in Patent Office: Days
• US Class Current: 702/5
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A method and apparatus for three-dimensionally transforming two-dimensional linear data in real time and a method and apparatus for three-dimensionally visualizing the two-dimensional linear data in real time. The method of three-dimensionally transforming two-dimensional linear data in real time includes: searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data; calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles; calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data; and calculating heights of the calculated intersection points. The two-dimensional linear data is three-dimensionally transformed in accordance with three-dimensional topography data in real time and three-dimensionally visualized together with three-dimensional topography data in real time, so that map information can be perceived intuitively and conveniently by a user.

Claims

1. A method of three-dimensionally transforming two-dimensional linear data in accordance with three-dimensional topography data in real time, comprising:

searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data; and

calculating heights of the calculated intersection points.

2. The method according to claim 1, further comprising:

determining an expression format of the three-dimensional topography data; and

generating triangle strips containing coordinates of the triangles constituting the three-dimensional topography data when an expression format is a digital elevation model (DEM) format.

3. The method according to claim 1, wherein the calculating heights of the vertexes comprises:

obtaining a plane equation ax+by+cz+d=0 for a plane containing the searched triangles; and

obtaining z coordinates of the vertexes by substituting x and y coordinates of the vertexes into the plane equation.

4. The method according to claim 3, wherein the obtaining a plane equation comprises:

selecting one of three angular points of each of the triangles;

obtaining vectors from the selected angular point of each of the triangles to the other two angular points of each of the triangles;

obtaining values of a, b, and c of the plane equation by calculating vector products of the obtained vectors; and

obtaining a value of d of the plane equation by substituting the coordinates of the selected angular point in the plane equation.

5. The method according to claim 1, wherein the three-dimensional topography data is expressed by using a triangulated irregular network (TIN) format.

6. The method according to claim 5, wherein the searching triangles comprises:

calculating boundary rectangles in which respective triangles constituting three-dimensional topography data are inscribed;

searching at least one boundary rectangle containing the vertexes among the calculated boundary rectangles;

defining a triangle corresponding to the searched boundary rectangle as a vertex-containing triangle in which the vertex is contained, when the number of the searched boundary rectangles is one; and

searching the vertex-containing triangle by determining whether or not the triangles corresponding to the boundary rectangles contain the vertex, when the number of the searched boundary rectangles is more than one.

7. The method according to claim 6, wherein the searching at least one boundary rectangle comprises:

arranging the searched boundary rectangles in an order of sizes of the x coordinates of the respective vertexes;

searching among the boundary rectangles arranged in an order of sizes of the x coordinates at least one of the boundary rectangles, the x coordinates of the vertexes being between the x coordinates of the vertexes;

arranging the searched boundary rectangles in an order of sizes of the y coordinates of the vertexes; and

searching among the boundary rectangles arranged in an order of sizes of the y coordinates at least one of the boundary rectangles, the y coordinates of the vertexes being between the y coordinates of the corners of the vertexes.

8. The method according to claim 5, wherein the calculating intersection points comprises:

calculating boundary rectangles in which respective triangles constituting the three-dimensional topography data are inscribed;

determining the boundary rectangles containing a portion of the straight line or a whole straight line; and

calculating intersection points between the straight line and the triangle corresponding to the boundary rectangle.

9. The method according to claim 1, wherein the three-dimensional topography data is expressed by using a digital elevation model (DEM) format.

10. The method according to claim 9, wherein the calculating intersection points comprises:

determining x coordinates of end points of bases of the triangles constituting the three-dimensional topography data;

calculating y coordinates of the intersection points by substituting the x coordinates of the end points of the bases in a linear equation;

determining y coordinates of bases of the triangles constituting the three-dimensional topography data;

calculating x coordinates of the intersection points by substituting the y coordinates of the base in the linear equation; and

obtaining two-dimensional coordinates of intersection points between hypotenuses of the triangles and the straight line.

11. The method according to claim 10, further comprising arranging the calculated intersection points in an order of a distance from one end point of the straight line.

12. The method according to claim 9, wherein the calculating heights of the calculated intersection points comprises calculating heights of the intersection points by performing an interpolation process using the coordinates of the vertexes of the triangles corresponding to the intersection points.

13. The method according to claim 9, further comprising calculating heights of the vertexes constituting the two-dimensional linear data by performing an interpolation process,

wherein the vertexes exist outside cells constituting the three-dimensional topography data, and

wherein the interpolation process is performed by using coordinates of angular points of a nearest cell of each of the vertexes constituting the two-dimensional linear data.

14. The method according to claim 1, wherein the two-dimensional linear data is data on a road, a railroad, or a river.

15. An apparatus for three-dimensionally transforming two-dimensional linear data in accordance with three-dimensional topography data in real time, comprising:

a triangle search unit searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

a vertex height calculation unit calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

an intersection point calculation unit calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data; and

an intersection point height calculation unit calculating heights of the calculated intersection points.

16. The apparatus according to claim 15, further comprising:

a topography determination unit determining an expression format of the three-dimensional topography data; and

a triangle strip generation unit generating triangle strips containing coordinates of the triangles constituting the three-dimensional topography data when an expression format is a digital elevation model (DEM) format.

17. The apparatus according to claim 15, wherein the vertex height calculation unit comprises:

a plane equation calculation unit obtaining a plane equation ax+by+cz+d=0 for a plane containing the searched triangles;

a z-coordinate calculation unit obtaining z coordinates of the vertexes by substituting x and y coordinates of the vertexes into the plane equation.

18. The apparatus according to claim 15, wherein the three-dimensional topography data is expressed by using a triangulated irregular network (TIN) format.

19. The apparatus according to claim 18, wherein the triangle search unit comprises:

a boundary rectangle calculation unit calculating boundary rectangles in which respective triangles constituting three-dimensional topography data are inscribed;

a boundary rectangle search unit searching at least one boundary rectangle containing the vertexes among the calculated boundary rectangles;

a triangle determination unit, when the number of the searched boundary rectangles is one, defining a triangle corresponding to the searched boundary rectangle as a vertex-containing triangle in which the vertex is contained and when the number of the searched boundary rectangles is more than one, searching the vertex-containing triangle by determining whether or not the triangles corresponding to the boundary rectangles contain the vertex.

20. The apparatus according to claim 19, wherein the boundary rectangle search unit comprises:

a first arrangement unit arranging the searched boundary rectangles in an order of sizes of the x coordinates of the vertexes;

a first search unit searching among the boundary rectangles arranged in an order of sizes of the x coordinates at least one of the boundary rectangles, the x coordinates of the vertexes being between the x coordinates of the vertexes; and

a second arrangement unit arranging the searched boundary rectangles in an order of sizes of the y coordinates of the vertexes;

a second search unit searching among the boundary rectangles arranged in an order of sizes of the y coordinates at least one of the boundary rectangles, the y coordinates of the vertexes being between the y coordinates of the corners of the vertexes.

21. The apparatus according to claim 15, wherein the three-dimensional topography data is expressed by using a digital elevation model (DEM) format.

22. The apparatus according to claim 21, wherein the intersection point calculation unit comprises:

an x-coordinate determination unit determining x coordinates of end points of bases of the triangles constituting the three-dimensional topography data;

a y-coordinate calculation unit calculating y coordinates of the intersection points by substituting the x coordinates of the end points of the bases in a linear equation;

a y-coordinate determination unit determining y coordinates of bases of the triangles constituting the three-dimensional topography data;

an x-coordinate calculation unit calculating x coordinates of the intersection points by substituting the y coordinates of the base in the linear equation; and

a hypotenuse intersection point calculation unit obtaining two-dimensional coordinates of intersection points between hypotenuses of the triangles and the straight line.

23. The apparatus according to claim 22, wherein the intersection point calculation unit arranges the calculated intersection points in an order of a distance from one end point of the straight line.

24. The apparatus according to claim 21, wherein the arranging comprises calculating heights of the intersection points by performing an interpolation process using the coordinates of the vertexes of the triangles corresponding to the intersection points.

25. The apparatus according to claim 21, further comprising an outer vertex height calculation unit calculating heights of the vertexes constituting the two-dimensional linear data by performing an interpolation process,

wherein the vertexes exist outside cells constituting the three-dimensional topography data, and

wherein the interpolation process is performed by using coordinates of angular points of a nearest cell of each of the vertexes constituting the two-dimensional linear data.

26. The apparatus according to claim 15, wherein the two-dimensional linear data is data on a road, a railroad, or a river.

27. A method of three-dimensionally visualizing two-dimensional linear data together with three-dimensional topography data in real time, comprising:

searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data;

calculating heights of the calculated intersection points; and

outputting the two-dimensional linear data in a three-dimensional format by using the three-dimensional coordinates of the vertexes and the three-dimensional coordinates of the intersection points.

28. The method according to claim 27, further comprising:

determining an expression format of the three-dimensional topography data; and

generating triangle strips containing coordinates of the triangles constituting the three-dimensional topography data when the expression format is a digital elevation model (DEM) format.

29. The method according to claim 28, further comprising outputting all the coordinate values constituting the triangle strips to an output device at one time.

30. The method according to claim 27, wherein the calculating heights of the vertexes comprises:

obtaining a plane equation ax+by+cz+d=0 for a plane containing the searched triangles; and

obtaining z coordinates of the vertexes by substituting x and y coordinates of the vertexes into the plane equation.

31. The method according to claim 30, wherein the obtaining a plane equation comprises:

selecting one of three angular points of each of the triangles;

obtaining vectors from the selected angular point of each of the triangles to the other two angular points of each of the triangles;

obtaining values of a, b, and c of the plane equation by calculating vector products of the obtained vectors; and

obtaining a value of d of the plane equation by substituting the coordinates of the selected angular point in the plane equation.

32. The method according to claim 27, wherein the three-dimensional topography data is expressed by using a triangulated irregular network (TIN) format.

33. The method according to claim 32, wherein the searching triangles comprises:

calculating boundary rectangles in which respective triangles constituting three-dimensional topography data are inscribed;

searching at least one boundary rectangle containing the vertexes among the calculated boundary rectangles;

defining a triangle corresponding to the searched boundary rectangle as a vertex-containing triangle in which the vertex is contained, when the number of the searched boundary rectangles is one; and

searching the vertex-containing triangle by determining whether or not the triangles corresponding to the boundary rectangles contain the vertex, when the number of the searched boundary rectangles is more than one.

34. The method according to claim 33, wherein the searching at least one boundary rectangle comprises:

arranging the searched boundary rectangles in an order of sizes of the x coordinates of the vertexes;

searching among the boundary rectangles arranged in an order of sizes of the x coordinates at least one of the boundary rectangles, the x coordinates of the vertexes being between the x coordinates of the vertexes;

arranging the searched boundary rectangles in an order of sizes of the y coordinates of the vertexes; and

searching among the boundary rectangles arranged in an order of sizes of the y coordinates at least one of the boundary rectangles, the y coordinates of the vertexes being between the y coordinates of the corners of the vertexes.

35. The method according to claim 32, wherein the calculating intersection points comprises:

calculating boundary rectangles in which respective triangles constituting the three-dimensional topography data are inscribed;

determining the boundary rectangles containing a portion of the straight line or a whole straight line; and

calculating intersection points between the straight line and the triangle corresponding to the boundary rectangle.

36. The method according to claim 27, wherein the three-dimensional topography data is expressed by using a digital elevation model (DEM) format.

37. The method according to claim 36, wherein the calculating intersection points comprises:

determining x coordinates of end points of bases of the triangles constituting the three-dimensional topography data;

calculating y coordinates of the intersection points by substituting the x coordinates of the end points of the bases in a linear equation;

determining y coordinates of bases of the triangles constituting the three-dimensional topography data;

calculating x coordinates of the intersection points by substituting the y coordinates of the base in the linear equation; and

obtaining two-dimensional coordinates of intersection points between hypotenuses of the triangles and the straight line.

38. The method according to claim 37, further comprising arranging the calculated intersection points in an order of a distance from one end point of the straight line.

39. The method according to claim 36, wherein the calculating heights of the calculated intersection points comprises calculating heights of the intersection points by performing an interpolation process using the coordinates of the vertexes of the triangles corresponding to the intersection points.

40. The method according to claim 36, further comprising calculating heights of the vertexes constituting the two-dimensional linear data by performing an interpolation process,

wherein the vertexes exist outside cells constituting the three-dimensional topography data, and

wherein the interpolation process is performed by using coordinates of angular points of a nearest cell of each of the vertexes constituting the two-dimensional linear data.

41. The method according to claim 27, wherein the two-dimensional linear data is data on a road, a railroad, or a river.

42. An apparatus for three-dimensionally visualizing two-dimensional linear data together with three-dimensional topography data in real time, comprising:

a triangle search unit searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

a vertex height calculation unit calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

an intersection point calculation unit calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data;

an intersection point height calculation unit calculating heights of the calculated intersection points; and

a data output unit storing the three-dimensional coordinates of the vertexes and the three-dimensional coordinates of the intersection points and outputting the two-dimensional linear data as a three-dimensional format by using the three-dimensional coordinates of the vertexes and the three-dimensional coordinates of the intersection points.

43. The apparatus according to claim 42, further comprising:

a topography determination unit determining an expression format of the three-dimensional topography data; and

a triangle strip generation unit generating triangle strips containing coordinates of the triangles constituting the three-dimensional topography data if the expression format is a digital elevation model (DEM) format.

44. The apparatus according to claim 43, wherein the data output unit comprises a triangle coordinate output unit outputting all the coordinate values constituting the triangle strips to an output device at one time.

45. The apparatus according to claim 42, wherein the vertex height calculation unit comprises:

a plane equation calculation unit obtaining a plane equation ax+by+cz+d=0 for a plane containing the searched triangles; and

a z-coordinate calculation unit obtaining z coordinates of the vertexes by substituting x and y coordinates of the vertexes into the plane equation.

46. The apparatus according to claim 42, wherein the three-dimensional topography data is expressed by using a triangulated irregular network (TIN) format.

47. The apparatus according to claim 46, wherein the triangle search unit comprises:

a boundary rectangle calculation unit calculating boundary rectangles in which respective triangles constituting three-dimensional topography data are inscribed;

a boundary rectangle search unit searching at least one boundary rectangle containing the vertexes among the calculated boundary rectangles; and

a triangle determination unit, when the number of the searched boundary rectangles is one, defining a triangle corresponding to the searched boundary rectangle as a vertex-containing triangle in which the vertex is contained and when the number of the searched boundary rectangles is more than one, searching the vertex-containing triangle by determining whether the triangles corresponding to the boundary rectangles contain the vertex.

48. The apparatus according to claim 47, wherein the boundary rectangle search unit comprises:

a first arrangement unit arranging the searched boundary rectangles in an order of sizes of the x coordinates of the vertexes;

a first search unit searching among the boundary rectangles arranged in an order of sizes of the x coordinates at least one of the boundary rectangles, the x coordinates of the vertexes being between the x coordinates of the vertexes;

a second arrangement unit arranging the searched boundary rectangles in an order of sizes of the y coordinates of the vertexes; and

a second search unit searching among the boundary rectangles arranged in an order of sizes of the y coordinates at least one of the boundary rectangles, the y coordinates of the vertexes being between the y coordinates of the corners of the vertexes.

49. The apparatus according to claim 42, wherein the three-dimensional topography data is expressed by using a digital elevation model (DEM) format.

50. The apparatus according to claim 49, wherein the intersection point calculation unit comprises:

an x-coordinate determination unit determining x coordinates of end points of bases of the triangles constituting the three-dimensional topography data;

a y-coordinate calculation unit calculating y coordinates of the intersection points by substituting the x coordinates of the end points of the bases in a linear equation;

a y-coordinate determination unit determining y coordinates of bases of the triangles constituting the three-dimensional topography data;

an x-coordinate calculation unit calculating x coordinates of the intersection points by substituting the y coordinates of the base in the linear equation; and

a hypotenuse intersection point calculation unit obtaining two-dimensional coordinates of intersection points between hypotenuses of the triangles and the straight line.

51. The apparatus according to claim 50, wherein the intersection point calculation unit arranges the calculated intersection points in an order of a distance from one end point of the straight line.

52. The apparatus according to claim 49, wherein the arranging comprises calculating heights of the intersection points by performing an interpolation process using the coordinates of the vertexes of the triangles corresponding to the intersection points.

53. The apparatus according to claim 49, further comprising an outer vertex height calculation unit calculating heights of the vertexes constituting the two-dimensional linear data by performing an interpolation process,

wherein the vertexes exist outside cells constituting the three-dimensional topography data, and

wherein the interpolation process is performed by using coordinates of angular points of a nearest cell of each of the vertexes constituting the two-dimensional linear data.

54. The apparatus according to claim 42, wherein the two-dimensional linear data is data on a road, a railroad, or a river.

55. A computer-readable medium having embodied thereon a computer program for a method of three-dimensionally transforming two-dimensional linear data in accordance with three-dimensional topography data in real time, the method comprising:

searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data; and

calculating heights of the calculated intersection points.

56. A computer-readable medium having embodied thereon a computer program for a method of three-dimensionally transforming two-dimensional linear data in accordance with three-dimensional topography data in real time, the method comprising:

searching triangles in which vertexes constituting the two-dimensional linear data are contained among triangles constituting the three-dimensional topography data;

calculating heights of the vertexes by using three-dimensional coordinates of the searched triangles;

calculating intersection points between the triangles constituting the three-dimensional topography data and straight lines constituting the two-dimensional linear data;

calculating heights of the calculated intersection points; and

outputting the two-dimensional linear data as a three-dimensional format by using the three-dimensional coordinates of the vertexes and the three-dimensional coordinates of the intersection points.