cliff@centaure.UUCP (Clifford Dibble) (11/11/89)
Earlier in the week I posted this message ... >My implementation of the Weiler-Atherton polygon clipping algorithm fails >when given certain combinations of input polygons, ... > > ... > >... The original paper that describes the algorithm [1] >is vague about these situations: "If care is taken in placement of >intersections where the subject and clip polygon contours are identical in >the XY plane, no degenerate polygons will be produced by the clipping >process". > > ... > > [1] "Hidden Surface Removal Using Polygon Area Sorting", K.Weiler, > P.Atherton, Computer Graphics 11(2), p 214, Summer 1977. > Three days after I posted the message I received a copy of Mr. Weiler's original M.S thesis. In it, he carefully classifies all degenerate conditions and shows how to resolve them. I *highly* recommend his thesis to anyone attempting to implement this algorithm; it's invaluable. One may order it directly from Cornell university's library. Allow 4-6 weeks for delivery. [2] "Hidden Surface Removal Using Polygon Area Sorting", K.Weiler, M.S. thesis, Cornell University, Ithaca N.Y. Jan. 1978. I believe the number 14853 is it's microfilm catalog ID. Cliff Dibble Centaure Systems Irvine, CA uunet!centaure!cliff
kjw@bacchus.ardent.com (Kevin Weiler) (11/16/89)
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