“Algebraic point set surfaces” by Guennebaud and Gross

In this paper we present a new Point Set Surface (PSS) definition based on moving least squares (MLS) fitting of algebraic spheres. Our surface representation can be expressed by either a projection procedure or in implicit form. The central advantages of our approach compared to existing planar MLS include significantly improved stability of the projection under low sampling rates and in the presence of high curvature. The method can approximate or interpolate the input point set and naturally handles planar point clouds. In addition, our approach provides a reliable estimate of the mean curvature of the surface at no additional cost and allows for the robust handling of sharp features and boundaries. It processes a simple point set as input, but can also take significant advantage of surface normals to improve robustness, quality and performance. We also present an novel normal estimation procedure which exploits the properties of the spherical fit for both direction estimation and orientation propagation. Very efficient computational procedures enable us to compute the algebraic sphere fitting with up to 40 million points per second on latest generation GPUs.

1. Adams, B., and Dutré, P. 2003. Interactive boolean operations on surfel-bounded solids. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 22, 3, 651–656. Google ScholarDigital Library
2. Adamson, A., and Alexa, M. 2003. Approximating and intersecting surfaces from points. In Proceedings of the Eurographics Symposium on Geometry Processing 2003, 230–239. Google ScholarDigital Library
3. Adamson, A., and Alexa, M. 2004. Approximating bounded, non-orientable surfaces from points. In Proceedings of Shape Modeling International 2004, IEEE Computer Society. Google ScholarDigital Library
4. Adamson, A., and Alexa, M. 2006. Anisotropic point set surfaces. In Afrigraph ’06: Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, ACM Press, 7–13. Google ScholarDigital Library
5. Adamson, A., and Alexa, M. 2006. Point-sampled cell complexes. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 25, 3, 671–680. Google ScholarDigital Library
6. 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, 149–156. Google ScholarCross Ref
7. Alexa, M., and Adamson, A. 2006. Interpolatory point set surfaces – convexity and hermite data. Submitted paper.Google Scholar
8. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Transactions on Computer Graphics and Visualization 9, 1, 3–15. Google ScholarDigital Library
9. Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Transactions on Graphics (SIGGRAPH 2004 Proceedings) 23, 3, 264–270. Google ScholarDigital Library
10. Amenta, N., and Kil, Y. 2004. The domain of a point set surface. In Proceedings of the Eurographics Symposium on Point-Based Graphics 2004, 139–147. Google ScholarCross Ref
11. 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, ACM Press, 223–232. Google ScholarDigital Library
12. Dey, T. K., and Sun, J. 2005. An adaptive MLS surface for reconstruction with guarantees. In Proceedings of the Eurographics Symposium on Geometry Processing 2005, 43–52. Google ScholarDigital Library
13. Dey, T. K., Goswami, S., and Sun, J. 2005. Extremal surface based projections converge and reconstruct with isotopy. manuscript.Google Scholar
14. Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics (SIGGRAPH 2005 Proceedings) 24, 3, 544–552. Google ScholarDigital Library
15. Gander, W., Golub, G. H., and Strebel, R. 1994. Least-squares fitting of circles and ellipses. BIT Numerical Mathematics 34, 4, 558–578.Google ScholarDigital Library
16. Guennebaud, G., Barthe, L., and Paulin, M. 2005. Interpolatory refinement for real-time processing of point-based geometry. Computer Graphics Forum (Proceedings of Eurographics 2005) 24, 3, 657–666.Google Scholar
17. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. of ACM SIGGRAPH ’92, ACM Press, 71–78. Google ScholarDigital Library
18. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proceedings of the Eurographics Symposium on Geometry Processing 2006, 43–52. Google ScholarDigital Library
19. Kolluri, R. 2005. Provably good moving least squares. In ACM-SIAM Symposium on Discrete Algorithms, 1008–1018. Google ScholarDigital Library
20. Levin, D. 2003. Mesh-independent surface interpolation. Geometric Modeling for Scientific Visualization, 181–187.Google Scholar
21. Mitra, N. J., Nguyen, A., and Guibas, L. 2004. Estimating surface normals in noisy point cloud data. International Journal of Computational Geometry and Applications 14, 4–5, 261–276.Google ScholarCross Ref
22. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-level partition of unity implicits. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 22, 3, 463–470. Google ScholarDigital Library
23. Pauly, M., Keiser, R., Kobbelt, L. P., and Gross, M. 2003. Shape modeling with point-sampled geometry. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 22, 3. Google ScholarDigital Library
24. Pauly, M., Mitra, N. J., and Guibas, L. 2004. Uncertainty and variability in point cloud surface data. In Proceedings of the Eurographics Symposium on Point-Based Graphics, 77–84. Google ScholarCross Ref
25. Pratt, V. 1987. Direct least-squares fitting of algebraic surfaces. In Proc. of ACM SIGGRAPH ’87, ACM Press, 145–152. Google ScholarDigital Library
26. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Transactions on Graphics (SIGGRAPH 2004), 896–904. Google ScholarDigital Library
27. Wald, I., and Seidel, H.-P. 2005. Interactive ray tracing of point based models. In Proceedings of the Eurographics Symposium on Point Based Graphics 2005. Google ScholarCross Ref
28. Waschbüsch, M., Gross, M., Eberhard, F., Lamboray, E., and Würmlin, S. 2004. Progressive compression of point-sampled models. In Proceedings of the Eurographics Symposium on Point-Based Graphics 2004, 95–102. Google ScholarCross Ref
29. Wicke, M., Teschner, M., and Gross, M. 2004. CSG tree rendering of point-sampled objects. In Proceedings of Pacific Graphics 2004, 160–168. Google ScholarDigital Library