home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / graphics / 12926 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  2.4 KB
  1. Path: sparky!uunet!mcsun!uknet!yorkohm!minster!john
  2. From: john@minster.york.ac.uk
  3. Newsgroups: comp.graphics
  4. Subject: Clipping polygon to rectangle
  5. Message-ID: <724442088.9285@minster.york.ac.uk>
  6. Date: 15 Dec 92 17:54:49 GMT
  7. Organization: Department of Computer Science, University of York, England
  8. Lines: 43
  9.  
  10. I have read the subsections of ``Computer graphics: principles
  11. and practice'' [Foley90], which describe algorithms for clipping a
  12. polygon to a rectangle. None of the algorithms there meet my desire
  13. for correctness with simplicity and practicality. (I do not require
  14. completeness, as I am prepared to accept the output of a single degenerate
  15. polygon instead of a list of disjoint polygons.) I've not found
  16. anything better in older graphics textbooks, or in a brief literature
  17. search. (Ok, so I'm crying for the moon - but someone out there
  18. probably has a method of reaching it. :-))
  19.  
  20. The Sutherland-Hodgman algorithm (described in [Foley90] and older
  21. graphics texts I have read) clips against each side of the
  22. rectangle in turn, and produces three intermediate polygons - which
  23. I assume require a (single, extra) temporary buffer to hold them.
  24. This I do not like. As I am prepared to accept the output of degenerate
  25. polygons, the Liang-Barsky algorithm (again in [Foley90]) sounds as
  26. if it will satisfy me. Unfortunately, the original paper [Liang83]
  27. indicates that the algorithm ``will sometimes generate extraneous
  28. turning vertices'' (p.870). Experimentation with my typed-in copy of
  29. the LB implementation confirms this warning. Foley, van Dam et. al.
  30. say that they have modified their implementation (p.932 ``The original
  31. algorithm operates in a slightly different order'') but this does not
  32. appear to correct (was not meant to correct?) the problem - in my
  33. typed-in copy of the FD et. al. code. (Note also that even the Nov.
  34. 1991 corrected printing of Foley et. al. has typographical errors in
  35. the code which I had to correct in my typed-in copy before it ran.)
  36.  
  37. So, can anyone suggest a better algorithm, or a `fixup' for
  38. the LB algorithm? C implementations preferred. :-) I don't really
  39. wish to reinvent the wheel.
  40.  
  41. John A. Murdie
  42.  
  43. 1. ``Computer graphics: principles and practice'',
  44.    Foley, van Dam, et. al
  45.    Addison-Wesley
  46.    Nov. 1991
  47.  
  48. 2. ``An analysis and algorithm for polygon clipping'',
  49.    Y.-D. Liang and B. A. Barsky,
  50.    Comm. ACM 26(11) pp.868-877,
  51.    Nov. 1983.
  52.    (Also corrigendum in CACM 27(2), Feb. 1984, p.151.
  53.