Map tile culling for displaying globe representations in an electronic map system

Patent metadata

Field	Value
Publication number	US-12548240-B2
Application number	US-202418440277-A
Country	US
Kind code	B2
Filing date	Feb 13, 2024
Priority date	Feb 13, 2023
Publication date	Feb 10, 2026
Grant date	Feb 10, 2026

Abstract

Functionality of an electronic map system allows the more efficient rendering of a map on the surface of a globe. The functionality includes culling functionality to more effectively remove from further processing the “tiles” of map data that will not end up being displayed on the globe. The culling functionality analyzes factors such as the present zoom level, a relationship of a tile to a map center, and a relationship of a three-dimensional bounding box of the tile to a present viewing frustrum, culling tiles that will not ultimately need to be rendered due to not being visible. The functionality also includes operations on the GPU buffer memory that better manage that memory, such as allocating only a single buffer for a grid of vertices, and causing less rendering towards the poles of the globe.

First claim

What is claimed is:

1 . A computer-implemented method of visually representing a geographical region mapped onto a surface of a globe in an electronic map system, the method comprising:
obtaining information for a tile from a geographic map database; determining a zoom level of the tile; responsive to the zoom level indicating that a scene viewpoint origin is at most a threshold distance from the tile:
computing an initial three-dimensional bounding box for the tile;
computing a two-dimensional projection of the tile onto the globe;
determining whether the two-dimensional projection encompasses a center point of a viewing plane;
responsive to the two-dimensional projection not encompassing the center point:
identifying arc edges of the tile intersecting with the globe;
identifying an arc edge of the identified arc edges that is closest to the center point;
determining extremum coordinate values of the identified arc edge in each of <x, y, z> coordinates;
determining height, width, and depth of the arc edge based on the extremum coordinate values; and
determining a resized three-dimensional bounding box for the initial three-dimensional bounding box using the height, width, and depth of the arc edge;

determining, based on the resized three-dimensional bounding box, whether to cull the tile; and processing the tile for rendering dependent on the determination of whether to cull the tile.

2 . A computer-implemented method of visually representing a geographical region mapped onto a surface of a globe in an electronic map system, the method comprising:
obtaining information for a tile from a geographic database; computing an initial three-dimensional bounding box for the tile; identifying arc edges of the tile intersecting with the globe; identifying an arc edge of the identified arc edges that is closest to a center point of a viewing plane; determining a resized bounding box for the initial bounding box based on extremum coordinate values of the identified arc edge; determining, based on the resized bounding box, whether to cull the tile; and processing the tile for rendering dependent on the determination of whether to cull the tile.

3 . The computer-implemented method of claim 2 , further comprising:
determining a zoom level of the tile; wherein the computing the initial three-dimensional bounding box is responsive to the zoom level indicating that a scene viewpoint origin is at most a threshold distance from the tile.

4 . The computer-implemented method of claim 2 , further comprising:
determining extremum coordinate values of the identified arc edge in each of <x, y, z> coordinates; determining height, width, and depth of the arc edge based on the extremum coordinate values; and determining the resized three-dimensional bounding box for the initial three-dimensional bounding box using the height, width, and depth of the arc.

5 . The computer-implemented method of claim 4 , further comprising using quaternion spherical linear interpolation to determine the extremum coordinate values.

6 . The computer-implemented method of claim 2 , wherein determining whether to cull the tile comprises determining whether the resized three-dimensional bounding box intersects a viewing frustrum determined using a current viewing position.

7 . The computer-implemented method of claim 2 , further comprising:
creating a rectangular grid of vertices corresponding to corners of tiles to be rendered; and uploading the rectangular grid to a graphics processing unit (GPU).

8 . The computer-implemented method of claim 7 , further comprising determining how much of the rectangular grid to render based on proximity to a pole of the globe.

9 . The computer-implemented method of claim 7 , further comprising allocating a single memory buffer within the GPU to store the rectangular grid of vertices.

Assignees

• Mapbox Inc

Inventors

• Valadbeigi Fouad
• Pulkki Mikko

Classifications

• G06T7/50

  Depth or shape recovery · CPC title

• G06T2210/12

  Bounding box · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T7/73

  using feature-based methods · CPC title

• G06T2210/21

  Collision detection, intersection · CPC title