Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!ucsd!nosc!crash!jcs
From: jcs@crash.cts.com (John Schultz)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <6393@crash.cts.com>
Date: 18 Dec 90 19:57:19 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> <7010@plains.NoDak.edu> <11697@alice.att.com> <59890@microsoft.UUCP>
Organization: Crash TimeSharing, El Cajon, CA
Lines: 68

In <59890@microsoft.UUCP> davidle@microsoft.UUCP (David LEVINE) writes:

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

  He is correct, mathematically.

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

  As has been previously stated, the Binary Space Partition and Depth Sort
with splits, will work for *any* scene from *any* angle, regardless of
the number of polygons. Study these algorithms to become enlightened.
Mathematically, these schemes are robust, and could probably even be written
as a proof (Tom?). Errors might occur due to loss of precision from
excessive plane divisions, but errors will not occur due to an error in the
algorithm, there are no "undefined" cases; it is completely general.

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

  Mathematicians have found the BSP and Depth Sort with Splits to be
valid. Sometimes math (directed) over "art" (pure trial and error) gives
best results.

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

  Generalized solutions cannot fail, else they aren't generalized. The BSP
is so simple (and fast) that you can readily see that it cannot fail to
produce the correct representation. The BSP is as accurate as the formula
to split two 3D planes. Check it out, you'll be pleasantly surprised
(See "Computer Graphics, Principles and Practice", Addison Wesley).
For doing engineering views of static scenes with variable viewing angles,
the BSP is ideal, and probably the fastest method.
  One doesn't need to be a "Wizard", just persistent and open minded.



  John