II.3

Clipping a Concave Polygon

S. Glassner Andrew,     Microsoft Corp. Redmond, Washington

Introduction

Polygons are a popular modeling primitive. Polygon clipping against a line or a plane is one of the most common 1 rendering operations. The classic reentrant method (Sutherland and Hodgman 1974) clips a convex polygon against a line, yielding a pair of polygons lying on either side of the line. The algorithm is conceptually elegant and easy to program for convex polygons, but becomes difficult to implement for concave ones. Although it can be patched up to treat these cases (Foley et al. 1990), the patching becomes complicated, involving the detection of degenerate edges.

This gem presents a simple yet robust method for clipping concave ...

Get Graphics Gems V (IBM Version) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.