Collapse-based mesh simplification using angular deviation and regularity bias

Abstract

A major research topic in computer graphics is mesh simplification, reducing the face count of complex 3D models to improve rendering performance while retaining visual quality. Current research prefers edge contraction based methods, such as Garland and Heckbert's Quadric Error Metric, as such methods lend themselves well to level-of-detail structures. Various research has suggested improvements to QEM based on curvature-based scoring; however, using the two principal curvatures and their directions can help reduce the inherent ambiguity of using a single score. The proposed extension to Garland and Heckbert's method calculates the principal curvatures and their directions for each vertex, to calculate the absolute normal curvature in the direction of contraction. Also, the regularity and the angular and dihedral deviations of the resulting faces are used to apply penalties. A heap updating scheme that only updates the top portion of the heap to save time is also described. The proposed method has been observed to reduce the average Hausdorff distance, a measure of mesh difference, in a range between 12%-70% from 5% to 50% face count, although QEM still produces lower distances at lower face count. Although the proposed algorithm retains an O(n log n) time complexity, the partial heap update scheme has improved the overall process by a factor of 5.4 compared to using full heap updates.