[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Numerical analysis of differential operators on raw point clouds

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

3D acquisition devices acquire object surfaces with growing accuracy by obtaining 3D point samples of the surface. This sampling depends on the geometry of the device and of the scanned object and is therefore very irregular. Many numerical schemes have been proposed for applying PDEs to regularly meshed 3D data. Nevertheless, for high precision applications it remains necessary to compute differential operators on raw point clouds prior to any meshing. Indeed differential operators such as the mean curvature or the principal curvatures provide crucial information for the orientation and meshing process itself. This paper reviews a half dozen local schemes which have been proposed to compute discrete curvature-like shape indicators on raw point clouds. All of them will be analyzed mathematically in a unified framework by computing their asymptotic form when the size of the neighborhood tends to zero. They are given in terms of the principal curvatures or of higher order intrinsic differential operators which, in return, characterize the discrete operators. All considered local schemes are of two kinds: either they perform a polynomial local regression, or they compute directly local moments. But the polynomial regression of order 1 is demonstrated to play a special role, because its iterations yield a scale space. This analysis is completed with numerical experiments comparing the accuracies of these schemes. We demonstrate that this accuracy is enhanced for all operators by applying previously the scale space.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. M-estimation: robust fitting of a model by minimization of an objective function of the residuals with an iterative reweighed least squares scheme.

  2. We could use \(z=f(x,y)=-\frac{1}{2}(k_1x^2+k_2y^2)+o(x^2+y^2) \) at the cost of changing the orientation and sign of \(k_1\), \(k_2\).

References

  1. Alexa, M., Adamson, A.: Interpolatory point set surfaces convexity and hermite data. ACM Trans. Graph. 28, 20:1–20:10 (2009)

    Article  Google Scholar 

  2. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., Silva, C.T.: Point set surfaces. In: Proceedings of the Conference on Vis ’01, pp. 21–28. IEEE Computer Society, Washington, DC (2001)

  3. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., Silva, C.T.: Computing and rendering point set surfaces. IEEE TVCG 9(1), 3–15 (2003)

    Google Scholar 

  4. Alliez, P., Cohen-Steiner, D., Tong, Y., Desbrun, M.: Voronoi-based variational reconstruction of unoriented point sets. In: Proceedings of the SGP ’07, pp. 39–48. Eurographics, Switzerland (2007)

  5. Amenta, N., Kil, Y.J.: Defining point-set surfaces. In: Proceedings of the SIGGRAPH ’04: ACM SIGGRAPH 2004 Papers, pp. 264–270. ACM Press, USA (2004)

  6. Belkin, M., Sun, J., Wang, Y.: Constructing laplace operator from point clouds in rd. In: Proceedings of the SODA ’09, pp. 1031–1040. SIAM, USA (2009)

  7. Berkmann, J., Caelli, T.: Computation of surface geometry and segmentation using covariance techniques. IEEE PAMI 16(11), 1114–1116 (1994)

    Article  Google Scholar 

  8. Buades, A., Coll, B., Morel, J.M.: Neighborhood filters and pdes. Numer. Math. 105(1), 1–34 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  9. Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C., Evans, T.R.: Reconstruction and representation of 3d objects with radial basis functions. In: SIGGRAPH 01, Proceedings of the 28th annual conference on Computer Graphics and Interactive Technics, pp. 67–76 (2001)

  10. Cazals, F., Pouget, M.: Estimating differential quantities using polynomial fitting of osculating jets. In: Proceedings of the SGP ’03, pp. 177–187. Eurographics, Switzerland (2003)

  11. Cazals, F., Pouget, M.: Topology driven algorithms for ridge extraction on meshes. Tech. Rep. INRIA (2005)

  12. Clarenz, U., Griebel, M., Rumpf, M., Schweitzer, M.A., Telea, A.: Feature sensitive multiscale editing on surfaces. Vis. Comput. 20, 329–343 (2004)

    Article  Google Scholar 

  13. Clarenz, U., Rumpf, M., Telea, A.: Robust feature detection and local classification for surfaces based on moment analysis. IEEE Trans. Vis. Comput. Graph. 10, 516–524 (2004)

    Article  Google Scholar 

  14. Cohen-Steiner, D., Morvan, J.M.: Restricted delaunay triangulations and normal cycle. In: Proceedings of the SCG ’03, pp. 312–321. ACM, USA (2003)

  15. Curless, B., Levoy, M.: A volumetric method for building complex models from range images. In: Proceedings of the SIGGRAPH ’96, pp. 303–312. ACM Press, USA (1996)

  16. Desbrun, M., Meyer, M., Schroder, P., Barr, A.H.: Implicit fairing of irregular meshes using diffusion and curvature flow. In: Proceedings of the SIGGRAPH ’99, pp. 317–324. ACM Press/Addison-Wesley Publishing Co., USA (1999)

  17. Digne, J., Morel, J.M., Mehdi-Souzani, C., Lartigue, C.: Scale space meshing of raw data point sets. Comput. Graph. Forum. 30(6):1630–1642 (2011)

    Google Scholar 

  18. Fleishman, S., Cohen-Or, D., Silva, C.T.: Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24(3), 544–552 (2005)

    Article  Google Scholar 

  19. Gelfand, N., Mitra, N.J., Guibas, L.J., Pottmann, H.: Robust global registration. In: Proceedings of the Third Eurographics Symposium on Geometry Processing. Eurographics Association, Switzerland (2005)

  20. Gross, M., Hubeli, A.: Eigenmeshes Technical Report. ETH Zurich, Switzerland (2000)

    Google Scholar 

  21. Guennebaud, G., Gross, M.: Algebraic point set surfaces. ACM Trans. Graph. 26(3), (2007)

  22. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., Stuetzle, W.: Surface reconstruction from unorganized points. In: Proceedings of the SIGGRAPH ’92, pp. 71–78. ACM Press, USA (1992)

  23. Hubeli, A., Gross, M.: Multiresolution feature extraction for unstructured meshes. In: Proceedings of the Conference on Visualization ’01, pp. 287–294. IEEE Computer Society, Washington, DC (2001)

  24. Hulin, D., Troyanov, M.: Mean curvature and asymptotic volume of small balls. Am. Math. Mon. 110(10), 947–950 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  25. Kalogerakis, E., Simari, P., Nowrouzezahrai, D., Singh, K.: Robust statistical estimation of curvature on discretized surfaces. In: Proceedings of the SGP ’07, pp. 13–22. Eurographics, Switzerland (2007)

  26. Karni, Z., Gotsman, C.: Spectral compression of mesh geometry. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’00), pp. 279–286. ACM Press/Addison-Wesley Publishing Co., USA (2000)

  27. Kazhdan, M.: Reconstruction of solid models from oriented point sets. In: Proceedings of the SGP ’05, p. 73. Eurographics Association, Switzerland (2005)

  28. Kazhdan, M., Bolitho, M., Hoppe, H.: Poisson surface reconstruction. In: Proceedings of the SGP ’06, pp. 61–70. Eurographics, Switzerland (2006)

  29. Kobbelt, L.P., Botsch, M., Schwanecke, U., Seidel, H.P.: Feature sensitive surface extraction from volume data. In: Proceedings of the SIGGRAPH ’01, pp. 57–66. ACM, USA (2001)

  30. Lancaster, P., Salkauskas, K.: Surfaces generated by moving least squares methods. Math. Comput. 37(155), 141–158 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  31. Levin, D.: The approximation power of moving least-squares. Math. Comput. 67(224), 1517–1531 (1998)

    Article  MATH  Google Scholar 

  32. Levin, D.: Mesh-independent surface interpolation. In: Brunnett, G., Hamann, B., Müller, H., Linsen, L. (eds.) Geometric Modeling for Scientific Visualization, pp. 37–49. Springer, New York (2003)

  33. Liang, P., Todhunter, J.S.: Representation and recognition of surface shapes in range images: a differential geometry approach. Comput. Vision Graph. Image Process. 52(1), 78–109 (1990)

    Article  Google Scholar 

  34. Lipman, Y., Cohen-Or, D., Levin, D.: Data-dependent mls for faithful surface approximation. In: Proceedings of the SGP ’07, pp. 59–67. Eurographics, Switzerland (2007)

  35. Lorensen, W.E., Cline, H.E.: Marching cubes: a high resolution 3d surface construction algorithm. In: Proceedings of the SIGGRAPH ’87, pp. 163–169. ACM Press, USA (1987)

  36. Magid, E., Soldea, O., Rivlin, E.: A comparison of gaussian and mean curvature estimation methods on triangular meshes of range image data. CVIU 107(3), 139–159 (2007)

    Google Scholar 

  37. Mérigot, Q., Ovsjanikov, M., Guibas, L.J.: Robust Voronoi-based curvature and feature estimation. In: Proceedings of the SIAM/ACM Joint Conference on Geometric and Physical Modeling. San Francisco, USA (2009)

  38. Meyer, M., Desbrun, M., Schröder, P., Barr, A.: Discrete differential geometry operators for triangulated 2-manifolds. In: Proceedings of the International Workshop on Visualization and Mathematics (2002)

  39. Oztireli, A.C., Guennebaud, G., Gross, M.: Feature preserving point set surfaces based on non-linear kernel regression. CGF 28(9), 493–501 ((2009))

    Google Scholar 

  40. Pauly, M., Gross, M., Kobbelt, L.P.: Efficient simplification of point-sampled surfaces. In: Proceedings of the VIS ’02, pp. 163–170. IEEE, USA (2002)

  41. Pauly, M., Kobbelt, L.P., Gross, M.: Point-based multiscale surface representation. ACM Trans. Graph. 25(2), 177–193 (2006)

    Article  Google Scholar 

  42. Pottmann, H., Wallner, J., Huang, Q.X., Yang, Y.L.: Integral invariants for robust geometry processing. CAGD 26(1), 37–60 (2009)

    MATH  MathSciNet  Google Scholar 

  43. Pottmann, H., Wallner, J., Yang, Y.L., Lai, Y.K., Hu, S.M.: Principal curvatures from the integral invariant viewpoint. CAGD 24(8–9), 428–442 (2007)

    MATH  MathSciNet  Google Scholar 

  44. Rusinkiewicz, S.: Estimating curvatures and their derivatives on triangle meshes. In: Proceedings of the 3DPVT ’04, pp. 486–493. IEEE, USA (2004)

  45. Tang, X.: A sampling framework for accurate curvature estimation in discrete surfaces. IEEE TVCG 11(5), 573–583 (2005)

    Google Scholar 

  46. Taubin, G.: Estimating the tensor of curvature of a surface from a polyhedral approximation. In: Proceedings of the ICCV ’95, p. 902. IEEE, USA (1995)

  47. Taubin, G.: A signal processing approach to fair surface design. In: Proceedings of the SIGGRAPH ’95, pp. 351–358. ACM Press, USA (1995)

  48. Theisel, H., Rossl, C., Zayer, R., Seidel, H.P.: Normal based estimation of the curvature tensor for triangular meshes. In: Proceedings of the PG’ 04, pp. 288–297. IEEE, USA (2004)

  49. Tong, W.S., Tang, C.K.: Robust estimation of adaptive tensors of curvature by tensor voting. IEEE PAMI 27(3), 434–449 (2005)

    Article  Google Scholar 

  50. Unnikrishnan, R., Hebert, M.: Multi-scale interest regions from unorganized point clouds. In: Proceedings of the Workshop on Search in 3D (S3D), IEEE CVPR, New York (2008)

  51. Yang, P., Qian, X.: Direct computing of surface curvatures for point-set surfaces. In: Proceedings of the PBG 07 (2007)

  52. Yang, Y.L., Lai, Y.K., Hu, S.M., Pottmann, H.: Robust principal curvatures on multiple scales. In: Proceedings of the SGP ’06, pp. 223–226. Eurographics, Aire-la-Ville (2006)

Download references

Acknowledgments

The authors acknowledge support by the E.R.C. advanced grant “Twelve labours”.

Author information

Authors and Affiliations

  1. LIRIS-Geomod, Université de Lyon, CNRS UMR5205, 3 boulevard du 11 novembre 1918, 69622 , Villeurbanne, France

    Julie Digne

  2. CMLA, Ecole Normale Supérieure de Cachan, 61 Avenue du Président Wilson, 94230 , Cachan, France

    Jean-Michel Morel

Authors
  1. Julie Digne
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean-Michel Morel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Julie Digne.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Digne, J., Morel, JM. Numerical analysis of differential operators on raw point clouds. Numer. Math. 127, 255–289 (2014). https://doi.org/10.1007/s00211-013-0584-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-013-0584-y

Mathematics Subject Classification

Search

Navigation