Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!atc
From: atc@cs.utexas.edu (Alvin T. Campbell III)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <15467@cs.utexas.edu>
Date: 5 Dec 90 17:06:59 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> <7010@plains.NoDak.edu>
Organization: Dept of Computer Sciences, UTexas, Austin
Lines: 45

In article 15436 of comp.graphics, (Jeffrey P. Bakke) writes:

>In article <18082@netcom.UUCP> rodent@netcom.UUCP (Richard Noah) writes:
>> 
>> If anyone could mention/describe/point to a SINGLE ALGORITHM ANYWHERE
>> that depth-sorts correctly, I would be indebted forever. 
>
>                                    ... 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 ... is the use of the Z-buffer algorithm 
>
>Anyone else out there want to take a shot at a better solution.

I would suggest the use of a Binary Space Partioning (BSP) Tree algorithm.
The basic technique leads to a depth sort without the limitations of the 
Newell-Newell-Sancha method, mentioned above.  

First, the input polygons are split across each other's planes, in order to 
prevent the intersection and cycled-ordering problems mentioned above.  This 
is done in an efficient manner which does not require each polygon to be 
tested against all others.

Next, a binary data structure is created which aids in the polygon
sorting process.  A modified inorder tree traversal results in a correct
depth sort of the polygons from any viewpoint.  Note that this data
structure is viewpoint-independent, and is well-suited for hidden
surface removal in animations where the only the viewpoint changes.

The basic work was done by Bruce Naylor in his dissertation research, 
and is documented in the somewhat theoretical paper:
Fuchs, Kedem, and Naylor, "On Visible Surface Generation by A Priori
Tree Structures", Proceedings of SIGGRAPH 1980, July 1980, pp. 124-133.

A later paper with a more practical orientation is:
Fuchs, Abram, and Grant, "Near Real-Time Shaded Display of Rigid 
Objects", Proceedings of SIGGRAPH 1983, JUly 1983, pp. 65-72.

I hope this information is helpful.

-- 
				A. T. Campbell, III
				CS Department, University of Texas
				atc@cs.utexas.edu


Brought to you by Super Global Mega Corp .com