Stable mesh decimation

ABSTRACT

Current mesh reduction techniques, while numerous, all primarily reduce mesh size by successive element deletion (e.g. edge collapses) with the goal of geometric and topological feature preservation. The choice of geometric error used to guide the reduction process is chosen independent of the function the end user aims to calculate, analyze, or adaptively refine. In this paper, we argue that such a decoupling of structure from function modeling is often unwise as small changes in geometry may cause large changes in the associated function. A stable approach to mesh decimation, therefore, ought to be guided primarily by an analysis of functional sensitivity, a property dependent on both the particular application and the equations used for computation (e.g. integrals, derivatives, or integral/partial differential equations). We present a methodology to elucidate the geometric sensitivity of functionals via two major functional discretization techniques: Galerkin finite element and discrete exterior calculus. A number of examples are given to illustrate the methodology and provide numerical examples to further substantiate our choices.

REFERENCES

• 1: I. Babuska and A. Aziz. Survey lectures on the mathematical foundations of the finite element method. In The Mathematical Foundations of the FEM with Applications to PDEs, Proc. Sympos., 1972.
• 2: I. Babuška, J. Chandra, and J. E. Flaherty. Adaptive Computational Methods for Partial Differential Equations. SIAM, Philadelphia, PA, USA, 1983.
• 3: I. Babuška, O. C. Zienkiewicz, J. Gago, and E. R. de A. Oliveira. Accuracy Estimates and Adaptive Refinements in Finite Element Computations. John Wiley and Sons, Chichester, 1986.
• 4: C. Bajaj and A. Chen. Efficient and accurate higher-order fast multipole bem for poisson-boltzmann electrostatics. SIAM J. on Sci. Comp., Submitted.
• 5: C. Bajaj, R. Chowdhury, and M. Rasheed. A dynamic data structure for flexible molecular maintenance and informatics. In SIAM/ACM GDSPM09, Accepted.
• 6: C. Bajaj and D. Schikore. Topology preserving data simplification with error bounds. Computers and Graphics, 22:3--12(10), 25 February 1998.
• 7: C. Bajaj and W. Zhao. Fast molecular solvation energetics and forces computation. SIAM J. Sci. Comp., Submitted.
• 8: N. A. Baker, D. Sept, M. J. Holst, and J. A. McCammon. The adaptive multilevel finite element solution of the Poisson-Boltzmann equation on massively parallel computers. J. Comput. Chem, 21, 2000.
• 9: W. N. Bell. Algebraic multigrid for discrete differential forms (dissertation). Technical report, University of Illinois at Urbana-Champaign, 2008.
• 10: H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I. Shindyalov, and P. Bourne. The Protein Data Bank. Nucleic Acids Research, pages 235--242, 2000.
• 11: S. Brenner and L. Scott. The Mathematical Theory of Finite Element Mehtods. Springer-Verlag, New York, 2002.
• 12: L. Chen, M. J. Holst, and J. Xu. The finite element approximation of the nonlinear poisson-boltzmann equation. SIAM J. Numer. Anal., 45(6):2298--2320, 2007.
• 13: CVC. TexMol. http://ccvweb.csres.utexas.edu/ccv/projects/project.php?proID=8.
• 14: L. Demkowicz. Computing with hp-adaptive finite elements. Chapman and Hall / CRC, 2007.
• 15: M. Desbrun, A. N. Hirani, M. Leok, and J. E. Marsden. Discrete Exterior Calculus. arXiv:math/0508341, 2005.
• 16: J. E. Flaherty, M. Shepard, P. Paslow, and D. Vasilakis. Adaptive Methods for Partial Differential Equations. SIAM, Philadelphia, PA, USA, 1989.
• 17: M. Garland. QSlim. http://graphics.cs.uiuc.edu/~garland/software/qslim.html, 2004.
• 18: M. Garland and P. S. Heckbert. Surface simplification using quadric error metrics. In SIGGRAPH '97, pages 209--216, New York, NY, USA, 1997.
• 19: A. Ghosh, C. S. Rapp, and R. A. Friesner. Generalized born model based on a surface integral formulation. The Journal of Physical Chemistry B, 102(52):10983--10990, 1998.
• 20: P. Heckbert and M. Garland. Survey of polygonal surface simplification algorithms. Technical report, Carnegie Mellon University, 1995.
• 21: A. N. Hirani. Discrete exterior calculus (dissertation). Technical report, Cal Tech, 2003.
• 22: A. N. Hirani, K. B. Nakshatrala, and J. H. Chaudhry. Numerical method for Darcy flow derived using Discrete Exterior Calculus. arXiv:0810.3434, 2008.
• 23: P. Lindstrom and G. Turk. Fast and memory efficient polygonal simplification. In VIS '98, pages 279--286, 1998.
• 24: P. Lindstrom and G. Turk. Evaluation of memoryless simplification. IEEE Transactions on Visualization and Computer Graphics, 5(2):98--115, 1999.
• 25: LLNL. TeraScale Browser. https://computing.llnl.gov/vis/terascale.shtml, 2007.
• 26: B. Lu, D. Zhang, and J. A. McCammon. Computation of electrostatic forces between solvated molecules determined by the poisson-boltzmann equation using a boundary element method. Journal of Chemical Physics, 122(21):214102-1-7, 2005.
• 27: D. Luebke, B. Watson, J. D. Cohen, M. Reddy, and A. Varshney. Level of Detail for 3D Graphics. Elsevier Science Inc., New York, 2002.
• 28: G. Xu, Q. Pan, and C. L. Bajaj. Discrete surface modelling using partial differential equations. CAGD, 23(2):125--145, 2006.
• 29: A. Yavari. On geometric discretization of elasticity. Journal of Mathematical Physics, 49(2):1--36, 2008.