Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!netcom!rodent
From: rodent@netcom.UUCP (Richard Noah)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <18082@netcom.UUCP>
Date: 5 Dec 90 00:43:10 GMT
References: <111@gem.stack.urc.tue.nl>
Organization: Netcom- The Bay Area's Public Access Unix System {408 241-9760 guest}
Lines: 34

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!

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
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.

Is there an algorithm that always works?  If there is, it's a closely
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.

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.

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
the high priests reading this group care to reveal this secret to the
masses?

---------------------------------
Ben Discoe, caltech escapee and frustrated visionary at large. 


Brought to you by Super Global Mega Corp .com