1. Field of the Invention
The present invention relates to electronic navigation maps, and, more particularly, to rendering images for electronic navigation maps.
2. Description of the Related Art
Navigation maps are essential resources for visitors to an unfamiliar city because these maps visually highlight landmarks including buildings, natural features, and points of interest such as museums, restaurants, parks and shopping districts. While most in-car and portable navigation devices (PNDs) rely on two-dimensional (2D) navigation maps to visualize these landmarks in 2D, three-dimensional (3D) in-car navigation systems are emerging.
Using a 3D map for navigation can provide a lot of benefits. For example, a 3D map can provide better driver orientation than a 2D map because people live in a 3D world. A 3D map can also improve landmark recognition as the important features (e.g., geometry, structures, textures) of 3D buildings/landmarks can be fully exposed so that it will be a lot easier for a user to match these features with what he could see through the windshield. However, introducing 3D in a navigation map also brings in typical 3D occlusion problems, which could negatively impact the visibility of route guidance for navigation.
A 3D navigation system allows drivers to locate point of interests (POIs) and set up routes in a 3D environment. However, high geometric complexity of scene buildings and the required 3D rendering efforts may affect the performance of such systems on embedded platforms. On one hand, complete data of 3D buildings with highly detailed structures are not yet available everywhere from data providers. In most cases, these highly detailed data (e.g., complex geometry, texture) are available for only a few outstanding landmarks (e.g., museums, tower) in cities or urban areas. The available information for most non-landmark buildings in these areas may include only some simple geometry information such as 2D footprint, the height of the building, and some descriptions for building types. The lack of detailed 3D geometry and building textures presents a great challenge for visualization in 3D navigation. It is possible to simply lift up a building from its 2D footprint according to the height of the building. This 2.5D approach was widely adopted in most commercial 3D navigation systems, an example of which is shown in FIG. 1. As can be seen in FIG. 1, such a building presentation (i.e., 2.5D lifting, no texture information) does not distinguish buildings with different types and therefore cannot improve building/landmark recognition or 3D orientation for the driver. On the other hand, rendering highly detailed city models may be limited by the available 3D computation resources provided by embedded hardware platforms for cars. In summary, the 2.5D approach can successfully handle the missing data problem by presenting city models with low details. However, the cost is that such a building presentation fails to convey sufficient information for navigation.
A photorealistic 3D Map with high details can present a vivid and realistic scene to drivers, an example of which is shown in FIG. 2. These maps try to faithfully visualize the structure, geometry and texture of every object in a 3D scene. However, it could be problematic to use such a building presentation for 3D navigation. For example, this presentation may overwhelm drivers with too many details. In other words, it could significantly increase the cognitive load on the user during driving, distract the driver's attention, and fail to convey important information to the driver.
Previous work on procedural modelling of buildings focuses on creating an urban environment with a large number of 3D buildings. CGA shape, a novel shape grammar, is used to iteratively produce more geometric details from a simple mass model, as described in “Procedural Modeling of Buildings” by P. Mueller, P. Wonka, S. Haegler, A. Ulmer, and L. V. Gool, Proceedings of ACM SIGGRAPH 2006, which is hereby incorporated by reference herein in its entirety. These works aim to generate buildings with complex structure and rich details. For example, in a typical urban scene, the number of polygons used in 3D buildings can reach one billion. However, for navigation applications, these approaches cannot be used for several reasons. First, the computation cost of the modelling process is too expensive. Generating one 3D building with high complexity (e.g., between one thousand and one hundred thousand polygons) takes about one to three seconds, which may not meet the speed requirement for on-line modelling for large-scale urban scenes in a 3D navigation. Second, the memory footprints for these highly detailed 3D buildings are too large for typical embedded platforms which usually have very limited memory capacity. Finally, although the subtle details of these 3D building are generated based on architecture principles, they are more likely to deviate a lot from a building's actual appearance. Drivers tend to take these random details as reference and try to match them with those from actual buildings. Therefore, these random and fake details distract users' attention from navigation without providing useful guidance. FIG. 5a illustrates such a building with such random details.
What is neither disclosed nor suggested by the prior art is a method for presenting 3D landmarks and other 3D objects on a navigation map that overcomes the problems and disadvantages described above.