Method, apparatus, and medium for three-dimensionally transforming and visualizing two-dimensional flyover data in three-dimensional graphics environment

• US 7,982,735 B2
• Filed: 09/15/2005
• Issued: 07/19/2011
• Est. Priority Date: 01/25/2005
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Shinjun, Lee, Heesae, Kim, Dokyoon, Ahn, Jeonghwan, Lee, Keechang
• Primary Examiner(s): Nguyen; Phu
• Application Number:
  US11/226,201
• Publication Number:
  US 20060164416A1
• Time in Patent Office: 2,133 Days
• Field of Search: 345/427, 345/419, 345/423, 345/582, 345/629, 345/630, 701/228
• US Class Current: 345/427
• CPC Class Codes: G01C 21/3638 including 3D objects and buildings three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

An apparatus for three-dimensionally visualizing two-dimensional flyover data in a three-dimensional graphics environment includes an overlapped region separation unit, a triangulation unit, a height coordinate addition unit, and a visualization unit. The division lines are selectively applied to a polygon to separate overlapped regions from the polygon, an ear cutting algorithm is applied to triangulate the polygon, and various different visualization processes are performed on different portions of the flyover data.

Claims

1. A method of three-dimensionally transforming two-dimensional flyover data in a three-dimensional graphics environment, comprising:

(a) generating a division line list including one or more division lines for dividing a polygon constituting the two-dimensional flyover data into two regions;

(b) selecting a division line for reducing a number of overlapped regions of the polygon among the division lines included in the division line list; and

(c) separating the polygon into regions by applying the selected division line to the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon, and

wherein the method is performed using at least one processor.

2. The method according to claim 1, wherein the operation (a) comprises:

(a1) selecting two vertexes among vertexes of the polygon; and

(a2) adding a line connecting the two vertexes to the division line list if the line does not intersect sides of the polygon and if the line exists within the polygon.

3. The method according to claim 1, further comprising (d) dividing each of the separated regions of the polygon into one or more triangles.

4. The method according to claim 3, wherein the operation (d) comprises:

(d1) searching ear vertexes among the vertexes of each of the separated regions of the polygon to generate an ear list;

(d2) selecting an ear vertex having an internal angle closest to 90°

among the ear vertexes included in the ear list; and

(d3) separating a triangle formed with the selected ear vertex and both adjacent side lines from the separated region of the polygon.

5. The method according to claim 4, wherein the operation (d1) comprises:

selecting a vertex among the vertexes of the separated region of the polygon;

selecting both vertexes adjacent to the selected vertex in the separated region of the polygon; and

adding the selected vertex to the ear list if a line connecting the both adjacent vertexes does not intersect side lines of the separated region of the polygon and if the line exist within the separated region of the polygon.

6. An apparatus for three-dimensionally transforming two-dimensional flyover data in a three-dimensional graphics environment, comprising:

a division line list generation unit to generate a division line list including one or more division lines of dividing a polygon constituting the two-dimensional flyover data into two regions;

a division line selection unit to select a division line for reducing the number of overlapped regions of the polygon among the division lines included in the division line list; and

a division line applying unit to separate the polygon into regions by applying the selected division line to the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon.

7. The apparatus according to claim 6, wherein the division line list generation unit comprises:

a vertex selection unit to select two vertexes among vertexes of the polygon; and

a division line addition unit to add a line connecting the two vertexes to the division line list if the line does not intersect side lines of the polygon and if the line exists within the polygon.

8. The apparatus according to claim 6, further comprising

a triangulation unit to divide each of the separated regions of the polygon into one or more triangles.

9. The apparatus according to claim 8, wherein the triangulation unit comprises:

an ear list generation unit to search ear vertexes among the vertexes of each of the separated regions of the polygon to generate an ear list;

an ear selection unit to select an ear vertex having an internal angle closest to 90°

among the ear vertexes included in the ear list; and

a triangle separation unit to separate a triangle formed with the selected ear vertex and both adjacent side lines from the separated region of the polygon.

10. The apparatus according to claim 9, wherein the ear list generation unit comprises:

a candidate vertex selection unit to select a vertex among the vertexes of the separated region of the polygon;

an adjacent vertex selection unit to select both vertexes adjacent to the selected vertex in the separated region of the polygon; and

an ear addition unit to add the selected vertex to the ear list if a line connecting the both adjacent vertexes does not intersect side lines of the separated region of the polygon and if the line exist within the separated region of the polygon.

11. A method of three-dimensionally visualizing two-dimensional flyover data in a three-dimensional graphics environment, comprising:

(a) separating a polygon constituting the two-dimensional flyover data into regions using one or more division lines, which are selected to reduce a number of overlapped regions of the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon;

(b) dividing each of the separated regions of the polygon into one or more triangles;

(c) generating three-dimensional flyover data by adding height coordinates to the respective vertexes of the divided triangles; and

(d) visualizing the three-dimensional flyover data,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon, and

wherein the method is performed using at least one processor.

12. The method according to claim 11, wherein the operation (a) comprises:

(a1) generating a division line list including one or more division lines of dividing the polygon constituting the two-dimensional flyover data into two regions;

(a2) selecting a division line for reducing the number of overlapped regions of the polygon among the division lines included in the division line list; and

(a3) separating the divided regions from the polygon by applying the selected division line to the polygon.

13. The method according to claim 12, wherein the operation (a1) comprises:

selecting two vertexes among vertexes of the polygon; and

adding a line connecting the two vertexes to the division line list if the line does not intersect side lines of the polygon and if the line exists within the polygon.

14. The method according to claim 11, wherein the operation (b) comprises:

(b1) searching ear vertexes among the vertexes of each of the separated regions of the polygon to generate an ear list;

(b2) selecting an ear vertex having an internal angle closest to 90°

among the ear vertexes included in the ear list; and

(b3) separating a triangle formed with the selected ear vertex and both adjacent side lines from the separated region of the polygon.

15. The method according to claim 14, wherein the operation (b1) comprises:

selecting a vertex among the vertexes of the separated region of the polygon;

selecting both vertexes adjacent to the selected vertex in the separated region of the polygon; and

adding the selected vertex to the ear list if a line connecting the both adjacent vertexes does not intersect side lines of the separated region of the polygon and if the line exist within the separated region of the polygon.

16. The method according to claim 11, wherein the operation (d) comprises:

(d1) rendering a shadow portion of the flyover; and

(d2) rendering an upper surface, a lower surface, and a guardrail of the flyover.

17. The method according to claim 16, wherein the operation (d1) comprises:

setting a transparency function and stopping a z-test function in a rendering device before the rendering of the shadow portion of the flyover starts, and restarting the z-test function after the rendering of the shadow portion of the flyover ends.

18. The method according to claim 16, wherein the operation (d2) comprises:

setting a back-face function in a rendering device.

19. The method according to claim 16, wherein the operation (d2) comprises:

applying textures to the upper surface of the flyover to render the upper surface of the flyover.

20. An apparatus for three-dimensionally visualizing two-dimensional flyover data in a three-dimensional graphics environment, comprising:

an overlapped region separation unit to separate a polygon constituting the two-dimensional flyover data into regions using one or more division lines, which are selected to reduce a number of overlapped regions of the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon;

a triangulation unit to divide each of the separated regions of the polygon into, one or more triangles;

a height coordinate addition unit to generate three-dimensional flyover data by adding height coordinates to the respective vertexes of the divided triangles; and

a visualization unit to visualize the three-dimensional flyover data,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon.

21. The apparatus according to claim 20, wherein the overlapped region separation unit comprises:

a division line list generation unit to generate a division line list including one or more division lines of dividing a polygon constituting the two-dimensional flyover data into two regions;

a division line selection unit to select a division line for reducing the number of overlapped regions of the polygon among the division lines included in the division line list; and

a division line applying unit to separate the divided regions from the polygon by applying the selected division line to the polygon.

22. The apparatus according to claim 21, wherein the division line list generation unit comprises:

a vertex selection unit to select two vertexes among vertexes of the polygon; and

a division line addition unit to add a line connecting the two vertexes to the division line list if the line does not intersect side lines of the polygon and if the line exists within the polygon.

23. The apparatus according to claim 20, wherein the triangulation unit comprises:

an ear list generation unit to search ear vertexes among the vertexes of each of the separated regions of the polygon to generate an ear list;

an ear selection unit to select an ear vertex having an internal angle closest to 90°

among the ear vertexes included in the ear list; and

a triangle separation unit to separate a triangle formed with the selected ear vertex and both adjacent side lines from the separated region of the polygon.

24. The apparatus according to claim 23, wherein the ear list generation unit comprises:

a candidate vertex selection unit to select a vertex among the vertexes of the separated region of the polygon;

an adjacent vertex selection unit to select both vertexes adjacent to the selected vertex in the separated region of the polygon; and

an ear addition unit to add the selected vertex to the ear list if a line connecting the both adjacent vertexes does not intersect side lines of the separated region of the polygon and if the line exist within the separated region of the polygon.

25. The apparatus according to claim 20, wherein the visualization unit comprises:

a shadow portion visualization unit to render a shadow portion of the flyover; and

a flyover body visualization unit to render an upper surface, a lower surface, and a guardrail of the flyover.

26. The apparatus according to claim 25, wherein the shadow portion visualization unit comprises:

a transparency setting unit to set a transparency function in a rendering device before the rendering of the shadow portion of the flyover starts, and

a z-test function setting unit to stop a z-test function in the rendering device before the rendering of the shadow portion of the flyover starts and restarting the z-test function after the rendering of the shadow portion of the flyover ends.

27. The apparatus according to claim 25, wherein the flyover body visualization unit sets a back-face function in a rendering device.

28. The apparatus according to claim 25, wherein the flyover body visualization unit applies textures to the upper surface of the flyover to render the upper surface of the flyover.

29. At least one computer-readable medium storing instructions that control at least one processor to perform a method of three-dimensionally transforming two-dimensional flyover data in a three-dimensional graphics environment, wherein the method comprises:

generating a division line list including one or more division lines of dividing a polygon constituting the two-dimensional flyover data into two regions;

selecting a division line for reducing the number of overlapped regions of the polygon among division lines included in the division line list; and

separating the polygon into regions by applying the selected division line to the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon.

30. At least one computer-readable medium storing instructions that control at least one processor to perform a method of three-dimensionally visualizing two-dimensional flyover data in a three-dimensional graphics environment, wherein the method comprises:

separating a polygon constituting the two-dimensional flyover data into regions using one or more division lines, which are selected to reduce a number of overlapped regions of the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon;

dividing each of the separated regions of the polygon into one or more triangles;

generating three-dimensional flyover data by adding height coordinates to the respective vertexes of the divided triangles; and

visualizing the three-dimensional flyover data,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon.

31. A method of three-dimensionally transforming two-dimensional flyover data in a three-dimensional graphics environment, comprising:

selecting a division line for reducing a number of overlapped regions of a polygon among a plurality of division lines, which divide a polygon comprising the two dimensional flyover data into regions; and

separating the polygon into regions by applying the selected division line to the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon,

wherein the selected division line directly connects two vertexes among vertexes forming the polygon, the selected division line does not intersect a sideline of the polygon, and the selected division line exists within the polygon, and

wherein the method is performed using at least one processor.

32. At least one computer-readable medium storing instructions that control at least one processor to perform a method of three-dimensionally transforming two-dimensional flyover data in a three-dimensional graphics environment, wherein the method comprises:

selecting a division line for reducing a number of overlapped regions of a polygon among a plurality of division lines, which divide a polygon comprising the two dimensional flyover data into regions; and

separating the polygon into regions by applying the selected division line to the polygon, wherein the separated regions overlap each other at an overlapped region within the polygon,

wherein each division line directly connects two vertexes among vertexes forming the polygon, each division line does not intersect a sideline of the polygon, and each division line exists within the polygon.