Abstract
In this paper, both general and exponential bounds of the distance between a uniform Catmull-Clark surface and its control polyhedron are derived. The exponential bound is independent of the process of subdivision and can be evaluated without recursive subdivision. Based on the exponential bound, we can predict the depth of subdivision within a user-specified error tolerance. This is quite useful and important for pre-computing the subdivision depth of subdivision surfaces in many engineering applications such as surface/surface intersection, mesh generation, numerical control machining and surface rendering.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes.Computer-Aided Design, 1978, 10: 350–355.
Stam J. Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values.Computer Graphics (Proc. SIGGRAPH'98), 1998, 32: 395–404.
Cheng F. Estimating subdivision depths for rational curves and surfaces.ACM Trans. Graphics, 1992, 11(2): 140–151.
Cohen E, Schumaker L L. Rates of convergence of control polygons.Computer Aided Geometric Design, 1985, 2: 229–235.
Lutterkort D, Peters J. The distance between a uniform B-spline and its control polygon. Technical Report TR-98-013, available from http://www.cise.uft.edu/research/tech-reports.
Nairn D, Peters J, Lutterkort D. Sharp, quantitative bounds on the distance between a polynomial piece and its Bezier control polygon.Computer Aided Geometric Design, 1990, 16: 613–631.
Prautzsch H, Kobbelt L. Convergence of subdivision and degree elevation.Adv. Comp. Math., 1994, 2: 143–154.
Reif U. Best bounds on the approximation of polynomials and splines by their control structure.Computer Aided Geometric Design, 2000, 17: 579–589.
Wang H, Guan Y, Qin K. Error estimate for Doo-Sabin surfaces.Progress in Natural Science, 2002, 12(9): 695–700.
Kobbelt L, Daubert K, Seidel H. Ray tracing of subdivision surfaces.Eurographics Rendering Workshop, 1998, Vienna, Austria, pp. 69–80.
Ball A A, Storry D J T. A matrix approach to the analysis of recursively generated B-spline surfaces.Computer-Aided Design, 1986, 18: 437–442.
Qin K, Wang H. Continuity of non-uniform recursive subdivision surfaces.Science in China (Series E), 2000, 43(5): 461–472.
Woodward C D. Cross-sectional design of B-spline surfaces.Computers and Graphics, 1987, 11(2): 193–201.
Halstead M, Kass M, DeRose T. Efficient, fair interpolation using Catmull-Clark surfaces.Computer Graphics (Proc. SIGGRAPH'93), 1993, 27: 35–44.
Hausdorff F. Set Theory, Chelsea (Translated from German), 1978.
Sederberg T W, Zheng J, Sewell D, Sabin M. Nonuniform recursive subdivision surfaces.Computer Graphics (Proc. SIGGRAPH'98), 1998, 32: 387–394.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China (Grant No.60273013), the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No.20010003048) and the 985 Fundamental Research Fund of Tsinghua University (Grant No.JC2002023).
Hua-Wei Wang is currently a Ph.D. candidate in Department of Computer Science and Technology at Tsinghua University, Beijing, P.R. China. He received his B.S. and B.E. degrees from Department of Applied Mathematics and Department of Computer Science and Technology, respectively, Tsinghua University in 1998. His research interests include computer graphics, computer aided geometric design, curves and surfaces, etc.
Kai-Huai Qin is a professor of computer science and technology, Tsinghua University. He was a postdoctoral fellow from 1990 to 1992, then joined the Department of Computer Science and Technology of Tsinghua University as an associate professor. He received his Ph.D. and M.Eng. from Huazhong University of Science and Technology in 1990 and 1984, and his B.Eng. from South China University of Technology in 1982. His research interests include computer graphics, computer aided geometric design, wavelets, virtual reality and intelligent and smart CAD/CAM.
Rights and permissions
About this article
Cite this article
Wang, HW., Qin, KH. Estimating subdivision depth of Catmull-Clark surfaces. J. Comput. Sci. & Technol. 19, 657–664 (2004). https://doi.org/10.1007/BF02945592
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02945592