Study Of Progressive Level Of Detail Method Based On Graph Rotation System

LOD (Levels of Detail) method is a new representation method. It changes the traditional thought that the more detail the better the model. LOD method can be used in many domains, such as real-time image communication, contact check, real-time render, interactive visualization and VR. LOD method represent the detail of meshes by create several simplified versions of original meshes. Thus the graph system can choose or reconstruct properly level of detail of model by importance of object or real-time condition, and render complicated scene rapidly and efficiently. Progressive LOD method is a continuous resolution method, so graph can be changed gradually, and the shape of model will not change suddenly.Topology simplification can simplify models by change the topology of them. It can gradually simplify any models to a simplest Genus-0 surface, which is called a tetrahedron. If topology simplification is used in LOD method, the simplification procedure can be optimized and better simplification can be got. But no current progressive LOD method can support topology simplification.Current LOD method can not preserve 2-manifold of models. In computer graphics preserve 2-manifold is an important and basic problem. Many often used algorithms in computer graphics require that the model to be operated must be 2-manifold, such as subdivision operation. If the model is not 2-manifold, these algorithms will not work or will be very complicated. In LOD method some wrong objects will appear if can not preserve 2-manifold of models.In this thesis a new progressive LOD method that can support topology simplification and can preserve 2-manifold of meshes is presented. The main contributions of this thesis include:1. A new data structure based on graph rotation system: Doubly Linked Rotation System (DLRS) is presented. A sound and complete operation set based on DLRS data structure has been constructed. Most current data structure can not preserve 2-manifold of models. The DLRS data structure can only represent 2-manifold models. It can completely support the 9 topology relations between vertices, edges and faces of polygons, so it is a full topology relation representation data structure. The operation set of DLRS data structure presented in this thesis is complete and sound. Complete means that every 2-manifold model can be constructed by using the operations in the operation set. Sound means that if operating a 2-manifold model only by the operations in the operation set the model will still be 2-manifold. If we use DLRS data structure represent meshes, and change meshes only use operations in operation set, then the model can preserve 2-manifold. DLRS data structure is simpler than DLFL data structure, and is more efficient than DCEL and graph adjacent list. A DLRS structure can be converted to a DLFL structure or a DCEL structure in linear time.2. A new progressive LOD method: Progressive LOD based on Graph Rotation System (PLG method) is presented. This method support topology simplification and can preserve 2-manifold of models. PLG method is a progressive method, can gradually change models. It is a lossless method. PLG method uses DLRS data structure to represent meshes, store level of detail by basic mesh and operation sequence. PLG method has two parts, one of them is an off-line preprocessor procedure which can create LOD, the other is an on-line procedure which render current scene in real time. The procedure to create LOD has two levels, which is direct operation level and indirect operation level. Operations of direct operation level is the operations in operation set of DLRS data structure, and can be get from preprocessor procedure. Operations of indirect operation level can be divided into topology change operation and topology preserve operation. PLG method support triangle meshes and polygonal meshes, and support several error estimate algorithms. 3. We present Edge Collapse operation and Vertex Decimation operation based on graph rotation system. We also present CutTunnel and CreateTunnel operations based on graph rotation system, PCutTunnel operation and PCreateTunnel operation based on graph rotation system. These 6 operations can preserve 2-manifold of models. Edge Collapse operation and Vertex Decimation operation based on graph rotation system are topology preserve operations of indirect operation level. CutTunnel, CreateTunnel, PCutTunnel and PCreateTunnel operation can change topology of models. CutTunnel operation can cut a complicated tunnel or close a hole. CreateTunnel operation is the reverse operation of CutTunnel. These two operations are easy-used and run rapidly. PCutTunnel operation can cut a tunnel by using a plane. The visualization effect on the tunnel to be cut will not change. PCreateTunnel operation is the reverse operation of PCutTunnel. These operations solve the problem that CutTunnel and CreateTunnel operation will greatly change the visualization of model.4. Experiments on cow, bone, bunny, dragon and buddhaf models of Stanford University have been done using DLRS data structure, PLG method, Edge Collapse operation based on graph rotation system, Vertex Decimation operation based on graph rotation system, CutTunnel/CreateTunnel operations and PCutTunnel/PCreateTunnel operations. The models run rapidly and preserve 2-manifold in the experiments. The results show that the DLRS data structure, PLG method, Edge Collapse operation based on graph rotation system, Vertex Decimation operation based on graph rotation system, CutTunnel/CreateTunnel operations and PCutTunnel/PCreateTunnel operations play well and the results is practical.