Path: utzoo!attcan!sobmips!uunet!cs.utexas.edu!usc!apple!netcom!dlb!ardent!bacchus!kjw
From: kjw@bacchus.ardent.com (Kevin Weiler)
Newsgroups: comp.graphics
Subject: Re: more: Weiler-Atherton polygon clipping
Summary: 1980 SIGGRAPH polygon clipper is more general
Message-ID: <9270@ardent.UUCP>
Date: 15 Nov 89 18:34:44 GMT
References: <121@centaure.UUCP>
Sender: news@ardent.UUCP
Reply-To: kjw@bacchus.ardent.com (Kevin Weiler)
Distribution: na
Organization: Stardent Computer Corp., Sunnyvale, CA
Lines: 41

As Spencer Thomas noted earlier, in addition to the polygon clipper
described at the 1977 SIGGRAPH, one should also look at the
polygon clipper described in the 1980 SIGGRAPH proceedings,
"Polygon Comparison Using a Graph Representation", for a more
general clipper that can also be used for polygon set operations
with two or more input polygons.

A significant difference between the two clippers is that the 
SIGGRAPH `77 clipper can't represent polygons which self-intersect
themselves at a single point, or intersections where a clip
polygon vertex touches the boundary of the subject polygon at a single
point from the interior of the subject polygon, unless one
slightly modifies the coordinate values of that particular point.  
This is covered on pages 41, 46, and 71-72 of my Cornell thesis
(which can be obtained from Cornell as Cliff Dibble recently 
described). While this works, I always found modifying data values
philosophically unsettling, and went on to produce the second 
algorithm, which eliminates the need for modifying data.

The SIGGRAPH `80 clipper uses a richer representational structure which 
can directly represent these situations without modifying data.
While the data structure is more complicated (it is in many ways
reminiscent of Baumgart's winged-edge solid modeling data structure),
it greatly reduces the number of intersection types from
about fourteen down to about three intersection types.  The '80 algorithm
basically merges the polygons together, collects some semi-global 
information, and classifies the results so that any of the set 
operation outputs, including clipping, can be obtained.

While I prefer the cleanliness and generality of the more sophisticated 
data structure approach myself, some people still prefer the simpler 
list of vertices approach of the first clipper, and don't mind modifying 
the coordinate values on occasion.

It may also be of interest to some that the three-dimensional analog of
the polygon comparison algorithm requires a non-manifold 
geometric modeling data structure.  Such a data structure, called the
Radial Edge data structure, is described in my 1986 RPI PhD thesis,
"Topological Structures for Geometric Modeling".

-Kevin Weiler