A Fast Mesh Simplification Algorithm Based on Octree with Quadratic Approximation

摘要

Simplification is a hot topic in the field of mesh modeling. Most of the algorithms are progressive, and generating the intermediate models makes the algorithms less efficient. Vertex clustering is generally adopted to reduce the sample points, but the error control is hard to achieve. This paper presents a novel fast simplification algorithm which is based on octree with quadratic approximation. Our algorithm is not progressive and avoids creating any intermediate models. Hence there is a considerable improvement in efficiency. At the mean time, the error could be controlled as the subdivision process of the octree is based on a quadratic approximation of the local surface. The subdivision would stop only when the surface could be represented by a quadratic function, that is, the least-square error is less than a given threshold. Sample points are then clustered and represented by the most important ones, which give the contour of the model. Testing results show that the time and memory consumptions are significantly reduced.