Meshing skin surfaces with certified topology. (English) Zbl 1118.65014
Skin surfaces form a class of tangent continuous surfaces defined in terms of a set of balls (the atoms of the molecule) and a shrink factor. They are used for the visualization of molecules and for approximation purposes. The authors present an algorithm that approximates a skin surface with a topologically correct mesh. The complexity of the mesh is linear in the size of the Delaunay triangulation of the balls, which is worst case optimal. They also adapt two existing refinement algorithms to improve the quality of the mesh and show that the same algorithm can be used for meshing a union of balls.
Reviewer: Vladimir Yu. Rovenskij (Nesher)
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 52B55 | Computational aspects related to convexity |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
isotopy; regular triangulation; visualization of molecules; Delaunay triangulation; refinement algorithmsReferences:
| [1] | Attali, D.; Boissonnat, J.-D., A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces, (Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications (2002), ACM Press), 139-146 |
| [2] | Bajaj, C.; Lee, H. Y.; Merkert, R.; Pascucci, V., Nurbs based b-rep models for macromolecules and their properties, (Proceedings of the Fourth ACM Symposium on Solid Modeling and Applications (1997), ACM Press), 217-228 |
| [3] | Bajaj, C. L.; Pascucci, V.; Shamir, A.; Holt, R. J.; Netravali, A. N., Dynamic maintenance and visualization of molecular surfaces, Discrete Appl. Math., 127, 1, 23-51 (2003) · Zbl 1047.92051 |
| [4] | Bloomenthal, J., Polygonization of implicit surfaces, Computer Aided Geometric Design, 5, 4, 341-355 (1988) · Zbl 0659.65013 |
| [5] | J.-D. Boissonnat, D. Cohen-Steiner, G. Vegter, Isotopic implicit surface meshing, in: ACM Symposium on Theory of Computing (STOC), 2004, pp. 301-309; J.-D. Boissonnat, D. Cohen-Steiner, G. Vegter, Isotopic implicit surface meshing, in: ACM Symposium on Theory of Computing (STOC), 2004, pp. 301-309 · Zbl 1192.65016 |
| [6] | Boissonnat, J.-D.; Yvinec, M., Algorithmic Geometry (1998), Cambridge University Press: Cambridge University Press Cambridge, UK, Translated by Hervé Brönnimann · Zbl 0917.68212 |
| [7] | Brönnimann, H.; Burnikel, C.; Pion, S., Interval arithmetic yields efficient dynamic filters for computational geometry, Discrete Appl. Math., 109, 25-47 (2001) · Zbl 0967.68157 |
| [8] | Cheng, H.-L.; Dey, T. K.; Edelsbrunner, H.; Sullivan, J., Interval arithmetic yields efficient dynamic filters for computational geometry, Discrete Comput. Geom., 25, 525-568 (2001) · Zbl 0984.68172 |
| [9] | Cheng, H.-L.; Shi, X., Guaranteed quality triangulation of molecular skin surfaces, (VIS’04: Proceedings of the Conference on Visualization ’04 (2004), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 481-488 |
| [10] | L. Chew, Guaranteed quality Delaunay meshing in 3d, in: Proceedings of the Thirteenth Annual ACM Symposium on Computational Geometry, 1997, pp. 391-393; L. Chew, Guaranteed quality Delaunay meshing in 3d, in: Proceedings of the Thirteenth Annual ACM Symposium on Computational Geometry, 1997, pp. 391-393 |
| [11] | S. Choi, N. Amenta, Delaunay triangulation programs on surface data, in: The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 135-136; S. Choi, N. Amenta, Delaunay triangulation programs on surface data, in: The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 135-136 · Zbl 1058.65023 |
| [12] | Computational Geometry Algorithms Library · Zbl 1365.68441 |
| [13] | Connolly, M. L., Analytical molecular surface calculation, J. Appl. Crystallogr., 16, 5, 548-558 (1983) |
| [14] | T.K. Dey, G. Li, T. Ray, Polygonal surface remeshing with Delaunay refinement, in: Proc. 14th Internat. Meshing Roundtable, 2005, pp. 343-361; T.K. Dey, G. Li, T. Ray, Polygonal surface remeshing with Delaunay refinement, in: Proc. 14th Internat. Meshing Roundtable, 2005, pp. 343-361 |
| [15] | Edelsbrunner, H., Deformable smooth surface design, Discrete Comput. Geom., 21, 87-115 (1999) · Zbl 0924.68197 |
| [16] | Edelsbrunner, H.; Mücke, E. P., Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms, ACM Trans. Graph., 9, 1, 66-104 (1990) · Zbl 0732.68099 |
| [17] | H. Edelsbrunner, A. Üngör, Relaxed scheduling in dynamic skin triangulation, in: Proceedings of the Japan Conference on Discrete and Computational Geometry, 2002, pp. 135-151; H. Edelsbrunner, A. Üngör, Relaxed scheduling in dynamic skin triangulation, in: Proceedings of the Japan Conference on Discrete and Computational Geometry, 2002, pp. 135-151 · Zbl 1179.68176 |
| [18] | Hartmann, E., A marching method for the triangulation of surfaces, The Visual Computer, 14, 3, 95-108 (1998) · Zbl 0906.68172 |
| [19] | Kobbelt, L., \( \sqrt{3} \)-subdivision, (Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (2000), ACM Press/Addison-Wesley Publishing Co.), 103-112 |
| [20] | N.G.H. Kruithof, G. Vegter, Triangulating skin surfaces, Technical Report ECG-TR-244303-01, Rijksuniversiteit Groningen, 2003; N.G.H. Kruithof, G. Vegter, Triangulating skin surfaces, Technical Report ECG-TR-244303-01, Rijksuniversiteit Groningen, 2003 · Zbl 1206.65052 |
| [21] | Kruithof, N. G.H.; Vegter, G., Approximation by skin surfaces, Computer-Aided Design, 36, 1075-1088 (2004) · Zbl 1206.65052 |
| [22] | Lorensen, W. E.; Cline, H. E., Marching cubes: A high resolution 3d surface construction algorithm, (SIGGRAPH ’87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (1987), ACM Press: ACM Press New York), 163-169 |
| [23] | Pedoe, D., Geometry, a Comprehensive Course (1970), Dover Publications: Dover Publications New York · Zbl 0213.22001 |
| [24] | S. Plantinga, G. Vegter, Isotopic approximation of implicit curves and surfaces, in: ACM SIGGRAPH Symposium on Geometry Processing, 2004, pp. 251-260; S. Plantinga, G. Vegter, Isotopic approximation of implicit curves and surfaces, in: ACM SIGGRAPH Symposium on Geometry Processing, 2004, pp. 251-260 |
| [25] | Treece, G. M.; Prager, R. W.; Gee, A. H., Regularised marching tetrahedra: Improved iso-surface extraction, Computers and Graphics, 23, 4, 583-598 (1999) |
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.
