System and method for approximating cartographic projections by linear transformation

• US 9,286,712 B2
• Filed: 03/15/2013
• Issued: 03/15/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kontkanen, Janne
• Primary Examiner(s): Thompson, James A
• Assistant Examiner(s): Ge, Jin
• Application Number:
  US13/843,535
• Publication Number:
  US 20140267236A1
• Time in Patent Office: 1,096 Days
• Field of Search: 345/419
• US Class Current: 1/1
• 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 system when the approximate distance is smaller than the threshold value, including;

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, wherein the matrix chain includes (a) a first matrix to transform coordinates between the 2D coordinate system of the map element and a global 2D geographic coordinate system, (b) a second matrix to transform coordinates between the global 2D geographic coordinate system and the 3D coordinate system, and (c) a third matrix to transform coordinates between the 3D coordinate system and an eye relative coordinate system, and

carrying out calculations in single precision on a graphics processing unit (GPU) that does not support double precision calculations,

(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; and

rendering the map element in accordance with the determined position using 3D geometry map data in order to improve mapping applications by providing 3D geometry interactive scenery on a mapping display.

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

3. 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.

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

5. The method of claim 4, 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.

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

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

8. 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.

9. 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.

10. 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, including;

compare the determined distance to a threshold value,

select a linear transformation between the 2D coordinate system and the 3D coordinate when the approximate distance is smaller than the threshold value, including;

(a) concatenate, using a central processing unit (CPU) that supports double precision operations, a matrix chain to generate a single matrix for transforming coordinates between the 2D coordinate system and the 3D coordinates, wherein the matrix chain includes a first matrix to transform coordinates between the 2D coordinate system of the map element and a global 2D geographic coordinate system, a second matrix to transform coordinates between the global 2D geographic coordinate system and the 3D coordinate system, and a third matrix to transform coordinates between the 3D coordinate system and an eye relative coordinate system, and (b) carry out calculations in single precision on a graphics processing unit (GPU) that does not support double precision calculations, and

select a non-linear transformation between the 2D coordinate system and the 3D coordinate system when the approximate distance is larger than the threshold value,

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

(vi) render the map element in accordance with the transformation to the 3D coordinate system using 3D geometry map data in order to improve mapping applications by providing 3D geometry interactive scenery on a mapping display.

11. The computing device of claim 10, 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.

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

e.

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

14. 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, including applying a non-linear transformation between the 2D coordinate system and the 3D coordinate system and

not applying the curvature factor when the distance d is less than a threshold value, including;

concatenating, using a central processing unit (CPU) that supports double precision operations, a matrix chain to generate a single matrix for transforming coordinates between the 2D coordinate system and the 3D coordinates, wherein the matrix chain includes (a) a first matrix to transform coordinates between the 2D coordinate system of the points and a global 2D geographic coordinate system, (b) a second matrix to transform coordinates between the global 2D geographic coordinate system and the 3D coordinate system, and (c) a third matrix to transform coordinates between the 3D coordinate system and an eye relative coordinate system, and

carrying out calculations in single precision on a graphics processing unit (GPU) that does not support double precision calculations; and

rendering the points in accordance with the determined transformation data in order to improve mapping applications by providing 3D geometry interactive scenery on a mapping display.

15. The method of claim 14, 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.

16. The method of claim 14, 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.

17. The method of claim 16, wherein the map element represents a road.