Height based indexing

• US 8,166,042 B1
• Filed: 04/07/2009
• Issued: 04/24/2012
• 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:
  US12/419,687
• Time in Patent Office: 1,113 Days
• Field of Search: 715/848, 715/760, 707/919, 707/920, 707/921, 707/724, 707/725, 707/943
• 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

The present invention provides 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 one or more vertical slices containing data in a dimension different than dimensions associated with the node;

(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, wherein the traversal 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, wherein the analyzing comprises;

determining if the indexed data stored at the root node covers at least a portion of a range of altitudes that lie within the view frustum; and

determining if a multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant,

wherein, if the indexed data stored at the root node covers at least the portion of the range of altitudes that lie within the view frustum and the multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant, the indexed data stored at the root node is to be displayed 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 1, further comprising:

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

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

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

5. The computer-implemented method of claim 1, 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.

6. The computer-implemented method of claim 1, wherein step (c) comprises extracting, for each analyzed node of the geo-spatial multi-resolution data structure, the indexed data from the at least one vertical slice of the respective node that corresponds to at least the portion of the range of altitudes that lie within the view frustum.

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.

12. The system of claim 1, wherein the frame updater/LOD determiner is configured to extract, for each analyzed node of the geo-spatial multi-resolution data structure, the indexed data from the at least one vertical slice of the respective node that corresponds to at least the portion of the range of altitudes that lie within the view frustum.

8. A system for parsing indexed data, comprising:

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

(a) 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 one or more vertical slices containing data in a dimension different than dimensions associated with the node,

(b) 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

(c) 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,

(d) receive a maximum multi-resolution data structure level constant,

(e) traverse the geo-spatial multi-resolution data structure 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, and

(f) analyze the root node of the branch by;

determining if the indexed data stored at the root node covers at least a portion of a range of altitudes that lie within the view frustum, and

determining if a multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant,

wherein, if the indexed data stored at the root node covers at least the portion of the range of altitudes that lie within the view frustum and the multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant, the indexed data stored at the root node is to be displayed within the view frustum.

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

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

11. The system of claim 8, 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.

13. The system of claim 8, 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.

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

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

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

(a) extracting data representing a three dimensional object in a three dimensional environment, 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, wherein at least a portion of the three dimensional environment lies within a view frustum, and at least one node of the neo-spatial multi-resolution data structure comprises one or more vertical slices containing data in a dimension different than dimensions associated with the node;

(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, wherein the traversal 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, wherein the analyzing comprises;

determining if the indexed data stored at the root node covers at least a portion of a range of altitudes that lie within the view frustum; and

determining if a multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant,

wherein, if the indexed data stored at the root node covers at least the portion of the range of altitudes that lie within the view frustum and the multi-resolution data structure level of the root node is less than or equal to the maximum multi-resolution data structure level constant, the indexed data stored at the root node is to be displayed within the view frustum; and

(c) storing the data in vertical slices at the node for later rendering and displaying of the three dimensional object by a client.

17. The computer-implemented method of claim 16, wherein each vertical slice is annotated with an altitude range, and wherein a union of each vertical slice altitude range equals an altitude range of the three dimensional object.

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

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

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