Efficient clipping of arbitrary polygons

ABSTRACT

Clipping 2D polygons is one of the basic routines in computer graphics. In rendering complex 3D images it has to be done several thousand times. Efficient algorithms are therefore very important. We present such an efficient algorithm for clipping arbitrary 2D-polygons. The algorithm can handle arbitrary closed polygons, specifically where the clip and subject polygons may self-intersect. The algoirthm is simple and faster that Vatti's (1992) algorithm, which was designed for the general case as well. Simple modifications allow determination of union and set-theoretic differences of two arbitrary polygons.

REFERENCES

• 1: ANDREEV, R.D. 1989. Algorithm for clipping arbitrary polygons. Comput. Graph. Forum 8 (1989), 183-191.
• 2: IEEE Computer Graphics and Applications, Fractional Invisibility, IEEE Computer Graphics and Applications, v.8 n.6, p.77-84, November 1988
• 3: BLINN, g. 1991. Line clipping. IEEE Comput. Graph. Appl. 11.
• 4: 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
• 5: You-Dong Liang , Brian A. Barsky, An analysis and algorithm for polygon clipping, Communications of the ACM, v.26 n.11, p.868-877, Nov. 1983 [doi>10.1145/182.358439]
• 6: MONTANI, C. AND RE, M. 1987. Vector and raster hidden surface removal using parallel connected stripes. IEEE Comput. Graph. Appl. 7, 14-23.
• 7: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 8: Ari Rappoport, An efficient algorithm for line and polygon clipping, The Visual Computer: International Journal of Computer Graphics, v.7 n.1, p.19-28, Jan. 1991 [doi>10.1007/BF01994114]
• 9: Stuart Sechrest , Donald P. Greenberg, A visible polygon reconstruction algorithm, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.17-27, August 1981
• 10: Ivan E. Sutherland , Gary W. Hodgman, Reentrant polygon clipping, Communications of the ACM, v.17 n.1, p.32-42, Jan. 1974 [doi>10.1145/360767.360802]
• 11: Bala R. Vatti, A generic solution to polygon clipping, Communications of the ACM, v.35 n.7, p.56-63, July 1992 [doi>10.1145/129902.129906]
• 12: Kevin Weiler, Polygon comparison using a graph representation, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.10-18, July 14-18, 1980, Seattle, Washington, United States
• 13: Kevin Weiler , Peter Atherton, Hidden surface removal using polygon area sorting, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.214-222, July 20-22, 1977, San Jose, California

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms

Keywords:
clipping, polygon comparison