Guided navigation through geo-located panoramas

• US 8,823,707 B2
• Filed: 11/22/2011
• Issued: 09/02/2014
• Est. Priority Date: 11/24/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Barcay, Daniel, Varadhan, Gokul
• Primary Examiner(s): Wu, Xiao
• Assistant Examiner(s): Salvucci, Matthew D
• Application Number:
  US13/302,470
• Publication Number:
  US 20120127169A1
• Time in Patent Office: 1,015 Days
• Field of Search: 345/427
• US Class Current: 345/427
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics

Abstract

A capability for guided navigation in an interactive virtual three-dimensional environment is provided. Such a capability may enhance user experience by providing the feeling of free-form navigation to a user. It may be necessary to constrain the user to certain areas of good visual quality, and subtly guide the user towards viewpoints with better rendering results without disrupting the metaphor of freeform navigation. Additionally, such a capability may enable users to “drive” down a street, follow curving roads, and turn around intersections within the interactive virtual three-dimensional environment. Further, this capability may be applicable to image-based rendering techniques in addition to any three-dimensional graphics system that incorporates navigation based on road networks and/or paths.

Claims

1. A computer-implemented method for guided navigation in three-dimensional environments, comprising:

displaying, by one or more computing devices, a first three-dimensional representation of a panoramic image within a three-dimensional environment from a viewpoint of a virtual camera;

identifying, by the one or more computing devices, one or more additional panoramic images linked to the first panoramic image based on metadata associated with the first panoramic image;

determining, by the one or more computing devices, a region of visual quality that satisfies a criteria associated with a visual representation for each of the first panoramic image and the one or lore additional panoramic images within the three-dimensional environment;

generating, by the one or more computing devices, one or more navigation channels relative to a path between the first panoramic image and the one or more additional panoramic images based on each region of visual quality, wherein each navigation channel has a rendering surface that constrains movement of the virtual camera within the region of visual quality in a bounded volume of space defined by the navigation channel; and

constructing, by the one or more computing devices, a navigation fillet around an intersection of the one or more navigation channels by fitting a collision sphere tangentially between different navigation channels of the one or more navigation channels, such that the navigation fillet represents a collision free zone and is parameterized according to distances of points of tangency relative to a center of one of the first panoramic images; and

in response to an input event indicating a desired movement of the virtual camera to a location in a second panoramic image of the one or more additional panoramic images, repositioning, by the one or more computing devices, the virtual camera in the three-dimensional environment along the path, within the collision free zone, from a first position associated with the first panoramic image toward a second position associated with the second panoramic image of the one or more additional panoramic images based on the input event, wherein moving comprises preventing movement of the virtual camera outside the region of visual quality in the bounded volume of space defined by the navigation channel even if the location indicated by the input event is outside the navigation channel.

2. The method of claim 1, wherein determining a region of visual quality comprises:

calculating a navigation radius for each of the first panoramic image and the one or more additional panoramic images based on a depth map associated with each of the panoramic images, wherein the navigation radius represents the region of visual quality for each of the panoramic images within the three-dimensional environment.

3. The method of claim 2 further comprising:

constructing a shell around each navigation channel based on interpolating a navigation sphere for each panoramic image along the path and the calculated navigation radius of each panoramic image, the shell defining a boundary for movement of the virtual camera within the three-dimensional environment.

4. The method of claim 1, further comprising:

generating a three-dimensional mesh of polygons for the first panoramic image and the one or more additional panoramic images based on depth values associated with image objects in each respective panoramic image.

5. The method of claim 4, further comprising:

determining first and second positions in the three-dimensional mesh corresponding to centers of each of the first and second panoramic images, wherein the first and second positions correspond to an accurate viewpoint of the image objects in the first and second panoramic images; and

calculating the navigation radius for each of the first and second panoramic images in the three-dimensional mesh based on the determined region of visual quality of each of the first and second panoramic images.

6. The method of claim 4, further comprising:

rendering a first portion of the three-dimensional mesh corresponding to the first panoramic image in the three-dimensional environment from a perspective of the virtual camera;

automatically rendering a second portion of the three-dimensional mesh corresponding to the second panoramic image within the three-dimensional environment as the virtual camera is moved along the path from the initial position to the target position; and

blending the second portion of the first three-dimensional mesh as it is rendered with the rendered first portion in the three-dimensional environment.

7. The method of claim 6, wherein the rendering of the first portion comprises:

rendering the first portion of the three-dimensional mesh within the three-dimensional environment according to a first texture based on the first panoramic image,

wherein the automatically rendering the second portion comprises;

automatically rendering the second portion of the three-dimensional mesh within the three-dimensional environment according to a second texture based on the second panoramic image, and

wherein the blending comprises;

blending the first texture and the second texture based on a blending parameter as second 3D mesh is rendered.

8. The method of claim 1, wherein the first panoramic image and the one or more additional panoramic images are associated with a network of streets in the three-dimensional environment.

9. The method of claim 8 further comprising:

determining a path to turn at an intersection within the associated network of streets in the three dimensional environment.

10. The method of claim 1, wherein the first panoramic image and the one or more additional panoramic images are geo-located, and the first and second positions associated with the respective first and second panoramic images within the three-dimensional environment correspond to geographic locations in a geographic information system (GIS).

11. The method of claim 1, further comprising:

dynamically updating the rendering surface of the navigation channel as the virtual camera is moved in the three-dimensional environment.

12. The method of claim 1, wherein the moving comprises:

determining a target location associated with the second panoramic image in the three-dimensional environment based on a view direction of a virtual camera;

moving the virtual camera within the navigation channel from the first position corresponding to an initial location associated with the first panoramic image toward the second position corresponding to the determined target location; and

aligning the view direction of the virtual camera toward the target location as the virtual camera is moved along the path, the aligning based on a minimum correction angle.

13. The method of claim 12, wherein the aligning further comprises:

applying a view direction correction and a view position correction as the virtual camera is moved in the three-dimensional environment based on an alignment for the view direction of the virtual camera relative to the path and a parameterization of a magnitude of the view direction correction and the view position correction.

14. The method of claim 13, wherein the magnitude of the view direction correction and view position correction is smoothly parameterized based on user input.

15. The method of claim 12, wherein the determined target location is a center of the first and second panoramic images.

16. A system for guided navigation in three-dimensional environments, comprising:

a renderer module, implemented on a computing device and configured to display a first three-dimensional representation of a first panoramic image within a three-dimensional environment from a viewpoint of a virtual camera and identify one or more additional panoramic images linked to the first panoramic image based on metadata associated with the first panoramic image;

a path planner module, implemented on the computing device and configured to determine a region of visual quality that satisfies a criteria associated with a visual representation for each of the first panoramic image and the one or more additional panoramic images within the three-dimensional environment; and

a path motion module, implemented on the computing device and configured to (i) generate one or more navigation channels relative to a path between the first panoramic image and the one or more additional panoramic images based on each region of visual quality, wherein each navigation channel has a rendering surface that constrains movement of the virtual camera within the region of visual quality, (ii) construct a navigation fillet around an intersection of the one or more navigation channels by fitting a collision sphere tangentially between different navigation channels of the one or more navigation channels, such that the navigation fillet represents a collision free zone and is parameterized according to distances of points of tangency relative to a center of one of the first panoramic images, and (iii) reposition the virtual camera in the three-dimensional environment along the path, within the collision free zone, from a first position associated with the first panoramic image toward a second position associated with a second panoramic image of the one or more additional panoramic images based on user input, the path motion nodule further configured to, in response to an input event indicating a desired movement of the virtual camera outside a bounded volume of space defined by each navigation channel, move the virtual camera along one of the one or more navigation channels instead.

17. The system of claim 16, wherein the path planner module is further configured to calculate a navigation radius for each of the first panoramic image and the one or more additional panoramic images based on a depth map associated with each panoramic image, wherein the navigation radius represents the region of visual quality for each panoramic image within the three-dimensional environment.

18. The system of claim 17, wherein the path planner module is further configured to construct a shell around each navigation channel based on interpolating a navigation sphere for each panoramic image along the path and the calculated navigation radius of each panoramic image, the shell defining a boundary for movement of the virtual camera within the three-dimensional environment.

19. The system of claim 16, wherein the renderer module is further configured to generate a three-dimensional mesh of polygons for the first panoramic image and the one or more additional panoramic images based on depth values associated with image objects in each respective panoramic image.

20. The system of claim 16, wherein the renderer module is further configured to dynamically update the rendering surface of the navigation channel as the virtual camera is moved in the three-dimensional environment.

21. The system of claim 19, wherein the path planner module is further configured to determine first and second positions in the three-dimensional mesh corresponding to centers of each of the first and second panoramic images, wherein the first and second positions correspond to an accurate viewpoint of the image objects in the first and second panoramic images, and calculate the navigation radius for each of the first and second panoramic images in the three-dimensional mesh based on the determined region of visual quality of each of the first and second panoramic images.

22. The system of claim 19, wherein the renderer module is further configured to:

render a first portion of the three-dimensional mesh corresponding to the first panoramic image in the three-dimensional environment from a perspective of the virtual camera;

automatically render a second portion of the three-dimensional mesh corresponding to the second panoramic image within the three-dimensional environment as the virtual camera is moved along the path from the initial position to the target position; and

blend the second portion of the first three-dimensional mesh as it is rendered with the rendered first portion in the three-dimensional environment.

23. The system of claim 22, wherein the renderer module is further configured to render the first portion of the three-dimensional mesh within the three-dimensional environment according to a first texture based on the first panoramic image, automatically render the second portion of the three-dimensional mesh within the three-dimensional environment according to a second texture based on the second panoramic image, and blend the first texture and the second texture based on a blending parameter as second 3D mesh is rendered.

24. The system of claim 16, wherein the first panoramic image and the one or more additional panoramic images are associated with a network of streets in the three-dimensional environment.

25. The system of claim 24, wherein the path planner module is further configured to

determine a path to turn at an intersection within the associated network of streets in the three dimensional environment.

26. The system of claim 16, wherein the path motion module is further configured to determine a target location associated with second panoramic image in the three-dimensional environment based on a view direction of a virtual camera, move the virtual camera within the navigation channel from the first position corresponding to an initial location associated with the first panoramic image toward the second position corresponding to the determined target location, and align the view direction of the virtual camera toward the target location as the virtual camera is moved along the path.

27. The system of claim 26, wherein the path motion module is further configured to apply a view direction correction and a view position correction as the virtual camera is moved in the three-dimensional environment based on an alignment for the view direction of the virtual camera relative to the path and a parameterization of a magnitude of the view direction correction and the view position correction.