Shou, LidanChionh, JasonHuang, ZhiyongRuan, YixinTan, Kian-Lee2015-11-112015-11-1120011017-4656https://doi.org/10.2312/egs.20011006In this paper, we study the problem of interactive walkthrough of a large virtual environment (VE) where the data representing 3D virtual objects can not reside completely in the main memory. We tap into the wealth of techniques (indexing, caching, prefetching) that have been widely used by the database community, and investigate how walkthrough semantics can be integrated into these techniques. In our approach, the VE data in the main memory are dynamically managed such that only those of the relevant 3D objects pertaining to the current user’s viewpoint are loaded into the main memory. The objects in the VE are spatially indexed by a spatial index structure (R-tree) as opposed to splitting the VE into smaller rigid-sized grids. Queries are issued to the R-tree to retrieve only the relevant objects. We propose a novel complement search algorithm to improve the standard search. In addition, we propose a cache replacement policy that considers the access pattern of walkthrough to facilitate effective memory management; and a prediction algorithm that computes the next likely position of the user in order to prefetch data. We implemented a prototype walkthrough system and evaluated it on a 1 GB synthetic dataset of a cityscape. Our results show that the proposed techniques deployed can lead to a high constant frame rate for the walkthrough.