Researches On Some Key Technologies Of Roaming In Virtual Scene Based On Voronoi Diagram

In recent years, the technology of virtual reality has been widely applied to the fields of military, aerospace, medicine, education, game, etc., wherein three-dimensional (3D) virtual indoor scenes like virtual museum continue to spring up so that people are not restricted by territory, time and space during visiting and learning.In order to make a roaming real-time and realistic in a virtual scene, key technologies, such as effective representation method of virtual scene, visibility computing, path planning and realistic motion synthesis of avatar, have to be studied. For a complex scene, establishing an optimized scene representation model plays an important role in accelerating the real-time roaming. The organization of the scene should be beneficial for resolving other problems of the roaming system, such as path planning, collision detection, visibility computing, illumination calculation, etc. The path planning problem belongs to the research content of virtual scene interactive roaming. Based on users’ different purposes of browsing, different path planning methods are needed to enable the avatar to roam along different paths. In addition, most of prior virtual scene roaming systems utilize arrows to guide users to browse and are lack of vicarious feeling of users. In some of these systems, although avatars are provided in the virtual scene, they can do trans lational motion only or has unitary motion effect. Therefore, avatars with realistic motion can be introduced into the roaming system to enhance the sense of reality of roaming. During the process of roaming, the vast majority of content of the scene is invisible due to the angle of view. Performing visibility computing and rendering visible area of the scene only are indispensable requirements to ensure that the roaming proceeds in a real-time manner.For this purpose, the present dissertation explores several key technologies to improve the reality and instantaneity of virtual indoor scene roaming system and in particular, the present dissertation puts emphasize on researches of some key problems like scene representation, path planning, visibility computing and motion synthesis of avatars so that uses can enjoy a much more realistic feeling during roaming in the virtual scene. Main research contents and distributions of the present dissertation are as following:1) Proposing a representation method of3D indoor virtual scenes based on Voronoi diagram of polygonsAccording to the features of3D indoor scenes, the present dissertation puts forward a representation method of3D indoor scenes based on Voronoi diagram. The method uses Voronoi diagram of polygons as the basic data structure and is based on the properties of Voronoi diagram of polygons like the most proximity, skeleton characteristics, etc. Problems, such as representation of virtual scene, data organization, path planning, visibility computing, etc. are all taken into consideration. Various algorithms are designed in a systemic way so that space is saved on the whole, algorithms are in mutual cooperation, and efficiency of algorithms is improved.2) Proposing a path planning method based on Voronoi diagram of polygonsIn a virtual scene, different motion paths are needed, including random path, Voronoi skeleton path which prevents collision of two sides, shortest path between starting point and ending point given by a user, curvilinear motion path, etc. The present dissertation mainly investigates how to compute the Voronoi skeleton path and the shortest path in polygons efficiently and proposes a computing method of the shortest Voronoi skeleton path and the shortest path in complicated polygons based on hierarchical Voronoi diagram. For any two points in a polygon, the shortest Voronoi skeleton path between them can be figured out by O(k+h log h+log n) while the shortest path between them can be figured out by O(m+h2log h+hlog(n/h)+logn), wherein:n is the number of vertices of the polygon, h is the number of "holes" contained in the polygon; k is the number of Voronoi sides in the shortest Voronoi skeleton path, and O(k)≤O(n); m is the number of sides in the shortest path and m≤n.3) Proposing a visibility computing method of curvilinear path based on Voronoi diagram of polygonsVisibility computing plays a very important role for accelerating scene rendering. The present dissertation puts forward a weak visibility computing method of NURBS curve based on Voronoi diagram of polygons and a method for computing visible polygons of a point which move along curvilinear path. Based on this method, for any given curvilinear trace, weak visible areas along the curve are pre-computed and in real roaming, only visible areas from viewpoints along the motion trace within the weak visible areas are computed so that the amount of computation is substantially reduced and the speed of rendering is increased. In addition, when the users are designing roaming paths interactively, the potential visible areas of the designed path curves can be displayed in a real-time way to enable the users to adjust the roaming paths effectively to cover areas to watch.4) Proposing a motion synthesis method of avatar based on motion capture dataTo improve the reality, avatars are added into the virtual scene. Study is made to investigate how to make the motion be realistic when the avatar is roaming along a given curvilinear path in the scene. For this aim, the present dissertation puts forward a method for synthesizing the motion of avatars in a real-time manner based on motion capture data and motion graph. The method takes little amount of captured sample data as input and synthesizes new motion by the way of motion graph so as to make the motion be more realistic when the virtual avatar is roaming along given motion trace in the virtual scene.For future study, Voronoi diagram of curvilinear polygons and its application algorithms will be further studied on the basis of the results of the present dissertation.