Research On Triangle Mesh Model Simplificaton Algorithm Based On The Probability Function And Its Implement

Triangle mesh models are widely used in many computer graphics systems, such as computer-aided design, computer animation, scientific visualization and virtual reality. A complex triangle mesh model will be heavy burden for computer to access and transfer it. However, not all 3D objects are constructed with much more details, for example, an object far away from viewers may have less detail than an object nearby. So in most of cases, we can simplify a complex triangle mesh model to suit different demands.This thesis is dedicated to a high efficiency method on simplifing triangle mesh models. First, we introduce some basic concepts about triangular mesh models and error evaluating methods, and then we survey some existed model simplification algorithms. On the basis of our research work, we present a new algorithm for simplifying triangle mesh models, which is based on probability function and applications of continuous collapse operation for triangles in meshes. In our algorithm, an adjustable weighted control function is used in controlling the simplification procedure. Specially, a probability function is constructed by means of error distribution. Each triangle in a mesh is distributed to a corresponding probability value by computing. All triangles are gradually collapsed according to their probability value. Triangles with a lower error and an upper probability are collapsed preferentially. In this way, after reordering triangles' errors, the number of collapsed triangles increases from one to several ones, and the single collapse mode is improved to the continuous collapse mode. Under same simplification rate, the sorting operation in continuous collapse simplification algorithms reduced remarkably when compared with that in single collapse simplification algorithms. As a result, the algorithm for simplifying triangle mesh model based on probability continuous collapse can speed up the simplification procedure on the aspect of error priority sort.In this paper, we give an analysis on the efficiency of our algorithm in theory and have also developed a demo system based on our algorithm. Results from our system show that the speed of continous collapsing operation is m times faster than single collapsing operation (m is the average number of continuous collapses), which is just consistent to the result from our theoretic analysis. And also, time consumption by running our demo system is 10 times less than that of any single collapsesimplification algorithm under the same error tolerance. Besides, we also compare our algorithm with simplification method by using the envelope as error tolerance. Result indicates that the speed of our algorithm is much faster than that of simplification method by using the envelope as error tolerance.