SYSTEM AND METHOD FOR LOADING AND RENDERING CURVED FEATURES IN A MAP

• US 20130321422A1
• Filed: 09/11/2012
• Published: 12/05/2013
• Est. Priority Date: 06/05/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pahwa, Aroon, Blumenberg, Christopher, Schuster, Michael D., Howard, James A., Hultquist, Jeffrey P.
• Granted Patent: US 9,224,218 B2
• Time in Patent Office: Days
• US Class Current: 345/428
• 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: G01C 21/3819 Road shape data, e.g. outline of a route
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

Embodiments of a system and method for loading and rendering curved features in a map are described. Embodiments may include a map tool of a mapping or navigation application configured to generate a display for a map that includes one or more curved features (e.g., curved roads or curved polygons). The map tool may be executed in a client/server environment in which a server portion receives digitized map data in the form of polylines, detects a curved feature in the map data by fitting it to a parametric curve, and transmits data representing the parametric curve to a client device for subsequent rendering. The client device may render the curved feature using the received parametric curve data or, dependent on characteristics of the client device, extract data corresponding to points on the parametric curve to generate a triangle mesh for rendering the curved feature at a suitable resolution.

Claims

1. A method for rendering a feature in a map, comprising:

performing by a computer;

receiving data defining a curve of the feature as a Bé

zier path;

determining a resolution at which the feature is to be displayed, wherein said determining is dependent on a performance characteristic of a device on which the feature is to be rendered;

determining a number of points on the curve for which data is to be extracted from the received data dependent on the determined resolution;

extracting data representing each of the determined number of points on the curve from the received data; and

rendering the feature in the map dependent on the extracted data.

2. The method of claim 1, wherein said rendering comprises:

creating a collection of triangles that represents the feature and whose vertices are defined by the extracted data; and

rendering the collection of triangles.

3. The method of claim 1, wherein said determining the number of points is dependent on a distance between endpoints of a portion of the feature that will be visible when the feature is displayed, or a zoom level at which the feature is to be displayed.

4. The method of claim 1, wherein said determining the number of points is dependent on one or more of:

a screen resolution for the device on which the feature is to be rendered, a performance characteristic of a processor of the device on which the feature is to be rendered, or a number of map features to be rendered simultaneously.

5. The method of claim 1, further comprising:

in response to detecting that a zoom level at which the feature is being displayed has changed;

determining a different number of points on the curve for which data is to be extracted from the received data dependent on the changed zoom level;

extracting data representing each of the different number of points on the curve from the received data; and

rendering the feature in the map dependent on the extracted data representing each of the different number of points on the curve.

6. A system, comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to implement a server application configured to;

access data defining a series of polylines corresponding to a feature on a map;

detect a curve in the feature dependent on the series of polylines, wherein said detecting comprises fitting at least a portion of the series of polylines to a Bé

zier path; and

store data representing the Bé

zier path in the memory for subsequent use in rendering the feature on the map.

7. The system of claim 6, wherein the server application is further configured to transmit the data representing the Bé

zier path to a client computer on which the feature is to be rendered.

8. The system of claim 6, wherein the data representing the Bé

zier path defines control points of the Bé

zier path.

9. The system of claim 8, wherein the number of control points is less than the number of points in the at least a portion of the series of polylines.

10. A multifunction device, comprising:

one or more processors; and

one or more memories storing a mapping application that is executable on the one or more processors to;

receive data defining a curve of a feature of a map using a parametric curve representation;

determine a resolution at which the feature is to be displayed on the multifunction device, wherein said determining is dependent on a characteristic of the multifunction device;

determine a number of points on the curve for which data is to be extracted from the received data dependent on the determined resolution;

extract data representing each of the determined number of points on the curve from the received data; and

generate a collection of triangles that represents the feature and whose vertices are defined by the extracted data.

11. The multifunction device of claim 10, wherein the mapping application is further executable to render the feature in the map dependent on the collection of triangles.

12. The multifunction device of claim 11,

wherein at least one of the one or more processors is a graphics processing unit (GPU);

and

wherein rendering the feature comprises the GPU rendering the collection of triangles.

13. The multifunction device of claim 10, wherein determining the number of points is dependent on a distance between endpoints of a portion of the feature that will be visible when the feature is displayed, or a zoom level at which the feature is to be displayed.

14. The multifunction device of claim 10, wherein said determining the number of points is dependent on one or more of:

a screen resolution for the multifunction device, a performance characteristic of a processor of the multifunction device, or a number of map features to be rendered simultaneously on the multifunction device.

15. The multifunction device of claim 10, wherein the mapping application is further executable to:

determine that a zoom level at which the feature is being displayed has changed by an amount or percentage greater than a pre-determined threshold amount or percentage;

determine a different number of points on the curve for which data is to be extracted from the received data dependent on the amount or percentage by which the zoom level has changed;

extract data representing each of the different number of points on the curve from the received data; and

render the feature in the map dependent on the extracted data representing each of the different number of points on the curve.

16. A non-transitory, computer-readable storage medium, storing program instructions executable on a computer to implement a mapping application configured to:

obtain data defining a curve of a feature of a map using a parametric curve representation;

determine a number of points on the curve for which data is to be extracted from the obtained data;

extract data representing each of the determined number of points on the curve from the obtained data; and

render the feature within the map dependent on the extracted data.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the mapping application is further configured to:

determine a resolution at which the feature is to be displayed, wherein determining the resolution is dependent on a characteristic of a multifunction device on which the feature is to be displayed, and wherein determining the number of points is dependent on the determined resolution.

18. The non-transitory, computer-readable storage medium of claim 16, wherein rendering the feature comprises:

creating a triangle strip or a triangle mesh that represents the feature and whose vertices are defined by the extracted data; and

rendering the triangle strip or triangle mesh.

19. The non-transitory, computer-readable storage medium of claim 16, wherein the feature comprises a curved road, a geographic feature, or a structure comprising one or more curved elements.

20. The non-transitory, computer-readable storage medium of claim 16,

wherein determining the number of points is dependent on a zoom level at which the feature is to be displayed;

and

wherein in response to detecting that a zoom level at which the feature is being displayed has changed, the mapping application is further configured to;

determine a different number of points on the curve for which data is to be extracted from the obtained data dependent on the changed zoom level;

extract data representing each of the different number of points on the curve from the obtained data; and

render the feature within the map dependent on the extracted data representing each of the different number of points on the curve.

21. The non-transitory, computer-readable storage medium of claim 16,

wherein determining the number of points is dependent on one or more characteristics of a multifunction device on which the feature is to be displayed;

and

wherein determining the number of points comprises detecting the multifunction device on which the feature is to be displayed.

22. A non-transitory, computer-readable storage medium, storing program instructions executable on a computer to implement a server application configured to:

receive data representing a series of polylines corresponding to a feature on a map;

detect a curve in the feature dependent on the series of polylines, wherein said detecting comprises fitting at least a portion of the series of polylines to a parametric curve;

transmit data representing the parametric curve to another computing device for subsequent rendering on the other computing device.

23. The non-transitory, computer-readable storage medium of claim 22, wherein receiving the data comprises receiving digitized map data from a service that provides map data over the Internet.

24. The non-transitory, computer-readable storage medium of claim 22,

wherein the parametric curve comprises a Bé

zier curve; and

wherein the data representing the parametric curve comprises control points of the Bé

zier curve.

25. The non-transitory, computer-readable storage medium of claim 22, wherein the amount of the data representing the parametric curve is less than the amount of the data representing the at least a portion of the series of polylines.