shal@csinc.UUCP (Shal Jain x848) (10/03/89)
Am looking for a very robust algorithm/code for clipping polygons to a
rectangular viewport. The polygons can be concave,convex or bow-tied.
The only reference I have is Newman-Sproull "Principals of Interactive
Computer Graphics". Any pointers,references etc. will be appreciated
EMAIL address uunet!csinc!shal
Phone 612 - 631 - 7848.
A special case I am interested is as such:
+ denotes viewport boundary. * is outline of target polygon.
@ is where the polygon crosses the viewport.
------------------
+ +
+ ****@*****
+ * + *
+ * + *
+ *+ *
+ @ *
+ +* *
+ + * *
+ +* *
+ @ *
+ *+ *
+ * + *
--------------@--- *
* *
***********faber@clown.cs.wisc.edu (Ted Faber) (10/03/89)
In article <120@csinc.UUCP> shal@csinc.UUCP (Shal Jain x848) writes: >Am looking for a very robust algorithm/code for clipping polygons to a >rectangular viewport. The polygons can be concave,convex or bow-tied. >The only reference I have is Newman-Sproull "Principals of Interactive >Computer Graphics". Any pointers,references etc. will be appreciated OK. I'll take a stab at this. No I'm not going to send code, but I do have a reference for you. Sutherland and Hodgman's "Reentrant Polygon Clipping" in Communications of the ACM, Vol 17, No. 1 Jan 1974 This is a good place to start, but I believe that their method will result in an unusual case for your case, namely that their algorithm will leave you with the two triangles in the viewport connected by two edges on the right edge of the VP. The two edges will be the same line. At the end of the paper they do go into detail about how to deal with this, as I recall, but it's been a while since I read it, so caveat emptor. The algorithm is an interesting approach and educational to implement. Good luck, Ted Faber No sig yet, but I can be reached at faber@cs.wisc.edu
bdb@becker.UUCP (Bruce Becker) (10/03/89)
In article <120@csinc.UUCP> shal@csinc.UUCP (Shal Jain x848) writes: |Am looking for a very robust algorithm/code for clipping polygons to a |rectangular viewport. The polygons can be concave,convex or bow-tied. |The only reference I have is Newman-Sproull "Principals of Interactive |Computer Graphics". Any pointers,references etc. will be appreciated |EMAIL address uunet!csinc!shal |Phone 612 - 631 - 7848. |A special case I am interested is as such: |[...] You might do well to look at "Procedural Elements for Computer Graphics", David F. Rogers, 1985, McGraw-Hill. Among other things the case you mention is covered... Cheers, -- __ Bruce Becker Toronto, Ont. w \../ Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu `/ /-e BitNet: BECKER@HUMBER.BITNET _/ \_ Beware the Fandom of the Oprah - P. Donahue
mitchell@cbmvax.UUCP (Fred Mitchell - QA) (10/04/89)
In article <120@csinc.UUCP> shal@csinc.UUCP (Shal Jain x848) writes: >Am looking for a very robust algorithm/code for clipping polygons to a >rectangular viewport. The polygons can be concave,convex or bow-tied. I have developed a method of doing this which is (kinda) simple. First, let's look at your figure: > ------------------ > + + > + ****@***** > + * + * > + * + * > + *+ * > + @ * > + +* * > + + * * > + +* * > + @ * > + *+ * > + * + * > --------------@--- * > * * > *********** Treat the horizontal bounds: > ---------------------------- > > ********** > * * > * * > * * > * * > * * > * * > * * > * * > * * > * * > --------------@-------@----- > * * > *********** And now check each line IN SEQUENCE, starting from any arbitrary beginning: from first line to last: a) A line segment that is COMPLETELY between leave alone b) A line segment that is COMPLETELY outside delete it c) A line segment that is BISECTED by a horizontal line determine point of intersection (@) truncate line at (@), and replace the old line with the part of the new line satifies (b). check truncation queue if (empty) place this point (@) in queue else pull out last (@) from queue create a new line ((@)-(@)) Now we should have: > ---------------------------- > > ********** > * * > * * > * * > * * > * * > * * > * * > * * > * * > * * > --------------@*******@----- So for the vertical case: > + + > + + > + ****@***** > + * + * > + * + * > + *+ * > + @ * > + +* * > + + * * > + +* * > + @ * > + *+ * > + * + * > + @**@****@ > + + > + + Apply the above algorithm, except for the vertical bounds. Then you will have: > + + > + + > + ****@ > + * * > + * * > + ** > + @ > + * > + * <--- artifact > + * > + @ > + ** > + * * > + @**@ > + + > + + Note that two of the lines overlap, the 'clip' lines. You may want to further processing to eliminate the 'artifact' area if that will interfere with your application. The artifact area will always be characterized by 'even' overlapped segments of the line (and, of course, coinciding with the boundary). Also, note that a line is counted as 'within bounds' if it coincides with the boundary lines. If you need any more help, E-Mail me! Address is: mitchell@cbmvax.UUCP -Mitchell
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/04/89)
In article <120@csinc.UUCP> shal@csinc.UUCP (Shal Jain x848) writes: >Am looking for a very robust algorithm/code for clipping polygons to a >rectangular viewport. Foley and Van Dam's text also discusses this problem. The classic paper is Ivan E. Sutherland & Gary W. Hodgman Reentrant Polygon Clipping Communications of the ACM Vol 7 No 1 (January 1974) pp. 32-42 Beware: There is one error in a diagram (a flowchart, I think) in the paper. The appendix to the paper discusses the particular problem you pose (a concave polygone which, after clipping, results in two or more disconnected polygonal regions). The solution requires sorting the points of intersection along each edge of the clipping window/viewport to discover the various pieces.