WO2007018329A1

WO2007018329A1 - Sytem and method for 3d graphic acceleration in synthesis cdma environment

Info

Publication number: WO2007018329A1
Application number: PCT/KR2005/003048
Authority: WO
Inventors: Yangmin Seo; Eunsang Cho
Original assignee: GQ SOFT CO Ltd
Current assignee: GQ SOFT CO Ltd
Priority date: 2005-08-05
Filing date: 2005-09-14
Publication date: 2007-02-15
Anticipated expiration: 2008-02-05
Also published as: KR20070016851A

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 3D object manager in communication with at least one geo-database to obtain geographic object data associated with the viewing frustum and generating a 3D object organizing the geographic object data, and a 3D object renderer which graphically renders the 3D object in real time. To enhance depiction, a method for blending images of different resolutions in the 3D object 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.

Description

SYSTEM AND METHOD FOR 3D GRAPHIC ACCELERATION IN SYNTHESIS CDMA ENVIRONMENT

Technical Field

[1] The present invention relates to 3D acceleration in synthesis cdma environment.

The present invention relates to computer systems that generate graphics and more particularly to generating 3-dimensional (3D) graphics. Background Art

[2] Using computer graphics software to accurately visually render the appearance of a local geographic environment in the view of a fixed observer (from a particular viewpoint chosen by the observer) is in itself a challenging task because of the difficulties involved in accurately simulating the various textures and graphical details of a scene in addition to the problems of reconstructing a scene according to the observer's viewpoint. However, modern visual navigation systems under current development place a far greater demand on graphics software: to accurately simulate the visual environment of a moving observer to serve as a navigational aid. Using rendering software to depict the local geographic environment of a moving observer, such as a driver in a vehicle, in real-time is obviously far more challenging than rendering the environment of a fixed observer, because as the location of the observer changes, the geographic objects within his or her viewing horizon and the appearance of these objects change, requiring a continual updating mechanism by which new graphical objects (local "points of interest"), textures, features and views and other reference data can be readily downloaded to accurately render and provide information pertaining to the local navigated environment in real time.

[3] Software application programs that utilize increased graphics have become more prevalent. For example, video games often utilize an increasing amount of 3D graphics for display on a typical personal computer (PC) monitor. These graphics applications require the computer system to include 3D rendering software to support the graphical content.

[4] What is therefore needed is a visualization system for mobile units, such as motor vehicle navigation systems or personal digital assistants (PDAs), that realistically renders the environment of a mobile observer with a high degree of detail according to any viewpoint, and also provides navigational aids such as route guidance and reference information pertinent to displayed objects.

Disclosure of Invention Technical Solution [5] To meet the needs noted above, the present invention provides a system for providing three-dimension visual navigation for a mobile unit that includes a location calculation unit for calculating an instantaneous position of the mobile unit, a viewpoint control unit for determining a viewing frustum based on the instantaneous position of the mobile unit, a 3D object manager in communication with at least one geo-database that obtains geographic object data associated with the viewing frustum from the at least one geo-database and generates a 3D object that organizes the obtained geographic object data, and a 3D object renderer which graphically renders the 3D object as three-dimensional depiction in real time.

[6] To enhance the realism of the depiction, the present invention provides a method for blending images of different resolutions pertinent to the viewing frustum in order to reduce unevenness and abrupt changes in the resulting depiction which would otherwise occur as the mobile unit moves closer toward, or further away from the depicted geographic area. Brief Description of the Drawings

[7] FIG. 1 shows the visual navigation system according to an exemplary embodiment of the present invention.

[8] FIG. 2 shows an exemplary abstract representation of a 2-dimensional geographically bounded area of a navigation system demonstrating a nested relationship between bounding boxes and tiles.

[9] FIG. 3 shows a hierarchical tree-like structure representing the nested bounding box relationship of FIG. 2.

[10] FIG. 4 shows an exemplary representation of the physical layout of the Level of

Details (LOD) file within a storage medium or memory according to an embodiment of the present invention. Mode for the Invention

[11] A system in accordance with the present invention generates a sequence of three- dimensional graphic visualizations, from an arbitrary viewpoint, of geographic areas for mobile navigation, orientation and reference. The graphic visualizations, or renderings, can contain representations of any type of data object for which local geographic information is available.

[12] FIG. 1 is a block diagram of the navigational system for advanced three-dimensional visualization according to an exemplary embodiment of the present invention. The navigational system 25 includes both on-board components 30 co- located with the mobile unit, and off-board components located remotely such as geographical databases ("geo-databases") 61 and 62. The geo-databases 61 and 62 contain the large amount of data pertaining to various geographical areas including map in- formation, geometrical and texture graphics information, and identification information.

[13] The visual navigation system 25 includes a location calculation unit 35 that may be implemented as a program stored in local memory and executed on a microprocessor of the mobile unit. The location calculation unit 35 receives input from position sensors 40 and calculates an instantaneous position (coordinates) of the mobile unit in Cartesian (x,y,z) space based upon the input information. According to one embodiment, the position sensors 40 include both GPS receivers which provide "absolute" position information and inertial sensors which may provide linear acceleration and angular velocity information from which "relative" position information can be calculated by integration.

[14] In order to minimize the loading time, memory usage, processing requirements and display rendering resources, the 3D object manager 55 may dynamically load on demand from the geo-databases 61 and 62. To query the geo-databases 61 and 62 to obtain this information, the 3D object manager 55 employs a hierarchical method for on-demand loading of object data which uses specifically defined data structures to organize the object data for efficient access.

[15] In an exemplary embodiment of the present invention, two data structures may be used as a guide for loading the landmark objects on-demand. The first data structure, referred to as the Resource Index File or simply the "RIF file", may provide storage for "meta-data" of the landmark objects. The second data structure, referred to as the Level of Detail file or simply the "LOD file", may store "actual data" pertaining to the landmark objects in multiple levels of detail.

[16] The meta-data stored in the RIF file may assist the 3D object manager in determining which resources are visible at a particular viewpoint and their level of detail. The meta-data may be small in size in comparison to the actual data. Therefore, by separating the meta-data from the actual data, memory usage, processing requirements, and initial application start-up time may be significantly reduced because the actual data may not need to be loaded until it is required. For example, during the initialization phase of the navigation system, the RIF file may be read to determine which resources are required to be loaded into the system memory without loading the actual data.

[17] The actual data stored in the LOD file may represent information regarding the resources of the system in multiple resolutions. Unlike conventional systems, which typically store actual data as leaf nodes only at non-intermediate levels of a hierarchical tree-like structure, the LOD file may provide storage of the data in the intermediate nodes as well. In this manner, the hierarchical tree-like structure may provide a more suitable arrangement to access the multi-resolution information by allowing a more selective loading of the required data for a particular resolution at a given viewpoint configuration. Thus, by arranging the data to be distributed among all levels of a hierarchical tree-like structure, a more expedient and efficient access of data may be achieved for the required resolution.

[18] FIG. 2 demonstrates the "nested" relationship between bounding boxes and tiles.

FIG. 2 shows an exemplary abstract representation 250 of a 2-dimensional geographically bounded area of a navigation system demonstrating the nested relationship between bounding boxes and tiles.

[19] FIG. 3 shows a hierarchical tree-like structure 260 for representing the nested bounding box relationship of FIG. 2.

[20] The set of features and associated data for tiles may be kept separate from the data that describes the dimensions of the tile and/or the parent-child relationship of the treelike structure. Such a separation of feature -related data (actual data) from the hierarchical data (meta data) may provide an overall improvement in performance.

[21] In an exemplary embodiment of the present invention, the separation of the meta data and the actual data may be implemented via two data structures, namely a Resource Index File (RIF) and a Level of Detail (LOD) file.

[22] FIG. 4 shows an exemplary representation of the physical layout of the LOD file within a storage medium or memory. The LOD file 400 may be stored as a sequence of contiguous bytes, which may be interpreted according to the structure as defined. For example, the N levels field 401 occupies the initial portion of memory, the N tiles field 402 occupies the next portion of memory, followed by the Tile Data (TD) and the Feature Data (FD). The Tile Data (TD) includes File Pointer fields to index into the Feature Data (FD), thereby permitting faster access to the particular features associated with a particular tile.

[23] The framework of the RIF and LOD files may provide improved performance. An efficient paging mechanism may be supported to perform a swapping in/out of the data from the geo-database or storage medium to the local memory resources of the mobile unit such as a graphics memory, for example. Thus, the computational complexity required by the system may be minimized.

[24] For instance, traversing the tree-like data structure of the RIF file may require only

O(log N) computational steps where N is the number of nodes and obtaining the actual data may only require 0(1) because the tile data associated with the data structure stores a file pointer to instantly locate information of the actual landmark objects.

[25] The framework of the RIF and LOD files may also provide fast initialization time because there may be no requirement to download all of the data into memory when the application starts, thereby reducing response time to the user. The framework of the RIF and LOD files may also provide reduced memory usage because only regions that are visible to the user need be loaded. Thus, actual memory usage may be reduced to accommodate the storage of only those features required by the user- visible regions without overwhelming the system resources. Use of the RIF and LOD files may also provide reduced pre-processing requirements because only resources within the tile need to be processed thereby eliminating the need to pre-process the data before sending it to other devices for rendering. Reduced data usage may provide faster processing time as well.

[26] According to one exemplary method, at system initialization time, the RIF file is read by the 3D object manager to create a run-time data structure in a tree-like hierarchical format to access meta data during the run-time operation of the navigation system. The RIF file is not read entirely, just the fields describing the dimension of the system 2 or 3, as well as a level of detail of the system as described by the number of levels of the tree-like data structure of the RIF. The nodes of the run-time tree-like data structure may be constructed and initialized as having no associated bounding boxes or attached tiles.

[27] In the foregoing description, the method and system of the present invention have been described with reference to a number of examples that are not to be considered limiting. Rather, it is to be understood and expected that variations in the principles of the method and apparatus herein disclosed may be made by one skilled in the art, and it is intended that such modifications, changes, and/or substitutions are to be included within the scope of the present invention as set forth in the appended claims. Industrial Applicability

[28] The benefits of synthesis 3D engine on CDMA environment are tremendous. The benefits of synthesis 3D engine on CDMA environment technology available for the developers are a savings of the cost of the development on all different CDMA environments.

Claims

[1] A system for providing 3D Engine for a mobile handset comprising the process actions of:

(a) verifying the graphics acceleration hardware of the video card is not on a list of video cards with known incompatibilities with the application software;

(b) verifying that the application software initializes the interface to the graphics acceleration hardware of the video card successfully;

(c) verifying that there is sufficient memory on the video card to conduct the tests;

(d) verifying that the calls to the video card hardware are successful;

(e) verifying that a sub-pixel positioning function to correct for offsets between actual pixel positions of a texture drawn to video card memory and expected pixel position of a texture drawn to video card memory is operational and wherein the process action of verifying that sub-pixel positioning function is operational comprises:

[2] The process of claim 1, further comprising the process actions of:

(a) initially determining whether a user has turned off a hardware acceleration option; and

(b) not using the graphics acceleration hardware and foregoing the attempting, testing and establishing process actions if the hardware acceleration option is turned off.

[3] The process of claim 1, further comprising the process actions of:

(a) initially determining whether the application software has turned off a hardware acceleration option; and

[4] The process of claim 1, further comprising the process actions of:

(a) setting a flag in the application software each time the application software is run using the graphics acceleration hardware;

(b) clearing the flag when the software application successfully completes using the graphics acceleration hardware; and

(c) checking if the flag is set each time the software application initializes,

(d) using graphics acceleration if the flag is not set, and,

(e) not using the graphics acceleration hardware and foregoing the attempting, testing and establishing process actions if the flag is set.