ABSTRACT
A polygon hidden surface and hidden line removal algorithm is presented. The algorithm recursively subdivides the image into polygon shaped windows until the depth order within the window is found. Accuracy of the input data is preserved.The approach is based on a two-dimensional polygon clipper which is sufficiently general to clip a concave polygon with holes to the borders of a concave polygon with holes.A major advantage of the algorithm is that the polygon form of the output is the same as the polygon form of the input. This allows entering previously calculated images to the system for further processing. Shadow casting may then be performed by first producing a hidden surface removed view from the vantage point of the light source and then resubmitting these tagged polygons for hidden surface removal from the position of the observer. Planar surface detail also becomes easy to represent without increasing the complexity of the hidden surface problem. Translucency is also possible.Calculation times are primarily related to the visible complexity of the final image, but can range from a linear to an exponential relationship with the number of input polygons depending on the particular environment portrayed. To avoid excessive computation time, the implementation uses a screen area subdivision preprocessor to create several windows, each containing a specified number of polygons. The hidden surface algorithm is applied to each of these windows separately. This technique avoids the difficulties of subdividing by screen area down to the screen resolution level while maintaining the advantages of the polygon area sort method.
- Appel, A., "The Notion of Quantitative invisibility and the Machine Rendering of Solids", Proceedings ACM National Conference (1967), pp. 387-393. Google ScholarDigital Library
- Atherton, Peter R., "Polygon Shadow Generation", M. S. Thesis, Cornell University, Ithaca, N. Y. (1977), (forthcoming).Google Scholar
- Bouknight, W. J., "A Procedure for Generation of Three Dimensional Half-toned Computer Graphics Representations", Comm. ACM, 13, 9 (Sept. 1970) pp. 527-536. Google ScholarDigital Library
- Galimberti, R., and Montanari, U., "An Algorithm for Hidden-Line Elimination", Comm. ACM, 12, 4, (April 1969), pp. 206-211. Google ScholarDigital Library
- Greenberg, Donald P., "An Interdisciplinary Laboratory for Graphics Research and Applications", Proceedings of the Fourth Annual Conference on Computer Graphics, Interactive Techniques and Image Processing - SIGGRAPH, 1977. Google ScholarDigital Library
- Myers, A. J., "An Efficient Visible Surface Program", CGRG, Ohio State U., (July 1975).Google Scholar
- Newell, M. E., Newell, R. G. and Sancha, T. L., "A Solution to the Hidden Surface Problem", Proceedings ACM National Conference, (1972), pp. 443-450. Google ScholarDigital Library
- Roberts, L. G., "Machine Perception of Three-Dimensional Solids", MIT Lincoln Laboratory, TR 315, (May 1963).Google Scholar
- Schumacher, R. A., Brand, B., Gilliand, M. and Sharp, W., "Study for Applying Computer Generated Images to Visual Simulation", AFHRL-TR-69-14, U. S. Air Force Human Resources Laboratory, (Sept. 1969).Google Scholar
- Sutherland, I. E., and Hodgman, G. W., "Reentrant Polygon Clipping", Communications of the ACM, Vol. 17, No. 1, (Jan. 1974), pp. 32-42. Google ScholarDigital Library
- Sutherland, I. E., Sproull, R. F., and Schumacker, R. A., "A Characterization of Ten Hidden Surface Algorithms", ACM Computing Surveys, Vol. 6, No. 1, (Mar. 1974), pp. 1-55. Google ScholarDigital Library
- Warnock, J. E., "A Hidden Surface Algorithm for Computer Generated Halftone Pictures", Dept. Comp. Sci., U. of Utah, (1969).Google Scholar
- Watkins, G. S., "A Real-Time Visible Surface Algorithm", Comp. Sci, Dept., U. of Utah, UTECH-CSC-70-101, (June 1975).Google Scholar
- Weiler, Kevin J., "Hidden Surface Removal Using Polygon Area Sorting", M. S. Thesis, Cornell University, Ithaca, N. Y. (1977), (forthcoming).Google Scholar
- Hidden surface removal using polygon area sorting
Recommendations
Hidden surface removal using polygon area sorting
A polygon hidden surface and hidden line removal algorithm is presented. The algorithm recursively subdivides the image into polygon shaped windows until the depth order within the window is found. Accuracy of the input data is preserved.The approach is ...
Polygon shadow generation
SIGGRAPH '78: Proceedings of the 5th annual conference on Computer graphics and interactive techniquesA general purpose method for generating shadows using a polygonal coordinate data base is presented. The method is based on an object space polygon clipping hidden surface removal algorithm. Output from the program is in the same three-dimensional ...
Polygon shadow generation
A general purpose method for generating shadows using a polygonal coordinate data base is presented. The method is based on an object space polygon clipping hidden surface removal algorithm. Output from the program is in the same three-dimensional ...
Comments