Surface reconstruction from unorganized point data with quadrics. (English) Zbl 1151.68710
Summary: We present a reverse engineering method for constructing a surface approximation scheme whose input is a set of unorganized noisy points in space and whose output is a set of quadric patches. The local surface properties, necessary for the subsequent segmentation, are estimated directly from the data using a simple and efficient data structure-the neighborhood graph. Our segmentation scheme, based on principal curvatures, constructs initial point subsets, which may be enlarged or further subdivided based on associated approximation error estimates obtained through approximation of the initial segments by quadric surfaces. Our method is highly efficient and produces a high-quality piecewise quadric surface approximation of engineering objects, which we demonstrate for several simple and complex example data sets.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U07 | Computer science aspects of computer-aided design |
Keywords:
Surface reconstruction; reverse engineering; principal curvatures; segmentation; quadric surfacesReferences:
| [1] | Amenta, 6th ACM symposium on Solid Modeling and Applications pp 249– (2001) |
| [2] | Attene, Hierarchical mesh segmentation based on fitting primitives, The Visual Computer: International Journal of Computer Graphics 22 (3) pp 181– (2006) |
| [3] | Albano, Representation of digitized contours in terms of conic arcs and straight-line segments, Computer Graphics and Image Processing 3 pp 23– (1974) |
| [4] | Ahn, Orthogonal distance fitting of implicit curves and surfaces, IEEE Transaction on Pattern Analysis and Machine Intelligence 24 (5) pp 620– (2002) |
| [5] | Boissonnat, 16th Annual Symposium on Computational geometry pp 223– (2000) |
| [6] | Blane, The 3L algorithm for fitting implicit polynomial curves and surfaces to data, IEEE Transaction on Pattern Analysis and Machine Intelligence 22 (3) pp 298– (2000) |
| [7] | Bernardini, The ball-pivoting algorithm for surface reconstruction, IEEE Transactions on Visualization and Computer Graphics 5 (4) pp 349– (1999) |
| [8] | Benkö, Algorithms for reverse engineering boundary representation models, COMPUTER-AIDED DESIGN 33 (11) pp 839– (2001) |
| [9] | Belyaev, Ridges and ravines on implicit surfaces, Computer Graphics International 00 (1998) · doi:10.1109/CGI.1998.694306 |
| [10] | Benkö, Geometric Modeling and Processing - Theory and Applications pp 169– (2002) |
| [11] | Benkö, Segmentation methods for smooth point regions of conventional engineering objects, Computer-Aided Design 36 (6) pp 511– (2004) |
| [12] | Douros, Scanning (2002) |
| [13] | Dey, IEEE symposium on parallel and large-data visualization and graphics pp 19– (2001) |
| [14] | Dey, 3rd Eurographics Symposium on Geometry Processing pp 43– (2005) |
| [15] | Edelsbrunner, Three-dimensional alpha shapes, ACM Transactions on Graphics 13 (1) pp 43– (1994) · Zbl 0806.68107 |
| [16] | Goldfeather, A novel cubic-order algorithm for approximating principal direction vectors, ACM Transactions on Graphics 23 1 pp 45– (2004) |
| [17] | Gnanadesikan, Methods for statistical data analysis of multivariate observations (1977) · Zbl 0403.62034 |
| [18] | Hamann, Curvature approximation for triangulated surfaces, Geometric Modelling, Computing Suppl. 8 pp 139– (1993) · doi:10.1007/978-3-7091-6916-2_10 |
| [19] | Helzer, Stable fitting of 2d curves and 3d surfaces by implicit polynomials, IEEE Transaction on Pattern Analysis and Machine Intelligence 26 (10) pp 1283– (2004) |
| [20] | Hoppe, SIGGRAPH’92 pp 71– (1992) |
| [21] | Krsek, The Mathematics of Surface VIII pp 1– (1998) |
| [22] | Lavoué, Computer Graphics International pp 10– (2004) |
| [23] | Lavoué, Computer Aided Design 37 10 pp 975– (2005) |
| [24] | Lai, ACM symposium on Solid and physical modeling pp 17– (2006) |
| [25] | Marshall, Robust segmentation of primitives from range data in the presence of geometric degeneracy, IEEE Trans. Pattern Anal. Mach. Intell. 23 (3) pp 304– (2001) |
| [26] | Mencl, Interpolation and approximation of surfaces from three-dimensional scattered data points pp 223– (1997) |
| [27] | Ohtake, ACM SIGGRAPH pp 463– (2003) |
| [28] | Petitjean, A survey of methods for recovering quadrics in triangle meshes, ACM Comput. Surv. 34 2 pp 211– (2002) |
| [29] | Pratt, ACM SIGGRAPH: 14th annual conference on Computer graphics and interactive techniques pp 145– (1987) |
| [30] | Razdan, Curvature estimation scheme for triangle meshes using biquadratic Bézier patches, Computer-Aided Design 37 (14) pp 1481– (2005) · Zbl 1206.65107 |
| [31] | Rusinkiewicz, 3D Data Processing, Visualization and Transmission pp 486– (2004) |
| [32] | Taubin, Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation, IEEE Transaction on Pattern Analysis and Machine Intelligence 13 (11) pp 1115– (1991) |
| [33] | Taubin, IEEE International Conference on Computer Vision pp 658– (1993) |
| [34] | Tong, Robust estimation of adaptive tensors of curvature by tensor voting, IEEE Transaction on Pattern Analysis and Machine Intelligence 27 (3) pp 434– (2005) |
| [35] | Vančo, Direct segmentation of algebraic models for reverse engineering, Computing 72 (1-2) pp 207– (2004) |
| [36] | Vančo, Geometric preprocessing of noisy point sets: an experimental study, Computing 79, Special issue on Geometric Modeling (2007) |
| [37] | Vančo, International Conference on Computer Graphics pp 120– (1999) |
| [38] | Várady, Automatic extraction of surface structures in digital shape reconstruction, Computer-Aided Design 39 (5) pp 379– (2007) |
| [39] | Várady, Reverse Engineering pp 651– (2002) |
| [40] | Várady, Reverse engineering of geometric models-an introduction, Computer Aided Design 29 (4) pp 255– (1997) |
| [41] | Vieira, Surface mesh segmentation and smooth surface extraction through region growing, Computer Aided Geometric Design 22 (8) pp 771– (2005) · Zbl 1119.65316 |
| [42] | Werghi, 2nd International Conference on 3D Digital Imaging and Modeling pp 280– (1999) |
| [43] | Werghi, 5th European Conference on Computer Vision-Volume II pp 185– (1998) |
| [44] | Wu, Structure recovery via hybrid variational surface approximation, Computer Graphics Forum 24 (3) pp 277– (2005) |
| [45] | Yoshizawa, ACM Symposium on Solid and physical modeling pp 227– (2005) |
| [46] | Yamauchi, International Conference on Shape Modeling and Applications 2005 pp 238– (2005) |
| [47] | Yan, Geometric Modeling and Processing pp 73– (2006) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
