Article

Algebraic point set surfaces

Authors:

Gaël Guennebaud,

Markus GrossAuthors Info & Claims

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

Pages 23 - es

https://doi.org/10.1145/1275808.1276406

Published: 29 July 2007 Publication History

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.

Supplementary Material

JPG File (pps023.jpg)

Download
12.49 KB

MP4 File (pps023.mp4)

Download
52.62 MB

References

[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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

[5]

Adamson, A., and Alexa, M. 2006. Point-sampled cell complexes. ACM Transactions on Graphics (SIGGRAPH 2003 Proceedings) 25, 3, 671--680.

Digital 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.

[7]

Alexa, M., and Adamson, A. 2006. Interpolatory point set surfaces - convexity and hermite data. Submitted paper.

[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.

Digital Library

[9]

Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Transactions on Graphics (SIGGRAPH 2004 Proceedings) 23, 3, 264--270.

Digital 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.

[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.

Digital 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.

Digital Library

[13]

Dey, T. K., Goswami, S., and Sun, J. 2005. Extremal surface based projections converge and reconstruct with isotopy. manuscript.

[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.

Digital 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.

Digital 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.

[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.

Digital 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.

Digital Library

[19]

Kolluri, R. 2005. Provably good moving least squares. In ACM-SIAM Symposium on Discrete Algorithms, 1008--1018.

Digital Library

[20]

Levin, D. 2003. Mesh-independent surface interpolation. Geometric Modeling for Scientific Visualization, 181--187.

[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.

[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.

Digital 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.

Digital 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.

[25]

Pratt, V. 1987. Direct least-squares fitting of algebraic surfaces. In Proc. of ACM SIGGRAPH '87, ACM Press, 145--152.

Digital 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.

Digital 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.

[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.

[29]

Wicke, M., Teschner, M., and Gross, M. 2004. CSG tree rendering of point-sampled objects. In Proceedings of Pacific Graphics 2004, 160--168.

Digital Library

Cited By

Bao YLi STang CSun ZYang KWang Y(2025)Research on Fitting and Denoising Subway Shield-Tunnel Cross-Section Point-Cloud Data Based on the Huber Loss FunctionApplied Sciences10.3390/app1504224915:4(2249)Online publication date: 19-Feb-2025
https://doi.org/10.3390/app15042249
Jin WZhou JWang MLi NWang WLiu X(2025)Enhanced normal estimation of point clouds via fine-grained geometric information learningMachine Vision and Applications10.1007/s00138-025-01671-236:2Online publication date: 22-Feb-2025
https://doi.org/10.1007/s00138-025-01671-2
Fang ZLiu YXu LShahed MShi L(2024)Research on a 3D Point Cloud Map Learning Algorithm Based on Point Normal ConstraintsSensors10.3390/s2419618524:19(6185)Online publication date: 24-Sep-2024
https://doi.org/10.3390/s24196185
Show More Cited By

Index Terms

Algebraic point set surfaces

Recommendations

Algebraic point set surfaces

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 ...
Multiresolution point-set surfaces
GI '08: Proceedings of Graphics Interface 2008

Multiresolution 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 ...
Piecewise Rational Manifold Surfaces with Sharp Features
Proceedings of the 13th IMA International Conference on Mathematics of Surfaces XIII

We 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

August 2007

1019 pages

ISBN:9781450378369

DOI:10.1145/1275808

Conference Chair:
Marc Levoy

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH07

Sponsor:

SIGGRAPH

SIGGRAPH07: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 5 - 9, 2007

California, San Diego

Acceptance Rates

SIGGRAPH '07 Paper Acceptance Rate 108 of 455 submissions, 24%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

118
Total Citations
View Citations
3,481
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)6

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bao YLi STang CSun ZYang KWang Y(2025)Research on Fitting and Denoising Subway Shield-Tunnel Cross-Section Point-Cloud Data Based on the Huber Loss FunctionApplied Sciences10.3390/app1504224915:4(2249)Online publication date: 19-Feb-2025
https://doi.org/10.3390/app15042249
Jin WZhou JWang MLi NWang WLiu X(2025)Enhanced normal estimation of point clouds via fine-grained geometric information learningMachine Vision and Applications10.1007/s00138-025-01671-236:2Online publication date: 22-Feb-2025
https://doi.org/10.1007/s00138-025-01671-2
Fang ZLiu YXu LShahed MShi L(2024)Research on a 3D Point Cloud Map Learning Algorithm Based on Point Normal ConstraintsSensors10.3390/s2419618524:19(6185)Online publication date: 24-Sep-2024
https://doi.org/10.3390/s24196185
He JZhang TKobayashi HKawamoto AZhou YNomura TZhu B(2024)Multi-level Partition of Unity on Differentiable Moving ParticlesACM Transactions on Graphics10.1145/368798943:6(1-21)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687989
Edirimuni DLu XLi GRobles-Kelly A(2024)Contrastive Learning for Joint Normal Estimation and Point Cloud FilteringIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.326386630:8(4527-4541)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3263866
Zhao TGao PTian TMa JTian J(2024)From Noise Addition to Denoising: A Self-Variation Capture Network for Point Cloud OptimizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.323168030:7(3413-3426)Online publication date: Jul-2024
https://doi.org/10.1109/TVCG.2022.3231680
Yousuf MHarb SAlkabbany IAli AElshazley SFarag A(2024)Colorectal Polyps Detection in Virtual Colonoscopy Using 3D Geometric Features and Deep Learning2024 IEEE International Symposium on Biomedical Imaging (ISBI)10.1109/ISBI56570.2024.10635785(1-4)Online publication date: 27-May-2024
https://doi.org/10.1109/ISBI56570.2024.10635785
Fu RWen CLi Q(2024)IMFIT: Normal Estimation via Learning Neural Implicit SurfaceICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10446949(2605-2609)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10446949
Ouasfi ABoukhayma A(2024)Unsupervised Occupancy Learning from Sparse Point Cloud2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02053(21729-21739)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02053
de Silva Edirimuni DLu XLi GWei LRobles-Kelly ALi H(2024)StraightPCF: Straight Point Cloud Filtering2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.01958(20721-20730)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.01958
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten