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: Approximating Bounded, Non-Orientable Surfaces from Points, Proceedings of the Shape Modeling International 2004, p.243-252, June 07-09, 2004 [doi>10.1109/SMI.2004.13]
• 2: Anders Adamson , Marc Alexa, Point-sampled cell complexes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 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: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January 2003 [doi>10.1109/TVCG.2003.1175093]
• 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: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 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: Tamal K. Dey , Jian Sun, An adaptive MLS surface for reconstruction with guarantees, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 11: Kobbelt, L. and Botsch, M. 2004. A survey of point-based techniques in computer graphics. Comput. Graph. 28, 6, 801--814.
• 12: Ravikrishna Kolluri, Provably good moving least squares, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: David Levin, The approximation power of moving least-squares, Mathematics of Computation, v.67 n.224, p.1517-1531, Oct. 1998 [doi>10.1090/S0025-5718-98-00974-0]
• 14: Levin, D. 2003. Mesh-Independent surface interpolation. In Geometric Modeling for Data Visualization. Springer, 37--49.
• 15: Mark Pauly , Richard Keiser , Leif P. Kobbelt , Markus Gross, Shape modeling with point-sampled geometry, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 16: Chen Shen , James F. O'Brien , Jonathan R. Shewchuk, Interpolating and approximating implicit surfaces from polygon soup, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 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: Matthias Zwicker , Mark Pauly , Oliver Knoll , Markus Gross, Pointshop 3D: an interactive system for point-based surface editing, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms

Keywords:
Hermite data, Point-based modeling, interpolation