Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!mit-eddie!media-lab!snorkelwacker!usc!samsung!noose.ecn.purdue.edu!iuvax!rutgers!njin!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: A-Buffer source (and plotting lots of triangles)?
Message-ID: <1307@idunno.Princeton.EDU>
Date: 19 Jul 90 15:52:21 GMT
References: <1990Jul16.225553.2623@maths.tcd.ie> <1264@idunno.Princeton.EDU> <104 <31667@masscomp.ccur.com>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Organization: Princeton University
Lines: 41

>Reply-To: mark@calvin.westford.ccur.com (Mark Thompson)
>In article <10491@odin.corp.sgi.com> robert@sgi.com writes:

>>I never was able to fully debug the alpha buffer.
>>Because of all sorts of odd boundary conditions, I occasionally
>>created incorrect masks.  The Z buffer was much simpler to code (about
>>1/7th the size of the alpha buffer), and worked flawlessly from the beginning.
>>The two algorithms produced almost identical images.

This is consistent with my intuition as to the costs involved.  Although
I am suprised that your Z buffer was slower.  I was glancing through my notes
and found a fragment of code that was supplied to me by Pat Hanrahan that
did "point-in-polygon" testing very efficiently for quadrilaterals.  If we
call this routine "sample", then rendering a micropolygon becomes something 
like:
	compute the screen bounds xmin-xmax ymin-ymax
	for (x = floor(xmin) ; x <= ceil(xmax) ; x++) {
		for (y = floor(ymin) ; y <= ceil(ymax) ; y++) {
			if (sample(poly, x, y))
				color(x, y, color_of(poly) ;
		}
	}

sample uses the Jordan Curve test to figure out if the point is in the polygon.
If an odd number of edges cross the +x axis, then you are inside.  This can
be done with some moderately small number of instructions.   Basically the 
idea is to recenter the polygon around the sample point.  Then, check vertices
0 and 2 to see if they have different signs.  If they do, then the line from 
0 to 1 or the line from 1 to 2 cross the X axis, depending on the sign of
1.  Similarly, the line from 0 to 3 or 3 to 2 crosses the the X axis as well.
If 0 and 2 are both on the same side of zero, then the line from 0-1 or 1-2
crosses dependant on the sign of 1, with similar cases for vertex 3.  
For each edge that crosses the X axis, you need to ensure that the edge
crosses the POSITIVE X axis, which takes two multiplies and a compare.
For each edge that does cross, you set a particular bit in a mask byte.  
At the end, if there are an odd number of bits set, you know that you are
inside and return a one.  Else, you can return a zero.  This can be done using
a table lookup.  All in all quite alot simpler than trying to clip each polygon
and perform all sorts of nonsense with coverage masks.

Mark