A Study On Parallel Level-of-detail Techniques For Out-of-core Meshes

With the rapid development in the field of modeling and scanning techniques,large scale meshes have become widely-used models in 3d graphics area.These models can satisfy the need of higher accuracy in simulation problems,and can produce realistic images for better visually perception.Another name of large scale meshes is out-of-core meshes,as the mesh is too large to be loaded into any regular memory at once.Up to now,there are still many primary problems must be tackled for the practical use of these meshes,one of them is considering the rendering speed,for example,making the mesh can be rendered in a complicate scene at interactive frame rates.To make the out-of-core meshes be rendered faster,researches have proposed a lot of methods that effectively reducing the executing time,but not enough yet.In this thesis,we consider to make a further improvement of one of these methods,the level-of-detail(LOD)technique.The LOD technique is a practical accelerating technique in many applications of 3d graphics.The core algorithm used in LOD construction is named mesh simplification.After two decades of development,the model processed by LOD technique has been moved from in-core meshes(can be loaded to regular memories at once)to out-of-core meshes,and a large amount of LOD algorithms for out-of-core meshes have been given out,but unfortunately,the speed of these algorithms is still not fast enough.Today,we are in an new phase of the information era,which may be given a name as cloud computing era.In this era,the distributed/parallel computing services can be employed by larger amount of lower-tier users.For this reason,the design and implementation of parallel algorithms for many original serial algorithms is thought to become an meaningful task.For LOD technique,we can use parallel strategy to make itself running more efficiently.This thesis did three works that are related to the LOD technique,the first one is a survey on LOD technique,the second one is a parallel algorithm for dynamic LOD construction,and the third one is a parallel algorithm for out-of-core mesh simplification.Here we put some brief descriptions about these works:(1)The survey of LOD technique is a systematical summary of the research results on the field of LOD technique and some relevant fields,including LOD's pipeline,LOD scheduling,model simplification algorithms,progressive meshes,out-of-core mesh simplification,and parallel mesh simpflication and LOD techniques.(2)The parallel algorithm for dynamic LOD contruction is based on a model cutting method named domain decomposition.The main contributions of this algorithm are presented as follows.Firstly,the traditional progressive mesh algorithm is improved by using quadric error metric method,to provide faster implementation.Then,a self-adaptive domain decomposition algorithm based on model's bounding box is put forward for cutting the original model into several blocks for parallel computing.Finally,a parallel dynamic level-of-detail construct algorithm by executing progressive mesh algorithm on the blocks in parallel is presented.As a result,this algorithm can generate high-qualified level-of-detail models,and has ideal speed-up ratio and expansibility.Compared to serial algorithms,this algorithm greatly reduces the execution time.(3)The parallel algorithm for out-of-core mesh simplification is a very efficient method based on vertex clustering and multi data stream.The main contributions of this algorithm are presented as follows.First,the procedure for representative point calculation in traditional vertex clustering algorithm is promoted by using the vertex filtering method.Second,a strategy for data external storage in distributed computing environment is presented.Third,the execution of two methods named cell filtering and vertex filtering is improved using the multi data stream theory.Finally,the three improvements are put together to form the integrated parallel out-of-core model simplification algorithm.As a result,this algorithm can avoid the destruction of original models generated by the domain decomposition procedure,so as to improve the simplified models' quality.Compared to several parallel algorithms,this algorithm drastically optimizes the load distribution efficiency,and has a better acceleration and parallel efficiency.