System and Method for Approximating Cartographic Projections by Linear Transformation

• US 20140267236A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kontkanen, Janne
• Granted Patent: US 9,286,712 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A map element parameterized in a two-dimensional (2D) coordinate system is applied to to three-dimensional (3D) geometry, parameterized in a 3D coordinate system, of a geographic area with which the map element is associated. The 3D geometry is rendered according to the selected perspective of a virtual camera. An approximate distance between the virtual camera and the 3D geometry is compared to a threshold value. A position of the map element is determined relative to the 3D geometry using (i) a linear transformation between the 2D coordinate system and the 3D coordinate when the approximate distance is smaller than the threshold value, and (ii) a non-linear transformation between the 2D coordinate system and the 3D coordinate system when the approximate distance is larger than the threshold value.

Claims

1. A method for applying a map element parameterized in a two-dimensional (2D) coordinate system to three-dimensional (3D) geometry of a geographic area with which the map element is associated, wherein the 3D geometry is parameterized in a 3D coordinate system, the method comprising:

rendering the 3D geometry according to a selected perspective of a virtual camera;

comparing an approximate distance between the virtual camera and the 3D geometry to a threshold value;

determining a position of the map element relative to the 3D geometry using (i) a linear transformation between the 2D coordinate system and the 3D coordinate when the approximate distance is smaller than the threshold value, and (ii) a non-linear transformation between the 2D coordinate system and the 3D coordinate system when the approximate distance is larger than the threshold value.

2. The method of claim 1, wherein determining the position of the map element using the linear transformation includes carrying out calculations in single precision on a graphics processing unit (GPU) that does not support double precision calculations.

3. The method of claim 2, further comprising:

using a central processing unit (CPU) that supports double precision operations, concatenating a matrix chain to generate a single matrix for transforming coordinates between the 2D coordinate system and the 3D coordinates.

4. The method of claim 3, wherein carrying out the calculations in single precision includes applying the single matrix in a shader.

5. The method of claim 3, wherein the matrix chain includes:

(i) a first matrix to transform coordinates between the 2D coordinate system of the map element and a global 2D geographic coordinate system,

(ii) a second matrix to transform coordinates between the global 2D geographic coordinate system and the 3D coordinate system, and

(iii) a third matrix to transform coordinates between the 3D coordinate system and an eye relative coordinate system.

6. The method of claim 1, wherein determining the position of the map element using the non-linear transformation includes one of:

carrying out calculations in double precision on the CPU, or

carrying out calculations in single precision on the GPU.

7. The method of claim 1, wherein:

the map element is rendered to a map texture for application to the 3D geometry,

determining the position of the map element when the approximate distance is larger than the threshold value includes using a curvature factor to account for the curvature of the Earth, and

determining the position of the map element when the approximate distance is smaller than the threshold value includes not accounting for the curvature of the Earth.

8. The method of claim 1, wherein the 2D coordinate system is associated with a geographic projection onto a plane.

9. The method of claim 8, wherein:

the 2D coordinate system is one of (i) Mercator or (ii) plate carré

e, and

the 3D coordinate system is a Cartesian coordinate system.

10. The method of claim 1, wherein the map element is a marker indicating a point of interest (POI).

11. The method of claim 1, wherein the map element is a text label.

12. The method of claim 1, wherein the map element represents a road, and wherein the map element is rendered to a map texture applied to the 3D geometry at the determined position.

13. The method of claim 1, wherein the threshold value corresponds to an altitude between 10,000 and 15,000 meters above the ground level of the 3D geometry.

14. A computing device comprising:

processing units including (i) a central processing unit (CPU) and (ii) a graphics processing unit (GPU),

a tangible computer-readable memory storing thereon instructions that, when executed on the processing units, cause the processing units to;

(i) render 3D geometry of a geographic area according to a selected perspective of a virtual camera in a 3D coordinate system,

(ii) receive a map element, parameterized in a 2D coordinate system, to be applied to the 3D geometry,

(iii) determine an approximate distance between the virtual camera and the 3D geometry, and

(iv) select a degree of precision for transformation of coordinates between the 2D coordinate system and the 3D coordinate system based on the approximate distance, and

(v) transform the map element to the 3D coordinate system according to the selected degree of precision.

15. The computing device of claim 14, wherein to select the degree of precision based on the determined distance, the instructions cause the processing units to:

compare the determined distance to a threshold value, and

apply (i) a linear transformation between the 2D coordinate system and the 3D coordinate when the approximate distance is smaller than the threshold value and (ii) a non-linear transformation between the 2D coordinate system and the 3D coordinate system when the approximate distance is larger than the threshold value,

wherein the linear transformation is associated with single precision, and the linear transformation is associated with double precision.

16. The computing device of claim 14, wherein the linear transformation is carried out at the GPU, and wherein the GPU does not support double precision calculations.

17. The computing device of claim 14, wherein to transform the map element to the 3D coordinate system, the instructions cause the processing units to:

determine a curvature factor to account for the curvature of the Earth when the approximate is larger than a threshold value, and

not account for the curvature of the Earth when the approximate is smaller than the threshold value.

18. The computing device of claim 14, wherein the 2D coordinate system is one of (i) Mercator or (ii) plate carré

e.

19. The computing device of claim 14, wherein the 3D coordinate system is an Earth-centered, Earth-fixed (ECEF) coordinate system.

20. A method in a computing system for transforming points from a 2D coordinate system in which map data describes a geographic projection onto a plane to a 3D coordinate system in which 3D geometry of a geographic area is defined, the method comprising:

receiving an indication of a position of a virtual camera in the 3D coordinate system, wherein the 3D geometry is rendered according to the indicated position, and wherein the position corresponds to approximate distance d between the virtual camera and a target point in the 3D geometry; and

transforming the points from the 2D coordinate system to the 3D coordinate system, including;

applying a curvature factor to account for the curvature of the Earth when the distance d is greater than a threshold value, and

not applying the curvature factor when the distance d is less than a threshold value.

21. The method of claim 20, wherein transforming the points from the 2D coordinate system to the 3D coordinate system includes:

using non-linear transformation between the 2D coordinate system and the 3D coordinate when the distance d is greater than a threshold value, and

using linear transformation between the 2D coordinate system and the 3D coordinate when the distance d is greater than a threshold value.

22. The method of claim 20, wherein transforming the points from the 2D coordinate system includes transforming a map element defined in the 2D coordinate system, wherein the map element is one of (i) a label or (ii) a marker indicating a POI.

23. The method of claim 20, wherein transforming the points from the 2D coordinate system includes generating a map texture using a map element representing a physical entity for applying to the 3D geometry.

24. The method of claim 23, wherein the map element represents a road.