Hidden curve removal for free form surfaces

ABSTRACT

This paper describes a hidden curve algorithm specifically designed for sculptured surfaces. A technique is described to extract the visible curves for a given scene without the need to approximate the surface by polygons. This algorithm produces higher quality results than polygon based algorithms, as most of the output set has an exact representation. Surface coherence is used to speed up the process. Although designed for sculptured surfaces, this algorithm is also suitable for polygonal data.

REFERENCES

• 1: Arthur Appel, The notion of quantitative invisibility and the machine rendering of solids, Proceedings of the 1967 22nd national conference, p.387-393, January 1967, Washington, D.C., United States [doi>10.1145/800196.806007]
• 2: James F. Blinn, A scan line algorithm for displaying parametrically defined surfaces, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.27, August 1978
• 3: B. Bruderlin, E. Cohen, and G. Elber. A Plane-Sweep Hidden-Surface Algorithm for Curved Surfaces. Technical report No. 90-006, Computer Science, University of Utah.
• 4: C. Sequin and P. Wensley. Visible Feature Return at Object Resolution. IEEE Computer Graphics and Application, May 1985, pp 27-50.
• 5: E. Cohen, T. Lyche, and R. Riesenfeld. Discrete B-splines and subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics. Computer Graphics and Image Processing, 14, 87-111 (1980).
• 6: Debra Dooley , Michael F. Cohen, Automatic illustration of 3D geometric models: lines, Proceedings of the 1990 symposium on Interactive 3D graphics, p.77-82, February 1990, Snowbird, Utah, United States
• 7: V. Fuson. Application of a Hidden Line Algorithm to Surface Visualization. MS thesis, Computer Science, University of Utah, 1984.
• 8: R. Galimberti, An algorithm for hidden line elimination, Communications of the ACM, v.12 n.4, p.206-211, April 1969 [doi>10.1145/362912.362921]
• 9: Griffith Hamlin, Jr. , C. William Gear, Raster-scan hidden surface algorithm techniques, ACM SIGGRAPH Computer Graphics, v.11 n.2, p.206-213, Summer 1977
• 10: C. Hornung. An Approach to a Calculation-Minimized Hidden Line Algorithm. Computer & Graphics, Vol 6, No 3, pp 121-126, 1982.
• 11: C. Hornung. A Method for Solving the Visibility Problem IEEE CG&A July 1984, pp. 26-33.
• 12: (3. Hornung, W. Lellek, P. Pehwald, and W. Strasser. An Area-Oriented Analytical Visiblity Method for Displaying Parametrically Defined Tensor-Product Surfaces. Computer Aided Geometric Design, 2 (1985) 197-205.
• 13: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 14: G. Elber and E. Cohen. Hidden Curve Removal for Untrimmed and Trimmed NURB Surfaces. Technical report No. 89-019, Computer Science, University of Utah.
• 15: Ralf Hartmut Güting , Thomas Ottmann, New algorithms for special cases of the hidden line elimination problem, Computer Vision, Graphics, and Image Processing, v.40 n.2, p.188-204, November 1, 1987 [doi>10.1016/S0734-189X(87)80114-7]
• 16: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 17: Tomihisa Kamada , Satoru Kawai, An enhanced treatment of hidden lines, ACM Transactions on Graphics (TOG), v.6 n.4, p.308-323, Oct. 1987 [doi>10.1145/35039.35042]
• 18: Jiri Kripac, Classification of edges and its application in determining visibility, Computer-Aided Design, v.17 n.1, p.30-36, Jan./Feb. 1985 [doi>10.1016/0010-4485(85)90008-9]
• 19: J. Lane and R. Riesenfeld. A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces. IEEE Transaction on pattern analysis and machine intelligence, vol. PAMI-2, No. 1, January 1980.
• 20: L. Li, Hidden-line algorithm for curved surfaces, Computer-Aided Design, v.20 n.10, p.466-470, Oct. 1988 [doi>10.1016/0010-4485(88)90004-8]
• 21: P. Loutrel. A Solution to the Hidden.line Problem for Computer Drawn Polyhedra IEEE Transactions on Computers, Vol. C-19, No. 3, 205-213, March 1970.
• 22: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 23: C. Montani and M. Re. Vector and Raster Hidden-Surface Removal Using Parallel Connected Stripes. IEEE Computer Graphics and Application, July 1987, pp 14-23.
• 24: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 25: J. Peterson. PItT - A High Quality Image Systhesis System for B-spline Sm~taces. MS thesis, Computer Science Dept., University of Utah, Dec. 1987'.
• 26: J. Ranldn. A Geometric Hidden-Line Processing Algorithm. Comput. & Graphics Vol. 11, No. 1, pp. 11-19. 1987'.
• 27: Thomas W. Sederberg , Ray J. Meyers, Loop detection in surface patch intersections, Computer Aided Geometric Design, v.5 n.2, p.161-171, July 1988 [doi>10.1016/0167-8396(88)90029-5]
• 28: Thomas W Sederberg , Scott R Parry, Comparison of three curve intersection algorithms, Computer-Aided Design, v.18 n.1, p.58-64, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80013-6]
• 29: M. Sweeney. Ray Tracing Free-Form B-Spline Surfaces. IEEE Computer Graphics and Application, Februaury 1986, pp 41-49.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems

General Terms:
Algorithms, Verification