Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!rutgers!att!att!dptg!ulysses!andante!alice!td
From: td@alice.att.com (Tom Duff)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Summary: confusion
Keywords: polygon overlap 2D
Message-ID: <11697@alice.att.com>
Date: 6 Dec 90 14:48:07 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> <7010@plains.NoDak.edu>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 29

rodent@netcom.UUCP says:
>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 find this hard to believe.  Foley, van Dam, Feiner & Hughes describe
the Newell, Newell & Sancha algorithm on pp 673-675 of Computer Graphics,
Principles & Practice.  The algorithm is fairly simple.
I've coded it up at least once, long ago when I gave it as a programming
assignment.  It took about a day, and
never caused any trouble.  I'm utterly astounded that anyone could spend
large amounts of time and still fail to get it working.

It's fairly obvious that the algorithm cannot fail to depth-sort a scene,
since whenever the depth order of two polygons cannot be determined, it
replaces one of them by splitting it in two pieces, one on each side of the
other (original) polygon.  Since the algorithm refuses to allow polygons
whose depth order cannot be determined to remain in the scene, the only
possible failure mode would be non-termination, not incorrect depth-sorting.
Non-termination is obviously out of the question, since each polygon can
be split at most by each other (original) polygon in the scene.

Maybe you could describe in more detail a simple scene on which your program
fails?