Visibility Computing Based On Voronol Diagram

While walking through the virtual scenes, it needs quickly determining which objects are visible when the viewers are moving on, so designing the appropriate visibility calculation methods not only implements fast rendering, but also reduces the storage and memory cost. In the case of the 2D scenes, it is that whether the viewer can see the sides and the visible parts of them when at one position of the polygon.Our research background is the archaeological Digital Museum of Shandong University employing the Voronoi diagram as the unified data structure, which is used in the layout of the gallery and the path planning. This paper researches and designs the rapid visibility calculation method mainly based on this data structure.Our algorithm can be divided into the potentially visible sets (PVSs) calculation phase and the visibility real-time calculation phase. The core part of our algorithm is the potentially visible sets calculation phase, which employs the sampling points and point visibility calculation method to obtain the potentially visible sets of the regions. In PVSs calculation phase, after the subdivision of the planar polygon of the virtual museum by Voronoi diagram, we get more appropriate view cells by subdividing the Voronoi regions. And then we sample points on the boundary sides every view cell, compute the sampling points exact visible sets, and merge all the visible sets of them into the potentially visible set of the view cell. In visibility real-time calculation phase, we firstly determine the view cell which the viewer is located in, and then use the potentially visible set of it to compute the visibility of the viewpoint, which can realize rapid 3D scene walkthrough rendering. When the viewer is moving, it can determine the new view cell where the viewpoint is located according to the proximity of the Voronoi diagram.The work and contributions of our algorithm is that we propose a visibility calculation method based on Voronoi diagram, which utilizes from-point visibility to compute from-region visibility, and raises the heuristic adaptive sampling method and the visible sets merge strategy of the points, in order to obtain more tight PVS. This algorithm together with the layout of the gallery, path planning and so on takes advantage of the unified data structure in the virtual archaeological walkthrough system, yet not depending on the additional data structures, which greatly saves the memory cost of the system.The algorithm takes advantage of the sampling visibility, not guaranteeing the PVS including all the visible objects. But the view space subdivision and the adaptive point sampling on the boundary sides of the view cells make the visible objects included in the PVS as many as possible.