Efficient fetching of a map data during animation

• US 9,514,551 B2
• Filed: 05/15/2014
• Issued: 12/06/2016
• Est. Priority Date: 05/15/2013
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Dewan, Maneesh, Nomura, Tatsuo, Xu, Zhaoyang, Byrne, Paul Vincent
• Primary Examiner(s): Cerullo, Liliana
• Application Number:
  US14/279,132
• Publication Number:
  US 20140340304A1
• Time in Patent Office: 936 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G09G 2360/121 using a cache memory
• CPC Class Codes: G09G 5/34 for rolling or scrolling
• CPC Class Codes: G09G 5/363 Graphics controllers
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory

Abstract

A first digital map is displayed in a viewport at an initial position. When a user gesture that communicates motion to the viewport is detected, a trajectory of the viewport from the initial position to a target position is determined based on kinematic quantities of the communicated motion. Map data for displaying a second digital map in the viewport at the target position is retrieved from a first memory, prior to the viewport reaching the target position. The retrieved map data is stored in a second memory having a higher speed of access than the first memory. The second memory is retrieved for display via the user interface when the viewport is at the target position.

Claims

1. A method for efficiently fetching digital map data displayed in a viewport, the method comprising:

displaying, via a user interface, a first digital map when a viewport is at an initial position corresponding to a first geographic area, the viewport defining a currently visible portion of a digital map;

detecting, by one or more processors via the user interface, a fling gesture that communicates motion to the viewport;

determining, by the one or more processors, a trajectory of the viewport from the initial position to a target position corresponding to a second geographic area, based on kinematic quantities of the communicated motion, wherein the trajectory includes a plurality of intermediate positions of the viewport along a path from the initial position to the target position;

prefetching, by the one or more processors from a first memory, map data for displaying a second digital map in the viewport at the second geographic area corresponding to the target position prior to the viewport reaching the target position, wherein the retrieved map data for the second geographic area is displayed when the viewport has reached the target position;

storing, by the one or more processors, the prefetched map data in a second memory having a higher speed of access than the first memory; and

retrieving, by the one or more processors, the prefetched map data from the second memory for display via the user interface when the viewport is at the target position.

2. The method of claim 1, further comprising:

prefetching, by the one or more processors from the first memory, map data for displaying respective digital maps in the viewport at the plurality of intermediate positions, before the viewport reaches the intermediate positions.

3. The method of claim 2, wherein prefetching the map data includes:

prefetching first map data corresponding to the target position of the viewport at a first level of detail, and

prefetching second map data corresponding to the plurality of intermediate positions of the viewport at a second level of detail,

wherein the first level of detail is higher than the second level of detail.

4. The method of claim 3, wherein the first level of detail at a certain zoom level includes city streets, and the second level of detail at the same zoom level does not include city streets.

5. The method of claim 1, further comprising:

determining, by the one or more processors, a respective speed of the viewport at a plurality of segments of the trajectory, and

retrieving, by the one or more processors, map data corresponding to a first one of the plurality of segments at a first level of detail when the speed at the first one of the plurality of segments is below a certain threshold, and

retrieving, by the one or more processors, map data corresponding to a second one of the plurality of segments at a second level of detail when the speed at the second one of the plurality of segments is not below the threshold,

wherein the first level of detail is higher than the second level of detail.

6. The method of claim 1, further comprising:

displaying geographic markers on the first digital map when the viewport is at the initial position, wherein the geographic markers correspond to results of a geographic query limited to the first geographic area;

automatically re-executing, by the one or more processors, the geographic query limited to the second geographic area, in response to detecting the fling gesture and prior to the viewport reaching the target position;

storing results of the re-executed geographic query in the second memory along with the retrieved map data; and

displaying second geographic markers on the second digital map when the viewport is at the target position, wherein the second geographic markers correspond to results of the geographic query limited to the second geographic area.

7. The method of claim 1, wherein determining the trajectory of the viewport includes using one or more of (i) a history of past user gestures and (ii) a history of past viewport trajectories.

8. The method of claim 1, wherein storing the map data in the second memory includes storing the map data in a cache of a rendering pipeline implemented in a graphics card.

9. The method of claim 1, wherein prefetching the map data from the first memory includes retrieving the map data from a network server via a communication network.

10. The method of claim 1, wherein determining the trajectory based on the kinematic quantities of the communicated motion includes determining how far the viewport will travel based on an acceleration communicated to the viewport.

11. The method of claim 1, wherein prefetching the map data includes retrieving a plurality of map tiles describing respective equal portions of the second digital map.

12. A computing device comprising:

a user interface configured to receive gesture input;

rendering hardware configured to generate graphics content via the user interface;

a non-transitory memory coupled to the rendering hardware; and

processing hardware configured to;

cause the rendering hardware to display, via the user interface, a digital map when a viewport is at an initial position corresponding to a first geographic area, the viewport defining a currently visible portion of a digital map,

in response to a fling gesture communicating motion to the viewport via the user interface in a certain direction and with a certain acceleration, determine a trajectory of the viewport from the initial position to a target position corresponding to a second geographic area, based on kinematic quantities of the communicated motion, wherein the trajectory includes a plurality of intermediate positions along a path between the initial position and the target position,

prefetch map data for generating respective digital maps at one or more of the plurality of intermediate positions of the viewport along the trajectory prior to the viewport reaching the one or more positions, wherein the processing hardware is configured to display the prefetched map data for the second geographic area when the viewport has reached the target position, and

transfer the map data to the memory, wherein the rendering hardware retrieves the map data from the memory when rendering the digital maps at the corresponding one or more positions of the viewport.

13. The computing device of claim 12, further comprising:

a graphics card, wherein the memory is a cache of the graphics card.

14. The computing device of claim 13, wherein the cache is a second memory, the computing device further comprising a first memory having a lower speed of access by the rendering hardware than the second memory;

wherein the processing hardware is configured to transfer the map data to the second memory from the first memory.

15. The computing device of claim 12, wherein to prefetch the map data, the processing hardware is further configured to:

obtain first map data for displaying a digital map of the first geographic area, at a first level of detail, and

obtain second map data for displaying respective digital maps in the viewport at a plurality of intermediate positions along the trajectory between the initial position and the target position, at a second level of detail,

wherein the first level of detail is higher than the second level of detail.

16. The computing device of claim 12, wherein the processing hardware is configured to determine the trajectory of the viewport further in view of one or more of (i) past user gestures and (ii) a history of past viewport trajectories.

17. A system for rendering digital maps, the system comprising:

a user interface configured to receive gesture input;

rendering hardware;

processing hardware;

a first memory not directly accessible by the rendering hardware, wherein the first memory stores map data for rendering digital maps;

a second memory accessible by the rendering hardware; and

wherein the processing hardware is configured to;

cause the rendering hardware to display, via the user interface, a first digital map when a viewport is at an initial position corresponding to a first geographic area, the viewport defining a currently visible portion of a digital map;

in response to a fling gesture communicating motion to the viewport via the user interface in a certain direction and with a certain acceleration, determine a trajectory of the viewport from the initial position to a target position corresponding to a second geographic area, based on kinematic quantities of the communicated motion, wherein the trajectory includes a plurality of intermediate positions along a path between the initial position and the target position;

transfer, from the first memory to the second memory, map data for generating a second digital map in the viewport at the target position, prior to the viewport reaching the target position, wherein the processing hardware is configured to display the retrieved map data for the second geographic area when the viewport has reached the target position, and

when the viewport reaches the target position, cause the rendering hardware to display the second digital map using the map data in the second memory.

18. The system of claim 17, wherein the rendering hardware and the second memory are implemented in a graphics card.

19. The system of claim 17, wherein the first memory is implemented in a network server coupled to the processing hardware via a communication network.