×

Adaptive skin meshes coarsening for biomolecular simulation. (English) Zbl 1218.92004

Summary: We present efficient algorithms for generating hierarchical molecular skin meshes with decreasing size and guaranteed quality. Our algorithms generate a sequence of coarse meshes for both the surfaces and the bounded volumes. Each coarser surface mesh is adaptive to the surface curvature and maintains the topology of the skin surface with guaranteed mesh quality. The corresponding tetrahedral mesh is conforming to the interface surface mesh and contains high quality tetrahedra that decompose both the interior of the molecule and the surrounding region (enclosed in a sphere).
Our hierarchical tetrahedral meshes have a number of advantages that will facilitate fast and accurate multigrid PDE solvers. Firstly, the quality of both the surface triangulations and tetrahedral meshes is guaranteed. Secondly, the interface in the tetrahedral mesh is an accurate approximation of the molecular boundary. In particular, all the boundary points lie on the skin surface. Thirdly, our meshes are Delaunay meshes. Finally, the meshes are adaptive to the geometry.

MSC:

92B05 General biology and biomathematics
92-08 Computational methods for problems pertaining to biology
92C40 Biochemistry, molecular biology

Software:

CGAL; FIST; Powercrust
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Amenta, N.; Choi, S.; Kolluri, R. K., The power crust, union of balls, and the medial axis transform, International Journal of Computational Geometry and its Applications, 19, 127-153 (2001) · Zbl 0988.65015
[2] Bajaj, C. L.; Pascucci, V.; Shamir, A.; Holt, R. J.; Netravali, A. N., Dynamic maintenance and visualization of molecular surfaces, Discrete Applied Mathematics, 127, 1, 23-51 (2003) · Zbl 1047.92051
[3] Berman, H.; Westbrook, J.; Feng, Z.; Gilliland, G.; Bhat, T.; Weissig, H.; Shindyalov, J.; Bourne, P., The protein data bank, Nucl. Acids Res., 28, 235-242 (2000)
[4] Botsch, M.; Pauly, M.; Kobbelt, L.; Alliez, P.; Lévy, B.; Bischoff, S.; Rössl, C., Geometric modeling based on polygonal meshes, (ACM SIGGRAPH, 2007 Courses, SIGGRAPH ʼ07 (2007), ACM Press: ACM Press New York, NY, USA)
[5] CGAL, 2011. Computational Geometry Algorithms Library, http://www.cgal.org; CGAL, 2011. Computational Geometry Algorithms Library, http://www.cgal.org
[6] Chavent, Matthieu; Levy, Bruno, MetaMol: High-quality visualization of molecular skin surface, Journal of Molecular Graphics and Modelling, 27, 209-216 (2007)
[7] Cheng, H.; Dey, T. K.; Edelsbrunner, H.; Sullivan, J., Dynamic skin triangulation, Discrete Comput. Geom., 25, 525-568 (2001) · Zbl 0984.68172
[8] Cheng, H., Shi, X., 2005. Quality mesh generation for molecular skin surfaces using restricted union of balls. In: Proceedings of IEEE Visualization, pp. 399-405.; Cheng, H., Shi, X., 2005. Quality mesh generation for molecular skin surfaces using restricted union of balls. In: Proceedings of IEEE Visualization, pp. 399-405.
[9] Cheng, H.-L., Shi, X., 2006. Quality tetrahedral mesh generation for macromolecules. In: ISAAC, pp. 203-212.; Cheng, H.-L., Shi, X., 2006. Quality tetrahedral mesh generation for macromolecules. In: ISAAC, pp. 203-212. · Zbl 1135.68597
[10] Cheng, S.-W.; Dey, T. K.; Edelsbrunner, H.; Facello, M. A.; Teng, S.-H., Sliver exudation, (Proceedings of the Fifteenth Annual Symposium on Computational Geometry (1999), ACM Press), 1-13
[11] Chentanez, N., Feldman, B.E., Labelle, F., OʼBrien, J.F., Shewchuk, J.R., 2007. Liquid simulation on lattice-based tetrahedral meshes. In: Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ʼ07, pp. 219-228.; Chentanez, N., Feldman, B.E., Labelle, F., OʼBrien, J.F., Shewchuk, J.R., 2007. Liquid simulation on lattice-based tetrahedral meshes. In: Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ʼ07, pp. 219-228.
[12] Chew, L. P., Constrained Delaunay triangulations, (SCG ʼ87: Proceedings of the Third Annual Symposium on Computational Geometry (1987), ACM Press: ACM Press New York, NY, USA), 215-222
[13] Cohen-Steiner, D.; de Verdiere, E. C.; Yvinec, M., Conforming delaunay triangulations in 3d, (Proceedings of the Eighteenth Annual Symposium on Computational Geometry (2002), ACM Press), 199-208 · Zbl 1414.68115
[14] Connolly, M. L., Molecular Surfaces: A Review (1996), Network Science
[15] Dey, T.; Edelsbrunner, H.; Guha, S.; Nekhayev, D., Topology preserving edge contraction, Publ. Inst. Math. (Beograd) (N.S.), 66, 23-45 (1999)
[16] Edelsbrunner, H., Deformable smooth surface design, Discrete Comput. Geom., 21, 87-115 (1999) · Zbl 0924.68197
[17] Edelsbrunner, H.; Mucke, E. P., Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, (ACM Trans. Graph., vol. 9 (1990), ACM Press), 66-104 · Zbl 0732.68099
[18] Edelsbrunner, H., Shah, N.R., 1992. Incremental topological flipping works for regular triangulations. In: Symposium on Computational Geometry, pp. 43-52.; Edelsbrunner, H., Shah, N.R., 1992. Incremental topological flipping works for regular triangulations. In: Symposium on Computational Geometry, pp. 43-52. · Zbl 0840.68050
[19] Edelsbrunner, H., Shah, N., 1994. Triangulating topological spaces. In: Proceedings 10th ACM Symposium on Computational Geometry, pp. 285-292.; Edelsbrunner, H., Shah, N., 1994. Triangulating topological spaces. In: Proceedings 10th ACM Symposium on Computational Geometry, pp. 285-292.
[20] Feng, Y. T.; Peric, D., Coarse mesh evolution strategies in the Galerkin multigrid method with adaptive remeshing for geometrically non-linear problems, International Journal for Numerical Methods in Engineering, 49, 547-571 (2000) · Zbl 0987.74065
[21] Garland, M., Heckbert, P.S., 1997. Surface simplification using quadric error metrics. In: SIGGRAPH, pp. 209-216.; Garland, M., Heckbert, P.S., 1997. Surface simplification using quadric error metrics. In: SIGGRAPH, pp. 209-216.
[22] Held, M., FIST: Fast industrial-strength triangulation of polygons, Algorithmica, 30, 4, 563-596 (2001) · Zbl 0980.65019
[23] Holst, M. J.; Saied, F., Numerical solution of the nonlinear Poisson-Boltzmann equation: Developing more robust and efficient methods, J. Comp. Chem., 16, 3, 337-364 (1995)
[24] Holst, M.; Baker, N. A.; Wang, F., Adaptive multilevel finite element solution of the Poisson-Boltzmann equation I. Algorithms and examples, J. Comp. Chem., 21, 15, 1319-1342 (2000)
[25] Kobbelt, L. P.; Bareuther, T.; Seidel, H.-P., Multiresolution shape deformations for meshes with dynamic vertex connectivity, Computer Graphics Forum, 19, 3, 249-260 (2003)
[26] Kruithof, N.; Vegter, G., Meshing skin surfaces with certified topology, Comput. Geom., 36, 3, 166-182 (2007) · Zbl 1118.65014
[27] Lu, B.; Zhou, Y. C.; Huber, G. A.; Bond, S. D.; Holst, M. J.; McCammon, J. A., Electrodiffusion: a continuum modeling framework for biomolecular systems with realistic spatiotemporal resolution, J. Chem. Phys., 127, 5102 (2007)
[28] Miller, G.L., Talmor, D., Teng, S.-H., 1997. Optimal good-aspect-ratio coarsening for unstructured meshes. In: SODA: ACM-SIAM Symposium on Discrete Algorithms.; Miller, G.L., Talmor, D., Teng, S.-H., 1997. Optimal good-aspect-ratio coarsening for unstructured meshes. In: SODA: ACM-SIAM Symposium on Discrete Algorithms. · Zbl 1321.65152
[29] Ollivier-Gooch, C., Coarsening unstructured meshes by edge contraction, International Journal for Numerical Methods in Engineering, 57, 391-414 (2003) · Zbl 1062.76527
[30] Pebay, P.P., Baker, J.T., 2001. A comparison of triangle quality measures. In: Proceedings 10th International Meshing Roundtable, pp. 327-340.; Pebay, P.P., Baker, J.T., 2001. A comparison of triangle quality measures. In: Proceedings 10th International Meshing Roundtable, pp. 327-340.
[31] Shewchuk, J.R., 1997. Delaunay refinement mesh generation, PhD thesis, Carnegie-Mellon University.; Shewchuk, J.R., 1997. Delaunay refinement mesh generation, PhD thesis, Carnegie-Mellon University. · Zbl 1016.68139
[32] Si, H., 2006. On refinement of constrained Delaunay tetrahedralizations. In: Proceedings of the 15th International Meshing Roundtable.; Si, H., 2006. On refinement of constrained Delaunay tetrahedralizations. In: Proceedings of the 15th International Meshing Roundtable.
[33] Si, H., Gaertner, K., 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Proceedings of the 14th International Meshing Roundtable, pp. 147-163.; Si, H., Gaertner, K., 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Proceedings of the 14th International Meshing Roundtable, pp. 147-163.
[34] Wolters, H. J., Geometric modeling applications in rational drug design: a survey, Computer Aided Geometric Design, 23, 6, 482-494 (2006) · Zbl 1098.92033
[35] Zhang, Y.; Xu, G.; Bajaj, C., Quality meshing of implicit solvation models of biomolecular structures, Computer Aided Geometric Design, 23, 6, 510-530 (2006) · Zbl 1098.92034
[36] Zomorodian, A.; Guibas, L.; Koehl, P., Geometric filtering of pairwise atomic interactions applied to the design of efficient statistical potentials, Computer Aided Geometric Design, 23, 6, 531-544 (2006) · Zbl 1098.92003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.