Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!ogicse!plains!bakke
From: bakke@plains.NoDak.edu (Jeffrey P. Bakke)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <7010@plains.NoDak.edu>
Date: 5 Dec 90 05:57:31 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP>
Organization: North Dakota State University, Fargo
Lines: 33

In article <18082@netcom.UUCP> rodent@netcom.UUCP (Richard Noah) writes:
> 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!
> 
[ Etc ... ]
> 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?
Well, I'm not a graphics Guru of any version but I really don't think there
is any way to have a depth sort algorithm work in all cases.  The depth
sort always fails whenever you have intersecting polygons or polygons that
overlay sections of each other.  I think the only way to work around this
problem short of ray-tracing or some other high cpu cost procedure is the
use of the Z-buffer algorithm (The painters is a simplified version of this
algorithm) when you generally depth sort each pixel individually instead of
each polygon.  This is all that I have ever seen to eliminate this problem
short of highly-intensive algorithms.  Only problem of course with the
Z buffer algorithm is that you need a fairly large amount of memory
to store the necessary information.  Although if you have the memory, there
would be very few ways of doing this any faster with a different algorithm.

Anyone else out there want to take a shot at a better solution.

-- 
Jeffrey P. Bakke                      |   There are a finite number of
  INTERNET:   bakke@plains.NoDak.edu  |   jokes in the world...         
  UUCP    : ...!uunet!plains!bakke    |     The overflow began 
  BITNET  : bakke@plains.bitnet       |   decades ago. 
"I am not a number, I am a free man!" - The Prisoner


Brought to you by Super Global Mega Corp .com