Gaël Guennebaud
Abstract
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.
Supplemental Material
- 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 Scholar
Digital Library
- 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
- 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
- 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
- Adamson, A., and Alexa, M. 2006. Point-sampled cell complexes. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 25, 3, 671--680. Google ScholarDigital Library
- 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
- Alexa, M., and Adamson, A. 2006. Interpolatory point set surfaces - convexity and hermite data. Submitted paper.Google Scholar
- 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
- Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Transactions on Graphics (SIGGRAPH 2004 Proceedings) 23, 3, 264--270. Google ScholarDigital Library
- 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
- 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
- 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
- Dey, T. K., Goswami, S., and Sun, J. 2005. Extremal surface based projections converge and reconstruct with isotopy. manuscript.Google Scholar
- 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
- 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
- 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
- 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
- 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
- Kolluri, R. 2005. Provably good moving least squares. In ACM-SIAM Symposium on Discrete Algorithms, 1008--1018. Google ScholarDigital Library
- Levin, D. 2003. Mesh-independent surface interpolation. Geometric Modeling for Scientific Visualization, 181--187.Google Scholar
- 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
- 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
- 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
- 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
- Pratt, V. 1987. Direct least-squares fitting of algebraic surfaces. In Proc. of ACM SIGGRAPH '87, ACM Press, 145--152. Google ScholarDigital Library
- 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
- 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
- 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
- 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
Index Terms
- Algebraic point set surfaces
Recommendations
Algebraic point set surfaces
SIGGRAPH '07: ACM SIGGRAPH 2007 papersIn 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 ...
Piecewise Rational Manifold Surfaces with Sharp Features
Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XIIIWe present a construction of a piecewise rational free-form surface of arbitrary topological genus which may contain sharp features: creases, corners or cusps. The surface is automatically generated from a given closed triangular mesh. Some of the edges ...
Multiresolution point-set surfaces
GI '08: Proceedings of Graphics Interface 2008Multiresolution representations of 3D surfaces make it possible to concentrate the efforts of a modification at the appropriate level of detail. This paper introduces a multiresolution representation for point-set surfaces. At each level, the point set ...
Comments