Method and system for generating and storing data objects for multi-resolution geometry in a three dimensional model

• US 9,311,748 B2
• Filed: 02/20/2013
• Issued: 04/12/2016
• Est. Priority Date: 02/20/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Schpok, Joshua Sam
• Primary Examiner(s): McDowell, Jr., Maurice L
• Assistant Examiner(s): Isanians, Raffi
• Application Number:
  US13/771,612
• Publication Number:
  US 20150178986A1
• Time in Patent Office: 1,147 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2210/36 Level of detail

Abstract

Methods and systems for generating data objects for multi-resolution geometry in a three-dimensional model are provided. A region of high resolution geometry in the three-dimensional model having a level of detail that is higher than a level of detail associated with geometry data surrounding the region of high resolution geometry can be identified. A boundary of the region of high resolution geometry can be extended and high resolution geometry can be generated within the extended boundary. The high resolution geometry can be spatially partitioned into a plurality of geospatial data objects according to a hierarchical spatial partitioning scheme. The geospatial data objects can be selectively stored in a memory. For instance, geospatial data objects associated with the extended boundary can be identified and excluded from a hierarchical tree data structure storing geometry data associated with the three-dimensional model.

Claims

1. A computer-implemented method of generating data objects for multi-resolution geometry in a three-dimensional model, comprising:

identifying, by one or more computing devices, a region of high resolution geometry in a multi-resolution three-dimensional model, the region of high resolution geometry having a first level of detail that is higher than a second level of detail associated with geometry data surrounding the region of high resolution geometry in the three-dimensional model;

extending, by the one or more computing devices, a boundary of the region of high resolution geometry by at least twice a geospatial extent of a geospatial data object associated with the level of detail of the region of high resolution geometry to an extended boundary such that the extended boundary encompasses geometry data associated with the first level of detail and geometry data associated with the second level of detail;

generating, by the one or more computing devices, high resolution geometry within the extended boundary such that a resolution of the geometry data associated with the second level of detail within the extended boundary matches the resolution of the geometry data associated with the first level of detail;

spatially partitioning, by the one or more computing devices, the high resolution geometry into a plurality of geospatial data objects; and

selectively storing, by the one or more computing devices, one or more of the plurality of geospatial data objects in a memory.

2. The method of claim 1, wherein selectively storing one or more of the plurality of geospatial data objects in a memory comprises:

identifying, by the one or more computing devices, one or more geospatial data objects associated with the extended boundary; and

selectively storing, by the one or more computing devices, the geospatial data objects in a hierarchical tree data structure such that the one or more geospatial data objects associated with the extended boundary are excluded from the hierarchical tree data structure.

3. The computer-implemented method of claim 1, wherein the method further comprises substituting, by the one or more computing devices, the region of high resolution geometry in the three-dimensional model.

4. The computer-implemented method of claim 1, wherein spatially partitioning, by the one or more computing devices, geometry data within the extended boundary into a plurality of geospatial data objects comprises spatially partitioning, by the one or more computing devices, the geometry data within the extended boundary pursuant to a hierarchical spatial partitioning scheme associated with the three-dimensional model.

5. The computer-implemented method of claim 1, wherein generating high resolution geometry within the extended boundary comprises:

identifying, by the one or more computing devices, the geometry data associated with the second level of detail within the extended boundary; and

upsampling, by the one or more computing devices, the identified geometry data.

6. The computer-implemented method of claim 5, wherein upsampling, by the one or more computing devices, the identified geometry data comprises upsampling, by the one or more computing devices, the identified geometry data such that the identified geometry data has a resolution that matches the high resolution geometry.

7. The computer-implemented method of claim 2, wherein identifying, by the one or more computing devices, one or more geospatial data objects associated with the extended boundary comprises identifying, by the one or more computing devices, one or more geospatial data objects having a mesh polygon with at least one edge along the extended boundary.

8. The computer-implemented method of claim 1, wherein the geospatial data objects are discrete geospatial volumes.

9. The computer-implemented method of claim 2, wherein the hierarchical tree data structure comprises an octree data structure.

10. The computer-implemented method of claim 1, wherein the three dimensional model is a stereo reconstruction.

11. The computer-implemented method of claim 10, wherein the region of high resolution geometry is associated with a street level resolution.

12. The computer-implemented method of claim 10, wherein the region of high resolution geometry is generated based on data acquired from a laser range finder.

13. A computing system for providing geospatial data objects associated with a three-dimensional model, the computing system comprising one or more processors configured to implement one or more modules, the one or more modules comprising:

an upsampling module-implemented by the one or more processors, the upsampling module configured to extend a boundary of a region of high resolution geometry in the three-dimensional model by at least twice a geospatial extent of a geospatial data object associated with the level of detail of the region of high resolution geometry to an extended boundary such that the extended boundary encompasses geometry data associated with the first level of detail and geometry data associated with the second level of detail, and the upsampling module further configured to generate high resolution geometry within the extended boundary such that a resolution of the geometry data associated with the second level of detail within the extended boundary matches the resolution of the geometry data associated with the first level of detail, the first level of detail being associated with a higher resolution than the second level of detail;

a chopper module implemented by the one or more processors, the chopper module configured to spatially partition the high resolution geometry into a plurality of discrete geospatial volumes; and

a selector module implemented by the one or more processor, the selector module configured to identify one or more of the plurality of discrete geospatial volumes associated with the extended boundary and to selectively store the discrete geospatial volumes in a memory encoded with a hierarchical tree data structure such that discrete geospatial volumes associated with the extended boundary are excluded from the hierarchical tree data structure.

14. The computing system of claim 13, wherein the computing system is configured to provide one or more of the discrete geospatial volumes for the three dimensional model to a remote computing device via a network interface.

15. The computing system of claim 13, wherein the hierarchical tree data structure is an octree data structure.

16. The computing system of claim 13, wherein the three dimensional model is a stereo reconstruction generated from aerial imagery and the high resolution geometry is generated based on data acquired from a laser range finder.

17. A computing system comprising one or more processors and at least one memory, the one or more processors configured to execute computer-readable instructions stored on the at least one memory to cause the one or more processors to perform operations, the operations comprising:

identifying a region of high resolution geometry in a multi-resolution three-dimensional model, the region of high resolution geometry having a first level of detail that is higher than a second level of detail associated with geometry data surrounding the region of high resolution geometry in the three-dimensional model;

extending a boundary of the region of high resolution geometry by at least twice a geospatial extent of a geospatial data object associated with the level of detail of the region of high resolution geometry to an extended boundary such that the extended boundary encompasses geometry data associated with the first level of detail and geometry data associated with the second level of detail;

generating high resolution geometry within the extended boundary such that a resolution of the geometry data associated with the second level of detail within the extended boundary matches the resolution of the geometry data associated with the first level of detail;

spatially partitioning the high resolution geometry into a plurality of geospatial data objects;

identifying one or more geospatial data objects associated with the extended boundary; and

selectively storing the geospatial data objects in a hierarchical tree data structure such that the one or more geospatial data objects associated with the extended boundary are excluded from the hierarchical tree data structure.

18. The computing system of claim 17, wherein the geometry data within the extended boundary is spatially partitioned pursuant to a hierarchical spatial partitioning scheme associated with the three-dimensional model.