Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!jarthur!uunet!microsoft!davidle
From: davidle@microsoft.UUCP (David LEVINE)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <59890@microsoft.UUCP>
Date: 17 Dec 90 18:06:04 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> <7010@plains.NoDak.edu> <11697@alice.att.com>
Reply-To: davidle@microsoft.UUCP (David LEVINE)
Organization: Microsoft Corp., Redmond WA
Lines: 79

In article <11697@alice.att.com> td@alice.att.com (Tom Duff) writes:
>
>>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?

I will admit that I have not followed this thread fully and am not up
on the very latest rendering techniques.  However, you seem to be assuming
that the computation of the relationship between pairs of polygons will
always be accurate.

Have you tried this algorithm on real world databases with many thousands of
polygons?  There is no fast, perfect hidden surface or hidden line
algorithm I know of.  Ray tracing is very good and insensitive to local
singularities which tend to be confined to one or two bad pixels.  Other
techniques will always fail on some databases in my experience.

Singularities crop up in complex scenes.  Accuracy is a more important
consideration than speed in finished engineering work.  For example, in
my experience, the multi-million dollar (yes, I know that means nothing)
CSG software we used could not generate a perfect hidden line view of our
model which contained over 100,000 polygons with much fine detail and lots
of trusses containing many points where several cones meet, each one involving
dozens of polygons with a common point.  Remember, this model is generated
with floating point coordinates such that even if the final work is done
in integer space, the result may be many polygons intersecting in arbitrary
ways.  Touch up work with white-out and a straight edge was very common
when finished drawings were being produced.

Other experience has show me that there is no perfect Computer Graphics
Wizard solution to this type of problem.  The "art" is to find algorithms
that are fast and that fail rarely and that, in failure, produce only
local errors as opposed to making large parts of the result incorrect.

Hidden line views are particularly troublesome in this respect because
often an entire line or a large portion of one is missing which is often
much more noticable then some pixels being the wrong color.  Hidden line
rendering is required for driving plotters, among other uses. 

Your logic on why one particular algorithm is perfect does not convince me.
It assumes that splitting polygons around others and other computations
always result in a correct representation.  In practice, I suspect that
in testing this approach, you would refine it until you think that it is
indeed perfect and then a customer will send you a model that fails in
one particular orientation and view in a way that your program did not
anticipate.  You must then change your algorithm, probably slowing it down
just a bit more and most likely destabalizing the code, fixing more failure
modes than are added or maybe not.

This is usually the development pattern of high end graphics packages that
must be robust.  We are learning much as the years go by and much of the
problems which are encountered may be found in the literature.  Still,
in the final result, rendering code that must be accurate seems to wind up
with a lot of magic in it and I think that is the experience reported by
the poster, by myself and by everybody else I have encountered in my
relatively limited exposure.

David Levine (davidle@microsoft)