“Topology- and Error-Driven Extension of Scalar Functions From Surfaces to Volumes” by Patane, Spagnuolo and Falcidieno

The behavior of a variety of phenomena measurable on the boundary of 3D shapes is studied by modeling the set of known measurements as a scalar function f 😛 → R, defined on a surface P. Furthermore, the large amount of scientific data calls for efficient techniques to correlate, describe, and analyze this data. In this context, we focus on the problem of extending the measures captured by a scalar function f, defined on the boundary surface P of a 3D shape, to its surrounding volume. This goal is achieved by computing a sequence of volumetric functions that approximate f up to a specified accuracy and preserve its critical points. More precisely, we compute a smooth map g : R³ → R such that the piecewise linear function h :=gP : P → R, which interpolates the values of g at the vertices of the triangulated surface P, is an approximation of f with the same critical points. In this way, we overcome the limitation of traditional approaches to function approximation, which are mainly based on a numerical error estimation and do not provide measurements of the topological and geometric features of f. The proposed approximation scheme builds on the properties of f related to its global structure, that is, its critical points, and ignores the local details of f, which can be successively introduced according to the target approximation accuracy.

1. Aronszajn, N. 1950. Theory of reproducing kernels. Trans. Amer. Math. Soc. 68, 337–404.
2. Bajaj, C. L. and Schikore, D. R. 1998. Topology preserving data simplification with error bounds. Comput. Graph. 22, 1, 3–12.
3. Banchoff, T. 1967. Critical points and curvature for embedded polyhedra. J. Differential Geom. 1, 245–256.
4. Belkin, M. and Niyogi, P. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 6, 1373–1396. 
5. Biasotti, S., Falcidieno, B., De Floriani, L., Frosini, P., Giorgi, D., Landi, C., Papaleo, L., and Spagnuolo, M. Describing shapes by geometric-topological properties of real functions. ACM Comput. Surv. 40, 4. 
6. Biasotti, S., Patanè, G., Spagnuolo, M., and Falcidieno, B. 2007. Analysis and comparison of real functions on triangulated surfaces. Modern Meth. Math., 41–50.
7. Bloomenthal, J. and Wyvill, B., eds. 1997. Introduction to Implicit Surfaces. Morgan Kaufmann Publishers. 
8. Bremer, P.-T., Edelsbrunner, H., Hamann, B., and Pascucci, V. 2004. A topological hierarchy for functions on triangulated surfaces. IEEE Trans. Visualiz. Comput. Graph. 10, 4, 385–396. 
9. Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proceedings of the ACM SIGGRAPH Conference. 67–76. 
10. Chen, S. and Wigger, J. 1995. Fast orthogonal least squares algorithm for efficient subset model selection. IEEE Trans. Signal Process. 43, 7, 1713–1715. 
11. Cipriano, G. and Gleicher, M. 2007. Molecular surface abstraction. IEEE Trans. Visualiz. Comput. Graph. 13, 6, 1608–1615. 
12. Co, C. S., Heckel, B., Hagen, H., Hamann, B., and Joy, K. 2003. Hierarchical clustering for unstructured volumetric scalar fields. In Proceedings of the IEEE Visualization Conference. 43. 
13. Cortes, C. and Vapnik, V. 1995. Support-Vector networks. Mach. Learn. 20, 3, 273–297. 
14. Dey, T. K. and Sun, J. 2005. An adaptive MLS surface for reconstruction with guarantees. In Proceedings of the ACM Symposium on Geometry Processing. 43–52. 
15. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. In Proceedings of the ACM SIGGRAPH Conference. 1057–1066. 
16. Dyn, N., Levin, D., and Rippa, S. 1986. Numerical procedures for surface fitting of scattered data by radial functions. SIAM J. Sci. Statist. Comput. 7, 2, 639–659.
17. Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2004. Local and global comparison of continuous functions. In Proceedings of the IEEE Visualization Conference. 275–280. 
18. Edelsbrunner, H., Morozov, D., and Pascucci, V. 2006. Persistence-Sensitive simplification functions on 2-manifolds. In Proceedings of the Symposium on Computational Geometry. ACM, 127–134. 
19. Fujishiro, I., Takeshima, Y., Azuma, T., and Takahashi, S. 2000. Volume data mining using 3D field topology analysis. IEEE Comput. Graph. Appl. 20, 5, 46–51. 
20. Gerstner, T. and Pajarola, R. 2000. Topology preserving and controlled topology simplifying multiresolution isosurface extraction. In Proceedings of the IEEE Visualization Conference. 259–266. 
21. Girosi, F. 1998. An equivalence between sparse approximation and support vector machines. Neural Comput. 10, 6, 1455–1480. 
22. Gyulassy, A., Natarajan, V., Pascucci, V., and Hamann, B. 2007. Efficient computation of Morse-Smale complexes for three-dimensional scalar functions. IEEE Trans. Visualiz. Comput. Graph. 13, 6, 1440–1447. 
23. Hansen, P. C. and O’Leary, D. P. 1993. The use of the l-curve in the regularization of discrete ill-posed problems. SIAM J. Sci. Comput. 14, 6, 1487–1503. 
24. Hart, J. C. 1998. Morse theory for implicit surface modeling. In Mathematical Visualization. Springer-Verlag, 257–268.
25. Hong, W., Neopytou, N., and Kaufman, A. 2006. Constructing 3D elliptical gaussian for irregular data. In Conference on Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Visualization.
26. Jang, Y., Weiler, M., Hopf, M., Huang, J., Ebert, D. S., Gaither, K. P., and Ertl, T. 2004. Interactively visualizing procedurally encoded scalar fields. In Proceedings of the VisSym Conference. 35–44, 339. 
27. Jang, Y., Botchen, R. P., Lauser, A., Ebert, D. S., Gaither, K. P., and Ertl, T. 2006. Enhancing the interactive visualization of procedurally encoded multifield data with ellipsoidal basis functions. Comput. Graph. Forum 25, 3, 587–596.
28. Jolliffe, I. T. 1986. Principal component analysis. In Principal Component Analysis. Springer Verlag.
29. Kanai, T., Ohtake, Y., and Kase, K. 2006. Hierarchical error-driven approximation of impplicit surfaces from polygonal meshes. In Proceedings of the Symposium on Geometry Processing. 21–30. 
30. Li, X., Guo, X., Wang, H., He, Y., Gu, X., and Qin, H. 2007. Harmonic volumetric mapping for solid modeling applications. In Proceedings of the Symposium on Solid and Physical Modeling. 109–120. 
31. Liu, Y.-S., Liu, M., Kihara, D., and Ramani, K. 2007. Salient critical points for meshes. In Proceedings of the Symposium on Solid and Physical Modeling. 277–282. 
32. Lloyd, S. 1982. An algorithm for vector quantizer design. IEEE Trans. Comm. 28, 7, 84–95.
33. Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM Trans. Graph. 21, 4, 163–169. 
34. Madsen, K., Nielsen, H. B., and Tingleff, O. 2004. Methods for Non-Linear Least Squares Problems, 2nd Ed. IMM.
35. Martin, T., Cohen, E., and Kirby, M. 2008. Volumetric parameterization and trivariate B-spline fitting using harmonic functions. In Proceedings of the Symposium on Solid and Physical Modeling. 269–280. 
36. Micchelli, C. A. 1986. Interpolation of scattered data: Distance matrices and conditionally positive definite functions. Constructive Approx. 2, 11–22.
37. Milnor, J. 1963. Morse Theory, Vol. 51 of Annals of Mathematics Studies, Princeton University Press.
38. Mitra, N. J. and Nguyen, A. 2003. Estimating surface normals in noisy point cloud data. In Proceedings of the Symposium on Computational Geometry. 322–328. 
39. Morse, B. S., Yoo, T. S., Chen, D. T., Rheingans, P., and Subramanian, K. R. 2001. Interpolating implicit surfaces from scattered surface data using compactly supported radial basis functions. In Proceedings of the Shape Modeling International. 89–98. 
40. Ni, X., Garland, M., and Hart, J. C. 2004. Fair Morse functions for extracting the topological structure of a surface mesh. In Proceedings of the ACM SIGGRAPH Conference. 613–622. 
41. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-Level partition of unity implicits. ACM Trans. Graph. 22, 3, 463–470. 
42. Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2005a. 3D scattered data interpolation and approximation with multilevel compactly supported RBFs. Graph. Models 67, 3, 150–165. 
43. Ohtake, Y., Belyaev, A. G., and Alexa, M. 2005b. Sparse low-degree implicits with applications to high quality rendering, feature extraction, and smoothing. In Proceedings of the Symposium on Geometry Processing. 149–158. 
44. Pascucci, V., Cole-McLaughlin, K., and Scorzelli, G. 2004. Multi-Resolution computation and presentation of contour trees. In Proceedings of the IASTED Conference on Visualization, Imaging, and Image Processing. 452–290.
45. Patanè, G. and Falcidieno, B. 2009. Computing smooth approximations of scalar functions with constraints. Comput. Graph. 33, 3, 399–413. 
46. Patanè, G. 2006. SIMS: A multi-level approach to surface reconstruction with sparse implicits. In Proceedings of the Shape Modeling and Applications Conference. 222–233. 
47. Poggio, T. and Girosi, F. 1990. Networks for approximation and learning. Proc. IEEE 78, 9, 1481–1497.
48. Schoelkopf, B. and Smola, A. J. 2002. Learning with Kernels. The MIT Press.
49. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Trans. Graph. 23, 3, 896–904. 
50. Stander, B. T. and Hart, J. C. 1997. Guaranteeing the topology of an implicit surface polygonization for interactive modeling. In Proceedings of the ACM SIGGRAPH Conference. 279–286. 
51. Steinke, F., Schölkopf, B., and Blanz, V. 2005. Support vector machines for 3D shape processing. Comput. Graph. Forum 24, 3, 285–294.
52. Taubin, G. 1995. A signal processing approach to fair surface design. In Proceedings of the ACM SIGGRAPH Conference. 351–358. 
53. Turk, G. and O’Brien, J. F. 2002. Modelling with implicit surfaces that interpolate. ACM Trans. Graph. 21, 4, 855–873. 
54. Wahba, G. 1990. Spline Models for Observational Data. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, SIAM, Philadelphia, PA.
55. Walder, C., Schölkopf, B., and Chapelle, O. 2006. Implicit surface modelling with a globally regularised basis of compact support. Comput. Graph. Forum 25, 3, 635–644.
56. Weber, G. H., Scheuermann, G., Hagen, H., and Hamann, B. 2002. Exploring scalar fields using critical isovalues. In Proceedings of the IEEE Visualization Conference. 171–178. 
57. Weber, G., Bremer, P.-T., and Pascucci, V. 2007. Topological landscapes: A terrain metaphor for scientific data. IEEE Trans. Visualiz. Comput. Graph. 13, 6, 1416–1423. 
58. Weiler, M., Botchen, R., Stegmaier, S., Ertl, T., Huang, J., Jang, Y., Ebert, D. S., and Gaither, K. P. 2005. Hardware-Assisted feature analysis and visualization of procedurally encoded multifield volumetric data. IEEE Comput. Graph. Appl. 25, 5, 72–81. 
59. Wendland, H. 1995. Real piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Adv. Comput. Math. 4, 4, 389–396.
60. Xie, H., McDonnell, K. T., and Qin, H. 2004. Surface reconstruction of noisy and defective data sets. In Proceedings of the IEEE Visualization Conference. 259–266.