>[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
As pointed out by others (and my email to Lyppens) this is really the
same as clipping - found in lots of books.
Quote:>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.)
Quote:>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
Quote:>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
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.
Quote:>the high priests reading this group care to reveal this secret to the
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.
employed by CSC working for NASA speaking for myself