Methods and Apparatus for Rendering Labels Based on Occlusion Testing for Label Visibility

• US 20130321397A1
• Filed: 08/31/2012
• Published: 12/05/2013
• Est. Priority Date: 06/05/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Chen, Billy P., Blumenberg, Christopher, Hultguist, Jeffrey P., Pahwa, Aroon
• Granted Patent: US 8,988,426 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G01C 21/3673 Labelling using text of road map data items, e.g. road names, POI names
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/004 Annotating, labelling

Abstract

Methods and apparatus for a map tool displaying a three-dimensional view of a map region, where the map tool determines whether or not partially occluded labels within the map region are to be drawn or are to not be drawn. The map tool determines whether or not to draw a label in a map view dependent upon mapping information and upon construction of a three-dimensional model based on one or more two- or three-dimensional data sets. The map tool further determines whether or not to draw a label in the map view dependent upon a measure of occlusion of a label in the map view. In order to determine a measure of occlusion, the map tool may calculate whether a line of sight projection from virtual camera viewpoint for the mobile device intersects, once or more than once, with any objects or landmarks within the three-dimensional model.

Claims

1. A method, comprising:

performing, by one or more computing devices;

generating a representation of a map region divided into a plurality of sections;

receiving height information corresponding to the map region,

wherein the height information includes height values corresponding to one or more locations in the map region;

extruding each respective section of the plurality of sections according to a corresponding respective height value of the height values,

wherein said extruding is based on a correspondence of the respective section to a respective location in the map region, and

wherein the respective height value corresponds to the respective location;

generating a three-dimensional representation of the map region based on said extruding each respective section of the plurality of sections;

determining, based on the three-dimensional representation of the map region, that a label in a map view of the map region is occluded below a threshold amount; and

rendering at least a portion of the label in the map view based on said determining that the label in the map view of the map region is occluded below the threshold amount.

2. The method of claim 1, further comprising:

updating the map view in response to user input indicating a change a virtual camera viewpoint.

3. The method of claim 1, wherein subsequent to said generating the three-dimensional model, the program instructions are further executable by the at least one processor to:

receive an indication of a new map region;

request updated height information, wherein the updated height information overlaps with the height information; and

generate another three-dimensional model based on the updated height information.

4. The system of claim 1, wherein said determining that a label in the map view of the map region is occluded below the threshold amount is further based on a virtual camera viewpoint.

5. The system of claim 1, wherein the three-dimensional model is based on correlations between two-dimensional mapping information and three-dimensional mapping information.

6. A system, comprising:

at least one processor; and

a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to;

receive mapping information corresponding to a map region, wherein the mapping information includes height values for the map region;

determine, based on the height values, a three-dimensional model of the map region;

determine, based on the three-dimensional model of the map region and based on coordinates for label in the map view of the map region, a measure of occlusion for a label in the map view,

wherein the coordinates for the label in the map view correspond to coordinates for the label in the three-dimensional model; and

render the label in the map view in response to the measure of occlusion satisfying a threshold to be included in the map view.

7. The system of claim 6, wherein to determine the three-dimensional model of the map region the program instructions are further executable by the at least one processor to:

extrude a plurality of sections of a grid representation of the map region, comprising;

correlating one or more points of the grid representation of the map region to the height values;

determining a respective height value for each section of the plurality of sections based on a correlation of a respective section to a respective point in the mapping information; and

extruding each section of the plurality of sections into three-dimensional space according to the respective height value in the height values corresponding to the respective point in the mapping information.

8. The system of claim 7, wherein the program instructions are further executable by the at least one processor to:

adjust a granularity of the three-dimensional model based on a configuration setting indicating a level of resolution for the map,

wherein an adjustment of the granularity of the three-dimensional model comprises increasing or decreasing the number of the plurality of sections.

9. The system of claim 8, wherein the program instructions are further executable by the at least one processor to:

adjust one or more bases on which the measure of occlusion is determined according to the granularity of the three-dimensional model.

10. The system of claim 6, wherein the program instructions are further executable by the at least one processor to:

adjust one or more bases on which the measure of occlusion is determined according to crowd sourcing information.

11. A computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

receiving a set of mapping information for a map region;

receiving an other set of mapping information for the map region;

correlating the set of mapping information with the other set of mapping information;

generating a three-dimensional model based on said correlating the set of mapping information with the other set of mapping information;

calculating, based on a virtual camera viewpoint, one or more measures of occlusion of a label in a map view of the map region, wherein said calculating is based on a correlation between the three-dimensional model and the map view of the map region; and

rendering, based on the one or more measures of occlusion of the label in the map view of the map region, the label in the map view of the map region.

12. The computer-readable storage medium of claim 11, wherein said rendering displays less than the entire label in the map view of the map region.

13. The computer-readable storage medium of claim 11, wherein the program instructions are computer-executable to further implement:

determining whether one or more areas of the label that are not occluded provide useful information,

wherein said determining is based on a percentage of text in the label that is visible; and

wherein said calculating is further based on said determining whether the one or more areas of the label that are not occluded provide useful information.

14. The computer-readable storage medium of claim 11, wherein the virtual camera viewpoint is based on a user selection of a ground-level view or a user selection of a bird'"'"'s eye.

15. The computer-readable storage medium of claim 11, wherein a measure of occlusion of the one or more measures of occlusion is based on a level of granularity of the three-dimensional model, and wherein the level of granularity of the three-dimensional model is adjustable.

16. A method, comprising:

performing, by one or more computing devices;

receiving mapping information for a map region;

approximating, based on the mapping information for the map region, a three-dimensional model of the map region;

determining a measure of occlusion for a label in a map view of the map region, wherein said determining is based on the three-dimensional model of the map region and based on a correlation between the three-dimensional model of the map region and the map view of the map region; and

rendering, based on the measure of occlusion for the label in the map view of the map region being less than a threshold value, the label in the map view.

17. The method of claim 16, further comprising:

determining a level of granularity for a three-dimensional model; and

calculating the three-dimensional model according to the level of granularity,

wherein the three-dimensional model is based on the mapping information, and

wherein the three-dimensional model is based on two-dimensional mapping information and three-dimensional mapping information.

18. The method of claim 17, wherein said determining the level of granularity is based on a configuration setting indicating a level of accuracy for the occlusion testing.

19. The method of claim 18, further comprising:

adjusting one or more bases on which the measure of occlusion is based according to a configuration setting indicating a level of tolerance for partially occluded labels.

20. The method of claim 16, wherein said determining the measure of occlusion is based in part on data received from a mobile device within proximity of wireless communication.

21. A computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:

receive mapping information for a map region;

generate a three-dimensional model based on the mapping information for the map region;

identify a label to be rendered in a map view of the map region;

determining, for the label to be rendered in the map view of the map region, label coordinates within the three-dimensional model;

determining that one or more points in the label coordinates within the three-dimensional model are unobstructed from a virtual camera viewpoint; and

rendering, in response to the one or more points in the label coordinates within the three-dimensional model being unobstructed from the virtual camera viewpoint satisfying a threshold value, at least a portion of the label in the map view;

22. The computer-readable storage medium of claim 21, wherein the virtual camera viewpoint is based on coordinates, within the three-dimensional model, of a device storing and executing the program instructions.

23. The computer-readable storage medium of claim 21, wherein the program instructions are further computer-executable to implement:

generating the three-dimensional model from the two-dimensional mapping information,

wherein a respective footprint for each object in the two-dimensional mapping information is extruded to a height corresponding a default height setting for a type of a respective object.

24. The computer-readable storage medium of claim 21, wherein the program instructions are computer-executable to further implement generating the map view based on the three-dimensional model.

25. The computer-readable storage medium of claim 24 wherein the program instructions are computer-executable to further implement generating an updated map view based on input indicated a change in the virtual camera viewpoint, wherein the updated map view is based on the already generated three-dimensional model.