A vehicle navigation system has a processing device. The processing device receives entries in a first data structure that are generated and are respectively associated with one tile of a tiling. The processing device may compare a three-dimensional terrain on the respective tile with at least one p
A vehicle navigation system has a processing device. The processing device receives entries in a first data structure that are generated and are respectively associated with one tile of a tiling. The processing device may compare a three-dimensional terrain on the respective tile with at least one pre-defined tile pattern. Either an identifier for a pre-defined tile pattern or data describing the terrain on the respective tile may be stored by the processing device in the entry.
대표청구항▼
1. A method of generating a database for a navigation system, the method comprising: receiving data defining a three-dimensional terrain;generating by a processor based on the data defining the three-dimensional terrain, a first data structure having a tiling which includes a first plurality of tile
1. A method of generating a database for a navigation system, the method comprising: receiving data defining a three-dimensional terrain;generating by a processor based on the data defining the three-dimensional terrain, a first data structure having a tiling which includes a first plurality of tiles, where an entry is generated in the first data structure for each tile of the tiling,where generating the entry comprises the steps of:comparing by the processor vertices of a surface mesh defining the three-dimensional terrain contained in a first tile of the first plurality of tiles to at least one pre-defined terrain pattern contained in a second tile included in a second data structure, where each pre-defined terrain pattern is stored in the second data structure only once,selecting by the processor, based on a result of the comparing, one of data defining the portion of the three-dimensional terrain or an identifier for a pre-defined terrain pattern included in the second data structure for storing in the entry, andstoring the first data structure and the second data structure in a database. 2. The method of claim 1, where coordinates of the vertices of the surface mesh defining the three-dimensional terrain are retrieved from the data defining the three-dimensional terrain or are generated based on the data defining the three-dimensional terrain, each one of the vertices respectively having a pair of lateral coordinates and a height coordinate, andwhere, for each tile of the tiling, the entry is respectively generated to include an identifier for a pre-defined terrain pattern included in the second data structure if relative lateral coordinates of all vertices located on the tile correspond to lateral coordinates of vertices in the pre-defined terrain pattern. 3. The method of claim 2, where the method further comprises the step of: determining, based on height coordinates of the vertices located on the tile, whether a height coordinate of at least one vertex located on the tile is to be stored in the first data structure in addition to the identifier for the pre-defined terrain pattern. 4. The method of claim 3, where height coordinates of all vertices located on the tile are stored in the entry in the first data structure if height coordinates of any pair of the vertices located on the tile differ from each other by more than a pre-determined threshold. 5. The method of claim 3, where at most one height shift value for all vertices located on the tile is stored in the entry in the first data structure if height coordinates of all vertices located on the tile differ from each other by at most a pre-determined threshold. 6. The method of claim 5, where one height shift value is stored in the entry in the first data structure if the height coordinates of all vertices are different from a default height value, andwhere no height shift value is stored in the entry in the first data structure if the height coordinates of all vertices are equal to the default height value. 7. The method of claim 2, where the one of data defining the portion of the three-dimensional terrain or the identifier is selected independently of height coordinates of all vertices located on the tile. 8. The method of claim 2, where the identifier for a pre-defined terrain pattern is selected for storing in the first data structure if all vertices located on the tile are located on a boundary, in particular on corners, of the tile. 9. The method of claim 1, where each pre-defined terrain pattern included in the second data structure includes lateral coordinates of a plurality of vertices and an array of indices describing triangular faces respectively having three of the vertices as corners. 10. A navigation system comprising: a database representing a three-dimensional terrain and including a first data structure having a plurality of entries, each one of the entries including a unique tile identifier for a different tile of a tiling of vertices of a surface mesh defining the three-dimensional terrain, and a second data structure defining at least one pre-defined terrain pattern contained in a second tile, where each pre-defined terrain pattern is stored in the second data structure only once; anda processor coupled to the database, the processor being configured to:access an entry of the first data structure using the unique tile identifier for a tile;determine whether the accessed entry includes a pattern identifier for a pre-defined terrain pattern stored in the second data structure;selectively retrieve information on the pre-defined terrain pattern from the second data structure if the entry includes the pattern identifier; anddetermine a height coordinate of one or plural locations based on the accessed entry of the first data structure and, if the entry includes the pattern identifier, based on the pre-defined terrain pattern included in the second data structure. 11. The navigation system of claim 10, where the processor is further configured to, if the entry includes a pattern identifier, determine a pair of lateral coordinates of the vertices of the surface mesh based on the retrieved information on the pre-defined terrain pattern and to respectively determine a height coordinate of the vertices based on the entry of the first data structure. 12. The navigation system of claim 11, where the processor is further configured to set height coordinates of the vertices to the same value if the entry of the first data structure includes the pattern identifier and at most one height coordinate. 13. The navigation system of claim 11, where the processor is further configured to determine different height coordinates for the vertices if the entry of the first data structure includes the pattern identifier and a plurality of height coordinates. 14. The navigation system of claim 11, where entries of the database which do not include an identifier for a pre-defined terrain pattern respectively include information on coordinate 3-tuples of vertices of a surface mesh. 15. A method of generating a database for a navigation system, the method comprising: receiving data defining a three-dimensional terrain;generating by a processor based on the data defining a three-dimensional terrain, a first data structure having a tiling which includes a first plurality of tiles, where an entry is generated in the first data structure for each tile of the tiling,where generating the entry comprises the steps of:comparing by the processor vertices of a surface mesh defining the three-dimensional terrain contained in a first tile of the first plurality of tiles to at least one pre-defined terrain pattern contained in a second tile included in a second data structure, where each pre-defined terrain pattern is stored in the second data structure only once,selecting by the processor, based on a result of the comparing, one of data defining the three-dimensional terrain or an identifier for a pre-defined terrain pattern included in the second data structure for storing in the entry,storing the first data structure and the second data structure in the database,where coordinates of the vertices of the surface mesh defining the three-dimensional terrain are retrieved from the data defining the three-dimensional terrain or are generated based on the data defining the three-dimensional terrain, each one of the vertices respectively having a pair of lateral coordinates and a height coordinate, andwhere, for each tile of the tiling, the entry is respectively generated to include an identifier for a pre-defined terrain pattern included in the second data structure if relative lateral coordinates of all vertices located on the tile correspond to lateral coordinates of vertices in the pre-defined terrain pattern, andwhere each pre-defined terrain pattern included in the second data structure includes lateral coordinates of a plurality of vertices and an array of indices describing triangular faces respectively having three of the vertices as corners. 16. The method of claim 15, where the method further comprises the step of: determining, based on height coordinates of the vertices located on the tile, whether a height coordinate of at least one vertex located on the tile is to be stored in the first data structure in addition to the identifier for the pre-defined terrain pattern. 17. The method of claim 16, where height coordinates of all vertices located on the tile are stored in the entry in the first data structure if height coordinates of any pair of the vertices located on the tile differ from each other by more than a pre-determined threshold. 18. The method of claim 16, where at most one height shift value for all vertices located on the tile is stored in the entry in the first data structure if height coordinates of all vertices located on the tile differ from each other by at most a pre-determined threshold. 19. The method of claim 18, where one height shift value is stored in the entry in the first data structure if the height coordinates of all vertices are different from a default height value, andwhere no height shift value is stored in the entry in the first data structure if the height coordinates of all vertices are equal to the default height value. 20. The method of claim 15, where the one of data defining the portion of the three-dimensional terrain or the identifier is selected independently of height coordinates of all vertices located on the tile. 21. The method of claim 15, where the identifier for a pre-defined terrain pattern is selected for storing in the first data structure if all vertices located on the tile are located on a boundary, in particular on corners, of the tile. 22. A method of determining height information in a navigation device, the navigation device having a database which includes a first data structure having a plurality of entries, each one of the entries including a unique tile identifier for a tile of a tiling, and a second data structure defining at least one pre-defined terrain pattern, where each pre-defined terrain pattern is contained in a different tile and stored in the second data structure only once, the method comprising: accessing an entry of the first data structure using the unique identifier for a tile;determining whether the entry includes a pattern identifier for a pre-defined terrain pattern stored in the second data structure;selectively retrieving, based on a result of the determining, information on the pre-defined terrain pattern from the second data structure if the entry includes the pattern identifier; anddetermining a height coordinate of one or more vertices of a surface mesh defining a three-dimensional terrain based on the accessed entry of the first data structure and, if the entry includes the pattern identifier, based on the pre-defined terrain pattern included in the second data structure. 23. A non-transitory computer readable storage medium having stored therein instructions executable by a programmed processor for generating a database for a navigation system, the storage medium comprising instructions for: receiving data defining a three-dimensional terrain;generating by a processor based on the data defining the three-dimensional terrain, a first data structure having a tiling which includes a first plurality of tiles, where an entry is generated in the first data structure for each tile of the tiling,where generating the entry comprises the steps of:comparing by the processor vertices of a surface mesh defining the three-dimensional terrain contained in a first tile of the first plurality of tiles to at least one pre-defined terrain pattern contained in a second tile included in a second data structure, where each pre-defined terrain pattern is stored in the second data structure only once,selecting by the processor, based on a result of the comparing, one of data defining the portion of the three-dimensional terrain or an identifier for a pre-defined terrain pattern included in the second data structure for storing in the entry, andstoring the first data structure and the second data structure in a database. 24. The navigation system of claim 10, wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include an identifier for a pre-defined terrain pattern included in the second data structure when relative lateral coordinates of all vertices located on the tile correspond to relative lateral coordinates of vertices in the pre-defined terrain pattern, and wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include vertex coordinates when relative lateral coordinates of all vertices located on the tile are different from relative lateral coordinates of vertices in the pre-defined terrain pattern. 25. The method of claim 22, wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include an identifier for a pre-defined terrain pattern included in the second data structure when relative lateral coordinates of all vertices located on the tile correspond to relative lateral coordinates of vertices in the pre-defined terrain pattern, and wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include vertex coordinates when relative lateral coordinates of all vertices located on the tile are different from relative lateral coordinates of vertices in the pre-defined terrain pattern. 26. The non-transitory computer readable storage medium of claim 23, wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include an identifier for a pre-defined terrain pattern included in the second data structure when relative lateral coordinates of all vertices located on the tile correspond to relative lateral coordinates of vertices in the pre-defined terrain pattern, and wherein, for each tile of the tiling, the entry corresponding to the tile is generated to include vertex coordinates when relative lateral coordinates of all vertices located on the tile are different from relative lateral coordinates of vertices in the pre-defined terrain pattern. 27. The method of claim 1, where each pre-defined terrain pattern contained in the second plurality of tiles includes one or more vertices defining a topology of a surface mesh. 28. The method of claim 1, where the second data structure includes a second plurality of tiles, and each tile included in the second plurality of tiles contains a different pre-defined terrain pattern.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (6)
Frederick Philip R., Automatic horizontal and vertical scanning radar with terrain display.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.