Hierarchical system and method for on-demand loading of data in a navigation system

• US 8,849,859 B2
• Filed: 10/19/2007
• Issued: 09/30/2014
• Est. Priority Date: 12/31/2002
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Schmidt, Hauke, Chen, Tuolin, Lee, Aaron
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US11/975,459
• Publication Number:
  US 20080091732A1
• Time in Patent Office: 2,538 Days
• Field of Search: 707/100, 707/102, 707/3, 707/101, 707/104.1, 707/956, 707600-899, 709/217, 382/232
• US Class Current: 707/791
• CPC Class Codes: G01C 21/3638 including 3D objects and buildings three dimensional [3D] modelling, e.g. data description of 3D objects G06T17/00; geographic models G06T17/05
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system providing three-dimensional visual navigation for a mobile unit includes a location calculation unit for calculating an instantaneous position of the mobile unit, a viewpoint control unit for determining a viewing frustum from the instantaneous position, a scenegraph manager in communication with at least one geo-database to obtain geographic object data associated with the viewing frustum and generating a scenegraph organizing the geographic object data, and a scenegraph renderer which graphically renders the scenegraph in real time. To enhance depiction, a method for blending images of different resolutions in the scenegraph reduces abrupt changes as the mobile unit moves relative to the depicted geographic objects. Data structures for storage and run-time access of information regarding the geographic object data permit on-demand loading of the data based on the viewing frustum and allow the navigational system to dynamically load, on-demand, only those objects that are visible to the user.

Claims

1. A hardware computer-readable medium having stored thereon a navigation display module and a hierarchical data structure, the navigation display module being executable by a computer processor and, when executed by the processor, causing the processor to perform a navigation display using the hierarchical data structure, the hierarchical data structure comprising:

meta data in a resource-index format (RIF); and

level-of-detail format data including actual data of the system, the actual data being loadable on demand;

wherein;

the meta data includes a file location field and is interpreted by the processor executing the navigation display module as defining a plurality of nodes that are hierarchically arranged in a meta data hierarchy;

for each of the nodes of the meta data hierarchy, the meta data is interpreted by the processor executing the navigation display module as defining the respective node by a bounding box field, a tiles field, and a number of children field;

the number of children field of each parent node of the meta data hierarchy is interpreted by the processor executing the navigation display module as recursively defining all descendent nodes of the respective node, the respective definition of all of the descendent nodes including the respective bounding box field of the respective descendent node, the respective tiles field of the respective descendent node and the respective number of children field of the respective descendent node; and

the recursive definition is such that, due to inclusion of the respective number of children field in the definition of each respective one of the nodes, the meta data thereby defines, for each descendent node that is a direct child of a parent node and that is being defined by the meta data before the definition of at least one other direct child node of the parent node, all descendent nodes of the respective descendent node before defining any of the at least one other direct child node.

2. The hardware computer-readable medium of claim 1, wherein the system includes a mobile navigational system.

3. The hardware computer-readable medium of claim 1, wherein the resource-index format data includes positional information of the system arranged in a hierarchical manner.

4. The hardware computer-readable medium of claim 1, wherein the resource-index format data includes a sequence of tile and bounding box information.

5. The hardware computer-readable medium of claim 1, wherein the level-of-detail format data includes resource object features in multiple levels of detail and a pointer to point to the resource object features.

6. The hardware computer-readable medium of claim 5, wherein the level-of-detail format data is arranged to optimize accessing of the resource object features.

7. The computer-readable medium of claim 1, wherein:

the nodes of the hierarchy include a root node, a plurality of terminal leaf nodes, and a plurality of intermediate nodes that define branches from the root node to the leaf nodes; and

the navigation display module, when executed by the processor, causes the processor to use one or more of the intermediate nodes to directly access respective portions of the actual data without use of any of the leaf nodes for display, by the processor executing the navigation display module, of structures defined by the directly accessed respective portions of the actual data.

8. A hardware computer-readable medium having stored thereon a navigation system accessible by a computer processor, the system comprising:

data; and

instructions that are executable by the processor, and that, when executed by the processor, are configured to cause the processor to perform a navigation method using the data, the data including;

at least one resource object;

meta data associated with a position of the at least one resource object; and

actual data associated with the at least one resource object;

wherein;

the meta data includes a file location field and is interpreted by the processor executing the instructions as defining a plurality of nodes that are hierarchically arranged in a hierarchy;

for each of the nodes of the hierarchy, the meta data is interpreted by the processor executing the instructions as defining the respective node by a bounding box field, a tiles field, and a number of children field;

the number of children field of each parent node of the hierarchy is interpreted by the processor executing the instructions as recursively defining all descendent nodes of the respective node, the respective definition of all of the descendent nodes including the respective bounding box field of the respective descendent node, the respective tiles field of the respective descendent node and the respective number of children field of the respective descendent node; and

the recursive definition is such that, due to inclusion of the respective number of children field in the definition of each respective one of the nodes, the meta data thereby defines, for each descendent node that is a direct child of a direct parent node and that is being defined by the meta data before the definition of at least one other direct child node of the direct parent node, all descendent nodes of the respective descendent node before defining any of the at least one other direct child node.

9. The computer-readable medium of claim 8, wherein the meta data and the actual data are arranged separately.

10. The computer-readable medium of claim 9, wherein the meta data is arranged in a resource index format and the actual data is arranged in a level-of-detail format.

11. The computer-readable medium of claim 10, wherein the level-of-detail format includes features of the at least one resource object in multiple levels of detail.

12. The computer-readable medium of claim 8, wherein:

the nodes of the hierarchy include a root node, a plurality of terminal leaf nodes, and a plurality of intermediate nodes that define branches from the root node to the leaf nodes; and

the instructions, when executed by the processor, cause the processor to use one or more of the intermediate nodes to directly access respective portions of the actual data without use of any of the leaf nodes for display, by the processor executing the instructions, of structures defined by the directly accessed respective portions of the actual data.

13. A hardware computer-readable medium having stored thereon a navigation system accessible by a computer processor, the system comprising:

data; and

instructions that are executable by the processor, and that, when executed by the processor, are configured to cause the processor to perform a navigation method using the data, the data including;

at least one resource object;

meta data to describe a hierarchical relationship between portions of the system and between the at least one resource object and the system; and

actual data to describe the at least one resource object, wherein;

the meta data and the actual data are arranged separately;

the meta data includes a file location field and is interpreted by the processor executing the instructions as defining a plurality of nodes that are hierarchically arranged in a hierarchy;

for each of the nodes of the hierarchy, the meta data is interpreted by the processor executing the instructions as defining the respective node by a bounding box field, a tiles field, and a number of children field;

the number of children field of each parent node of the hierarchy is interpreted by the processor executing the instructions as recursively defining all descendent nodes of the respective node, the respective definition of all of the descendent nodes including the respective bounding box field of the respective descendent node, the respective tiles field of the respective descendent node and the respective number of children field of the respective descendent node; and

the recursive definition is such that, due to inclusion of the respective number of children field in the definition of each respective one of the nodes, the meta data thereby defines, for each descendent node that is a direct child of a direct parent node and that is being defined by the meta data before the definition of at least one other direct child node of the direct parent node, all descendent nodes of the respective descendent node before defining any of the at least one other direct child node.

14. The computer-readable medium of claim 13, wherein:

the nodes of the hierarchy include a root node, a plurality of terminal leaf nodes, and a plurality of intermediate nodes that define branches from the root node to the leaf nodes; and

the instructions, when executed by the processor, cause the processor to use one or more of the intermediate nodes to directly access respective portions of the actual data without use of any of the leaf nodes for display, by the processor executing the instructions, of structures defined by the directly accessed respective portions of the actual data.

15. A hardware computer-readable medium comprising:

meta data; and

instructions that are executable by a computer processor, the instructions which, when executed by the processor, cause the processor to perform a navigation method using (a) the meta data and (b) actual data that are referenced by the meta data and that define structures which the processor displays when performing the navigation method;

wherein;

the meta data is interpreted by the processor when performing the method as defining a plurality of nodes that are hierarchically arranged in a hierarchy;

for each of the nodes of the hierarchy, the meta data is interpreted by the processor when performing the method as defining the respective node by a plurality of fields, the plurality of fields including (a) at least one field that references a respective portion of the actual data and (b) a number of children field;

the number of children field of each parent node of the hierarchy is interpreted by the processor when performing the method as recursively defining all descendent nodes of the respective node, the respective definitions of all of the descendent nodes including (a) the respective at least one field of the respective descendent node and (b) the respective number of children field of the respective descendent node; and

the recursive definition is such that, due to inclusion of the respective number of children field in the definition of each respective one of the nodes, the meta data thereby defines, for each descendent node that is a direct child of a direct parent node and that is being defined by the meta data before the definition of at least one other direct child node of the direct parent node, all descendent nodes of the respective descendent node before defining any of the at least one other direct child node.

16. The computer-readable medium of claim 15, wherein:

the nodes of the hierarchy include a root node, a plurality of terminal leaf nodes, and a plurality of intermediate nodes that define branches from the root node to the leaf nodes; and

the instructions, when executed by the processor, cause the processor to use one or more of the intermediate nodes to directly access respective portions of the actual data without use of any of the leaf nodes for display by the processor of the structures defined by the directly accessed respective portions of the actual data.

17. The computer-readable medium of claim 15, wherein the meta data, including the recursive definition, are arranged as fields in a flat file.