Path Planning For Street Level Navigation In A Three-Dimensional Environment, And Applications Thereof

• US 20120127170A1
• Filed: 11/22/2011
• Published: 05/24/2012
• Est. Priority Date: 11/24/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Varadhan, Gokul
• Granted Patent: US 8,686,995 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

Embodiments relate to navigating along a street network in a geographic information system. In an embodiment, a computer-implemented method navigates a virtual camera in a three-dimensional environment at street-level. The virtual camera defines a perspective to display the three-dimensional environment. In the method, a target location is determined in the three-dimensional environment. A path along a representation of a street in the three-dimensional environment is determined. The path is from a first position corresponding to an initial location of the virtual camera to a second position corresponding to the target location. A virtual camera is moved in the three-dimensional environment toward the target location along the path. Finally, the virtual camera is oriented to face the target location as the virtual camera moves along the path.

Claims

1. A computer-implemented method for street-level navigation of a virtual camera in a three-dimensional environment, the virtual camera defining a perspective to display the three-dimensional environment, comprising:

(a) determining a target location in the three-dimensional environment;

(b) determining a path along a representation of a street in the three-dimensional environment, the path being from a first position corresponding to an initial location of the virtual camera to a second position corresponding to the target location;

(c) moving a virtual camera in the three-dimensional environment toward the target location along the path determined in (b); and

(d) orienting the virtual camera to face the target location as the virtual camera moves along the path.

2. The method of claim 1, wherein the three-dimensional environment includes a plurality of building models, at least one building model in the plurality of building models positioned between the initial location of the virtual camera and the target location, whereby the virtual camera is moved along the path in (c) to avoid colliding with the at least one building model.

3. The method of claim 1, wherein determining (b) comprises:

(i) determining the path to turn at an intersection in a representation of a street network in the three-dimensional environment, and

(ii) interpolating a spline at the turn in the path to smooth motion of the virtual camera at the turn.

4. The method of claim 1, wherein the path comprises a discontinuous series of points on the representation of the street in the three-dimensional environment, wherein the moving (c) comprises:

(e) moving the virtual camera to each point in the series of points in an order specified by the series.

5. The method of claim 4, wherein each point in the series of points represents a position of a panoramic photograph.

6. The method of claim 5, wherein determining (b) comprises determining a first point in the series of points to be a position of the panoramic photograph closest to the initial location of virtual camera that does not specify that the virtual camera move away from the target location.

7. The method of claim 5, wherein determining (b) comprises determining a final point in the series of points to be a position of the panoramic photograph closest to the target location of virtual camera that does not specify that the virtual camera move past the target location.

8. The method of claim 1, wherein determining (b) comprises determining the path not to exceed a maximum length value.

9. The method of claim 1, wherein determining (a) comprises:

(i) receiving position data representing a position on a viewport selected by a user;

(ii) extending a ray based on the position selected by the user;

(iii) determining the target location to be an intersection of the ray with an object in the three-dimensional model.

10. The method of claim 1, further comprising:

(e) prefetching geographic data along the path.

12. The system of claim 10, wherein the three-dimensional environment includes a plurality of building rmodels, at least one building model in the plurality of building models positioned between the initial location of the virtual camera and the target location, whereby the virtual camera is moved along the path to avoid colliding with the at least one building model.

13. The system of claim 10, wherein the path planner module determines the path to turn at an intersection in a representation of a street network in the three-dimensional environment and interpolates a spline at the turn in the path to smooth motion of the virtual camera at the turn.

14. The system of claim 10, wherein the path comprises a discontinuous series of points on the representation of the street in the three-dimensional environment, wherein the path motion module moves the virtual camera to each point in the series and in the order specified by the series.

15. The system of claim 13, wherein each point in the series of points represents a position of a panoramic photograph.

16. The system of claim 14, wherein the path planner module determines a first point in the series of points to be a position of the panoramic photograph closest to the initial location of virtual camera that does not specify that the virtual camera move away from the target location.

17. The system of claim 14, wherein the path planner module determines a final point in the series of points to be the position of the panoramic photograph closest to the target location of virtual camera that does not specify that the virtual camera move past the target location.

18. The system of claim 10, wherein the path planner module determines the path not to exceed a maximum length value.

19. The system of claim 10, wherein the target module receives position data representing a position on a viewport selected by a user, extends a ray based on the position selected by the user, and determines the target location to be an intersection of the ray with an object in the three-dimensional model.

20. The method of claim 10, wherein the path motion module prefetches geographic data along the path.

21. The system of claim 10, further comprising:

at least one computing device that implements the target module, the path planner module, and the path motion module.

11. A system for street-level navigation of a virtual camera in a three-dimensional environment, the virtual camera defining a perspective to display the three-dimensional environment, comprising:

a target module that determines a target location in the three-dimensional environment;

a path planner module that determines a path along a representation of a street in the three-dimensional environment, the path being from a first position corresponding to an initial location of the virtual camera to a second position corresponding to the target location; and

a path motion module that moves a virtual camera in the three-dimensional environment toward the target location along the path and orients the virtual camera to face the target location as the virtual camera moves along the path.

22. A computer-implemented method for street-level navigation of a virtual camera in a three-dimensional environment, the virtual camera defining a perspective to display the three-dimensional environment, comprising:

(a) determining a target location in the three-dimensional environment;

(b) determining a path along a representation of real-world pathway in the three-dimensional environment, the path being from a first position corresponding to an initial location of the virtual camera to a second position corresponding to the target location;

thesaurus

(c) moving a virtual camera in the three-dimensional environment toward the target location along the path determined in (b); and

(d) orienting the virtual camera to face the target location as the virtual camera moves along the path.