Streaming and interactive visualization of filled polygon data in a geographic information system

• US 7,746,343 B1
• Filed: 06/27/2006
• Issued: 06/29/2010
• Est. Priority Date: 06/27/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Charaniya, Amin, Jones, Michael T., Rohlf, John
• Primary Examiner(s): Wu; Xiao M
• Assistant Examiner(s): Welch; David T
• Application Number:
  US11/426,686
• Time in Patent Office: 1,463 Days
• Field of Search: 345/428, 715/700
• US Class Current: 345/428
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Interactive geographic information systems (GIS) and techniques are disclosed that provide users with a greater degree of flexibility, utility, and information. A markup language is provided that facilitates communication between servers and clients of the interactive GIS, which enables a number of GIS features, such as network links (time-based and/or view-dependent dynamic data layers), ground overlays, screen overlays, placemarks, 3D models, and stylized GIS elements, such as geometry, icons, description balloons, polygons, and labels in the viewer by which the user sees the target area. Also, “virtual tours” of user-defined paths in the context of distributed geospatial visualization is enabled. Streaming and interactive visualization of filled polygon data are also enabled thereby allowing buildings and other such features to be provided in 3D. Also, techniques for enabling ambiguous search requests in a GIS are provided.

Claims

1. A method executed by a geographic information computer system for streaming and interactive visualization of filled polygon data, the method comprising:

receiving a complex polygon dataset associated with a geographic location, the complex polygon dataset including 3D buildings represented by polygons at a first level of detail, each building having a height;

filtering the polygons representing the buildings according to height of the buildings to form a first group of polygons for buildings having at least a minimum height, the first group of polygons associated with the first level of detail;

simplifying geometry of the first group of polygons to form a second group of less complex polygons at a second level of detail, wherein the second level of detail is lower than the first level of detail, and wherein simplifying geometry to form a second group of less complex polygons further comprises;

sorting polygons based on volumes enclosed by the polygons; and

eliminating polygons that do not enclose at least a minimum volume from the second group; and

storing in a computer storage medium the second group of polygons at the second level of detail so that it is available for subsequent incremental streaming in response to client fly-through requests.

2. The method of claim 1 wherein receiving a complex polygon dataset associated with a geographic location includes creating a vector asset based on the dataset.

3. The method of claim 1 further comprising:

partitioning the complex polygon dataset into quads, wherein each quad comprises a smaller, spatially-indexed set of polygons; and

clipping polygons that fall on quad boundaries.

4. The method of claim 1 wherein simplifying geometry to form a second group of less complex polygons further comprises:

eliminating collinear vertices.

5. The method of claim 1 further comprising:

receiving a request from a client device to fly through a geographic location at an altitude;

selecting a set of polygons of buildings for a level of detail corresponding to the altitude; and

incrementally streaming the selected polygons to the client device.

6. The method of claim 1 wherein the complex polygon dataset includes data representing at least one of protruding non-terrain geographic features and non-protruding non-terrain geographic features.

7. The method of claim 1 wherein simplifying geometry to form a second group of less complex polygons further comprises:

preserving shape of 2D polygons on a per-polygon basis by eliminating non-critical vertices.

8. The method of claim 1 wherein simplifying geometry to form a second group of less complex polygons further comprises:

replacing complex triangle meshes with simpler triangle meshes.

9. The method of claim 1 wherein simplifying geometry to form a second group of less complex polygons further comprises:

creating a plurality of simplified sets of geometry based on at least one of different camera positions and orientations.

10. A non-transitory machine-readable medium encoded with instructions, that when executed by a processor of a geographic information computer system, cause the processor to carry out a process for streaming and interactive visualization of filled polygon data, the process comprising:

receiving a complex polygon dataset associated with a geographic location, the complex polygon dataset including 3D buildings represented by polygons at a first level of detail, each building having a height;

filtering the polygons representing the buildings according to height of the buildings to form a first group of polygons for buildings having at least a minimum height, the first group of polygons associated with the first level of detail;

simplifying geometry of the first group of polygons to form a second group of less complex polygons at a second level of detail, wherein the second level of detail is lower than the first level of detail, and wherein simplifying geometry to form a second group of less complex polygons further comprises;

sorting polygons based on volumes enclosed by the polygons; and

eliminating polygons that do not enclose at least a minimum volume from the

second group; and

storing in a computer storage medium the second group of polygons at the second level of detail so that it is available for subsequent incremental streaming in response to client fly-through requests.

11. The non-transitory machine-readable medium of claim 10 wherein receiving a complex polygon dataset associated with a geographic location includes creating a vector asset based on that dataset.

12. The non-transitory machine-readable medium of claim 10 wherein the process further comprises:

partitioning the complex polygon dataset into quads, wherein each quad comprises a smaller, spatially-indexed set of polygons; and

clipping polygons that fall on quad boundaries.

13. The non-transitory machine-readable medium of claim 12 wherein clipping polygons that fall on quad boundaries generates additional geometry in the form of newly introduced vertices and edges in the interior of the polygons, the process further comprising:

designating these vertices and edges as being internal to the quad; and

executing a degenerate edge removal process.

14. The non-transitory machine-readable medium of claim 10 wherein simplifying geometry to form a second group of less complex polygons further comprises:

eliminating collinear vertices.

15. The non-transitory machine-readable medium of claim 10 wherein simplifying geometry to form a second group of less complex polygons further comprises:

preserving shape of 2D polygons on a per-polygon basis by eliminating non-critical vertices.

16. The non-transitory machine-readable medium of claim 10 wherein simplifying geometry to form a second group of less complex polygons further comprises:

replacing complex triangle meshes with simpler triangle meshes.

17. The non-transitory machine-readable medium of claim 10 wherein simplifying geometry to form a second group of less complex polygons further comprises:

creating a plurality of simplified sets of geometry based on at least one of different camera positions and orientations.

18. The non-transitory machine-readable medium of claim 10 further comprising:

receiving a request from a client device to fly through a geographic location at an altitude;

selecting a set of polygons of buildings for a level of detail corresponding to the altitude; and

incrementally streaming the selected polygons to the client device.

19. A geographic information computer system for streaming and interactive visualization of filled polygon data, the system comprising:

an asset creation module for receiving a complex polygon dataset associated with a geographic location, the complex polygon dataset including 3D buildings represented by polygons at a first level of detail, each building having a height;

a height-based pre-filtering module for filtering the polygons representing 3D buildings according to height of the buildings to form a first group of polygons for buildings having a least a minimum height, the first group of polygons associated with the first level of detail

a feature-preserving simplification module for simplifying geometry of the group of polygons to form a second group of less complex polygons at a second level of detail, wherein the second level of detail is lower than the first level of detail, and wherein the feature-preserving simplification module is configured for sorting polygons based on volumes enclosed by the polygons and eliminating polygons that do not enclose at least a minimum volume from the second group; and

a database for storing the second group of polygons at the second level of detail so that it is available for subsequent incremental streaming in response to client fly-through requests.

20. The system of claim 19 wherein the asset creation module is further configured for creating a vector asset based on the dataset.

21. The system of claim 19 further comprising:

a clipping module for partitioning the complex polygon dataset into quads, wherein each quad comprises a smaller, spatially-indexed set of polygons, wherein the clipping module is further configured for clipping polygons that fall on quad boundaries.

22. The system of claim 19 wherein the feature-preserving simplification module for simplifying geometry is configured for eliminating collinear vertices.

23. The system of claim 19 wherein the feature-preserving simplification module for simplifying geometry is configured for preserving shape of 2D polygons on a per-polygon basis by eliminating non-critical vertices.

24. The system of claim 19 wherein the feature-preserving simplification module for simplifying geometry is configured for replacing complex triangle meshes with simpler triangle meshes.

25. The system of claim 19 wherein the feature-preserving simplification module for simplifying geometry is configured for creating a plurality of simplified sets of geometry based on at least one of different camera positions and orientations.