Polygon Clipping

• Sutherland-Hodgman Polygon Clipping (1974) Highly efficient when polygon either entirely inside or outside clipping window. Requires dynamic memory allocation (given that more than one run is done over the vertices).
• Weiler-Atherton (1977) more complex, good for clipping against non-rectangular Window (i.e. not applicable to general SR case).

  Optimised version of Weiler-Atherton for rectangular clipping presented by

  [AK87] A. Kilgour. Unifying vector and polygon algorithms for scan conversion and clipping. Proceedings of Eurographics '87, pages 363—375. 8/1987.

• Laing-Barsky (1983) may be slightly faster when polygon intersects clipping window. Note that this case occurs less frequently in Geometrical SR reconstruction. Apparently twice as fast as Sutherland-Hodgman, according to

  [PM92] Patrick-Gilles Maillot. A New, Fast Method For 2D Polygon Clipping: Analysis and Software Implementation. ACM Transactions on Graphics, 11(3):276—290, 3/7/1992.

According to Eric Haines in Ray Tracing News Vol 10 No 3, Dr David Rogers mentions in his book Procedural Elements for Computer Graphics (2nd ed.) that Liang-Barsky is a special case of Cyrus-Beck.

No dynamic memory allocation required.

References

• http://www.cs.fit.edu/~wds/classes/graphics/Clip/clip/clip.html
• http://www.codeguru.com/Cpp/misc/misc/graphics/article.php/c8965/

---

[ Front | phdwiki | Index ]

Updated September 25, 2008

---