Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!slxsys!dircon!uad1077
From: uad1077@dircon.uucp (Ian Kemmish)
Newsgroups: comp.graphics
Subject: Re: checking whether 2 2D polygons overlap
Keywords: polygon overlap 2D
Message-ID: <1990PMFri.07.1168@dircon.uucp>
Date: 8 Dec 90 02:01:34 GMT
References: <111@gem.stack.urc.tue.nl> <18082@netcom.UUCP> <7010@plains.NoDak.edu>
Organization: The Direct Connection, UK
Lines: 27


<Discussion of overlapping polygons in the depth sort. >

There are various ways to do this.  The A-buffer fudges it, on the
basis that in most cases the error introdiced by fudging isv.
small.  (And I've known plenty of commercial work done this way
that seems to bear this out.)  The Warnock subdivision algorithm
would certainly handle it OK, until you got to the sub-pixel level,
when you could again fudge it.  I beleive the Weiler-Atherton algorithm
handles it if done properly.  Catmull's analytic algorithm (SIGGRAPH 84)
certainly does it properly.

I am surprised at the claim that no textbooks could be found that
mentioned these algorithms.

Also, note that `doing it properly' is not necessarily expensive.  Most
of these algorithms were devised when the VAX was new.  These days,
a flop is far cheaper than a page fault -- I am in the middle of
moving from a super-sampled jittered z-buffer to an analytic
visibility algorithm with direct-convolution filtering for just
that reason (plus a natural fear of patent lawyers!).

-- 
Ian D. Kemmish                    Tel. +44 767 601 361
18 Durham Close                   uad1077@dircon.UUCP
Biggleswade                       ukc!dircon!uad1077
Beds SG18 8HZ United Kingd    uad1077%dircon@ukc.ac.uk