“Point morphology” by Calderon and Boubekeur

  • ©Stéphane Calderon and Tamy Boubekeur



Session Title:

    Points & Reconstruction


    Point morphology



    We introduce a complete morphological analysis framework for 3D point clouds. Starting from an unorganized point set sampling a surface, we propose morphological operators in the form of projections, allowing to sample erosions, dilations, closings and openings of an object without any explicit mesh structure. Our framework supports structuring elements with arbitrary shape, accounts robustly for geometric and morphological sharp features, remains efficient at large scales and comes together with a specific adaptive sampler. Based on this meshless framework, we propose applications which benefit from the non-linear nature of morphological analysis and can be expressed as simple sequences of our operators, including medial axis sampling, hysteresis shape filtering and geometry-preserving topological simplification.


    1. Adamson, A., and Alexa, M. 2004. Approximating bounded, non-orientable surfaces from points. In Proceedings of the Shape Modeling International 2004, IEEE Computer Society, Washington, DC, USA, SMI ’04, 243–252. Google ScholarDigital Library
    2. Adamson, A., and Alexa, M. 2006. Point-sampled cell complexes. ACM Trans. Graph. 25, 3, 671–680. Google ScholarDigital Library
    3. Alexa, M., and Adamson, A. 2009. Interpolatory point set surfaces—convexity and hermite data. ACM Trans. Graph. 28, 2 (May), 20:1–20:10. Google ScholarDigital Library
    4. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2001. Point set surfaces. In Proceedings of the conference on Visualization ’01, IEEE Computer Society, Washington, DC, USA, VIS ’01, 21–28. Google ScholarDigital Library
    5. Alexa, M., Rusinkiewicz, S., Alexa, M., and Adamson, A. 2004. On normals and projection operators for surfaces defined by point sets. In In Eurographics Symp. on Point-Based Graphics, 149–155. Google ScholarDigital Library
    6. Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. In ACM SIGGRAPH 2004 Papers, ACM, New York, NY, USA, SIGGRAPH ’04, 264–270. Google ScholarDigital Library
    7. Amenta, N., Choi, S., and Kolluri, K. 2001. The power crust. In 6th ACM Symposium on Solid Modeling, 249–260. Google ScholarDigital Library
    8. Babaud, J., Witkin, A. P., Baudin, M., and Duda, R. O. 1986. Uniqueness of the gaussian kernel for scale-space filtering. IEEE Trans. Pattern Anal. Mach. Intell. 8, 1 (Jan.), 26–33. Google ScholarDigital Library
    9. Barki, H., Denis, F., and Dupont, F. 2011. Contributing vertices-based minkowski sum of a nonconvex–convex pair of polyhedra. ACM Trans. Graph. 30 (Feb.), 3:1–3:16. Google ScholarDigital Library
    10. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, SIGGRAPH ASIA ’10, 166:1–166:10. Google ScholarDigital Library
    11. Campen, M., and Kobbelt, L. 2010. Polygonal boundary evaluation of minkowski sums and swept volumes. Computer Graphics Forum 29, 5, 1613–1622.Google ScholarCross Ref
    12. Chen, Y., Wang, H., W. Rosen, D., and Rossignac, J. 2005. A point-based offsetting method of polygonal meshes. Tech. rep.Google Scholar
    13. Cheng, Y. 1995. Mean shift, mode seeking, and clustering. IEEE Trans. Pattern Anal. Mach. Intell. 17, 8 (Aug.), 790–799. Google ScholarDigital Library
    14. Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24, 3, 544–552. Google ScholarDigital Library
    15. Fukunaga, K., and Hostetler, L. D. 1975. The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Transactions on Information Theory 21, 1, 32–40. Google ScholarDigital Library
    16. Garland, M., and Heckbert, P. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 209–216. Google ScholarDigital Library
    17. Guennebaud, G., and Gross, M. 2007. Algebraic point set surfaces. In ACM SIGGRAPH 2007 papers, ACM, New York, NY, USA, SIGGRAPH ’07. Google ScholarDigital Library
    18. Jacobson, A., Kavan, L., and Sorkine-Hornung, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4, 33:1–33:12. Google ScholarDigital Library
    19. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’06, 61–70. Google ScholarDigital Library
    20. Kobbelt, L. P., Botsch, M., Schwanecke, U., and Seidel, H.-P. 2001. Feature sensitive surface extraction from volume data. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’01, 57–66. Google ScholarDigital Library
    21. Kolluri, R. 2008. Provably good moving least squares. ACM Trans. Algorithms 4, 2 (May), 18:1–18:25. Google ScholarDigital Library
    22. Levin, D. 1998. The approximation power of moving least-squares. Mathematics of Computation 67, 1517–1531. Google ScholarDigital Library
    23. Levin, D. 2003. Mesh-independent surface interpolation. Geometric Modeling for Scientific Visualization 3, 37–49.Google Scholar
    24. Lien, J.-M. 2007. Point-based minkowski sum boundary. In Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, IEEE Computer Society, Washington, DC, USA, 261–270. Google ScholarDigital Library
    25. Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    26. Mellado, N., Barla, P., Guennebaud, G., Reuter, P., and Schlick, C. 2012. Growing least squares for the continuous analysis of manifolds in scale-space. Computer Graphics Forum (July). Google ScholarDigital Library
    27. Miklos, B., Giesen, J., and Pauly, M. 2010. Discrete scale axis representations for 3d geometry. In ACM SIGGRAPH 2010 Papers, ACM, New York, NY, USA, SIGGRAPH ’10, 101:1–101:10. Google ScholarDigital Library
    28. Molchanov, V., Rosenthal, P., and Linsen, L. 2010. Noniterative second-order approximation of signed distance functions for any isosurface representation. Computer Graphics Forum 29, 3, 1211–1220. Google ScholarDigital Library
    29. Najman, L., and Talbot, H., Eds. 2010. Mathematical Morphology: From Theory to Applications. Wiley.Google Scholar
    30. Nelaturi, S., and Shapiro, V. 2009. Configuration products in geometric modeling. In 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, ACM, New York, NY, USA, SPM ’09, 247–258. Google ScholarDigital Library
    31. Ohtake, Y., and Belyaev, A. G. 2002. Dual/primal mesh optimization for polygonized implicit surfaces. In Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications, ACM, New York, NY, USA, SMA ’02, 171–178. Google ScholarDigital Library
    32. Öztireli, C., Guennebaud, G., and Gross, M. 2009. Feature preserving point set surfaces based on non-linear kernel regression. Computer Graphics Forum 28, 2, 493–501.Google ScholarCross Ref
    33. Öztireli, A. C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, SIGGRAPH ASIA ’10, 168:1–168:8. Google ScholarDigital Library
    34. Pauly, M., Kobbelt, L. P., and Gross, M. 2006. Point-based multiscale surface representation. ACM Trans. Graph. 25 (April), 177–193. Google ScholarDigital Library
    35. Peternell, M., and Steiner, T. 2007. Minkowski sum boundary surfaces of 3d-objects. Graph. Models 69, 3–4 (May), 180–190. Google ScholarDigital Library
    36. Reuter, P., Joyot, P., Trunzler, J., Boubekeur, T., and Schlick, C. 2005. Surface reconstruction with enriched reproducing kernel particle approximation. In IEEE/Eurographics Symposium on Point-Based Graphics, Eurographics/IEEE Computer Society, 79–87. Google ScholarDigital Library
    37. Serra, J. 1983. Image Analysis and Mathematical Morphology. Academic Press, Inc., Orlando, FL, USA. Google ScholarDigital Library

ACM Digital Library Publication: