| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Implicit Simplicial Models for Adaptive Curve Reconstruction
March 1996 (vol. 18 no. 3)
pp. 321-325
Abstract—Parametric deformable models have been extensively and very successfully used for reconstructing free-form curves and surfaces, and for tracking nonrigid deformations, but they require previous knowledge of the topological type of the data, and good initial curve or surface estimates. With deformable models, it is also computationally expensive to check for and to prevent self-intersections while tracking deformations. The Implicit Simplicial Models that we introduce in this paper are implicit curves and surfaces defined by piece-wise linear functions. This representation allows for local deformations, control of the topological type, and prevention of self-intersections during deformations. As a first application, we also describe in this paper an algorithm for two-dimensional curve reconstruction from unorganized sets of data points. The topology, the number of connected components, and the geometry of the data are all estimated using an adaptive space subdivision approach. The main four components of the algorithm are topology estimation, curve fitting, adaptive space subdivision, and mesh relaxation.
[1] 321 G.E. Farin, Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide.New York: Academic Press, 1988.[2] M. Hall and J. Warren, "Adaptive polygonalization of implicitly defined surfaces," IEEE Computer Graphics and Applications, pp. 33-42, Nov. 1990.[3] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Surface Reconstruction from Unorganized Points,” Proc. SIGGRAPH '92, pp. 71-78, 1992.[4] M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: Active contour models," Int'l J. Computer Vision, vol. 1, no. 4, pp. 321-331, 1988.[5] D. Liu and J. Nocedal, "On the limited memory bfgs method for large scale optimization," Mathematical Programming, vol. B45, pp. 503-528, 1989.[6] D. Metaxas and D. Terzopoulos, “Dynamic Deformation of Solid Primitives with Constraints,” Proc. ACM SIGGRAPH, pp. 309-312, July 1992.[7] D. Moore and J. Warren, "Approximation of dense scattered data using algebraic surfaces," Technical Report Rice COMP TR90-135, Department of Computer Science, Rice University, Houston, Oct. 1990.[8] R. Szeliski and D. Tonnesen, "Surface Modelling with Oriented Particle Systems," Computer Graphics(Proc. Siggraph 92), vol. 26, no. 2, 1992, pp. 185-194.[9] G. Taubin, "Nonplanar curve and surface estimation in 3-space," Proc. IEEE Conf. Robotics and Automation, pp. 644-645, May 1988.[10] G. Taubin,“Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 11, pp. 1115-1137, Nov. 1991.[11] G. Taubin, "An improved algorithm for algebraic curve and surface fitting," Proc. Fourth Int'l Conf. Computer Vision, pp. 658-665,Berlin, Germany, May 1993.[12] G. Taubin, F. Cukierman, S. Sullivan, J. Ponce, and D.J. Kriegman, “Parameterized Families of Polynomials for Bounded Algebraic Curve and Surface Fitting,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 3, pp. 287-303, Mar. 1994.[13] D. Terzopoulos and K. Fleischer, "Deformable models," The Visual Computer, vol. 4, pp. 306-311, 1988.[14] G.L. Tindle, The Mathematics of Surfaces II, pp. 387-394.Oxford, England: Clarendon Press, 1987.
Index Terms:
Curve fitting, topology estimation, shape recovery, geometric modeling.
Citation:
Gabriel Taubin, Remi Ronfard, "Implicit Simplicial Models for Adaptive Curve Reconstruction," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 321-325, Mar. 1996, doi:10.1109/34.485559
