Method and apparatus for 3D path

• US 8,823,698 B2
• Filed: 06/30/2008
• Issued: 09/02/2014
• Est. Priority Date: 05/14/2008
• Status: Active Grant

• Current Assignee: Thinkware Systems Corporation
• Original Assignee: Thinkware Systems Corporation
• Inventors: Seo, Jung Kak
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): CHEN, FRANK S
• Application Number:
  US12/992,173
• Publication Number:
  US 20110074774A1
• Time in Patent Office: 2,255 Days
• US Class Current: 345/419
• CPC Class Codes: G01C 21/3635 Guidance using 3D or perspective road maps
• 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 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images

Abstract

An apparatus and method for generating a three-dimensional (3D) path are provided. The apparatus includes: a polygon generation unit to generate a left polygon and a right polygon on the left and the right of path data, respectively, based on a linear interpolation point of the path data; and a polygon conversion unit to apply a height value to the linear interpolation point based on the left polygon and the right polygon and to thereby generate the 3D path.

Claims

1. An apparatus for generating a three-dimensional (3D) path, the apparatus comprising:

a path generation unit to generate a map using map data between a location of the 3D path generating apparatus and a destination, and to generate a path from the location to the destination on the generated map,

a polygon generation unit to generate a left polygon and a right polygon on the left and the right of path data, respectively, based on a linear interpolation point of the path data; and

a polygon conversion unit to apply a height value to the linear interpolation point to thereby generate a 3D path vertex, and to connect the left polygon and the right polygon to the 3D path vertex to thereby generate the 3D path; and

an inappropriate data removal unit to remove an inappropriate linear interpolation point in the path data and to provide, to the polygon generation unit, the path data in which the inappropriate linear interpolation point is removed,

wherein the path data includes a path having a first linear interpolation point, a second linear interpolation point immediately following the first linear interpolation point, and a third linear interpolation point immediately following the second linear interpolation point, and

wherein, when the third linear interpolation point is a retrograde linear interpolation point against a heading direction of the path, such that the retrograde linear interpolation point is closer to the first linear interpolation point of the path than the second linear interpolation point is to the first linear interpolation point of the path, the inappropriate data removal unit determines the third linear interpolation point as an inappropriate linear interpolation point to thereby remove the determined inappropriate linear interpolation point.

2. The apparatus of claim 1, wherein, when a plurality of linear interpolation points exists in the path data within a predetermined distance, the inappropriate data removal unit selects any one linear interpolation point from the plurality of linear interpolation points, and determines the remaining linear interpolation points as inappropriate linear interpolation points to thereby remove the determined inappropriate linear interpolation points.

3. The apparatus of claim 1, wherein the polygon generation unit calculates a left direction vector and a right direction vector at the linear interpolation point, generates a left polygon point and a right polygon point at the left and the right of the linear interpolation point, based on the left direction vector and the right direction vector, respectively, connects the linear interpolation point and the left polygon point to thereby generate the left polygon, and connects the linear interpolation point and the right polygon point to thereby generate the right polygon.

4. The apparatus of claim 3, wherein the polygon generation unit rotates a heading direction vector of a first linear interpolation point of the path data at a designated angle to thereby calculate a first left direction vector and a first right direction vector, and the polygon generation unit generates the left polygon point and the right polygon point at points that are moved from the first linear interpolation point to the left and the right thereof by a predetermined distance in correspondence to the first left direction vector and the first right direction vector.

5. The apparatus of claim 3, wherein the polygon generation unit calculates a heading left direction vector and a heading right direction vector at another linear interpolation point excluding a first linear interpolation point and a last linear interpolation point of the path data based on an angle difference between linear interpolation points, and the polygon generation unit generates the left polygon point at an intersecting point between a straight line corresponding to the heading left direction vector and a straight line corresponding to the heading direction of the path data based on a left polygon point that is generated at a previous linear interpolation point, and generates the right polygon point at an intersecting point between a straight line corresponding to the heading right direction vector and the straight line corresponding to the heading direction of the path data based on a right polygon point that is generated at the previous linear interpolation point, based on another linear interpolation point excluding the first linear interpolation point and the last linear interpolation point.

6. The apparatus of claim 3, wherein the polygon generation unit rotates a heading direction vector of a last linear interpolation point of the path data at a designated angle to thereby calculate a last left direction vector and a last right direction vector, and wherein the polygon generation unit generates the left polygon point and the right polygon point at points that are moved from the last linear interpolation point to the left and the right thereof by a predetermined distance in correspondence to the last left direction vector and the last right direction vector.

7. The apparatus of claim 1, wherein the polygon conversion unit triangulates the 3D path to thereby display the 3D path in a 3D form.

8. A method of generating a 3D path, the method comprising:

generating a map, by a 3D path generating apparatus, using map data between a location of the 3D path generating apparatus and a destination;

generating a path from the location to the destination on the generated map;

generating a left polygon and a right polygon on the left and the right of path data, respectively, based on a linear interpolation point of the path data;

applying a height value to the linear interpolation point to thereby generate a 3D path vertex;

connecting the left polygon and the right polygon to the 3D path vertex to thereby generate the 3D path; and

removing an inappropriate linear interpolation point in the path data,

wherein the generating of the left polygon and the right polygon comprises generating the left polygon and the right polygon on using the path data in which the inappropriate linear interpolation point is removed,

wherein the path data includes a path having a first linear interpolation point, a second linear interpolation point immediately following the first linear interpolation point, and a third linear interpolation point immediately following second linear interpolation point, and

wherein, when the third linear interpolation point is a retrograde linear interpolation point against a heading direction of the path, such that the third linear interpolation point is closer to the first linear interpolation point of the path than the second linear interpolation point is to the first linear interpolation point of the path, the removing of the inappropriate linear interpolation point comprises determining the third linear interpolation point as an inappropriate linear interpolation point to thereby remove the determined inappropriate linear interpolation point.

9. The method of claim 8, wherein, when a plurality of linear interpolation points exists in the path data within a predetermined distance, the removing of the inappropriate linear interpolation point comprises selecting any one linear interpolation point from the plurality of linear interpolation points, and determining the remaining linear interpolation points as inappropriate linear interpolation points to thereby remove the determined inappropriate linear interpolation points.

10. The method of claim 8, wherein the generating of the left polygon and the right polygon comprises:

calculating a left direction vector and a right direction vector at the linear interpolation point;

generating a left polygon point and a right polygon point at the left and the right of linear interpolation point, based on the left direction vector and the right direction vector, respectively; and

connecting the linear interpolation point and the left polygon point to thereby generate the left polygon, and connecting the linear interpolation point and the right polygon point to thereby generate the right polygon.

11. The method of claim 10, wherein the calculating of the left direction vector and the right direction vector comprises rotating a heading direction vector of a first linear interpolation point of the path data at a designated angle to thereby calculate a first left direction vector and a first right direction vector, and the generating of the left polygon point and the right polygon point comprises generating the left polygon point and the right polygon point at points that are moved from the first linear interpolation point to the left and the right thereof by a predetermined distance in correspondence to the first left direction vector and the first right direction vector.

12. The method of claim 10, wherein the calculating of the left direction vector and the right direction vector comprises calculating a heading left direction vector and a heading right direction vector at another linear interpolation point excluding a first linear interpolation point and a last linear interpolation point of the path data based on an angle difference between linear interpolation points, and the generating of the left polygon point and the right polygon point comprises generating the left polygon point at an intersecting point between a straight line corresponding to the heading left direction vector and a straight line corresponding to the heading direction of the path data based on a left polygon point that is generated at a previous linear interpolation point, and generating the right polygon point at an intersecting point between a straight line corresponding to the heading right direction vector and the straight line corresponding to the heading direction of the path data based on a right polygon point that is generated at the previous linear interpolation point, based on another linear interpolation point excluding the first linear interpolation point and the last linear interpolation point.

13. The method of claim 10, wherein the calculating of the left direction vector and the right direction vector comprises rotating a heading direction vector of a last linear interpolation point of the path data at a designated angle to thereby calculate a last left direction vector and a last right direction vector, and the generating of the left polygon point and the right polygon point comprises generating the left polygon point and the right polygon point at points that are moved from the last linear interpolation point to the left and the right thereof by a predetermined distance in correspondence to the last left direction vector and the last right direction vector.

14. The method of claim 8, further comprising:

triangulating the 3D path to display the 3D path in a 3D form.

15. A non-transitory computer-readable recording medium storing a program for implementing the method according to claim 8.