Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!usenet.ins.cwru.edu!eagle!data.nas.nasa.gov!wk207!uselton From: uselton@nas.nasa.gov (Samuel P. Uselton) Newsgroups: comp.graphics Subject: Re: checking whether 2 2D polygons overlap Keywords: polygon overlap 2D Message-ID: <1990Dec5.175212.24487@nas.nasa.gov> Date: 5 Dec 90 17:52:12 GMT References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> Sender: news@nas.nasa.gov Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA Lines: 84 posted from rodent@netcom.UUCP (Richard Noah), but signed by Ben Discoe: >hugo@gem.stack.urc.tue.nl (Hugo Lyppens) writes: >[implementing newell-newell-sancha on an Amiga] >>the screen overlap or not. I haven't been able to find an article on this >>subject, not even in articles from the authors of the painter's algorithm >>themselves! > As pointed out by others (and my email to Lyppens) this is really the same as clipping - found in lots of books. >I did this a while ago, using Foley-VanDam. The 2D-overlap algo is either >in the same book, or another common reference, because I didn't have >trouble finding it. The only problem is, this algorithm DOESN'T WORK ^^^^^^^^^^^^^^ Newell-Newell-Sancha or the overlap (clipping) ?? (I assume N-N-S Painter's visible surface alg.) >CONSISTENTLY. Even if you limit yourself to scenes composed of the simplest >non-intersecting triangles, newell-newell-sancha algo will occasionally >be unable to depth-sort them correctly. There is a standard picture in most texts showing a set of three convex polygons that overlap in x y and z without intersecting. They can not be "properly" depth sorted BY ANY METHOD! (So don't blame N-N-S or the text authors.) The standard solution in this case is to split one of the polygons along the plane of another. This results in four convex polygons that ARE readily depth "sortable". The main benefit of this algorithm is not its speed for a single frame but rather the fact that in most SEQUENCES the order of the polygons changes very little from one frame to the next, so frames 2 through N can be done faster. This speed is useful in real (or near real) time work, but requires fairly clever implementation to take full advantage. > >Is there an algorithm that always works? If there is, it's a closely ^^^^^^^^^^^^ "Hidden Surface Removal" I assume >gaurded secret of the high priests of computer graphics. I've tried for >years to find an algorithm that will work in all cases, spending months >coding, testing, and ending up in defeat. There is no ONE visible surface rendering algorithm best for all purposes. That is why there are so many choices. And why people ("high priests"? :-) ) continue to do research and publish new algorithms and improvements to the old ones. I'm only a low priest I guess ( :-) ) but in every graphics class I ever taught (in 10 years) we spent at least a couple of weeks discussing the hidden/visible surface problem, why there were choices to be made, and what the question were to help determine which answer is appropriate. Hardly a "closely guarded secret." > >I went to Computer Literacy (for those unknowing, it's a VERY complete >bookstore) and looked in EVERY computer graphics text they had. >Many didn't even mention hidden-line algos, some mentioned them but didn't >elaborate, and several only had elaborate rendering techniques useless >for real-time. It is a HARD problem. Saying "useless for real-time" and discounting the entire content is throwing the baby out with the bathwater. It also suggests that your hardware is not (yet) up to the task you are attempting. > >Only two books (everybody knows which) had a depth-sort algorithm in >detail, and they both described the (oh no!) Newell-Newell-Sancha algo. > >If anyone could mention/describe/point to a SINGLE ALGORITHM ANYWHERE >that depth-sorts correctly, I would be indebted forever. Would one of ^^^^^^^^^^^^^^^^^^^^^^^^^^^ as pointed out above, this is mathematically impossible in general. >the high priests reading this group care to reveal this secret to the >masses? > Another possibility you might consider (before buying a Personal Iris and making the problem moot) is the BSP-tree based algorithm. It requires building a tree data structure rather than a sorted list. Traversing the tree at rendering time is almost as fast. The tree does not need changed as a viewer moves around, but will need revised when objects move relative to each other. [Foley, VanDam, Feiner & Hughes starting p. 675] >--------------------------------- >Ben Discoe, caltech escapee and frustrated visionary at large. Sam Uselton uselton@nas.nasa.gov ex-prof, now just research! employed by CSC working for NASA speaking for myself Brought to you by Super Global Mega Corp .com