ych@maps.cs.cmu.edu (Yuan Hsieh) (06/14/88)
Is there a good algorithm to clip two polygons against each other? In another word, if I put two polygons on top of one another, I don't want to see the portions of the lower polygon covered by the upper one. Polygons are described by a list of points and I want to do the clipings before I display them. So the standard hidden line removal method that sorts the polygons and then draw over them doesn't work. If there are solutions for both convex and concave polygons, that'll be great! Otherwise I can live with just the convex solution. Pointers to published paper will suffice. Please reply to ych@maps.cmu.cs.edu since I don't usually read this bboard. Thanks. -Y' --
allan@calgary.UUCP (Jeff Allan) (06/15/88)
In article <1932@pt.cs.cmu.edu>, ych@maps.cs.cmu.edu (Yuan Hsieh) writes: > Is there a good algorithm to clip two polygons against each other? The most general polygon clipping algorithm that I know of is the Weiler-Atherton algorithm. It is described in: "Fundamentals of Computer Graphics", J.D. Foely & A. van Dam, Addison Wesley, 1983. It was originally published in: Hidden Surface Removal using Polygon Area Sorting, Kevin Weiler & Peter Atherton, SIGGRAPH '77 Procedings published as Computer Graphics 11(2), Summer 1977, pp.214-222. The algorithm clips a concave polygon (possibly with holes) to another concave polygon (also, possibly with holes). I am not convinced that the hidden surface/line removal algorithm described in the paper works for line drawings, but then I've never tried to implement it. Hope this helps. -- Jeff Allan, University of Calgary ..!{ubc-vision,ihnp4}!alberta!calgary!allan
dfr@usna.MIL (David F. Rogers <dfr@usna>) (06/16/88)
The net address given in the article did not work so am posting to the net. Sorry about that. There are 2 basic algorithms for doing what you want. The first is the Sutherland-Hodgman algorithm, the second is the Weiler-Atherton algorithm. The Weiler-Atherton algorithm is more general but more difficult to implement. Both are described in Procedural Elements for Computer Graphics by Rogers, McGraw-Hill. This should be in your library. References to the original papers are contained therein if needed.
richard@gryphon.COM (Richard Sexton) (05/09/89)
given two objects with m and n elements: these can be intersected in n*m amount of time. if one of them is represented by a BSP tree than the intersection takes n*log(m) time.... if both are represented by BSP trees...is the time log(n)*log(m)... and exactly how is this intersection accomplished? please send email -- ``But if she wants it (particularly if she wants it bad), I am going to have a hard time saying "no".'' - Ted Kaldis richard@gryphon.COM decwrl!gryphon!richard gryphon!richard@elroy.jpl.NASA.GOV