Abstract
Radial Basis Functions are widely used in scattered data interpolation. The surface-reconstruction method using radial basis functions consists of two steps: (i) computing an interpolating implicit function the zero set of which contains the points in the data set, followed by (ii) extraction of isocurves or isosurfaces. In this paper we focus on the second step, generalizing the work on certified meshing of implicit surfaces based on interval arithmetic (Plantinga and Vegter in Visual Comput. 23:45–58, 2007). It turns out that interval arithmetic, and even the usually faster affine arithmetic, are far too slow in the context of RBF-based implicit surface meshing. We present optimized strategies giving acceptable running times and better space complexity, exploiting special properties of RBF-interpolants. We present pictures and timing results confirming the improved quality of these optimized strategies.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Boissonnat, J.-D., Cohen-Steiner, D., Vegter, G.: Isotopic implicit surface meshing. Discrete Comput. Geom. 39, 138–157 (2008)
Boost interval arithmetic library: http://www.boost.org (2011)
Buhmann, M.: Radial Basis Functions. Cambridge Monographs on Applied and Computational Mathematics, vol. 12. Cambridge University Press, Cambridge (2003)
Burr, M., Choi, S., Galehouse, B., Yap, C.: Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves. In: Proc. Int’l Symp. Symbolic and Algebraic Comp. (ISSAC’08), pp. 87–94, Hagenberg, Austria, Jul. 20–23, 2008 (2008)
C++ affine arithmetic library: http://savannah.nongnu.org/projects/libaffa (2011)
GTS the gnu triangulated surface library: http://gts.sourceforge.net (2011)
de Figueiredo, L.H., Stolfi, J.: Affine arithmetic: concepts and applications. Numer. Algorithms 37(1–4), 147–158 (2004)
Iske, A.: Scattered data modelling using radial basis functions. In: Iske, A., Quak, E., Floater, M.S. (eds.) Tutorials on Multiresolution in Geometric Modelling, Mathematics and Visualization, pp. 287–315. Springer, Heidelberg (2002)
Lodha, S., Franke, R.: Scattered data techniques for surfaces. In: Proceedings of Dagstuhl Conference on Scientific Visualization, pp. 182–222. IEEE Computer Society Press, Los Alamitos (1999)
Lopes, H., Oliveria, J., Figueiredo, L.: Robust adaptive polygonal approximation of implicit curves. Comput. Graph. 26(6), 841–852 (2002)
Lorensen, W., Cline, H.: Marching cubes: a high resolution 3D surface construction algorithm. Comput. Graph., 21, 163–169 (1987). Proceedings SIGGRAPH 1987, Annual Conference Series
Martin, R., Shou, H., Voiculescu, I., Bowyer, A., Wang, G.: Comparison of interval methods for plotting algebraic curves. Comput. Aided Geom. Des. 19(7), 553–587 (2002)
Moore, R.: Interval Analysis. Prentice-Hall, New York (1996)
Plantinga, S., Vegter, G.: Isotopic meshing of implicit surfaces. Vis. Comput. 23, 45–58 (2007)
Powell, M.J.D.: Approximation Theory and Methods. Cambridge University Press, Cambridge (1981)
Schaback, R., Wendland, H.: Characterization and construction of radial basis functions. In: Dyn, N., Leviatan, D., Levin, D., Pinkus, A. (eds.) Multivariate Approximation and Applications, Chap. 1, pp. 1–24. Cambridge University Press, Cambridge (2001)
Shou, H., Song, W., Shen, J., Martin, R., Wang, G.: A recursive Taylor method for ray casting algebraic surfaces. In: Proc. 2006 Int. Conf. Computer Graphics and Virtual Reality, pp. 196–202. CSREA Press, Las Vegas (2006). ISBN:1932415858
Stander, B., Hart, J.: Guaranteeing the topology of an implicit surface polygonizer for interactive modeling. In: Proceedings SIGGRAPH, pp. 279–286 (1997)
Stolfi, J., de Figueiredo, L.: Self-validated numerical methods and applications. In: Brazilian Mathematics Colloquium Monograph, IMPA (1997)
Wendland, H.: Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics, vol. 17. Cambridge University Press, Cambridge (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chattopadhyay, A., Plantinga, S. & Vegter, G. Certified meshing of Radial Basis Function based isosurfaces. Vis Comput 28, 445–462 (2012). https://doi.org/10.1007/s00371-011-0627-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-011-0627-2