A survey of methods for recovering quadrics in triangle meshes

ABSTRACT

In a variety of practical situations such as reverse engineering of boundary representation from depth maps of scanned objects, range data analysis, model-based recognition and algebraic surface design, there is a need to recover the shape of visible surfaces of a dense 3D point set. In particular, it is desirable to identify and fit simple surfaces of known type wherever these are in reasonable agreement with the data. We are interested in the class of quadric surfaces, that is, algebraic surfaces of degree 2, instances of which are the sphere, the cylinder and the cone. A comprehensive survey of the recent work in each subtask pertaining to the extraction of quadric surfaces from triangulations is presented.

REFERENCES

• 1: Nabih N. Abdelmalek, Algebraic error analysis for surface curvatures and segmentation of 3-d range images, Pattern Recognition, v.23 n.8, p.807-817, 1990 [doi>10.1016/0031-3203(90)90128-8]
• 2: Lyuba Alboul , Ruud van Damme, Polyhedral Metrics in Surface Reconstruction, Proceedings of the 6th IMA Conference on the Mathematics of Surfaces, p.171-200, September 01, 1994
• 3: L. Alonso , F. Cuny , S. Petit Jean , J.-C. Paul , S. Lazard , E. Wies, The virtual mesh: a geometric abstraction for efficiently computing radiosity, ACM Transactions on Graphics (TOG), v.20 n.3, p.169-201, July 2001 [doi>10.1145/501786.501789]
• 4: Elli Angelopoulou , Lawrence B. Wolff, Sign of Gaussian Curvature From Curve Orientation in Photometric Space, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.10, p.1056-1066, October 1998 [doi>10.1109/34.722615]
• 5: Farshid Arman , J. K. Aggarwal, Model-based object recognition in dense-range images—a review, ACM Computing Surveys (CSUR), v.25 n.1, p.5-43, March 1993 [doi>10.1145/151254.151255]
• 6: Chandrajit Bajaj , Insung Ihm , Joe Warren, Higher-order interpolation and least-squares approximation using implicit algebraic surfaces, ACM Transactions on Graphics (TOG), v.12 n.4, p.327-347, Oct. 1993 [doi>10.1145/159730.159734]
• 7: Banegas, F., Michelucci, D., Roelens, M., and Jaeger, M. 1999. Automatic extraction of significant features from 3D point clouds by ellipsoidal skeleton. In Proceedings of International Conference on Visual Computing (Goa, India). 58--67.
• 8: Belyaev, A. and Ohtake, Y. 2000. An image Processings approach to detection of ridges and ravines on polygonal surfaces. In Proceedings of Eurographics. Short presentation.
• 9: J. Berkmann , T. Caelli, Computation of Surface Geometry and Segmentation Using Covariance Techniques, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.11, p.1114-1116, November 1994 [doi>10.1109/34.334391]
• 10: Paul J. Besl , Ramesh C. Jain, Invariant surface characteristics for 3D object recognition in range images, Computer Vision, Graphics, and Image Processing, v.33 n.1, p.33-80, Jan. 1986 [doi>10.1016/0734-189X(86)90220-3]
• 11: P. J. Besl , R. C. Jain, Segmentation through Variable-Order Surface Fitting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.2, p.167-192, March 1988 [doi>10.1109/34.3881]
• 12: Björk, Å. 1996. Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics.
• 13: Blinn, J. 1997. The algebraic properties of second-order surfaces. In Introduction to Implicit Surfaces, J. Bloomenthal, Ed. Morgan-Kaufmann, 52--97.
• 14: Bock, M. and Guerra, C. 1999. A geometric approach to the segmentation of range images. In Proceedings of 2nd International Conference on 3-D Imaging and Modeling (Ottawa, Ont., Canada). 261--269.
• 15: Paul T. Boggs , Richard H. Byrd , Robert B. Schnabel, A stable and efficient algorithm for nonlinear orthogonal distance regression, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1052-1078, November 1, 1987 [doi>10.1137/0908085]
• 16: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 17: R M Bolle , D B Cooper, On optimally combining pieces of information, with application to estimating 3-Dcomplex-object position from range data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.5, p.619-638, Sept. 1986 [doi>10.1109/TPAMI.1986.4767836]
• 18: Bolles, R. and Fischler, M. 1981. A RANSAC-based approach to model fitting and its application to finding cylinders in range data. In Proceedings of the International Joint Conference on Artificial Intelligence. 637--643.
• 19: Bookstein, F. 1979. Fitting conic sections to scattered data. Comput. Vis. Graph. Image Proc. 9, 56--71.
• 20: Boulanger, P. and Rioux, M. 1987. Segmentation of planar and quadric surfaces. In SPIE Proceedings, Advances in Intelligent Robotics Systems, (Boston, Mass.). 848--861.
• 21: Bourdet, P., Lartigue, C., and Leveaux, F. 1993. Effects of data point distribution and mathematical model on finding the best-fit sphere to data. Prec. Eng. 15, 3, 150--157.
• 22: Brady, M., Ponce, J., Yuille, A., and Asada, H. 1985. Describing surfaces. Comput. Vis. Graph. Image Proc. 32, 1--28.
• 23: Ivan Bricault , Olivier Monga, From volume medical images to quadratic surface patches, Computer Vision and Image Understanding, v.67 n.1, p.24-38, July 1997 [doi>10.1006/cviu.1996.0501]
• 24: J. W. Bruce , P. J. Giblin , F. Tari, Ridges, crests and sub-parabolic lines of evolving surfaces, International Journal of Computer Vision, v.18 n.3, p.195-210, June 1996 [doi>10.1007/BF00123141]
• 25: Cai, L. 1989. A "small leakage" model for diffusion smoothing of image data. In Proceedings International Joint Conference on Artificial Intelligence. 1585--1590.
• 26: Cao, X. and Shrikhande, N. 1991. Quadric surface fitting for sparse range data. In Proceedings of the IEEE/SMC International Conference on Systems, Man and Cybernetics. 123--128.
• 27: Xingping Cao , Neelima Shrikhande , Gongzhu Hu, Approximate orthogonal distance regression method for fitting quadric surfaces to range data, Pattern Recognition Letters, v.15 n.8, p.781-796, Aug. 1994 [doi>10.1016/0167-8655(94)90006-X]
• 28: Chaine, R., Bouakaz, S., and Vandorpe, D. 1999. Extraction de descripteurs surfaciques pour la reconstruction 3D. Revue de CFAO et d'informatique graphique 14, 1, 93--107.
• 29: Xin Chen , Francis Schmitt, Intrinsic Surface Properties from Surface Triangulation, Proceedings of the Second European Conference on Computer Vision, p.739-743, May 19-22, 1992
• 30: Chivate, N., Goodall, C., and Jablokow, A. 1994. Comparative evaluation of surface fitting techniques for implicit surfaces. In Joint Statistical Meetings (Toronto, Ont., Canada).
• 31: Chivate, P. and Jablokow, A. 1993. Solid-model generation from measured point data. Comput. Aid. Des. 25, 9, 587--600.
• 32: Dai, M. and Newman, T. 1998. Hyperbolic and parabolic quadric surface fitting algorithms---Comparison between the least squares approach and the parameter optimization approach. Tech. Rep. TR-UAH-CS-1998-02, University of Alabama.
• 33: Dai, M. and Newman, T. 1999. Accurate reference surface recovery and defect detection for hyperboloid and paraboloid surfaces. In Proceedings 5th International Conference on Quality Control by Artificial Vision (Quebec, Canada). 165--170.
• 34: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 35: Desbrun, M., Meyer, M., Schröder, P., and Barr, A. 2000. Discrete differential-geometry operators in nD. Preprint, The Caltech Multi-Res Modeling Group.
• 36: do Carmo, M. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall, Englewood Cliffs, N.J.
• 37: David W. Eggert , Andrew W. Fitzgibbon , Robert B. Fisher, Simultaneous registration of multiple range views for use in reverse engineering of CAD models, Computer Vision and Image Understanding, v.69 n.3, p.253-272, March 1998 [doi>10.1006/cviu.1998.0667]
• 38: Fan, T., Medioni, G., and Nevatia, R. 1987. Segmented descriptions of 3D surfaces. IEEE J. Robot. Automat. 3, 6, 527--538.
• 39: T.-J. Fan , G. Medioni , R. Nevatia, Recognizing 3-D Objects Using Surface Descriptions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1140-1157, November 1989 [doi>10.1109/34.42853]
• 40: O D Faugeras , M Hebert, The representation, recognition, and locating of 3-d objects, International Journal of Robotics Research, v.5 n.3, p.27-52, Fall 1986 [doi>10.1177/027836498600500302]
• 41: Faugeras, O., Hebert, M., and Pauchon, E. 1983. Segmentation of range data into planar and quadric patches. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 8--13.
• 42: F. P. Ferrie , J. Lagarde , P. Whaite, Darboux Frames, Snakes, and Super-Quadrics: Geometry from the Bottom Up, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.8, p.771-784, August 1993 [doi>10.1109/34.236252]
• 43: Ferrie, F., Mathur, S., and Soucy, G. 1993b. Feature extraction for 3-D model building and object recognition. In Three-Dimensional Object Recognition Systems, P. Flynn and A. Jain, Eds. Elsevier Press, 57--88.
• 44: R. B. Fisher , A. W. Fitzgibbon , D. Eggert, Extracting surface patches from complete range descriptions, Proceedings of the International Conference on Recent Advances in 3-D Digital Imaging and Modeling, p.148, May 12-15, 1997
• 45: Fitzgibbon, A., Eggert, D., and Fisher, R. 1997. High-level CAD model acquisition from range images. Comput. Aid. Des. 29, 4, 321--330.
• 46: Fitzgibbon, A. and Fisher, R. 1993. Invariant fitting for arbitrary single-extremum surfaces. In Proceedings British Machine Vision Conference (Surrey, England). 569--578.
• 47: Andrew W. Fitzgibbon , Robert B. Fisher, A buyer's guide to conic fitting, Proceedings of the 6th British conference on Machine vision (Vol. 2), p.513-522, July 1995, Birmingham, United Kingdom
• 48: Andrew Fitzgibbon , Maurizio Pilu , Robert B. Fisher, Direct Least Square Fitting of Ellipses, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.476-480, May 1999 [doi>10.1109/34.765658]
• 49: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 50: Flynn, P. and Jain, A. 1988. Surface classification: hypothesis testing and parameter estimation. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition. 261--267.
• 51: Flynn, P. and Jain, A. 1989. On reliable curvature estimation. In Proc. IEEE Conference on Computer Vision and Pattern Recognition. 110--116.
• 52: Patrick J. Flynn , Anil K. Jain, CAD-Based Computer Vision: From CAD Models to Relational Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.2, p.114-132, February 1991 [doi>10.1109/34.67642]
• 53: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 54: Gopi, M., Krishnan, S., and Silva, C. 2000. Surface reconstruction based on lower dimensional localized Delaunay triangulation. Comput. Graph. Forum 19, 3, 467--478. Proc. of Eurographics.
• 55: Gouraud, H. 1971. Continuous shading of curved surfaces. IEEE Trans. Computers 20, 6, 623--629.
• 56: Grimson, W., Lozano-Perez, T., Noble, N., and White, S. 1993. An automatic tube inspection system that finds cylinders in range data. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition (New York, N.Y.), 446--452.
• 57: Hall, E., Tio, J., McPherson, C., and Sadjadi, F. 1982. Measuring curved surfaces for robot vision. IEEE Comput. 15, 12, 42--54.
• 58: B. Hamann, Curvature approximation for triangulated surfaces, Geometric modelling, Springer-Verlag, London, 1993
• 59: Han, J., Volz, R., and Mudge, T. 1987. Range image segmentation and surface parameter extraction for 3D object recognition of industrial parts. In Proceedings of International Conference on Robotics and Automation. 1582--1589.
• 60: Hebert, M. and Ponce, J. 1982. A new method for segmenting 3D scenes into primitives. In Proceedings International Conference on Pattern Recognition. 836--838.
• 61: Paul S. Heckbert , Michael Garland, Optimal triangulation and quadric-based surface simplification, Computational Geometry: Theory and Applications, v.14 n.1-3, p.49-65, Nov. 1999 [doi>10.1016/S0925-7721(99)00030-9]
• 62: Hilton, A., Illingworth, J., and Windeatt, T. 1995. Statistics of surface curvature estimates. Patt. Rec. 28, 8, 1201--1221.
• 63: R. Hoffman , A. K. Jain, Segmentation and classification of range images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.5, p.608-620, Sept. 1987 [doi>10.1109/TPAMI.1987.4767955]
• 64: Adam Hoover , Gillian Jean-Baptiste , Xiaoyi Jiang , Patrick J. Flynn , Horst Bunke , Dmitry B. Goldgof , Kevin Bowyer , David W. Eggert , Andrew Fitzgibbon , Robert B. Fisher, An Experimental Comparison of Range Image Segmentation Algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.7, p.673-689, July 1996 [doi>10.1109/34.506791]
• 65: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 66: Josef Hoschek , Ulrich Dietz , Wilhelm Wilke, A geometric concept of reverse engineering of shape: approximation and feature lines, Proceedings of the international conference on Mathematical methods for curves and surfaces II Lillehammer, 1997, p.253-262, June 1998, Lillehammer, Norway
• 67: Anil K. Jain , Richard Hoffman, Evidence-Based Recognition of 3-D Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.6, p.783-802, November 1988 [doi>10.1109/34.9102]
• 68: Xiaoyi Jiang , Horst Bunke, Edge detection in range images based on scan line approximation, Computer Vision and Image Understanding, v.73 n.2, p.183-199, Feb. 1999 [doi>10.1006/cviu.1998.0715]
• 69: Jones, G. and Illingworth, J. 1994. Robust segmentation of curved surfaces from range data. In Proc. of, 7th International Conference on Progress in Image Analysis. 453--456.
• 70: Karbacher, S. and Häusler, G. 1998. A new approach for modeling and smoothing of scattered 3D data. In Three-Dimensional Image Capture and Applications, R. Ellson and J. Nurre, Eds. SPIE Proceedings, vol. 3313. The International Society for Optical Engineering, 168--177.
• 71: Karras, G. 1992. On the orientation of digital elevation models in biostereometrics. In Surface Topography and Spinal Deformity, A. Alberti, B. Drerup, and E. Hierholzer, Eds. G. Fischer Verlag, Stuttgart, 162--165.
• 72: Kobbelt, L. 1997. Discrete fairing. In The Mathematics of Surfaces VII, T. Goodman, Ed. Oxford University Press, 101--131.
• 73: Jan J. Koenderink, Solid shape, MIT Press, Cambridge, MA, 1990
• 74: Géza Kós , Ralph R. Martin , Tamás Várady, Methods to recover constant radius rolling ball blends in reverse engineering, Computer Aided Geometric Design, v.17 n.2, p.127-160, Feb. 2000 [doi>10.1016/S0167-8396(99)00043-6]
• 75: Klaus Köster , Michael Spann, MIR: An Approach to Robust Clustering-Application to Range Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.5, p.430-444, May 2000 [doi>10.1109/34.857001]
• 76: Krsek, P., Lukács, G., and Martin, R. 1998. Algorithms for computing curvatures from range data. In The Mathematics of Surfaces VIII, R. Cripps, Ed. Information Geometers, 1--16.
• 77: Krsek, P., Pajdla, T., and Hlavac, V. 1997. Estimation of differential structures on triangulated surfaces. In Proc. of 21st Workshop of the Austrian Association for Pattern Recognition, R. Oldenbourg, Ed. 157--164.
• 78: Lagarde, J. 1997. Constraints and their satisfaction in the recovery of local surface structure. M.S. thesis, Department of Electrical Engineering, McGill University.
• 79: V. Lang , A. G. Belyaev , I. A. Bogaevsici , T. L. Kunii, Fast algorithms for ridge detection, Proceedings of the 1997 International Conference on Shape Modeling and Applications (SMA '97), p.189, March 03-06, 1997
• 80: Lee, C.-K., Haralick, R., and Deguchi, K. 1993. Estimation of curvature from sampled noisy data. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, New York. 536--541.
• 81: Kil-Moo Lee , Peter Meer , Rae-Hong Park, Robust Adaptive Segmentation of Range Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.2, p.200-205, February 1998 [doi>10.1109/34.659940]
• 82: André Lejeune , Frank P. Ferrie, Finding the parts of objects in range images, Computer Vision and Image Understanding, v.64 n.2, p.230-247, Sept. 1996 [doi>10.1006/cviu.1996.0056]
• 83: R. Lengagne , P. Fua , O. Monga, Using Crest Lines to Guide Surface Reconstruction from Stereo, Proceedings of the 1996 International Conference on Pattern Recognition (ICPR '96) Volume I, p.9, August 25-30, 1996
• 84: Aleš Leonardis , Alok Gupta , Ruzena Bajcsy, Segmentation of range images as the search for geometric parametric models, International Journal of Computer Vision, v.14 n.3, p.253-277, April 1995 [doi>10.1007/BF01679685]
• 85: Ping Liang , John S. Todhunter, Representation and recognition of surface shapes in range images: a differential geometry approach, Computer Vision, Graphics, and Image Processing, v.52 n.1, p.78-109, Oct. 1990 [doi>10.1016/0734-189X(90)90124-E]
• 86: Lin, C. and Perry, M. 1982. Shape description using surface triangulation. In Proc. of IEEE Workshop on Comput. Vis. Represent. Control, Rindge, NH. 38--43.
• 87: Antonio M. López , Felipe Lumbreras , Joan Serrat , Juan J. Villanueva, Evaluation of Methods for Ridge and Valley Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.4, p.327-335, April 1999 [doi>10.1109/34.761263]
• 88: Gábor Lukács , László Andor, Computing natural division lines on free-form surfaces based on measured data, Proceedings of the international conference on Mathematical methods for curves and surfaces II Lillehammer, 1997, p.319-326, June 1998, Lillehammer, Norway
• 89: Gabor Lukács , Ralph Martin , Dave Marshall, Faithful Least-Squares Fitting of Spheres, Cylinders, Cones and Tori for Reliable Segmentation, Proceedings of the 5th European Conference on Computer Vision-Volume I, p.671-686, June 02-06, 1998
• 90: Alan P. Mangan , Ross T. Whitaker, Partitioning 3D Surface Meshes Using Watershed Segmentation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.308-321, October 1999 [doi>10.1109/2945.817348]
• 91: Martin, R. 1998. Estimation of principal curvatures from range data. Int. J. Shape Model. 4, 3,4, 99--109.
• 92: Shailendra Mathur , F. P. Ferrie, Edge Localization in Surface Reconstruction Using Optimal Estimation Theory, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.833, June 17-19, 1997
• 93: Nelson Max, Weights for computing vertex normals from facet normals, Journal of Graphics Tools, v.4 n.2, p.1-6, March 1999
• 94: McIvor, A. 1998. A cubic facet based method for estimating the principal quadric. In Proc. of Image and Vision Computing New Zealand, Auckland. 136--141.
• 95: Alan M. McIvor , Robert J. Valkenburg, A comparison of local surface geometry estimation methods, Machine Vision and Applications, v.10 n.1, p.17-26, 1997 [doi>10.1007/s001380050055]
• 96: Alan McIvor , Peter T. Waltenberg, Recognition of Simple Curved Surfaces from 3D Surface Data, Proceedings of the Third Asian Conference on Computer Vision-Volume I, p.434-441, January 08-10, 1998
• 97: Medioni, G. and Parvin, B. 1986. Segmentation of range images into planar surfaces by split and merge. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition. 415--417.
• 98: D. S. Meek , D. J. Walton, On surface normal and Gaussian curvature approximations given data sampled from a smooth surface, Computer Aided Geometric Design, v.17 n.6, p.521-543, July 2000 [doi>10.1016/S0167-8396(00)00006-6]
• 99: Mencl, E. and Müller, H. 1998. Interpolation and approximation of surfaces from three-dimensional scattered data points. In State of the Art Reports, Eurographics'98. 51--67.
• 100: James V. Miller , Charles V. Stewart, MUSE: Robust Surface Fitting using Unbiased Scale Estimates, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.300, June 18-20, 1996
• 101: Moore, D. and Warren, J. 1991. Approximation of dense scattered data using algebraic surfaces. In Proc. of IEEE Hawaiian International Conference on System Sciences. 681--690.
• 102: Muller, Y. and Mohr, R. 1984. Planes and quadrics detection using Hough transform. In Proc. of International Conference on Pattern Recognition, Montreal. Vol. 2. 1101--1103.
• 103: Timothy S. Newman , Patrick J. Flynn , Anil K. Jain, Model-based classification of quadric surfaces, CVGIP: Image Understanding, v.58 n.2, p.235-249, Sept. 1993 [doi>10.1006/ciun.1993.1040]
• 104: Nguyen, V.-D., Nzomigni, V., and Stewart, C. 1999. Fast and robust registration of 3D surfaces using low curvature patches. In Proc. of 2nd International Conference on 3-D Imaging and Modeling, (Ottawa, Ont., Canada). 201--208.
• 105: Nourse, B., Hakala, D., Hillyard, R., and Malraison, P. 1980. Natural quadrics in mechanical design. In Proc. of Autofact West (Anaheim, CA.), Vol. 1. 363--378.
• 106: Yutaka Ohtake , Alexander G. Belyaev , Ilia A. Bogaevski, Polyhedral Surface Smoothing with Simultaneous Mesh Regularization, Proceedings of the Geometric Modeling and Processing 2000, p.229, April 10-12, 2000
• 107: Ohtake, Y., Belyaev, A., and Bogaevski, I. 2001. Mesh regularization and adaptive smoothing. Comput. Aid. Design 33, 789--800.
• 108: Oshima, M. and Shirai, Y. 1983. Object recognition using three dimensional information. IEEE Trans. Patt. Anal. Mach. Int. 5, 4, 353--361.
• 109: Xavier Pennec , Nicholas Ayache , Jean-Philippe Thirion, Landmark-based registration using features identified through differential geometry, Handbook of medical imaging, Academic Press, Inc., Orlando, FL, 2000
• 110: Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 1, 15--36.
• 111: Ponce, J. and Brady, J. 1987. Toward a surface primal sketch. In Three-Dimensional Machine Vision, T. Kanade, Ed. Kluwer Publishers, 195--240.
• 112: Mark W. Powell , Kevin W. Bowyer , Xiaoyi Jiang , Horst Bunke, Comparing Curved-Surface Range Image Segmenters, Proceedings of the Sixth International Conference on Computer Vision, p.286, January 04-07, 1998
• 113: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.145-152, August 1987
• 114: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 115: Requicha, A. and Voelcker, H. 1982. Solid modeling: a historical summary and contemporary assessment. IEEE Comput. Graph. Appl. 2, 1, 9--24.
• 116: Robertson, C., Fisher, R., Werghi, N., and Ashbrook, A. 1999. An improved algorithm to extract surfaces from complete range descriptions. In Proc. of WMC'99 (World Manufacturing Conference). 592--598.
• 117: Paul L. Rosin, Analysing error of fit functions for ellipses, Pattern Recognition Letters, v.17 n.14, p.1461-1470, Dec. 30, 1996 [doi>10.1016/S0167-8655(96)00102-X]
• 118: Rössl, C., Kobbelt, L., and Seidel, H.-P. 2000. Extraction of feature lines on triangulated surfaces using morphological operators. In Proc. of Smart Graphics'00, AAAI Spring Symposium, Stanford University. 71--75.
• 119: Sacchi, R., Poliakoff, J., Thomas, P., and Häfele, K.-H. 1999. Curvature estimation for segmentation of triangulated surfaces. In Proc. of 2nd International Conference on 3-D Imaging and Modeling (Ottawa, Ont., Canada). 536--543.
• 120: Emanuel Sachs , Andrew Roberts , David Stoops, 3-Draw: A Tool for Designing 3D Shapes, IEEE Computer Graphics and Applications, v.11 n.6, p.18-26, November 1991 [doi>10.1109/38.103389]
• 121: Samson, P. and Mallet, J.-L. 1997. Curvature analysis of triangulated surfaces in structural geology. J. Math. Geol. 29, 3, 391--412.
• 122: P. T. Sander , S. W. Zucker, Inferring Surface Trace and Differential Structure from 3-D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.9, p.833-854, September 1990 [doi>10.1109/34.57680]
• 123: Peter T. Sander , Steven W. Zucker, Singularities of Principal Direction Fields from 3-D Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.3, p.309-317, March 1992 [doi>10.1109/34.120326]
• 124: Allen Reed Sanderson, Shape recovery of volume data with deformable b-spline models, 1996
• 125: Nickolas S. Sapidis , Paul J. Besl, Direct construction of polynomial surfaces from dense range images through region growing, ACM Transactions on Graphics (TOG), v.14 n.2, p.171-200, April 1995 [doi>10.1145/221659.221672]
• 126: G. Soucy , F. P. Ferrie, Surface recovery from range images using curvature and motion consistency, Computer Vision and Image Understanding, v.65 n.1, p.1-18, Jan. 1997 [doi>10.1006/cviu.1996.0485]
• 127: Ernest M. Stokely , Shang You Wu, Surface Parametrization and Curvature Measurement of Arbitrary 3-D Objects: Five Practical Methods, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.8, p.833-840, August 1992 [doi>10.1109/34.149594]
• 128: Chi-Keung Tang , Gérard Medioni, Inference of Integrated Surface, Curve, and Junction Descriptions From Sparse 3D Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.11, p.1206-1223, November 1998 [doi>10.1109/34.730555]
• 129: Tang, C.-K. and Medioni, G. 1999. Robust estimation of curvature information from noisy 3D data for shape description. In Proc. of International Conference on Computer Vision (Corfu, Greece). 426--433.
• 130: Gabriel Taubin, Estimation of Planar Curves, Surfaces, and Nonplanar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.11, p.1115-1138, November 1991 [doi>10.1109/34.103273]
• 131: Taubin, G. 1993. An improved algorithm for algebraic curve and surface fitting. In Proc. of International Conference on Computer Vision. 658--665.
• 132: G. Taubin, Curve and surface smoothing without shrinkage, Proceedings of the Fifth International Conference on Computer Vision, p.852, June 20-23, 1995
• 133: G. Taubin, Estimating the tensor of curvature of a surface from a polyhedral approximation, Proceedings of the Fifth International Conference on Computer Vision, p.902, June 20-23, 1995
• 134: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 135: Russell W. Taylor , Massimo Savini, Fast segmentation of range imagery into planar regions, Computer Vision, Graphics, and Image Processing, v.45 n.1, p.42-60, January 1989 [doi>10.1016/0734-189X(89)90069-8]
• 136: Jean-Philippe Thirion , Alexis Gourdon, Computing the differential characteristics of isointensity surface, Computer Vision and Image Understanding, v.61 n.2, p.190-202, March 1995 [doi>10.1006/cviu.1995.1015]
• 137: Thompson, W., de St. Germain, J., Stark, S., and Henderson, T. 1999. Feature-based reverse engineering of mechanical parts. IEEE Trans. Robotics Automat. 15, 1, 57--66.
• 138: Grit Thürmer , Charles A. Wüthrich, Computing vertex normals from polygonal facets, Journal of Graphics Tools, v.3 n.1, p.43-46, Mar 1998
• 139: Trucco, E. and Fisher, R. 1992. Computing surface-based representations from range images. In Proc. of IEEE International Symposium on Intelligent Control 275--280.
• 140: Emanuele Trucco , Robert B. Fisher, Experiments in Curvature-Based Segmentation of Range Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.2, p.177-182, February 1995 [doi>10.1109/34.368172]
• 141: Várady, T., Kós, G., and Benkõ, P. 1998. Reverse engineering regular objects: simple segmentation and surface fitting procedures. Int. J. Shape Model. 4, 3 & 4, 127--142.
• 142: Várady, T., Martin, R., and Cox, J. 1997. Reverse engineering of geometric models---An introduction. Comput. Aid. Des. 29, 4, 255--269.
• 143: Watanabe, K. and Belyaev, A. 2000. Detection of curvature extrema on polygonal surfaces. In Proc. of International Conference on Human and Computer 11--14.
• 144: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 145: Werghi, N., Fisher, R., Ashbrook, A., and Robertson, C. 1999. Object reconstruction by incorporating geometric constraints in reverse engineering. Comput. Aid. Des. 31, 6, 363--399.
• 146: Naoufel Werghi , Robert Fisher , Craig Robertson , Anthony Ashbrook, Modelling Objects having Quadric Surfaces Incorporating Geometric cCnstraints, Proceedings of the 5th European Conference on Computer Vision-Volume II, p.185-201, June 02-06, 1998
• 147: Werghi, N., Fisher, R., Robertson, C., and Ashbrook, A. 2000. Faithful recovering of quadric surfaces from 3D range data by global fitting. Int. J. Shape Modell. 6, 1, 65--78.
• 148: Yang, M. and Lee, E. 1999. Segmentation of measured point data using a parametric quadric surface approximation. Comput. Aid. Des. 31, 7, 449--458.
• 149: Naokazu Yokoya , Martin D. Levine, Range Image Segmentation Based on Differential Geometry: A Hybrid Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.6, p.643-649, June 1989 [doi>10.1109/34.24798]
• 150: Yoshimi, T. and Tomita, F. 1994. Robust estimation for range image segmentation and reconstruction. In Proc. of IAPR Workshop on Machine Vision Applications (Kawasaki, Japan). 506--509.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.0 GENERAL

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation

General Terms:
Algorithms, Performance

Keywords:
Data fitting, geometry enhancement, local geometry estimation, mesh fairing, shape recovery