Height based indexing
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 12)
-
-
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. - View Dependent Claims (9, 10, 11, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20)
-
Specification