An interactive walkthrough for a city area using the efficient 3D object management

An efficient 3D object management system using the hierarchical spatial data structure, called the MD-tree, is developed for an interactive walkthrough for the wide area facility management system. In the system, 3D objects in a city area are automatically generated from 2D-maps based on the appropriate rules. The entire 3D space is split into several layers depending on the height. The objects intersecting with a layer are managed by a 2D MD-tree corresponding to that layer. The objects close to a viewpoint are searched by the MD-tree corresponding to the lower layers. To provide the background of the scene (the distance view), far objects are searched by the MD-tree corresponding to the higher layer, because the lower objects far from the viewpoint may not be visible. The potentially visible objects can be obtained in a few milliseconds by the MD-trees. According as the number of the obtained objects and the distance from the viewpoint to the object, the rendering complexity of each object is controlled to accomplish the constant time rendering. With these techniques, an interactive walkthrough with the constant time response can be realized for the wide city area with more than 200,000 objects