skip to main content
10.5555/1281991.1281997acmotherconferencesArticle/Chapter ViewAbstractPublication PagessgpConference Proceedingsconference-collections
Article

Voronoi-based variational reconstruction of unoriented point sets

Published: 04 July 2007 Publication History

Abstract

We introduce an algorithm for reconstructing watertight surfaces from unoriented point sets. Using the Voronoi diagram of the input point set, we deduce a tensor field whose principal axes and eccentricities locally represent respectively the most likely direction of the normal to the surface, and the confidence in this direction estimation. An implicit function is then computed by solving a generalized eigenvalue problem such that its gradient is most aligned with the principal axes of the tensor field, providing a best-fitting isosurface reconstruction. Our approach possesses a number of distinguishing features. In particular, the implicit function optimization provides resilience to noise, adjustable fitting to the data, and controllable smoothness of the reconstructed surface. Finally, the use of simplicial meshes (possibly restricted to a thin crust around the input data) and (an)isotropic Laplace operators renders the numerical treatment simple and robust.

References

[1]
{AB99} Amenta N., Bern M. W.: Surface reconstruction by Voronoi filtering. GEOMETRY: Discrete & Computational Geometry 22 (1999).
[2]
{BC02} Boissonnat, Cazals: Smooth surface reconstruction via natural neighbour interpolation of distance functions. CGTA: Computational Geometry: Theory and Applications 22 (2002).
[3]
{BO05} Boissonnat J.-D., Oudot S.: Provably good sampling and meshing of surfaces. Graph. Models 67, 5 (2005), 405--451.
[4]
{Boi84} Boissonnat J.-D.: Geometric structures for three-dimensional shape representation. ACM Trans. on Graphics 3, 4 (1984), 266--286.
[5]
{CBC*01} 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 (2001), pp. 67--76.
[6]
{CG06} Cazals F., Giesen J.: Delaunay triangulation based surface reconstruction. In Effective Computational Geometry for Curves and Surfaces, Boissonnat J., Teillaud M., (Eds.). Springer-Verlag, Math. and Visualization, 2006, pp. 231--276.
[7]
{CGAL03} Computational Geometry Algorithms Library CGAL-3.2. http://www.cgal.org/, 2003.
[8]
{CP03} Cazals F., Pouget M.: Estimating differential quantities using polynomial fitting of osculating jets. In Symposium on Geometry Processing (2003), pp. 177--187.
[9]
{Dey06} Dey T. K.: Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge Monographs on Applied and Computational Mathematics, 2006.
[10]
{DGGZ03} Dey T. K., Giesen J., Goswami S., Zhao W.: Shape dimension and approximation from samples. Discrete & Computational Geometry 29, 3 (2003).
[11]
{DKT06} Desbrun M., Kanso E., Tong Y.: Discrete differential forms for computational modeling. In Discrete Differential Geometry. ACM SIGGRAPH Course Notes, 2006.
[12]
{DLS05} Dey T. K., Li G., Sun J.: Normal estimation for point clouds: A comparison study for a Voronoi based method. In Symposium on Point-Based Graphics (2005), pp. 39--46.
[13]
{DS05} Dey T. K., Sun J.: Normal and Feature Estimations from Noisy Point Clouds. Tech. Rep. OSU-CISRC-7/50-TR50, Ohio State University, 2005.
[14]
{GS} Gomes F. M., Sorensen D. C.: ARPACK++: A C++ implementation of ARPACK eigenvalue package.
[15]
{Gus02} Guskov I.: An anisotropic parameterization scheme. In Proc. of Int. Meshing Roundtable (2002), pp. 325--332.
[16]
{HDD*92} Hoppe H., DeRose T., Duchamp T., McDonald J., Stuetzle W.: Surface reconstruction from unorganized points. In Proc. of ACM SIGGRAPH (1992), pp. 71--78.
[17]
{HK06} Hornung A., Kobbelt L.: Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information. In Symposium on Geometry Processing (2006), pp. 41--50.
[18]
{HXMP05} Hu G., Xu J., Miao L., Peng Q.: Bilateral estimation of vertex normal for point-sampled models. In Int. Conf. on Comp. Science and Appl. (2005), vol. 3480, pp. 758--768.
[19]
{KBH06} Kazhdan M., Bolitho M., Hoppe H.: Poisson Surface Reconstruction. In Symposium on Geometry Processing (2006), pp. 61--70.
[20]
{KSO04} Kolluri R., Shewchuk J. R., O'Brien J. F.: Spectral surface reconstruction from noisy point clouds. In Symposium on Geometry Processing (2004), pp. 11--21.
[21]
{LP05} Lange C., Polthier K.: Anisotropic smoothing of point sets. Computer Aided Geometric Design 22, 7 (2005), 680--692.
[22]
{MM06} Mordohai P., Medioni G.: Tensor Voting: A Perceptual Organization Approach to Computer Vision and Machine Learning. Morgan & Claypool, 2006.
[23]
{MNG04} Mitra N. J., Nguyen A., Guibas L.: Estimating surface normals in noisy point cloud data. In Int. J. of Comp. Geometry and Applications (2004), vol. 14(4--5), pp. 261--276.
[24]
{OBA*03} Ohtake Y., Belyaev A., Alexa M., Turk G., Seidel H.-P.: Multi-level partition of unity implicits. In Proc. of ACM SIGGRAPH (2003), vol. 22(3), pp. 463--470
[25]
{OF05} OuYang D., Feng H.-Y.: On the normal vector estimation for point cloud data from smooth surfaces. Computer-Aided Geometric Design 37, 10 (2005), 1071--1079.
[26]
{PKKG03} Pauly M., Keiser R., Kobbelt L. P., Gross M.: Shape modeling with point-sampled geometry. In (SIGGRAPH) (2003), vol. 22(3) of ACM Trans. on Graphics, pp. 641--650.
[27]
{PSQ06} Paris S., Sillion F. X., Quan L.: A surface reconstruction method using global graph cut optimization. Int. J. Comput. Vision 66, 2 (2006), 141--161.
[28]
{PWY*06} Pottmann H., Wallner J., Yang Y.-L., Lai Y.-K., Hu S.-M.: Principal curvatures from the integral invariant viewpoint. Comput. Aided Geom. Design (2006). in print.
[29]
{RY06} Rineau L., Yvinec M.: A generic software design for Delaunay refinement meshing. Tech. Rep. 5983, INRIA, 2006.
[30]
{SM00} Shi J., Malik J.: Normalized cuts and image segmentation. In Transactions on Pattern Analysis and Machine Intelligence (2000), pp. 888--905.
[31]
{SW90} Smith W. H. F., Wessel P.: Gridding with continuous curvature splines in tension. Geophysics 55, 3 (1990), 293--305.
[32]
{TCR05} Toledo S., Chen D., Rotkin V.: TAUCS. Available at http://www.tau.ac.il/~stoledo/taucs, 2005.
[33]
{TLHD03} Tong Y., Lombeyda S., Hirani A. N., Desbrun M.: Discrete multiscale vector field decomposition. In ACM SIGGRAPH (2003), pp. 445--452.
[34]
{WCS05} Walder C., Chapelle O., Schölkopf B.: Implicit surface modelling as an eigenvalue problem. In Machine Learning ICML 2005 (2005), pp. 936--939.
[35]
{ZRS05} Zayer R., R Ossl C., Seidel H.-P.: Setting the boundary free: A composite approach to surface parameterization. In Symposium on Geometry Processing (2005), pp. 91--100.

Cited By

View all
  • (2024)Stochastic Normal Orientation for Point CloudsACM Transactions on Graphics10.1145/368794443:6(1-12)Online publication date: 19-Dec-2024
  • (2024)Consistent Point Orientation for Manifold Surfaces via Boundary IntegrationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657475(1-11)Online publication date: 13-Jul-2024
  • (2023)MSECNet: Accurate and Robust Normal Estimation for 3D Point Clouds by Multi-Scale Edge ConditioningProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3613762(2535-2543)Online publication date: 26-Oct-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing
July 2007
273 pages
ISBN:9783905673463

Sponsors

  • EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 04 July 2007

Check for updates

Qualifiers

  • Article

Conference

SGP '07
Sponsor:
  • EUROGRAPHICS
SGP '07: Geometry processing
July 4 - 6, 2007
Barcelona, Spain

Acceptance Rates

SGP '07 Paper Acceptance Rate 21 of 74 submissions, 28%;
Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Stochastic Normal Orientation for Point CloudsACM Transactions on Graphics10.1145/368794443:6(1-12)Online publication date: 19-Dec-2024
  • (2024)Consistent Point Orientation for Manifold Surfaces via Boundary IntegrationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657475(1-11)Online publication date: 13-Jul-2024
  • (2023)MSECNet: Accurate and Robust Normal Estimation for 3D Point Clouds by Multi-Scale Edge ConditioningProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3613762(2535-2543)Online publication date: 26-Oct-2023
  • (2022)Iterative poisson surface reconstruction (iPSR) for unoriented pointsACM Transactions on Graphics10.1145/3528223.353009641:4(1-13)Online publication date: 22-Jul-2022
  • (2019)Variational implicit point set surfacesACM Transactions on Graphics10.1145/3306346.332299438:4(1-13)Online publication date: 12-Jul-2019
  • (2018)Surface Reconstruction Based on the Modified Gauss FormulaACM Transactions on Graphics10.1145/323398438:1(1-18)Online publication date: 14-Dec-2018
  • (2018)Propagation-based marching cubes algorithm using open boundary loopThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-017-1417-234:10(1339-1355)Online publication date: 1-Oct-2018
  • (2017)3D Stereo-lithographic models placed in Virtual Reality to assist in pre-operative planningProceedings of the 10th EAI International Conference on Simulation Tools and Techniques10.1145/3173519.3173522(87-92)Online publication date: 11-Sep-2017
  • (2017)Sketch-based guided modeling of 3D buildings from oriented photosProceedings of the 21st ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/3023368.3023374(1-8)Online publication date: 25-Feb-2017
  • (2017)A Survey of Surface Reconstruction from Point CloudsComputer Graphics Forum10.1111/cgf.1280236:1(301-329)Online publication date: 1-Jan-2017
  • Show More Cited By

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media