Interpolatory point set surfaces—convexity and Hermite data

Abstract

Point set surfaces define a (typically) manifold surface from a set of scattered points. The definition involves weighted centroids and a gradient field. The data points are interpolated if singular weight functions are used to define the centroids. While this way of deriving an interpolatory scheme appears natural, we show that it has two deficiencies: Convexity of the input is not preserved and the extension to Hermite data is numerically unstable. We present a generalization of the standard scheme that we call Hermite point set surface. It allows interpolating, given normal constraints in a stable way. It also yields an intuitive parameter for shape control and preserves convexity in most situations. The analysis of derivatives also leads to a more natural way to define normals, in case they are not supplied with the point data. We conclude by comparing to similar surface definitions.

References

1. Adamson, A. and Alexa, M. 2004. Approximating bounded, non-orientable surfaces from points. In Proceedings of the Shape Modeling International Conference, F. Giannini and A. Pasko, Eds. IEEE Computer Society, 243--252.
2. Adamson, A. and Alexa, M. 2005. Point-Sampled cell complexes. ACM Trans. Comput. Graph. 25, 3, 671--680.
3. Alexa, M. and Adamson, A. 2004. On normals and projection operators for surfaces defined by point sets. In Proceedings of the Eurographics Symposium on Point-based Graphics, M. Alexa, et al., Eds. Eurographics, 149--156.
4. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Trans. Comput. Graph. and Visualization 9, 1, 3--15.
5. Amenta, N. and Kil, Y. 2004a. The domain of a point set surface. In Proceedings of the Eurographics/IEEE Symposium on Point-Based Graphics. Eurographics, 139--148.
6. Amenta, N. and Kil, Y. J. 2004b. Defining point set surfaces. ACM Trans. Graph. 23, 3, 264--270.
7. Boissonnat, J.-D. and Cazals, F. 2000. Smooth shape reconstruction via natural neighbor interpolation of distance functions. In Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00). ACM Press, New York, 223--232.
8. Bremer, P.-T. and Hart, J. C. 2005. A sampling theorem for mls surfaces. In Proceedings of the Symposium on Point-Based Graphics. Eurographics, 47--54.
9. Dey, T. K., Goswami, S., and Sun, J. 2005. Extremal surface based projections converge and reconstruct with isotopy. Tech. rep. OSU-CISRC-05-TR25, Stanford University. http://www.stanford.edu/~sunjian.
10. Dey, T. K. and Sun, J. 2005. An adaptive MLS surface for reconstruction with guarantees. In Proceedings of the ACM Symposium on Geometry Processing. Eurographics, 43--52.
11. Kobbelt, L. and Botsch, M. 2004. A survey of point-based techniques in computer graphics. Comput. Graph. 28, 6, 801--814.
12. Kolluri, R. 2005. Provably good moving least squares. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1008--1018.
13. Levin, D. 1998. The approximation power of moving least-squares. Math. Comput. 67, 224, 1517--1531.
14. Levin, D. 2003. Mesh-Independent surface interpolation. In Geometric Modeling for Data Visualization. Springer, 37--49.
15. Pauly, M., Kaiser, R., Kobbelt, L., and Gross, M. 2003. Shape modeling with point-sampled geometry. ACM Trans. Graph. 22, 3, 641--650.
16. 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.
17. Wald, I. and Seidel, H.-P. 2005. Interactive ray tracing of point based models. In Proceedings of the Symposium on Point-Based Graphics. Eurographics, 9--16.
18. Wendland, H. 1995. Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Adv. Comput. Math. 4, 4, 389--396.
19. Zwicker, M., Pauly, M., Knoll, O., and Gross, M. 2002. Pointshop 3d: An interactive system for point-based surface editing. ACM Trans. Graph. 21, 3, 322--329.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Approximation algorithms