Height based indexing

• US 8,447,765 B1
• Filed: 01/06/2012
• Issued: 05/21/2013
• Est. Priority Date: 04/14/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Praun, Emil C., Touma, Costa, Strauss, Paul S., Udeshi, Tushar
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US13/344,854
• Time in Patent Office: 501 Days
• Field of Search: 707/743, 707/919, 707/921, 707/724, 707/725, 707/943, 715/848
• US Class Current: 707/743
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/921 Spatial

Abstract

Embodiments provide a system and method for height based indexing of data. In an embodiment, the present invention parses indexed data by (1) storing a geo-spatial multi-resolution data structure that represents a three dimensional environment, where at least a portion of the three dimensional environment lies within a view frustum; (2) traversing recursively the geo-spatial multi-resolution data structure, where the traversal is based on a range of coordinates that lie within the view frustum; and (3) extracting the indexed data from at least one vertical slice of at least one node of the geo-spatial multi-resolution data structure, where the extracted indexed data is displayed in the view frustum.

Claims

1. A computer-implemented method for parsing indexed data, comprising:

(a) storing a geo-spatial multi-resolution data structure that represents a three dimensional environment, wherein at least a portion of the three dimensional environment lies within a view frustum, and at least one node of the geo-spatial multi-resolution data structure comprises a plurality of vertical slices, each vertical slice containing indexed data associated with one or more regions of a three dimensional object, each region corresponding to a range of altitudes, wherein the vertical slices together cover the full range of altitudes that the three dimensional object covers;

(b) traversing recursively the geo-spatial multi-resolution data structure, wherein the traversal is based on a range of coordinates that lie within the view frustum; and

(c) extracting the indexed data from at least one vertical slice of at least one node of the geo-spatial multi-resolution data structure, wherein the extracted indexed data is displayed in the view frustum.

2. The computer-implemented method of claim 1, further comprising:

(d) receiving a maximum multi-resolution data structure level constant.

3. The computer-implemented method of claim 2, wherein step (b) comprises:

(i) choosing a branch of the geo-spatial multi-resolution data structure if the branch corresponds to at least a portion of the range of coordinates that lie within the view frustum; and

(ii) analyzing a root node of the branch to determine if indexed data stored at the root node is to be displayed within the view frustum.

4. The computer-implemented method of claim 3, further comprising:

(iii) repeating steps (i) and (ii) for each node in the branch.

5. The computer-implemented method of claim 4, further comprising:

(iv) repeating steps (i) through (iii) for each branch in the geo-spatial multi-resolution data structure.

6. The computer-implemented method of claim 3, further comprising:

(iii) repeating steps (i) and (ii) for each node in the branch that is located at a multi-resolution data structure level in the geo-spatial multi-resolution data structure less than or equal to the maximum multi-resolution data structure level constant.

7. The computer-implemented method of claim 1, further comprising:

(d) fetching indexed data stored in at least one vertical slice adjacent to the at least one vertical slice that stores the extracted indexed data.

8. The method of claim 1, wherein the three dimensional object is a building and wherein each vertical slice contains indexed data associated with a single floor of the building.

9. The method of claim 1, wherein the three dimensional object is a building and wherein each vertical slice contains indexed data associated with a respective height range of the building.

10. A system for parsing indexed data, comprising:

a frame updater/level of detail (LOD) determiner that is configured to

store a geo-spatial multi-resolution data structure that represents a three dimensional environment, wherein at least a portion of the three dimensional environment lies within a view frustum, and at least one node of the geo-spatial multi-resolution data structure comprises a plurality of vertical slices, each vertical slice containing data associated with one or more regions of a three dimensional object, each region corresponding to a range of altitudes, wherein the vertical slices together cover the full range of altitudes that the three dimensional object covers,

traverse recursively the geo-spatial multi-resolution data structure, wherein the traversal is based on a range of coordinates that lie within the view frustum, and

extract the indexed data from at least one vertical slice of at least one node of the geo-spatial multi-resolution data structure, wherein the extracted indexed data is displayed in the view frustum.

11. The system of claim 10, wherein the frame updater/LOD determiner is further configured to receive a maximum multi-resolution data structure level constant.

12. The system of claim 11, wherein the frame updater/LOD determiner is configured to traverse by choosing a branch of the geo-spatial multi-resolution data structure if the branch corresponds to at least a portion of the range of coordinates that lie within the view frustum, and by analyzing a root node of the branch to determine if indexed data stored at the root node is to be displayed within the view frustum.

13. The system of claim 12, wherein the frame updater/LOD determiner is further configured to repeat the traverse for each node in the branch.

14. The system of claim 13, wherein the frame updater/LOD determiner is further configured to repeat the traverse for each branch in the geo-spatial multi-resolution data structure.

15. The system of claim 12, wherein the frame updater/LOD determiner is further configured to repeat the traverse for each node in the branch that is located at a multi-resolution data structure level in the geo-spatial multi-resolution data structure less than or equal to the maximum multi-resolution data structure level constant.

16. The system of claim 10, wherein the frame updater/LOD determiner is further configured to fetch indexed data stored in at least one vertical slice adjacent to the at least one vertical slice that stores the extracted indexed data.

17. The system of claim 10, further comprising a multi-resolution data structure database configured to store the geo-spatial multi resolution data structure.

18. The system of claim 10, further comprising a multi-resolution data structure level database configured to store one or more coefficients designating a multi-resolution data structure level.

19. A computer-implemented method for storing data in a geo-spatial multi-resolution data structure, comprising:

(a) extracting data representing a three dimensional object, the data made up of a plurality of packets, wherein the three dimensional object includes a coordinate and an importance, and wherein the data covers a range of altitudes;

(b) traversing the geo-spatial multi-resolution data structure to find a node that encompasses the coordinate, wherein a multi-resolution data structure level of the node is associated with the importance; and

(c) storing the data in a plurality of vertical slices at the node for later rendering and displaying of the three dimensional object by a client, each vertical slice containing data associated with one or more regions of the three dimensional object, each region corresponding to the range of altitudes, wherein a union of each vertical slice altitude range equals an altitude range of the three dimensional object.

20. The computer-implemented method of claim 19, wherein each vertical slice is annotated with an altitude range.

21. The computer-implemented method of claim 20, wherein step (c) comprises storing each packet of data in a vertical slice that corresponds to its range of altitudes.

22. The computer-implemented method of claim 21, wherein successive vertical slices include at least one similar data packet.

23. The computer-implemented method of claim 21, wherein each vertical slice is located at a same multi-resolution data structure level as the node.