Add RenderAddTraps. Rewrite trapezoid rendering code.

15 files changed, 1040 insertions, 1582 deletions

diff --git a/fb/fbedge.c b/fb/fbedge.c
new file mode 100644
index 000000000..7a383020b
--- /dev/null
+++ b/fb/fbedge.c
@@ -0,0 +1,134 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include "fb.h"
+
+#ifdef RENDER
+
+#include "picturestr.h"
+#include "mipict.h"
+#include "renderedge.h"
+#include "fbpict.h"
+
+/*
+ * 8 bit alpha
+ */
+
+#define N_BITS	8
+#define rasterizeEdges   fbRasterizeEdges8
+
+#define DefineAlpha(line,x) \
+    CARD8	*__ap = (CARD8 *) line + (x)
+
+#define StepAlpha	__ap++
+
+#define AddAlpha(a) {				    \
+    CARD16 __a = a + *__ap;			    \
+    *__ap = ((CARD8) ((__a) | (0 - ((__a) >> 8)))); \
+}
+
+#include "fbedgeimp.h"
+
+#undef AddAlpha
+#undef StepAlpha
+#undef DefineAlpha
+#undef rasterizeEdges
+#undef N_BITS
+
+/*
+ * 4 bit alpha
+ */
+
+#define N_BITS	4
+#define rasterizeEdges	fbRasterizeEdges4
+
+#if BITMAP_BIT_ORDER == LSBFirst
+#define Shift4(o)	((o) << 2)
+#else
+#define Shift4(o)	((1-(o)) << 2)
+#endif
+
+#define Get4(x,o)	(((x) >> Shift4(o)) & 0xf)
+#define Put4(x,o,v)	(((x) & ~(0xf << Shift4(o))) | (((v) & 0xf) << Shift4(o)))
+
+#define DefineAlpha(line,x) \
+    CARD8   *__ap = (CARD8 *) line + ((x) >> 1); \
+    int	    __ao = (x) & 1
+
+#define StepAlpha	((__ap += __ao), (__ao ^= 1))
+
+#define AddAlpha(a) {						\
+    CARD8   __o = *__ap;					\
+    CARD8   __a = (a) + Get4(__o, __ao);			\
+    *__ap = Put4 (__o, __ao, __a | (0 - ((__a) >> 4)));		\
+}
+
+#include "fbedgeimp.h"
+
+#undef AddAlpha
+#undef StepAlpha
+#undef DefineAlpha
+#undef rasterizeEdges
+#undef N_BITS
+
+
+/*
+ * 1 bit alpha
+ */
+
+#define N_BITS 1
+#define rasterizeEdges	fbRasterizeEdges1
+
+#include "fbedgeimp.h"
+
+#undef rasterizeEdges
+#undef N_BITS
+
+void
+fbRasterizeEdges (FbBits	*buf,
+		  int		bpp,
+		  int		width,
+		  int		stride,
+		  RenderEdge	*l,
+		  RenderEdge	*r,
+		  xFixed	t,
+		  xFixed	b)
+{
+    switch (bpp) {
+    case 1:
+	fbRasterizeEdges1 (buf, width, stride, l, r, t, b);
+	break;
+    case 4:
+	fbRasterizeEdges4 (buf, width, stride, l, r, t, b);
+	break;
+    case 8:
+	fbRasterizeEdges8 (buf, width, stride, l, r, t, b);
+	break;
+    }
+}
+
+#endif /* RENDER */
diff --git a/fb/fbedgeimp.h b/fb/fbedgeimp.h
new file mode 100644
index 000000000..4a91adc19
--- /dev/null
+++ b/fb/fbedgeimp.h
@@ -0,0 +1,134 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef rasterizeSpan
+#endif
+
+static void
+rasterizeEdges (FbBits		*buf,
+		int		width,
+		int		stride,
+		RenderEdge	*l,
+		RenderEdge	*r,
+		xFixed		t,
+		xFixed		b)
+{
+    xFixed  y = t;
+    FbBits  *line;
+    
+    line = buf + xFixedToInt (y) * stride;
+    
+    for (;;)
+    {
+	xFixed	lx, rx;
+	int	lxi, rxi;
+	
+	/* clip X */
+	lx = l->x;
+	if (lx < 0)
+	    lx = 0;
+	rx = r->x;
+	if (xFixedToInt (rx) >= width)
+	    rx = IntToxFixed (width);
+	
+	/* Skip empty (or backwards) sections */
+	if (rx > lx)
+	{
+
+	    /* Find pixel bounds for span */
+	    lxi = xFixedToInt (lx);
+	    rxi = xFixedToInt (rx);
+
+#if N_BITS == 1
+	    {
+		FbBits  *a = line;
+		FbBits  startmask, endmask;
+		int	    nmiddle;
+		int	    width = rxi - lxi;
+		int	    x = lxi;
+
+		a += x >> FB_SHIFT;
+		x &= FB_MASK;
+
+		FbMaskBits (x, width, startmask, nmiddle, endmask);
+		if (startmask)
+		    *a++ |= startmask;
+		while (nmiddle--)
+		    *a++ = FB_ALLONES;
+		if (endmask)
+		    *a |= endmask;
+	    }
+#else
+	    {
+		DefineAlpha(line,lxi);
+		int	    lxs, rxs;
+
+		/* Sample coverage for edge pixels */
+		lxs = RenderSamplesX (lx, N_BITS);
+		rxs = RenderSamplesX (rx, N_BITS);
+
+		/* Add coverage across row */
+		if (lxi == rxi)
+		{
+		    AddAlpha (rxs - lxs);
+		}
+		else
+		{
+		    int	xi;
+
+		    AddAlpha (N_X_FRAC(N_BITS) - lxs);
+		    StepAlpha;
+		    for (xi = lxi + 1; xi < rxi; xi++)
+		    {
+			AddAlpha (N_X_FRAC(N_BITS));
+			StepAlpha;
+		    }
+		    AddAlpha (rxs);
+		}
+	    }
+#endif
+	}
+
+	if (y == b)
+	    break;
+
+#if N_BITS > 1
+	if (xFixedFrac (y) != Y_FRAC_LAST(N_BITS))
+	{
+	    RenderEdgeStepSmall (l);
+	    RenderEdgeStepSmall (r);
+	    y += STEP_Y_SMALL(N_BITS);
+	}
+	else
+#endif
+	{
+	    RenderEdgeStepBig (l);
+	    RenderEdgeStepBig (r);
+	    y += STEP_Y_BIG(N_BITS);
+	    line += stride;
+	}
+    }
+}
+
+#undef rasterizeSpan
diff --git a/fb/fbpict.c b/fb/fbpict.c
index 2abdd32d5..ff638e5ce 100644
--- a/fb/fbpict.c
+++ b/fb/fbpict.c
@@ -1230,6 +1230,8 @@ fbPictureInit (ScreenPtr pScreen, PictFormatPtr formats, int nformats)
     ps->Glyphs = miGlyphs;
     ps->CompositeRects = miCompositeRects;
     ps->RasterizeTrapezoid = fbRasterizeTrapezoid;
+    ps->AddTraps = fbAddTraps;
+    ps->AddTriangles = fbAddTriangles;
 
 #endif /* RENDER */
 
diff --git a/fb/fbpict.h b/fb/fbpict.h
index cbf213b64..4b09bc881 100644
--- a/fb/fbpict.h
+++ b/fb/fbpict.h
@@ -25,6 +25,8 @@
 #ifndef _FBPICT_H_
 #define _FBPICT_H_
 
+#include "renderedge.h"
+
 #define FbIntMult(a,b,t) ( (t) = (a) * (b) + 0x80, ( ( ( (t)>>8 ) + (t) )>>8 ) )
 #define FbIntDiv(a,b)	 (((CARD16) (a) * 255) / (b))
 
@@ -199,6 +201,15 @@ typedef struct _FbAccessMap {
  */
 extern FbAccessMap  fbAccessMap[];
 
+/* fbaddtrap.c */
+
+void
+fbAddTraps (PicturePtr	pPicture,
+	    INT16	xOff,
+	    INT16	yOff,
+	    int		ntrap,
+	    xTrap	*traps);
+
 /* fbcompose.c */
 
 typedef struct _fbCompSrc {
@@ -817,6 +828,17 @@ fbCompositeGeneral (CARD8	op,
 		    CARD16	height);
 
 
+/* fbedge.c */
+void
+fbRasterizeEdges (FbBits	*buf,
+		  int		bpp,
+		  int		width,
+		  int		stride,
+		  RenderEdge	*l,
+		  RenderEdge	*r,
+		  xFixed	t,
+		  xFixed	b);
+
 /* fbpict.c */
 CARD32
 fbOver (CARD32 x, CARD32 y);
@@ -1024,10 +1046,25 @@ fbComposite (CARD8      op,
 	     CARD16     height);
 
 /* fbtrap.c */
+
+void
+fbAddTraps (PicturePtr	pPicture,
+	    INT16	xOff,
+	    INT16	yOff,
+	    int		ntrap,
+	    xTrap	*traps);
+
 void
 fbRasterizeTrapezoid (PicturePtr    alpha,
 		      xTrapezoid    *trap,
 		      int	    x_off,
 		      int	    y_off);
 
+void
+fbAddTriangles (PicturePtr  pPicture,
+		INT16	    xOff,
+		INT16	    yOff,
+		int	    ntri,
+		xTriangle   *tris);
+
 #endif /* _FBPICT_H_ */
diff --git a/fb/fbtrap.c b/fb/fbtrap.c
index 8fcd2b5cc..09bff0bfd 100644
--- a/fb/fbtrap.c
+++ b/fb/fbtrap.c
@@ -1,30 +1,26 @@
 /*
- * $XFree86: xc/programs/Xserver/fb/fbtrap.c,v 1.9 2002/09/26 02:56:48 keithp Exp $
+ * $Id$
  *
- * Copyright © 2000 University of Southern California
+ * Copyright © 2004 Keith Packard
  *
- * Permission to use, copy, modify, distribute, and sell this software
- * and its documentation for any purpose is hereby granted without
- * fee, provided that the above copyright notice appear in all copies
- * and that both that copyright notice and this permission notice
- * appear in supporting documentation, and that the name of University
- * of Southern California not be used in advertising or publicity
- * pertaining to distribution of the software without specific,
- * written prior permission.  University of Southern California makes
- * no representations about the suitability of this software for any
- * purpose.  It is provided "as is" without express or implied
- * warranty.
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
  *
- * University of Southern California DISCLAIMS ALL WARRANTIES WITH
- * REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE BE LIABLE FOR
- * ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
- * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
- * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
- * SOFTWARE.
- *
- * Author: Carl Worth, USC, Information Sciences Institute */
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
 
 #include "fb.h"
 
@@ -32,1351 +28,208 @@
 
 #include "picturestr.h"
 #include "mipict.h"
+#include "renderedge.h"
 #include "fbpict.h"
 
-#ifdef DEBUG
-#include <stdio.h>
-#include <assert.h>
-
-#define ASSERT(e)   assert(e)
-
-#endif
-
-#ifndef ASSERT
-#define ASSERT(e)
-#endif
-
-#define MAX(a, b) ((a) > (b) ? (a) : (b))
-#define MIN(a, b) ((a) < (b) ? (a) : (b))
-
-#define MAX_AREA 0x80000000
-
-/*
- * A RationalPoint is an exact position along one of the trapezoid
- * edges represented by an approximate position (x,y) and two error
- * terms (ex_dy, ey_dx).  The error in X is multiplied by the Y 
- * dimension of the line while the error in Y is multiplied by the
- * X dimension of the line, allowing an exact measurement of the
- * distance from (x,y) to the line.
- *
- * Generally, while walking an edge, one of ex_dy/ey_dx will be zero
- * indicating that the position error is held in the other.
- */
-typedef struct {
-    xFixed x;
-    xFixed ex_dy;
-    xFixed y;
-    xFixed ey_dx;
-} RationalPoint;
-
-/*
- * Edges are walked both horizontally and vertically
- * They are walked vertically to get to a particular row
- * of pixels, and then walked horizontally within that row
- * to compute pixel coverage.
- *
- * Edges are always walked from top to bottom and from
- * left to right.  This means that for lines moving leftwards
- * from top to bottom, the left to right walking actually moves
- * backwards along the line with respect to the top to bottom
- * walking.
- */
-
-/*
- * A RationalRow represents the two positions where
- * an edge intersects a row of pixels.  This is used
- * to walk an edge vertically
- */
-
-typedef struct {
-    RationalPoint   top;	/* intersection at top of row */
-    RationalPoint   bottom;	/* intersection at bottom of row */
-    RationalPoint   pixel_top;	/* intersection at top of pixel */
-} RationalRow;
-
-/*
- * A RationalCol represents the two positions where
- * an edge intersects a column of pixels
- */
-
-typedef struct {
-    RationalPoint   left;	/* intersection at left of column */
-    RationalPoint   right;	/* intersection at right of column */
-} RationalCol;
-
-/*
-  Here are some thoughts on line walking:
-
-  Conditions: c2.x - c1.x = 1
-  	      r2.y - r1.y = 1
-
-    A       B       C       D       E        F       G        H
-                c1\      c1           c2       /c2
-r1      r1        |\      \ r1     r1 /     r1/|        r1        r1
-\-+---+ \-+---+   +-\-+   +\--+   +--/+    +-/-+   +---+-/  +---+-/ 
- \|   |  `.c1 |   |r1\|   | \ |   | / |    |/  |   |   .'   |   |/
-c1\   |   |`-.|c2 |   \c2 | | |   | | |  c1/   | c1|,_/|c2  |   /c2
-  |\  |   |   `.  |   |\  | \ |   | / |   /|   |  ./   |    |  /|
-  +-\-+   +---+-\ +---+-\ +--\+   +/--+  /-+---+ /-+---+    +-/-+
-   r2\|        r2      r2   r2\   /r2    r2      r2         |/r2
-      \c2                     c2 c1                       c1/
-
- Bottom   Right   Right   Bottom   Top      Top    Right    Right
-
-State transitions:
-
-A -> C, D       	E -> E, F
-B -> A, B          	F -> G, H
-C -> A, B       	G -> G, H
-D -> C, D       	H -> E, F
-
-*/
-
-/*
- * Values for PixelWalk.depart. Top and Bottom can have the same value
- * as only one mode is possible given a line of either positive or
- * negative slope.  These mark the departure edge while walking
- * rightwards across columns.
- */
-
-typedef enum _departure {
-    DepartTop = 0,	    /* edge exits top of pixel */
-    DepartBottom = 0,	    /* edge exits bottom of pixel */
-    DepartRight = 1	    /* edge exits right edge of pixel */
-} Departure;
-
-/*
- * PixelWalk
- *
- * This structure holds state to walk a single edge down the trapezoid.
- *
- * The edge is walked twice -- once by rows and once by columns.
- * The two intersections of the pixel by the edge are then set
- * from either the row or column position, depending on which edge 
- * is intersected.
- *
- * Note that for lines moving left, walking by rows moves down the
- * line (increasing y) while walking by columns moves up the line 
- * (decreasing y).
- */
-typedef struct {
-    xFixed dx;
-    xFixed ey_thresh;
-    xFixed dy;
-    xFixed ex_thresh;
-
-    Departure depart;
-
-    /* slope */
-    xFixed m;
-    xFixed em_dx;
-    xFixed y_correct;
-    xFixed ey_correct;
-
-    /* Inverse slope. Does this have a standard symbol? */
-    xFixed p;
-    xFixed ep_dy;
-    xFixed x_correct;
-    xFixed ex_correct;
-
-    /* Trapezoid bottom, used to limit walking to the last row */
-    xFixed bottom;
-
-    /*
-     * Current edge positions along pixel rows and columns
-     */
-    RationalRow row;
-    RationalCol col;
-
-    /*
-     * The three pixel intersection points, copied from the appropriate
-     * row or column position above
-     */
-    RationalPoint p_pixel_top;
-    RationalPoint p_trap_top;
-    RationalPoint p_trap_bottom;
-} PixelWalk;
-
-#if 0
-#ifdef GCC
-#define INLINE inline
-#endif
-#endif
-
-#ifndef INLINE
-#define INLINE
-#endif
-
-/* 
- * Step 'pt' vertically to 'newy'.
- */
-static INLINE void
-pixelWalkMovePointToRow (PixelWalk *pw, RationalPoint *pt, xFixed newy)
+void
+fbAddTraps (PicturePtr	pPicture,
+	    INT16	x_off,
+	    INT16	y_off,
+	    int		ntrap,
+	    xTrap	*traps)
 {
-    xFixed_32_32    oex;
-    xFixed	    xoff;
-
-    /* X error of old X position and new Y position */
-    oex = (xFixed_32_32) pw->dx * (newy - pt->y) - pt->ey_dx + pt->ex_dy;
+    FbBits	*buf;
+    int		bpp;
+    int		width;
+    int		stride;
+    int		height;
+    int		pxoff, pyoff;
+
+    xFixed	x_off_fixed;
+    xFixed	y_off_fixed;
+    RenderEdge  l, r;
+    xFixed	t, b;
     
-    /* amount to step X by */
-    xoff = oex / pw->dy;
+    fbGetDrawable (pPicture->pDrawable, buf, stride, bpp, pxoff, pyoff);
 
-    /* step X */
-    pt->x = pt->x + xoff;
+    width = pPicture->pDrawable->width;
+    height = pPicture->pDrawable->height;
+    x_off += pxoff;
+    y_off += pyoff;
     
-    /* set new X error value for new X position and new Y positition */
-    pt->ex_dy = oex - (xFixed_32_32) pw->dy * xoff;
+    x_off_fixed = IntToxFixed(y_off);
+    y_off_fixed = IntToxFixed(y_off);
 
-    /* set new Y position, set Y error to zero */
-    pt->y = newy;
-    pt->ey_dx = 0;
-}
-
-/*
- * Step 'pt' horizontally to 'newx' 
- */
-static INLINE void
-pixelWalkMovePointToCol (PixelWalk *pw, RationalPoint *pt, xFixed newx)
-{
-    xFixed_32_32    oey;
-    xFixed	    yoff;
-
-    /* Special case vertical lines to arbitrary y */
-    if (pw->dx == 0) 
+    while (ntrap--)
     {
-	pt->x = newx;
-	pt->ex_dy = 0;
-	pt->y = 0;
-	pt->ey_dx = 0;
-    }
-    else 
-    {
-	/* Y error of old Y position and new X position */
-	oey = (xFixed_32_32) pw->dy * (newx - pt->x) - pt->ex_dy + pt->ey_dx;
-
-	/* amount to step Y by */
-	yoff = oey / pw->dx;
-
-	/* step Y */
-	pt->y = pt->y + yoff;
-
-	/* set new Y error value for new Y position and new X position */
-	pt->ey_dx = oey - (xFixed_32_32) pw->dx * yoff;
-
-	/* set new X position, set X error to zero */
-	pt->x = newx;
-	pt->ex_dy = 0;
-    }
-}
-
-/*
- * Step the 'row' element of 'pw' vertically 
- * (increasing y) by one whole pixel
- */
-static INLINE void
-pixelWalkStepRow (PixelWalk *pw)
-{
-    xFixed  y_next = xFixedFloor (pw->row.bottom.y) + xFixed1;
+	t = traps->top.y + y_off_fixed;
+	if (t < 0)
+	    t = 0;
+	t = RenderSampleCeilY (t, bpp);
     
-    if (y_next > pw->bottom)
-	y_next = pw->bottom;
-
-    /* pw.row.top.y < pw.row.bottom.y */
-    pw->row.top = pw->row.bottom;
-
-    if (y_next - pw->row.bottom.y == xFixed1)
-    {
-	pw->row.pixel_top = pw->row.bottom;
-	pw->row.bottom.y += xFixed1;
-	pw->row.bottom.x += pw->p;
-	pw->row.bottom.ex_dy += pw->ep_dy;
-	if (abs (pw->row.bottom.ex_dy) > pw->ex_thresh) 
-	{
-	    pw->row.bottom.x += pw->x_correct;
-	    pw->row.bottom.ex_dy += pw->ex_correct;
-	}
-    }
-    else
-    {
-	pixelWalkMovePointToRow (pw, &pw->row.pixel_top, 
-				 xFixedCeil (y_next) - xFixed1);
-	pixelWalkMovePointToRow (pw, &pw->row.bottom, y_next);
-    }
-}
-
-/*
- * Step the 'col' element of 'pw' horizontally
- * (increasing x) by one whole pixel
- */
-static INLINE void
-pixelWalkStepCol (PixelWalk *pw)
-{
-    /* pw.col.p1.x < pw.col.p2.x */
-    /*
-     * Copy the current right point into the left point
-     */
-    pw->col.left = pw->col.right;
-
-    /*
-     * Now incrementally walk across the pixel
-     */
-    pw->col.right.x += xFixed1;
-    pw->col.right.y += pw->m;
-    pw->col.right.ey_dx += pw->em_dx;
-    if (pw->col.right.ey_dx > pw->ey_thresh) 
-    {
-	pw->col.right.y += pw->y_correct;
-	pw->col.right.ey_dx += pw->ey_correct;
-    }
-}
-/*
- * Walk to the nearest edge of the next pixel, filling in both p1 and
- * p2 as necessary from either the row or col intersections.
- *
- * The "next" pixel is defined to be the next pixel intersected by the
- * line with pixels visited in raster scan order, (for the benefit of
- * cache performance). For lines with positive slope it is easy to
- * achieve raster scan order by simply calling StepCol for each pixel
- * in a given scanline, then calling StepRow once at the end of each
- * scanline.
- *
- * However, for lines of negative slope where the magnitude of dx is
- * greater than dy, a little more work needs to be done. The pixels of
- * a particular scanline will be visited by succesive calls to StepCol
- * as before. This will effectively step "up" the line as we scan from
- * left to right. But, the call to StepRow at the end of the scan line
- * will step "down" the line and the column information will be
- * invalid at that point.
- *
- * For now, I fix up the column of all negative slope lines by calling
- * MovePointToCol at the end of each scanline. However, this is an
- * extremely expensive operation since it involves a 64-bit multiply
- * and a 64-bit divide. It would be much better, (at least as long as
- * abs(dx) is not much greater than dy), to instead step the col
- * backwards as many times as necessary. Or even better, we could
- * simply restore col to the position it began at when we started the
- * scanline, then simply step it backwards once. That would give a
- * performance benefit for lines with slope of any magnitude. 
- */
-
-static INLINE void
-pixelWalkNextPixel (PixelWalk *pw)
-{
-    if (pw->dx < 0) 
-    {
-	/* 
-	 * left moving lines
-	 *
-	 * Check which pixel edge we're departing from 
-	 *
-	 * Remember that in this case (dx < 0), the 'row' element of 'pw'
-	 * walks down the line while 'col' walks up
-	 */
-	if (pw->depart == DepartTop) 
-	{
-	    /*
-	     * The edge departs the row at this pixel, the
-	     * next time it gets used will be for the next row
-	     *
-	     * Step down one row and then recompute the
-	     * column values to start the next row of
-	     * pixels
-	     */
-	    pixelWalkStepRow(pw);
-	    /*
-	     * Set column exit pixel
-	     */
-	    pixelWalkMovePointToCol(pw, &pw->col.right, xFixedFloor(pw->row.bottom.x));
-	    /*
-	     * This moves the exit pixel to the entry pixel
-	     * and computes the next exit pixel
-	     */
-	    pixelWalkStepCol(pw);
-	    /*
-	     * The first pixel on the next row will always
-	     * be entered from below, set the lower
-	     * intersection of this edge with that pixel
-	     */
-	    pw->p_trap_bottom = pw->row.bottom;
-	} 
-	else	/* pw->depart == DepartRight */
-	{ 
-	    /*
-	     * easy case -- just move right one pixel 
-	     */
-	    pixelWalkStepCol(pw);
-	    /* 
-	     * Set the lower intersection of the edge with the
-	     * pixel -- that's just where the edge entered
-	     * the pixel from the left
-	     */
-	    pw->p_trap_bottom = pw->col.left;
-	}
-	/*
-	 * Now compute which edge the pixel
-	 * is departing from
-	 */
-	if (pw->row.top.x <= pw->col.right.x) 
-	{
-	    /* 
-	     * row intersection is left of column intersection,
-	     * that means the edge hits the top of the pixel
-	     * before it hits the right edge
-	     */
-	    pw->p_trap_top = pw->row.top;
-	    pw->depart = DepartTop;
-	    /*
-	     * Further check to see whether the edge
-	     * leaves the right or top edge of the
-	     * whole pixel
-	     */
-	    if (pw->row.pixel_top.x <= pw->col.right.x)
-		pw->p_pixel_top = pw->row.pixel_top;
-	    else
-		pw->p_pixel_top = pw->col.right;
-	}
-	else 
-	{
-	    /*
-	     * Row intersection is right of colum intersection,
-	     * that means the edge hits the right edge of the
-	     * pixel first
-	     */
-	    pw->p_trap_top = pw->col.right;
-	    pw->p_pixel_top = pw->col.right;
-	    pw->depart = DepartRight;
-	}
-    } 
-    else 
-    {
-	/*
-	 * right moving lines
-	 *
-	 * Check which edge we're departing from
-	 *
-	 * In the dx >= 0 case, the row and col elements both
-	 * walk downwards
-	 */
-	if (pw->depart == DepartBottom) 
-	{
-	    /*
-	     * The edge departs the row at this pixel,
-	     * the next time it gets used will be for the
-	     * next row
-	     *
-	     * Step down one row and (maybe) over one
-	     * column to prepare for the next row
-	     */
-	    if (pw->row.bottom.x == pw->col.right.x)
-	    {
-		/* 
-		 * right through the corner of the pixel,
-		 * adjust the column
-		 */
-		pixelWalkStepCol(pw);
-	    }
-	    pixelWalkStepRow(pw);
-	    /*
-	     * Set the upper intersection of the edge with
-	     * the pixel, the first pixel on the next
-	     * row is always entered from the top
-	     */
-	    pw->p_trap_top = pw->row.top;
-	    pw->p_pixel_top = pw->row.pixel_top;
-	}
-	else	/* pw->depart == DepartRight */
-	{ 
-	    /*
-	     * Easy case -- move right one
-	     * pixel
-	     */
-	    pixelWalkStepCol(pw);
-	    /*
-	     * Set the upper intersection of the edge
-	     * with the pixel, that's along the left
-	     * edge of the pixel
-	     */
-	    pw->p_trap_top = pw->col.left;
-	    pw->p_pixel_top = pw->col.left;
-	}
-	/*
-	 * Now compute the exit edge and the
-	 * lower intersection of the edge with the pixel
-	 */
-	if (pw->row.bottom.x <= pw->col.right.x) 
-	{
-	    /*
-	     * Hit the place where the edge leaves
-	     * the pixel, the lower intersection is
-	     * where the edge hits the bottom
-	     */
-	    pw->p_trap_bottom = pw->row.bottom;
-	    pw->depart = DepartBottom;
-	}
-	else 
-	{
-	    /*
-	     * The edge goes through the
-	     * next pixel on the row,
-	     * the lower intersection is where the
-	     * edge hits the right side of the pixel
-	     */
-	    pw->p_trap_bottom = pw->col.right;
-	    pw->depart = DepartRight;
-	}
-    }
-}
-
-/*
- * Compute the first pixel intersection points
- * and the departure type from that pixel
- */
-static void 
-pixelWalkFirstPixel (PixelWalk *pw)
-{
-    if (pw->dx < 0) 
-    {
-	if (pw->row.top.x <= pw->col.right.x) 
-	{
-	    /*
-	     * leaving through the top.
-	     * upper position is the upper point of
-	     * the 'row' element
-	     */
-	    pw->depart = DepartTop;
-	    pw->p_trap_top = pw->row.top;
-	    /*
-	     * further check for pixel top
-	     */
-	    if (pw->row.pixel_top.x <= pw->col.right.x)
-		pw->p_pixel_top = pw->row.pixel_top;
-	    else
-		pw->p_pixel_top = pw->col.right;
-	}
-	else 
-	{
-	    /*
-	     * leaving through the right side
-	     * upper position is the right point of
-	     * the 'col' element
-	     */
-	    pw->depart = DepartRight;
-	    pw->p_trap_top = pw->col.right;
-	    pw->p_pixel_top = pw->col.right;
-	}
-	/*
-	 * Now find the lower pixel intersection point
-	 */
-	if (pw->row.bottom.x >= pw->col.left.x)
-	    /*
-	     * entering through bottom,
-	     * lower position is the bottom point of
-	     * the 'row' element
-	     */
-	    pw->p_trap_bottom = pw->row.bottom;
-	else
-	    /*
-	     * entering through left side,
-	     * lower position is the left point of
-	     * the 'col' element
-	     */
-	    pw->p_trap_bottom = pw->col.left;
-    }
-    else 
-    {
-	if (pw->row.bottom.x <= pw->col.right.x)
-	{
-	    /*
-	     * leaving through the bottom (or corner).
-	     * lower position is the lower point of
-	     * the 'row' element
-	     */
-	    pw->depart = DepartBottom;
-	    pw->p_trap_bottom = pw->row.bottom;
-	} 
-	else 
-	{
-	    /*
-	     * leaving through the right side
-	     * lower position is the right point of
-	     * the 'col' element
-	     */
-	    pw->depart = DepartRight;
-	    pw->p_trap_bottom = pw->col.right;
-	}
-	/*
-	 * Now find the upper pixel intersection point
-	 */
-	if (pw->row.top.x >= pw->col.left.x)
-	{
-	    /*
-	     * entering through the top (or corner),
-	     * upper position is the top point
-	     * of the 'row' element
-	     */
-	    pw->p_trap_top = pw->row.top;
-	    /*
-	     * further check for pixel entry
-	     */
-	    if (pw->row.pixel_top.x >= pw->col.left.x)
-		pw->p_pixel_top = pw->row.pixel_top;
-	    else
-		pw->p_pixel_top = pw->col.left;
-	}
-	else
-	{
-	    /*
-	     * entering through the left side,
-	     * upper position is the left point of
-	     * the 'col' element
-	     */
-	    pw->p_trap_top = pw->col.left;
-	    pw->p_pixel_top = pw->col.left;
+	b = traps->bot.y + y_off_fixed;
+	if (xFixedToInt (b) >= height)
+	    b = IntToxFixed (height) - 1;
+	b = RenderSampleFloorY (b, bpp);
+	
+	if (b >= t)
+	{
+	    /* initialize edge walkers */
+	    RenderEdgeInit (&l, bpp, t,
+			    traps->top.l + x_off_fixed,
+			    traps->top.y + y_off_fixed,
+			    traps->bot.l + x_off_fixed,
+			    traps->bot.y + y_off_fixed);
+	
+	    RenderEdgeInit (&r, bpp, t,
+			    traps->top.r + x_off_fixed,
+			    traps->top.y + y_off_fixed,
+			    traps->bot.r + x_off_fixed,
+			    traps->bot.y + y_off_fixed);
+	    
+	    fbRasterizeEdges (buf, bpp, width, stride, &l, &r, t, b);
 	}
+	traps++;
     }
 }
 
-static void 
-pixelWalkInit (PixelWalk *pw, xLineFixed *line, xFixed top_y, xFixed bottom_y)
+void
+fbRasterizeTrapezoid (PicturePtr    pPicture,
+		      xTrapezoid  *trap,
+		      int	    x_off,
+		      int	    y_off)
 {
-    xFixed_32_32    dy_inc, dx_inc;
-    xFixed	    next_y;
-    xFixed	    left_x;
-    xPointFixed	    *top, *bot;
-
-    next_y = xFixedFloor (top_y) + xFixed1;
-    if (next_y > bottom_y)
-	next_y = bottom_y;
-
-    /*
-     * Orient lines top down
-     */
-    if (line->p1.y < line->p2.y) 
-    {
-	top = &line->p1;
-	bot = &line->p2;
-    }
-    else
-    {
-	top = &line->p2;
-	bot = &line->p1;
-    }
-
-    pw->dx = bot->x - top->x;
-    pw->ey_thresh = abs(pw->dx >> 1);
-    pw->dy = bot->y - top->y;
-    pw->ex_thresh = pw->dy >> 1;
-
-    /*
-     * Set step values for walking lines
-     */
-    if (pw->dx < 0) 
-    {
-	pw->x_correct = -1;
-	pw->ex_correct = pw->dy;
-	pw->y_correct = -1;
-	pw->ey_correct = pw->dx;
-    }
-    else 
-    {
-	pw->x_correct = 1;
-	pw->ex_correct = -pw->dy;
-	pw->y_correct = 1;
-	pw->ey_correct = -pw->dx;
-    }
-
-    pw->bottom = bottom_y;
-
-    /*
-     * Compute Bresenham values for walking edges incrementally
-     */
-    dy_inc = (xFixed_32_32) xFixed1 * pw->dy;			/* > 0 */
-    if (pw->dx != 0) 
-    {
-	pw->m = dy_inc / pw->dx;				/* sign(dx) */
-	pw->em_dx = dy_inc - (xFixed_32_32) pw->m * pw->dx;	/* > 0 */
-    }
-    else 
-    {
-	/* Vertical line. Setting these to zero prevents us from
-           having to put any conditions in pixelWalkStepCol. */
-	pw->m = 0;
-	pw->em_dx = 0;
-    }
-
-    dx_inc = (xFixed_32_32) xFixed1 * (xFixed_32_32) pw->dx;	/* sign(dx) */
-    pw->p = dx_inc / pw->dy;					/* sign(dx) */
-    pw->ep_dy = dx_inc - (xFixed_32_32) pw->p * pw->dy;		/* sign(dx) */
-
-    /*
-     * Initialize 'row' for walking down rows
-     */
-    pw->row.bottom.x = top->x;
-    pw->row.bottom.ex_dy = 0;
-    pw->row.bottom.y = top->y;
-    pw->row.bottom.ey_dx = 0;
-
-    /*
-     * Initialize 'pixel_top' to be on the line for
-     * the first step
-     */
-    pw->row.pixel_top = pw->row.bottom;
-    /*
-     * Move to the pixel above the 'top_y' coordinate,
-     * first setting 'bottom' and then using StepRow
-     * which moves that to 'top' and computes the next 'bottom'
-     */
-    pixelWalkMovePointToRow(pw, &pw->row.bottom, top_y);
-    pixelWalkStepRow(pw);
-
-    /*
-     * Initialize 'col' for walking across columns
-     */
-    pw->col.right.x = top->x;
-    pw->col.right.ex_dy = 0;
-    pw->col.right.y = top->y;
-    pw->col.right.ey_dx = 0;
-
-    /*
-     * First set the column to the left most
-     * pixel hit by the row
-     */
-    if (pw->dx < 0)
-	left_x = pw->row.bottom.x;
-    else
-	left_x = pw->row.top.x;
+    FbBits	*buf;
+    int		bpp;
+    int		width;
+    int		stride;
+    int		height;
+    int		pxoff, pyoff;
+
+    xFixed	x_off_fixed;
+    xFixed	y_off_fixed;
+    RenderEdge	l, r;
+    xFixed	t, b;
     
-    pixelWalkMovePointToCol(pw, &pw->col.right, xFixedFloor (left_x));
-    pixelWalkStepCol(pw);
-    
-    /*
-     * Compute first pixel intersections and the
-     * first departure state
-     */
-    pixelWalkFirstPixel (pw);
-}
-
-#define RoundShift(a,b) (((a) + (1 << ((b) - 1))) >> (b))
-#define MaxAlpha(depth) ((1 << (depth)) - 1)
-
-#define AreaAlpha(area, depth) (RoundShift (RoundShift (area, depth) *  \
-					    MaxAlpha (depth), \
-					    (31 - depth)))
-
-/*
-  Pixel coverage from the upper-left corner bounded by one horizontal
-  bottom line (bottom) and one line defined by two points, (x1,y1) and
-  (x2,y2), which intersect the pixel. y1 must be less than y2. There
-  are 8 cases yielding the following area calculations:
-
-  A     B     C     D     E     F     G     H
-+---+ +---+ +-1-+ +1--+ +--1+ +-1-+ +---+ +---+ 
-|   | 1   | |  \| | \ | | / | |/  | |   1 |   |
-1   | |`-.| |   2 | | | | | | 2   | |,_/| |   1
-|\  | |   2 |   | | \ | | / | |   | 2   | |  /|
-+-2-+ +---+ +---+ +--2+ +2--+ +---+ +---+ +-2-+
-
-A:  (1/2 *       x2  * (y2 - y1))
-B:  (1/2 *       x2  * (y2 - y1)) + (bottom - y2) * x2
-C:  (1/2 * (x1 + x2) *  y2      ) + (bottom - y2) * x2
-D:  (1/2 * (x1 + x2) *  y2      )
-E:  (1/2 * (x1 + x2) *  y2      )
-F:  (1/2 *  x1       *  y2      )
-G:  (1/2 *  x1       * (y2 - y1))                      + x1 * y1
-H:  (1/2 * (x1 + x2) * (y2 - y1))                      + x1 * y1
-
-The union of these calculations is valid for all cases. Namely:
-
-    (1/2 * (x1 + x2) * (y2 - y1)) + (bottom - y2) * x2 + x1 * y1
-
-An exercise for later would perhaps be to optimize the calculations
-for some of the cases above. Specifically, it's possible to eliminate
-multiplications by zero in several cases, leaving a maximum of two
-multiplies per pixel calculation. (This is even more promising now
-that the higher level code actually computes the exact same 8 cases
-as part of its pixel walking).
-
-But, for now, I just want to get something working correctly even if
-slower. So, we'll use the non-optimized general equation.
-
-*/
-
-/* 1.16 * 1.16 -> 1.31 */
-#define AREA_MULT(w, h) ( (xFixed_1_31) (((((xFixed_1_16)w)*((xFixed_1_16)h) + 1) >> 1) | (((xFixed_1_16)w)&((xFixed_1_16)h)&0x10000) << 15))
-
-/* (1.16 + 1.16) / 2 -> 1.16 */
-#define WIDTH_AVG(x1,x2) (((x1) + (x2) + 1) >> 1)
-
-#define SubPixelArea(x1, y1, x2, y2, bottom)	\
-(xFixed_1_31) ( 						\
-   AREA_MULT((x1), (y1))			\
- + AREA_MULT(WIDTH_AVG((x1), (x2)), (y2) - (y1))\
- + AREA_MULT((x2), (bottom) - (y2))		\
-)
+    fbGetDrawable (pPicture->pDrawable, buf, stride, bpp, pxoff, pyoff);
 
-/*
-static xFixed_1_31
-SubPixelArea (xFixed_1_16	x1,
-              xFixed_1_16       y1,
-              xFixed_1_16       x2,
-              xFixed_1_16       y2,
-              xFixed_1_16       bottom)
-{
-    xFixed_1_16	    x_trap;
-    xFixed_1_16     h_top, h_trap, h_bot;
-    xFixed_1_31     area;
-    
-    x_trap = WIDTH_AVG(x1,x2);
-    h_top = y1;
-    h_trap = (y2 - y1);
-    h_bot = (bottom - y2);
+    width = pPicture->pDrawable->width;
+    height = pPicture->pDrawable->height;
+    x_off += pxoff;
+    y_off += pyoff;
     
-    area = AREA_MULT(x1, h_top) +
-	AREA_MULT(x_trap, h_trap) +
-	AREA_MULT(x2, h_bot);
-    
-    return area;
-}
-*/
-
-#define SubPixelAlpha(x1, y1, x2, y2, bottom, depth)		\
-(								\
-    AreaAlpha(							\
-	SubPixelArea((x1), (y1), (x2), (y2), (bottom)),		\
-	(depth)							\
-    )								\
-)
-
-/*
-static int
-SubPixelAlpha (xFixed_1_16	x1,
-	       xFixed_1_16	y1,
-	       xFixed_1_16	x2,
-	       xFixed_1_16	y2,
-	       xFixed_1_16	bottom,
-	       int		depth)
-{
-    xFixed_1_31	area;
-
-    area = SubPixelArea(x1, y1, x2, y2, bottom);
+    x_off_fixed = IntToxFixed(x_off);
+    y_off_fixed = IntToxFixed(y_off);
+    t = trap->top + y_off_fixed;
+    if (t < 0)
+	t = 0;
+    t = RenderSampleCeilY (t, bpp);
+
+    b = trap->bottom + y_off_fixed;
+    if (xFixedToInt (b) >= height)
+	b = IntToxFixed (height) - 1;
+    b = RenderSampleFloorY (b, bpp);
     
-    return AreaAlpha(area, depth);
+    if (b >= t)
+    {
+	/* initialize edge walkers */
+	RenderLineFixedEdgeInit (&l, bpp, t, &trap->left, x_off, y_off);
+	RenderLineFixedEdgeInit (&r, bpp, t, &trap->right, x_off, y_off);
+	
+	fbRasterizeEdges (buf, bpp, width, stride, &l, &r, t, b);
+    }
 }
-*/
-
-/* Alpha of a pixel above a given horizontal line */
-#define AlphaAbove(pixel_y, line_y, depth)			\
-(								\
-    AreaAlpha(AREA_MULT((line_y) - (pixel_y), xFixed1), depth)	\
-)
 
 static int
-RectAlpha(xFixed pixel_y, xFixed top, xFixed bottom, int depth)
+_GreaterY (xPointFixed *a, xPointFixed *b)
 {
-    if (depth == 1)
-	return top == pixel_y ? 1 : 0;
-    else
-	return (AlphaAbove (pixel_y, bottom, depth) -
-		AlphaAbove (pixel_y, top, depth));
+    if (a->y == b->y)
+	return a->x > b->x;
+    return a->y > b->y;
 }
 
-
 /*
- * Pixel coverage from the left edge bounded by one horizontal lines,
- * (top and bottom), as well as one PixelWalk line.
+ * Note that the definition of this function is a bit odd because
+ * of the X coordinate space (y increasing downwards).
  */
 static int
-AlphaAboveLeft(RationalPoint	*upper,
-	       RationalPoint	*lower,
-	       xFixed		bottom,
-	       xFixed		pixel_x,
-	       xFixed		pixel_y,
-	       int		depth)
+_Clockwise (xPointFixed *ref, xPointFixed *a, xPointFixed *b)
 {
-    return SubPixelAlpha(upper->x - pixel_x,
-			 upper->y - pixel_y,
-			 lower->x - pixel_x,
-			 lower->y - pixel_y,
-			 bottom - pixel_y,
-			 depth);
-}
-
-/*
-  Pixel coverage from the left edge bounded by two horizontal lines,
-  (top and bottom), as well as one line two points, p1 and p2, which
-  intersect the pixel. The following condition must be true:
+    xPointFixed	ad, bd;
 
-  p2.y > p1.y
-*/
-
-/*
-          lr
-           |\
-        +--|-\-------+
-        | a| b\      |
-    =======|===\========== top
-        | c| d  \    |
-    =======|=====\======== bot
-        |  |      \  |
-        +--|-------\-+
+    ad.x = a->x - ref->x;
+    ad.y = a->y - ref->y;
+    bd.x = b->x - ref->x;
+    bd.y = b->y - ref->y;
 
-   alpha(d) = alpha(cd) - alpha(c) = alpha(abcd) - alpha(ab) - (alpha(ac) - alpha(c))
-
-   alpha(d) = pixelalpha(top, bot, right) - pixelalpha(top, bot, left)
-
-   pixelalpha(top, bot, line) = subpixelalpha(bot, line) - subpixelalpha(top, line)
-*/
-
-static int
-PixelAlpha(xFixed	pixel_x,
-	   xFixed	pixel_y,
-	   xFixed	top,
-	   xFixed	bottom,
-	   PixelWalk	*pw,
-	   int		depth)
-{
-    int alpha;
-
-#ifdef DEBUG
-    fprintf(stderr, "alpha (%f, %f) - (%f, %f) = ",
-	    (double) pw->p1.x / (1 << 16),
-	    (double) pw->p1.y / (1 << 16),
-	    (double) pw->p2.x / (1 << 16),
-	    (double) pw->p2.y / (1 << 16));
-    fflush(stderr);
-#endif
-
-    /*
-     * Sharp polygons are different, alpha is 1 if the
-     * area includes the pixel origin, else zero, in
-     * the above figure, only 'a' has alpha 1
-     */
-    if (depth == 1)
-    {
-	alpha = 0;
-	if (top == pixel_y && pw->p_pixel_top.x != pixel_x)
-	    alpha = 1;
-    }
-    else
-    {
-	alpha = (AlphaAboveLeft(&pw->p_pixel_top, &pw->p_trap_bottom,
-				bottom, pixel_x, pixel_y, depth) 
-		 - AlphaAboveLeft(&pw->p_pixel_top, &pw->p_trap_top,
-				  top, pixel_x, pixel_y, depth));
-    }
-    
-#ifdef DEBUG
-    fprintf(stderr, "0x%x => %f\n",
-	    alpha,
-	    (double) alpha / ((1 << depth) -1 ));
-    fflush(stderr);
-#endif
-
-    return alpha;
+    return ((xFixed_32_32) bd.y * ad.x - (xFixed_32_32) ad.y * bd.x) < 0;
 }
 
-#define INCREMENT_X_AND_PIXEL		\
-{					\
-    pixel_x += xFixed1;			\
-    (*mask.over) (&mask);		\
-}
-
-/* XXX: What do we really want this prototype to look like? Do we want
-   separate versions for 1, 4, 8, and 16-bit alpha? */
-
-#define saturateAdd(t, a, b) (((t) = (a) + (b)), \
-			       ((CARD8) ((t) | (0 - ((t) >> 8)))))
-
-#define addAlpha(mask, depth, alpha, temp) (\
-    (*(mask)->store) ((mask), (alpha == (1 << depth) - 1) ? \
-		      0xff000000 : \
-		      (saturateAdd (temp,  \
-				    alpha << (8 - depth),  \
-				    (*(mask)->fetch) (mask) >> 24) << 24)) \
-)
-
+/* FIXME -- this could be made more efficient */
 void
-fbRasterizeTrapezoid (PicturePtr    pMask,
-		      xTrapezoid    *pTrap,
-		      int	    x_off,
-		      int	    y_off)
+fbAddTriangles (PicturePtr  pPicture,
+		INT16	    x_off,
+		INT16	    y_off,
+		int	    ntri,
+		xTriangle *tris)
 {
-    xTrapezoid	trap = *pTrap;
-    int alpha, temp;
-    
-    FbCompositeOperand	mask;
+    xPointFixed	  *top, *left, *right, *tmp;
+    xTrapezoid	    trap;
 
-    int depth = pMask->pDrawable->depth;
-    int max_alpha = (1 << depth) - 1;
-    int buf_width = pMask->pDrawable->width;
-
-    xFixed x_off_fixed = IntToxFixed(x_off);
-    xFixed y_off_fixed = IntToxFixed(y_off);
-    xFixed buf_width_fixed = IntToxFixed(buf_width);
-
-    PixelWalk left, right;
-    xFixed pixel_x, pixel_y;
-    xFixed first_right_x;
-    xFixed y, y_next;
-
-    /* trap.left and trap.right must be non-horizontal */
-    if (trap.left.p1.y == trap.left.p2.y
-	|| trap.right.p1.y == trap.right.p2.y) {
-	return;
-    }
-
-    trap.top += y_off_fixed;
-    trap.bottom += y_off_fixed;
-    trap.left.p1.x += x_off_fixed;
-    trap.left.p1.y += y_off_fixed;
-    trap.left.p2.x += x_off_fixed;
-    trap.left.p2.y += y_off_fixed;
-    trap.right.p1.x += x_off_fixed;
-    trap.right.p1.y += y_off_fixed;
-    trap.right.p2.x += x_off_fixed;
-    trap.right.p2.y += y_off_fixed;
-
-#ifdef DEBUG
-    fprintf(stderr, "(top, bottom) = (%f, %f)\n",
-	    (double) trap.top / (1 << 16),
-	    (double) trap.bottom / (1 << 16));
-#endif
-
-    pixelWalkInit(&left, &trap.left, trap.top, trap.bottom);
-    pixelWalkInit(&right, &trap.right, trap.top, trap.bottom);
-
-    /* XXX: I'd still like to optimize this loop for top and
-       bottom. Only the first row intersects top and only the last
-       row, (which could also be the first row), intersects bottom. So
-       we could eliminate some unnecessary calculations from all other
-       rows. Unfortunately, I haven't found an easy way to do it
-       without bloating the text, (eg. unrolling a couple iterations
-       of the loop). So, for sake of maintenance, I'm putting off this
-       optimization at least until this code is more stable.. */
-
-    if (!fbBuildCompositeOperand (pMask, &mask, 0, xFixedToInt (trap.top), FALSE, FALSE))
-	return;
-    
-    for (y = trap.top; y < trap.bottom; y = y_next)
+    for (; ntri; ntri--, tris++)
     {
-	pixel_y = xFixedFloor (y);
-	y_next = pixel_y + xFixed1;
-	if (y_next > trap.bottom)
-	    y_next = trap.bottom;
-	
-	ASSERT (left.row.top.y == y);
-	ASSERT (left.row.bottom.y == y_next);
-	ASSERT (right.row.top.y == y);
-	ASSERT (right.row.bottom.y == y_next);
-	
-	pixel_x = xFixedFloor(left.col.left.x);
+	top = &tris->p1;
+	left = &tris->p2;
+	right = &tris->p3;
+	if (_GreaterY (top, left)) {
+	    tmp = left; left = top; top = tmp;
+	}
+	if (_GreaterY (top, right)) {
+	    tmp = right; right = top; top = tmp;
+	}
+	if (_Clockwise (top, right, left)) {
+	    tmp = right; right = left; left = tmp;
+	}
 	
 	/*
-	 * Walk pixels on this row that are left of the
-	 * first possibly lit pixel
+	 * Two cases:
 	 *
-	 * pixelWalkNextPixel will change .row.top.y
-	 * when the last pixel covered by the edge
-	 * is passed
+	 *		+		+
+	 *	       / \             / \
+	 *	      /   \           /   \
+	 *	     /     +         +     \
+	 *      /    --           --    \
+	 *     /   --               --   \
+	 *    / ---                   --- \
+	 *	 +--                         --+
 	 */
-
-	first_right_x = xFixedFloor(right.col.left.x);
-	while (right.row.top.y == y && first_right_x < pixel_x)
-	{
-	    /* these are empty */
-	    pixelWalkNextPixel (&right);
-	    /* step over */
-	    first_right_x += xFixed1;
-	}
-
-	(*mask.set) (&mask, xFixedToInt (pixel_x), xFixedToInt (y));
 	
-	/* 
-	 * Walk pixels on this row intersected by only trap.left
-	 *
-	 */
-	while (left.row.top.y == y && pixel_x < first_right_x) 
-	{
-	    alpha = (RectAlpha (pixel_y, y, y_next, depth)
-		     - PixelAlpha(pixel_x, pixel_y, y, y_next, &left, depth));
-	    
-	    if (alpha > 0)
-	    {
-		if (0 <= pixel_x && pixel_x < buf_width_fixed)
-		    addAlpha (&mask, depth, alpha, temp);
-	    }
-	    
-	    /*
-	     * Step right
-	     */
-	    pixelWalkNextPixel(&left);
-	    INCREMENT_X_AND_PIXEL;
-	}
-
-	/*
-	 * Either pixels are covered by both edges or
-	 * there are fully covered pixels on this row
-	 */
-	if (pixel_x == first_right_x)
-	{
-	    /*
-	     * Now walk the pixels on this row intersected
-	     * by both edges
-	     */
-	    while (left.row.top.y == y && right.row.top.y == y)
-	    {
-		alpha = (PixelAlpha(pixel_x, pixel_y, y, y_next, &right, depth)
-			 - PixelAlpha(pixel_x, pixel_y, y, y_next, &left, depth));
-		if (alpha > 0)
-		{
-		    ASSERT (0 <= alpha && alpha <= max_alpha);
-		    if (0 <= pixel_x && pixel_x < buf_width_fixed)
-			addAlpha (&mask, depth, alpha, temp);
-		}
-		pixelWalkNextPixel(&left);
-		pixelWalkNextPixel(&right);
-		INCREMENT_X_AND_PIXEL;
-	    }
-	    /*
-	     * If the right edge is now left of the left edge,
-	     * the left edge will end up only partially walked,
-	     * walk it the rest of the way
-	     */
-	    while (left.row.top.y == y)
-		pixelWalkNextPixel(&left);
-	}
+	trap.top = top->y;
+	trap.left.p1 = *top;
+	trap.left.p2 = *left;
+	trap.right.p1 = *top;
+	trap.right.p2 = *right;
+	if (right->y < left->y)
+	    trap.bottom = right->y;
 	else
+	    trap.bottom = left->y;
+	fbRasterizeTrapezoid (pPicture, &trap, x_off, y_off);
+	if (right->y < left->y)
 	{
-	    /*
-	     * Fully covered pixels simply saturate 
-	     */
-	    alpha = RectAlpha (pixel_y, y, y_next, depth);
-	    if (alpha == max_alpha)
-	    {
-		while (pixel_x < first_right_x) 
-		{
-		    if (0 <= pixel_x && pixel_x < buf_width_fixed)
-			(*mask.store) (&mask, 0xff000000);
-		    INCREMENT_X_AND_PIXEL;
-		}
-	    }
-	    else 
-	    {
-		while (pixel_x < first_right_x) 
-		{
-		    ASSERT (0 <= alpha && alpha <= max_alpha);
-		    if (0 <= pixel_x && pixel_x < buf_width_fixed)
-			addAlpha (&mask, depth, alpha, temp);
-		    INCREMENT_X_AND_PIXEL;
-		}
-	    }
+	    trap.top = right->y;
+	    trap.bottom = left->y;
+	    trap.right.p1 = *right;
+	    trap.right.p2 = *left;
 	}
-
-	/*
-	 * Finally, pixels intersected only by trap.right 
-	 */
-	while (right.row.top.y == y)
+	else
 	{
-	    alpha = PixelAlpha(pixel_x, pixel_y, y, y_next, &right, depth);
-	    if (alpha > 0)
-	    {
-		if (0 <= pixel_x && pixel_x < buf_width_fixed)
-		    addAlpha (&mask, depth, alpha, temp);
-	    }
-	    pixelWalkNextPixel(&right);
-	    INCREMENT_X_AND_PIXEL;
-	}
-    }
-}
-
-/* Some notes on walking while keeping track of errors in both dimensions:
-
-That's really pretty easy.  Your bresenham should be walking sub-pixel
-coordinates rather than pixel coordinates.  Now you can calculate the
-sub-pixel Y coordinate for any arbitrary sub-pixel X coordinate (or vice
-versa).
-
-        ey:     y error term (distance from current Y sub-pixel to line) * dx
-        ex:     x error term (distance from current X sub-pixel to line) * dy
-        dx:     difference of X coordinates for line endpoints
-        dy:     difference of Y coordinates for line endpoints
-        x:      current fixed-point X coordinate
-        y:      current fixed-point Y coordinate
-
-One of ey or ex will always be zero, depending on whether the distance to
-the line was measured horizontally or vertically.
-
-In moving from x, y to x1, y1:
-
-        (x1 + e1x/dy) - (x + ex/dy)   dx
-        --------------------------- = --
-        (y1 + e1y/dx) - (y + ey/dx)   dy
-
-        (x1dy + e1x) - (xdy + ex) = (y1dx + e1y) - (ydx + ey)
-
-        dy(x1 - x) + (e1x - ex) = dx(y1-y) + (e1y - ey)
-
-So, if you know y1 and want to know x1:
-
-    Set e1y to zero and compute the error from x:
-
-        oex = dx(y1 - y) - ey + ex
-
-    Compute the number of whole pixels to get close to the line:
-
-        wx = oex / dy
-
-    Set x1:
-
-    Now compute the e1x:
-
-        e1x = oex - wx * dy
-
-A similar operation moves to a known y1.  Note that this computation (in
-general) requires 64 bit arithmetic.  I suggest just using the available
-64 bit datatype for now, we can optimize the common cases with a few
-conditionals.  There's some cpp code in fb/fb.h that selects a 64 bit type
-for machines that XFree86 builds on; there aren't any machines missing a
-64 bit datatype that I know of.
-*/
-
-/* Here's a large-step Bresenham for jogging my memory.
-
-void large_bresenham_x_major(x1, y1, x2, y2, x_inc)
-{
-    int x, y, dx, dy, m;
-    int em_dx, ey_dx;
-
-    dx = x2 - x1;
-    dy = y2 - y1;
-
-    m = (x_inc * dy) / dx;
-    em_dx = (x_inc * dy) - m * dx;
-
-    x = x1;
-    y = y1;
-    ey = 0;
-
-    set(x,y);
-    
-    while (x < x2) {
-	x += x_inc;
-	y += m;
-	ey_dx += em_dx;
-	if (ey_dx > dx_2) {
-	    y++;
-	    ey_dx -= dx;
+	    trap.top = left->y;
+	    trap.bottom = right->y;
+	    trap.left.p1 = *left;
+	    trap.left.p2 = *right;
 	}
-	set(x,y);
+	fbRasterizeTrapezoid (pPicture, &trap, x_off, y_off);
     }
 }
 
-*/
-
-/* Here are the latest, simplified equations for computing trapezoid
-   coverage of a pixel:
-
-        alpha_from_area(A) = round(2**depth-1 * A)
-
-        alpha(o) = 2**depth-1
-
-        alpha(a) = alpha_from_area(area(a))
-
-        alpha(ab) = alpha_from_area(area(ab))
-
-        alpha(b) = alpha(ab) - alpha (a)
-
-        alpha(abc) = alpha_from_area(area(abc))
-
-        alpha(c) = alpha(abc) - alpha(ab)
-
-        alpha(ad) = alpha_from_area(area(ad))
-
-        alpha (d) = alpha(ad) - alpha (a)
-
-        alpha (abde) = alpha_from_area(area(abde))
-
-        alpha (de) = alpha (abde) - alpha (ab)
-
-        alpha (e) = alpha (de) - alpha (d)
-
-        alpha (abcdef) = alpha_from_area(area(abcdef))
-
-        alpha (def) = alpha (abcdef) - alpha (abc)
-
-        alpha (f) = alpha (def) - alpha (de)
-
-        alpha (adg) = alpha_from_area(area(adg))
-
-        alpha (g) = alpha (adg) - alpha (ad)
-
-        alpha (abdegh) = alpha_from_area(area(abdegh))
-
-        alpha (gh) = alpha (abdegh) - alpha (abde)
-
-        alpha (h) = alpha (gh) - alpha (g)
-
-        alpha (abcdefghi) = alpha_from_area(area(abcdefghi)) =
-        alpha_from_area(area(o)) = alpha_from_area(1) = alpha(o)
-
-        alpha (ghi) = alpha (abcdefghi) - alpha (abcdef)
-
-        alpha (i) = alpha (ghi) - alpha (gh)
-*/
-
-/* Latest thoughts from Keith on implementing area/alpha computations:
-
-*** 1.16 * 1.16 -> 1.31 ***
-#define AREA_MULT(w,h)  ((w)&(h) == 0x10000 ? 0x80000000 : (((w)*(h) + 1) >> 1)
-
-*** (1.16 + 1.16) / 2 -> 1.16 ***
-#define WIDTH_AVG(x1,x2) (((x1) + (x2) + 1) >> 1)
-
-xFixed_1_31
-SubpixelArea (xFixed_1_16        x1,
-              xFixed_1_16        x2,
-              xFixed_1_16        y1,
-              xFixed_1_16        y2,
-              xFixed_1_16        bottom)
-    {
-        xFixed_1_16      x_trap;
-        xFixed_1_16      h_top, h_trap, h_bot;
-        xFixed_1_31      area;
-
-        x_trap = WIDTH_AVG(x1,x2);
-        h_top = y1;
-        h_trap = (y2 - y1);
-        h_bot = (bottom - y2);
-
-        area = AREA_MULT(x1, h_top) +
-	AREA_MULT(x_trap, h_trap) +
-	AREA_MULT(x2, h_bot);
-
-        return area;
-    }
-
-To convert this xFixed_1_31 value to alpha using 32 bit arithmetic:
-
-int
-AreaAlpha (xFixed_1_31 area, int depth)
-    {
-        return ((area >> bits) * ((1 << depth) - 1)) >> (31 - depth);
-    }
-
-Avoiding the branch bubble in the AREA_MULT could be done with either:
-
-area = (w * h + 1) >> 1;
-area |= ((area - 1) & 0x80000000);
-
-or
-        #define AREA_MULT(w,h) ((((w)*(h) + 1) >> 1) | ((w)&(h)&0x10000) << 15)
-
-depending on your preference, the first takes one less operation but
-can't be expressed as a macro; the second takes a large constant which may
-require an additional instruction on some processors.  The differences
-will be swamped by the cost of the multiply.
-
-*/
-
 #endif /* RENDER */
diff --git a/render/mipict.c b/render/mipict.c
index ed97acc7b..e642b9910 100644
--- a/render/mipict.c
+++ b/render/mipict.c
@@ -456,6 +456,35 @@ miFillColor (CARD32 pixel, int bits)
     return (CARD16) pixel;
 }
 
+Bool
+miIsSolidAlpha (PicturePtr pSrc)
+{
+    ScreenPtr	pScreen = pSrc->pDrawable->pScreen;
+    char	line[1];
+    
+    /* Alpha-only */
+    if (PICT_FORMAT_TYPE (pSrc->format) != PICT_TYPE_A)
+	return FALSE;
+    /* repeat */
+    if (!pSrc->repeat)
+	return FALSE;
+    /* 1x1 */
+    if (pSrc->pDrawable->width != 1 || pSrc->pDrawable->height != 1)
+	return FALSE;
+    line[0] = 1;
+    (*pScreen->GetImage) (pSrc->pDrawable, 0, 0, 1, 1, ZPixmap, ~0L, line);
+    switch (pSrc->pDrawable->bitsPerPixel) {
+    case 1:
+	return (CARD8) line[0] == 1 || (CARD8) line[0] == 0x80;
+    case 4:
+	return (CARD8) line[0] == 0xf || (CARD8) line[0] == 0xf0;
+    case 8:
+	return (CARD8) line[0] == 0xff;
+    default:
+	return FALSE;
+    }
+}
+
 void
 miRenderPixelToColor (PictFormatPtr format,
 		      CARD32	    pixel,
@@ -516,5 +545,9 @@ miPictureInit (ScreenPtr pScreen, PictFormatPtr formats, int nformats)
     ps->TriStrip	= miTriStrip;
     ps->TriFan		= miTriFan;
     
+    ps->RasterizeTrapezoid = 0;			/* requires DDX support */
+    ps->AddTraps	= 0;			/* requires DDX support */
+    ps->AddTriangles	= 0;			/* requires DDX support */
+
     return TRUE;
 }
diff --git a/render/mipict.h b/render/mipict.h
index 4af4c56be..f990e7939 100644
--- a/render/mipict.h
+++ b/render/mipict.h
@@ -124,6 +124,9 @@ miRenderPixelToColor (PictFormatPtr pPict,
 		      CARD32	    pixel,
 		      xRenderColor  *color);
 
+Bool
+miIsSolidAlpha (PicturePtr pSrc);
+
 void
 miCompositeRects (CARD8		op,
 		  PicturePtr	pDst,
diff --git a/render/mitrap.c b/render/mitrap.c
index 05db36ec8..77cdcf03f 100644
--- a/render/mitrap.c
+++ b/render/mitrap.c
@@ -136,16 +136,25 @@ miTrapezoids (CARD8	    op,
 {
     ScreenPtr		pScreen = pDst->pDrawable->pScreen;
     PictureScreenPtr    ps = GetPictureScreen(pScreen);
-    PicturePtr		pPicture = 0;
-    BoxRec		bounds;
-    INT16		xDst, yDst;
-    INT16		xRel, yRel;
-    
-    xDst = traps[0].left.p1.x >> 16;
-    yDst = traps[0].left.p1.y >> 16;
-    
-    if (maskFormat)
+
+    /*
+     * Check for solid alpha add
+     */
+    if (op == PictOpAdd && miIsSolidAlpha (pSrc))
+    {
+	for (; ntrap; ntrap--, traps++)
+	    (*ps->RasterizeTrapezoid) (pDst, traps, 0, 0);
+    } 
+    else if (maskFormat)
     {
+	PicturePtr	pPicture;
+	BoxRec		bounds;
+	INT16		xDst, yDst;
+	INT16		xRel, yRel;
+	
+	xDst = traps[0].left.p1.x >> 16;
+	yDst = traps[0].left.p1.y >> 16;
+
 	miTrapezoidBounds (ntrap, traps, &bounds);
 	if (bounds.y1 >= bounds.y2 || bounds.x1 >= bounds.x2)
 	    return;
@@ -154,37 +163,9 @@ miTrapezoids (CARD8	    op,
 					 bounds.y2 - bounds.y1);
 	if (!pPicture)
 	    return;
-    }
-    for (; ntrap; ntrap--, traps++)
-    {
-	if (!xTrapezoidValid(traps))
-	    continue;
-	if (!maskFormat)
-	{
-	    miTrapezoidBounds (1, traps, &bounds);
-	    if (bounds.y1 >= bounds.y2 || bounds.x1 >= bounds.x2)
-		continue;
-	    pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat,
-					     bounds.x2 - bounds.x1,
-					     bounds.y2 - bounds.y1);
-	    if (!pPicture)
-		continue;
-	}
-	(*ps->RasterizeTrapezoid) (pPicture, traps, 
-				   -bounds.x1, -bounds.y1);
-	if (!maskFormat)
-	{
-	    xRel = bounds.x1 + xSrc - xDst;
-	    yRel = bounds.y1 + ySrc - yDst;
-	    CompositePicture (op, pSrc, pPicture, pDst,
-			      xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			      bounds.x2 - bounds.x1,
-			      bounds.y2 - bounds.y1);
-	    FreePicture (pPicture, 0);
-	}
-    }
-    if (maskFormat)
-    {
+	for (; ntrap; ntrap--, traps++)
+	    (*ps->RasterizeTrapezoid) (pPicture, traps, 
+				       -bounds.x1, -bounds.y1);
 	xRel = bounds.x1 + xSrc - xDst;
 	yRel = bounds.y1 + ySrc - yDst;
 	CompositePicture (op, pSrc, pPicture, pDst,
@@ -193,4 +174,13 @@ miTrapezoids (CARD8	    op,
 			  bounds.y2 - bounds.y1);
 	FreePicture (pPicture, 0);
     }
+    else
+    {
+	if (pDst->polyEdge == PolyEdgeSharp)
+	    maskFormat = PictureMatchFormat (pScreen, 1, PICT_a1);
+	else
+	    maskFormat = PictureMatchFormat (pScreen, 8, PICT_a8);
+	for (; ntrap; ntrap--, traps++)
+	    miTrapezoids (op, pSrc, pDst, maskFormat, xSrc, ySrc, 1, traps);
+    }
 }
diff --git a/render/mitri.c b/render/mitri.c
index b0526256d..5d5df1c61 100644
--- a/render/mitri.c
+++ b/render/mitri.c
@@ -65,82 +65,6 @@ miTriangleBounds (int ntri, xTriangle *tris, BoxPtr bounds)
 }
 
 void
-miRasterizeTriangle (PicturePtr	pPicture,
-		     xTriangle	*tri,
-		     int	x_off,
-		     int	y_off)
-{
-    ScreenPtr		pScreen = pPicture->pDrawable->pScreen;
-    PictureScreenPtr    ps = GetPictureScreen(pScreen);
-    xPointFixed		*top, *left, *right, *t;
-    xTrapezoid		trap[2];
-
-    top = &tri->p1;
-    left = &tri->p2;
-    right = &tri->p3;
-    if (left->y < top->y) {
-	t = left; left = top; top = t;
-    }
-    if (right->y < top->y) {
-	t = right; right = top; top = t;
-    }
-    if (right->x < left->x) {
-	t = right; right = left; left = t;
-    }
-    
-    /*
-     * Two cases:
-     *
-     *		+		+
-     *	       / \             / \
-     *	      /   \           /   \
-     *	     /     +         +     \
-     *      /    --           --    \
-     *     /   --               --   \
-     *    / ---                   --- \
-     *	 +--                         --+
-     */
-    
-    trap[0].top = top->y;
-    
-    trap[0].left.p1.x = top->x;
-    trap[0].left.p1.y = trap[0].top;
-    trap[0].left.p2.x = left->x;
-    trap[0].left.p2.y = left->y;
-    
-    trap[0].right.p1 = trap[0].left.p1;
-    trap[0].right.p2.x = right->x;
-    trap[0].right.p2.y = right->y;
-    
-    if (right->y < left->y)
-    {
-	trap[0].bottom = trap[0].right.p2.y;
-
-	trap[1].top = trap[0].bottom;
-	trap[1].bottom = trap[0].left.p2.y;
-	
-	trap[1].left = trap[0].left;
-	trap[1].right.p1 = trap[0].right.p2;
-	trap[1].right.p2 = trap[0].left.p2;
-    }
-    else
-    {
-	trap[0].bottom = trap[0].left.p2.y;
-	
-	trap[1].top = trap[0].bottom;
-	trap[1].bottom = trap[0].right.p2.y;
-	
-	trap[1].right = trap[0].right;
-	trap[1].left.p1 = trap[0].left.p2;
-	trap[1].left.p2 = trap[0].right.p2;
-    }
-    if (trap[0].top != trap[0].bottom)
-	(*ps->RasterizeTrapezoid) (pPicture, &trap[0], x_off, y_off);
-    if (trap[1].top != trap[1].bottom)
-	(*ps->RasterizeTrapezoid) (pPicture, &trap[1], x_off, y_off);
-}
-
-void
 miTriangles (CARD8	    op,
 	     PicturePtr	    pSrc,
 	     PicturePtr	    pDst,
@@ -151,16 +75,25 @@ miTriangles (CARD8	    op,
 	     xTriangle	    *tris)
 {
     ScreenPtr		pScreen = pDst->pDrawable->pScreen;
-    BoxRec		bounds;
-    PicturePtr		pPicture = 0;
-    INT16		xDst, yDst;
-    INT16		xRel, yRel;
-    
-    xDst = tris[0].p1.x >> 16;
-    yDst = tris[0].p1.y >> 16;
+    PictureScreenPtr    ps = GetPictureScreen(pScreen);
     
-    if (maskFormat)
+    /*
+     * Check for solid alpha add
+     */
+    if (op == PictOpAdd && miIsSolidAlpha (pSrc))
     {
+	(*ps->AddTriangles) (pDst, 0, 0, ntri, tris);
+    }
+    else if (maskFormat)
+    {
+	BoxRec		bounds;
+	PicturePtr	pPicture;
+	INT16		xDst, yDst;
+	INT16		xRel, yRel;
+	
+	xDst = tris[0].p1.x >> 16;
+	yDst = tris[0].p1.y >> 16;
+
 	miTriangleBounds (ntri, tris, &bounds);
 	if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
 	    return;
@@ -169,34 +102,8 @@ miTriangles (CARD8	    op,
 					 bounds.y2 - bounds.y1);
 	if (!pPicture)
 	    return;
-    }
-    for (; ntri; ntri--, tris++)
-    {
-	if (!maskFormat)
-	{
-	    miTriangleBounds (1, tris, &bounds);
-	    if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
-		continue;
-	    pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat,
-					     bounds.x2 - bounds.x1,
-					     bounds.y2 - bounds.y1);
-	    if (!pPicture)
-		break;
-	}
-	miRasterizeTriangle (pPicture, tris, -bounds.x1, -bounds.y1);
-	if (!maskFormat)
-	{
-	    xRel = bounds.x1 + xSrc - xDst;
-	    yRel = bounds.y1 + ySrc - yDst;
-	    CompositePicture (op, pSrc, pPicture, pDst,
-			      xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			      bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
-	    FreePicture (pPicture, 0);
-	}
-	/* XXX adjust xSrc and ySrc */
-    }
-    if (maskFormat)
-    {
+	(*ps->AddTriangles) (pPicture, -bounds.x1, -bounds.y1, ntri, tris);
+	
 	xRel = bounds.x1 + xSrc - xDst;
 	yRel = bounds.y1 + ySrc - yDst;
 	CompositePicture (op, pSrc, pPicture, pDst,
@@ -204,6 +111,16 @@ miTriangles (CARD8	    op,
 			  bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
 	FreePicture (pPicture, 0);
     }
+    else
+    {
+	if (pDst->polyEdge == PolyEdgeSharp)
+	    maskFormat = PictureMatchFormat (pScreen, 1, PICT_a1);
+	else
+	    maskFormat = PictureMatchFormat (pScreen, 8, PICT_a8);
+	
+	for (; ntri; ntri--, tris++)
+	    miTriangles (op, pSrc, pDst, maskFormat, xSrc, ySrc, 1, tris);
+    }
 }
 
 void
@@ -217,64 +134,24 @@ miTriStrip (CARD8	    op,
 	    xPointFixed	    *points)
 {
     ScreenPtr		pScreen = pDst->pDrawable->pScreen;
-    xTriangle		tri;
-    BoxRec		bounds;
-    PicturePtr		pPicture = 0;
-    INT16		xDst, yDst;
-    INT16		xRel, yRel;
-    
-    xDst = points[0].x >> 16;
-    yDst = points[0].y >> 16;
+    PictureScreenPtr    ps = GetPictureScreen(pScreen);
+    xTriangle		*tris, *tri;
+    int			ntri;
     
     if (npoint < 3)
 	return;
-    if (maskFormat)
-    {
-	miPointFixedBounds (npoint, points, &bounds);
-	if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
-	    return;
-	pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat,
-					 bounds.x2 - bounds.x1,
-					 bounds.y2 - bounds.y1);
-	if (!pPicture)
-	    return;
-    }
-    for (; npoint >= 3; npoint--, points++)
-    {
-	tri.p1 = points[0];
-	tri.p2 = points[1];
-	tri.p3 = points[2];
-	if (!maskFormat)
-	{
-	    miTriangleBounds (1, &tri, &bounds);
-	    if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
-		continue;
-	    pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat, 
-					     bounds.x2 - bounds.x1,
-					     bounds.y2 - bounds.y1);
-	    if (!pPicture)
-		continue;
-	}
-	miRasterizeTriangle (pPicture, &tri, -bounds.x1, -bounds.y1);
-	if (!maskFormat)
-	{
-	    xRel = bounds.x1 + xSrc - xDst;
-	    yRel = bounds.y1 + ySrc - yDst;
-	    CompositePicture (op, pSrc, pPicture, pDst,
-			      xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			      bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
-	    FreePicture (pPicture, 0);
-	}
-    }
-    if (maskFormat)
+    ntri = npoint - 2;
+    tris = ALLOCATE_LOCAL (ntri & sizeof (xTriangle));
+    if (!tris)
+	return;
+    for (tri = tris; npoint >= 3; npoint--, points++, tri++)
     {
-	xRel = bounds.x1 + xSrc - xDst;
-	yRel = bounds.y1 + ySrc - yDst;
-	CompositePicture (op, pSrc, pPicture, pDst,
-			  xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			  bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
-	FreePicture (pPicture, 0);
+	tri->p1 = points[0];
+	tri->p2 = points[1];
+	tri->p3 = points[2];
     }
+    (*ps->Triangles) (op, pSrc, pDst, maskFormat, xSrc, ySrc, ntri, tris);
+    DEALLOCATE_LOCAL (tris);
 }
 
 void
@@ -288,65 +165,24 @@ miTriFan (CARD8		op,
 	  xPointFixed	*points)
 {
     ScreenPtr		pScreen = pDst->pDrawable->pScreen;
-    xTriangle		tri;
-    BoxRec		bounds;
-    PicturePtr		pPicture = 0;
+    PictureScreenPtr    ps = GetPictureScreen(pScreen);
+    xTriangle		*tris, *tri;
     xPointFixed		*first;
-    INT16		xDst, yDst;
-    INT16		xRel, yRel;
-    
-    xDst = points[0].x >> 16;
-    yDst = points[0].y >> 16;
+    int			ntri;
     
     if (npoint < 3)
 	return;
-    if (maskFormat)
-    {
-	miPointFixedBounds (npoint, points, &bounds);
-	if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
-	    return;
-	pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat,
-					 bounds.x2 - bounds.x1,
-					 bounds.y2 - bounds.y1);
-	if (!pPicture)
-	    return;
-    }
+    ntri = npoint - 2;
+    tris = ALLOCATE_LOCAL (ntri & sizeof (xTriangle));
+    if (!tris)
+	return;
     first = points++;
-    npoint--;
-    for (; npoint >= 2; npoint--, points++)
+    for (tri = tris; npoint >= 3; npoint--, points++, tri++)
     {
-	tri.p1 = *first;
-	tri.p2 = points[0];
-	tri.p3 = points[1];
-	if (!maskFormat)
-	{
-	    miTriangleBounds (1, &tri, &bounds);
-	    if (bounds.x2 <= bounds.x1 || bounds.y2 <= bounds.y1)
-		continue;
-	    pPicture = miCreateAlphaPicture (pScreen, pDst, maskFormat, 
-					     bounds.x2 - bounds.x1,
-					     bounds.y2 - bounds.y1);
-	    if (!pPicture)
-		continue;
-	}
-	miRasterizeTriangle (pPicture, &tri, -bounds.x1, -bounds.y1);
-	if (!maskFormat)
-	{
-	    xRel = bounds.x1 + xSrc - xDst;
-	    yRel = bounds.y1 + ySrc - yDst;
-	    CompositePicture (op, pSrc, pPicture, pDst,
-			      xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			      bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
-	    FreePicture (pPicture, 0);
-	}
-    }
-    if (maskFormat)
-    {
-	xRel = bounds.x1 + xSrc - xDst;
-	yRel = bounds.y1 + ySrc - yDst;
-	CompositePicture (op, pSrc, pPicture, pDst,
-			  xRel, yRel, 0, 0, bounds.x1, bounds.y1,
-			  bounds.x2 - bounds.x1, bounds.y2 - bounds.y1);
-	FreePicture (pPicture, 0);
+	tri->p1 = *first;
+	tri->p2 = points[0];
+	tri->p3 = points[1];
     }
+    (*ps->Triangles) (op, pSrc, pDst, maskFormat, xSrc, ySrc, ntri, tris);
+    DEALLOCATE_LOCAL (tris);
 }
diff --git a/render/picture.c b/render/picture.c
index 77593db52..64e29a0cb 100644
--- a/render/picture.c
+++ b/render/picture.c
@@ -1462,7 +1462,18 @@ CompositeTriFan (CARD8		op,
     (*ps->TriFan) (op, pSrc, pDst, maskFormat, xSrc, ySrc, npoints, points);
 }
 
-typedef xFixed_32_32	xFixed_48_16;
+void
+AddTraps (PicturePtr	pPicture,
+	  INT16		xOff,
+	  INT16		yOff,
+	  int		ntrap,
+	  xTrap		*traps)
+{
+    PictureScreenPtr	ps = GetPictureScreen(pPicture->pDrawable->pScreen);
+    
+    ValidatePicture (pPicture);
+    (*ps->AddTraps) (pPicture, xOff, yOff, ntrap, traps);
+}
 
 #define MAX_FIXED_48_16	    ((xFixed_48_16) 0x7fffffff)
 #define MIN_FIXED_48_16	    (-((xFixed_48_16) 1 << 31))
diff --git a/render/picture.h b/render/picture.h
index e3e48d0d5..4ed6e6ae0 100644
--- a/render/picture.h
+++ b/render/picture.h
@@ -186,6 +186,11 @@ typedef long long int	xFixed_32_32;
 # endif
 #endif
 
+typedef xFixed_32_32	xFixed_48_16;
+
+#define MAX_FIXED_48_16	    ((xFixed_48_16) 0x7fffffff)
+#define MIN_FIXED_48_16	    (-((xFixed_48_16) 1 << 31))
+
 typedef CARD32		xFixed_1_31;
 typedef CARD32		xFixed_1_16;
 typedef INT32		xFixed_16_16;
diff --git a/render/picturestr.h b/render/picturestr.h
index 70881fc78..cdeb207a6 100644
--- a/render/picturestr.h
+++ b/render/picturestr.h
@@ -226,6 +226,18 @@ typedef void	(*UpdateIndexedProcPtr)	    (ScreenPtr	    pScreen,
 					     int	    ndef,
 					     xColorItem	    *pdef);
 
+typedef void	(*AddTrapsProcPtr)	    (PicturePtr	    pPicture,
+					     INT16	    xOff,
+					     INT16	    yOff,
+					     int	    ntrap,
+					     xTrap	    *traps);
+
+typedef void	(*AddTrianglesProcPtr)	    (PicturePtr	    pPicture,
+					     INT16	    xOff,
+					     INT16	    yOff,
+					     int	    ntri,
+					     xTriangle	    *tris);
+
 typedef struct _PictureScreen {
     int				totalPictureSize;
     unsigned int		*PicturePrivateSizes;
@@ -273,6 +285,11 @@ typedef struct _PictureScreen {
     TriFanProcPtr		TriFan;
 
     RasterizeTrapezoidProcPtr	RasterizeTrapezoid;
+
+    AddTrianglesProcPtr		AddTriangles;
+
+    AddTrapsProcPtr		AddTraps;
+
 } PictureScreenRec, *PictureScreenPtr;
 
 extern int		PictureScreenPrivateIndex;
@@ -516,6 +533,13 @@ AnimCurInit (ScreenPtr pScreen);
 int
 AnimCursorCreate (CursorPtr *cursors, CARD32 *deltas, int ncursor, CursorPtr *ppCursor);
 
+void
+AddTraps (PicturePtr	pPicture, 
+	  INT16		xOff,
+	  INT16		yOff,
+	  int		ntraps,
+	  xTrap		*traps);
+
 #ifdef PANORAMIX
 void PanoramiXRenderInit (void);
 void PanoramiXRenderReset (void);
diff --git a/render/render.c b/render/render.c
index b752a7760..49d5c8707 100644
--- a/render/render.c
+++ b/render/render.c
@@ -1,4 +1,4 @@
-/* $XdotOrg: xc/programs/Xserver/render/render.c,v 1.3 2004/06/30 20:06:56 kem Exp $ */
+/* $XdotOrg: xc/programs/Xserver/render/render.c,v 1.4 2004/07/26 22:41:47 herrb Exp $ */
 /*
  * $XFree86: xc/programs/Xserver/render/render.c,v 1.27tsi Exp $
  *
@@ -78,6 +78,7 @@ static int ProcRenderSetPictureTransform (ClientPtr pClient);
 static int ProcRenderQueryFilters (ClientPtr pClient);
 static int ProcRenderSetPictureFilter (ClientPtr pClient);
 static int ProcRenderCreateAnimCursor (ClientPtr pClient);
+static int ProcRenderAddTraps (ClientPtr pClient);
 
 static int ProcRenderDispatch (ClientPtr pClient);
 
@@ -111,6 +112,7 @@ static int SProcRenderSetPictureTransform (ClientPtr pClient);
 static int SProcRenderQueryFilters (ClientPtr pClient);
 static int SProcRenderSetPictureFilter (ClientPtr pClient);
 static int SProcRenderCreateAnimCursor (ClientPtr pClient);
+static int SProcRenderAddTraps (ClientPtr pClient);
 
 static int SProcRenderDispatch (ClientPtr pClient);
 
@@ -147,6 +149,7 @@ int	(*ProcRenderVector[RenderNumberRequests])(ClientPtr) = {
     ProcRenderQueryFilters,
     ProcRenderSetPictureFilter,
     ProcRenderCreateAnimCursor,
+    ProcRenderAddTraps,
 };
 
 int	(*SProcRenderVector[RenderNumberRequests])(ClientPtr) = {
@@ -182,6 +185,7 @@ int	(*SProcRenderVector[RenderNumberRequests])(ClientPtr) = {
     SProcRenderQueryFilters,
     SProcRenderSetPictureFilter,
     SProcRenderCreateAnimCursor,
+    SProcRenderAddTraps,
 };
 
 static void
@@ -1813,6 +1817,27 @@ ProcRenderCreateAnimCursor (ClientPtr client)
 }
 
 static int
+ProcRenderAddTraps (ClientPtr client)
+{
+    int		ntraps;
+    PicturePtr	pPicture;
+    REQUEST(xRenderAddTrapsReq);
+
+    REQUEST_AT_LEAST_SIZE(xRenderAddTrapsReq);
+    VERIFY_PICTURE (pPicture, stuff->picture, client, SecurityWriteAccess, 
+		    RenderErrBase + BadPicture);
+    ntraps = (client->req_len << 2) - sizeof (xRenderAddTrapsReq);
+    if (ntraps % sizeof (xTrap))
+	return BadLength;
+    ntraps /= sizeof (xTrap);
+    if (ntraps)
+	AddTraps (pPicture,
+		  stuff->xOff, stuff->yOff,
+		  ntraps, (xTrap *) &stuff[1]);
+    return client->noClientException;
+}
+
+static int
 ProcRenderDispatch (ClientPtr client)
 {
     REQUEST(xReq);
@@ -2278,6 +2303,21 @@ SProcRenderCreateAnimCursor (ClientPtr client)
 }
 
 static int
+SProcRenderAddTraps (ClientPtr client)
+{
+    register int n;
+    REQUEST (xRenderAddTrapsReq);
+    REQUEST_AT_LEAST_SIZE (xRenderAddTrapsReq);
+
+    swaps(&stuff->length, n);
+    swapl(&stuff->picture, n);
+    swaps(&stuff->xOff, n);
+    swaps(&stuff->yOff, n);
+    SwapRestL(stuff);
+    return (*ProcRenderVector[stuff->renderReqType]) (client);
+}
+
+static int
 SProcRenderDispatch (ClientPtr client)
 {
     REQUEST(xReq);
@@ -2922,6 +2962,44 @@ PanoramiXRenderColorTriangles(ClientPtr client)
 
 #endif
 
+static int
+PanoramiXRenderAddTraps (ClientPtr client)
+{
+    PanoramiXRes    *picture;
+    int		    result = Success, j;
+    REQUEST(xRenderAddTrapsReq);
+    char	    *extra;
+    int		    extra_len;
+    INT16    	    x_off, y_off;
+
+    REQUEST_AT_LEAST_SIZE (xRenderAddTrapsReq);
+    VERIFY_XIN_PICTURE (picture, stuff->picture, client, SecurityWriteAccess, 
+			RenderErrBase + BadPicture);
+    extra_len = (client->req_len << 2) - sizeof (xRenderAddTrapsReq);
+    if (extra_len &&
+	(extra = (char *) ALLOCATE_LOCAL (extra_len)))
+    {
+	memcpy (extra, stuff + 1, extra_len);
+	x_off = stuff->xOff;
+	y_off = stuff->yOff;
+	FOR_NSCREENS_FORWARD(j) {
+	    if (j) memcpy (stuff + 1, extra, extra_len);
+	    stuff->picture = picture->info[j].id;
+	    
+	    if (picture->u.pict.root)
+	    {
+		stuff->xOff = x_off + panoramiXdataPtr[j].x;
+		stuff->yOff = y_off + panoramiXdataPtr[j].y;
+	    }
+	    result = (*PanoramiXSaveRenderVector[X_RenderAddTraps]) (client);
+	    if(result != Success) break;
+	}
+	DEALLOCATE_LOCAL(extra);
+    }
+
+    return result;
+}
+
 void
 PanoramiXRenderInit (void)
 {
@@ -2949,6 +3027,7 @@ PanoramiXRenderInit (void)
     ProcRenderVector[X_RenderTriangles] = PanoramiXRenderTriangles;
     ProcRenderVector[X_RenderTriStrip] = PanoramiXRenderTriStrip;
     ProcRenderVector[X_RenderTriFan] = PanoramiXRenderTriFan;
+    ProcRenderVector[X_RenderAddTraps] = PanoramiXRenderAddTraps;
 }
 
 void
diff --git a/render/renderedge.c b/render/renderedge.c
new file mode 100644
index 000000000..f9518b671
--- /dev/null
+++ b/render/renderedge.c
@@ -0,0 +1,197 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "renderedge.h"
+
+/*
+ * Compute the smallest value no less than y which is on a
+ * grid row
+ */
+
+xFixed
+RenderSampleCeilY (xFixed y, int n)
+{
+    xFixed   f = xFixedFrac(y);
+    xFixed   i = xFixedFloor(y);
+    
+    f = ((f + Y_FRAC_FIRST(n)) / STEP_Y_SMALL(n)) * STEP_Y_SMALL(n) + Y_FRAC_FIRST(n);
+    if (f > Y_FRAC_LAST(n))
+    {
+	f = Y_FRAC_FIRST(n);
+	i += xFixed1;
+    }
+    return (i | f);
+}
+
+#define div(a,b)    ((a) >= 0 ? (a) / (b) : -((-(a) + (b) - 1) / (b)))
+
+/*
+ * Compute the largest value no greater than y which is on a
+ * grid row
+ */
+xFixed
+RenderSampleFloorY (xFixed y, int n)
+{
+    xFixed   f = xFixedFrac(y);
+    xFixed   i = xFixedFloor (y);
+    
+    f = div(f - Y_FRAC_FIRST(n), STEP_Y_SMALL(n)) * STEP_Y_SMALL(n) + Y_FRAC_FIRST(n);
+    if (f < Y_FRAC_FIRST(n))
+    {
+	f = Y_FRAC_LAST(n);
+	i -= xFixed1;
+    }
+    return (i | f);
+}
+
+/*
+ * Step an edge by any amount (including negative values)
+ */
+void
+RenderEdgeStep (RenderEdge *e, int n)
+{
+    xFixed_48_16	ne;
+
+    e->x += n * e->stepx;
+    
+    ne = e->e + n * (xFixed_48_16) e->dx;
+    
+    if (n >= 0)
+    {
+	if (ne > 0)
+	{
+	    int nx = (ne + e->dy - 1) / e->dy;
+	    e->e = ne - nx * (xFixed_48_16) e->dy;
+	    e->x += nx * e->signdx;
+	}
+    }
+    else
+    {
+	if (ne <= -e->dy)
+	{
+	    int nx = (-ne) / e->dy;
+	    e->e = ne + nx * (xFixed_48_16) e->dy;
+	    e->x -= nx * e->signdx;
+	}
+    }
+}
+
+/*
+ * A private routine to initialize the multi-step
+ * elements of an edge structure
+ */
+static void
+_RenderEdgeMultiInit (RenderEdge *e, int n, xFixed *stepx_p, xFixed *dx_p)
+{
+    xFixed	stepx;
+    xFixed_48_16	ne;
+    
+    ne = n * (xFixed_48_16) e->dx;
+    stepx = n * e->stepx;
+    if (ne > 0)
+    {
+	int nx = ne / e->dy;
+	ne -= nx * e->dy;
+	stepx += nx * e->signdx;
+    }
+    *dx_p = ne;
+    *stepx_p = stepx;
+}
+
+/*
+ * Initialize one edge structure given the line endpoints and a
+ * starting y value
+ */
+void
+RenderEdgeInit (RenderEdge	*e,
+		int		n,
+		xFixed		y_start,
+		xFixed		x_top,
+		xFixed		y_top,
+		xFixed		x_bot,
+		xFixed		y_bot)
+{
+    xFixed	dx, dy;
+
+    e->x = x_top;
+    e->e = 0;
+    dx = x_bot - x_top;
+    dy = y_bot - y_top;
+    e->dy = dy;
+    if (dy)
+    {
+	if (dx >= 0)
+	{
+	    e->signdx = 1;
+	    e->stepx = dx / dy;
+	    e->dx = dx % dy;
+	    e->e = -dy;
+	}
+	else
+	{
+	    e->signdx = -1;
+	    e->stepx = -(-dx / dy);
+	    e->dx = -dx % dy;
+	    e->e = 0;
+	}
+    
+	_RenderEdgeMultiInit (e, STEP_Y_SMALL(n), &e->stepx_small, &e->dx_small);
+	_RenderEdgeMultiInit (e, STEP_Y_BIG(n), &e->stepx_big, &e->dx_big);
+    }
+    RenderEdgeStep (e, y_start - y_top);
+}
+
+/*
+ * Initialize one edge structure given a line, starting y value
+ * and a pixel offset for the line
+ */
+void
+RenderLineFixedEdgeInit (RenderEdge *e,
+			 int	    n,
+			 xFixed	    y,
+			 xLineFixed *line,
+			 int	    x_off,
+			 int	    y_off)
+{
+    xFixed	x_off_fixed = IntToxFixed(x_off);
+    xFixed	y_off_fixed = IntToxFixed(y_off);
+    xPointFixed	*top, *bot;
+
+    if (line->p1.y <= line->p2.y)
+    {
+	top = &line->p1;
+	bot = &line->p2;
+    }
+    else
+    {
+	top = &line->p2;
+	bot = &line->p1;
+    }
+    RenderEdgeInit (e, n, y,
+		    top->x + x_off_fixed,
+		    top->y + y_off_fixed,
+		    bot->x + x_off_fixed,
+		    bot->y + y_off_fixed);
+}
+
diff --git a/render/renderedge.h b/render/renderedge.h
new file mode 100644
index 000000000..d621d9dcf
--- /dev/null
+++ b/render/renderedge.h
@@ -0,0 +1,120 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef _RENDEREDGE_H_
+#define _RENDEREDGE_H_
+
+#include "picturestr.h"
+
+#define MAX_ALPHA(n)	((1 << (n)) - 1)
+#define N_Y_FRAC(n)	((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
+#define N_X_FRAC(n)	((1 << ((n)/2)) + 1)
+
+#define STEP_Y_SMALL(n)	(xFixed1 / N_Y_FRAC(n))
+#define STEP_Y_BIG(n)	(xFixed1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
+
+#define Y_FRAC_FIRST(n)	(STEP_Y_SMALL(n) / 2)
+#define Y_FRAC_LAST(n)	(Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))
+
+#define STEP_X_SMALL(n)	(xFixed1 / N_X_FRAC(n))
+#define STEP_X_BIG(n)	(xFixed1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
+
+#define X_FRAC_FIRST(n)	(STEP_X_SMALL(n) / 2)
+#define X_FRAC_LAST(n)	(X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
+
+#define RenderSamplesX(x,n)	((n) == 1 ? 0 : (xFixedFrac (x) + X_FRAC_FIRST(n)) / STEP_X_SMALL(n))
+
+/*
+ * An edge structure.  This represents a single polygon edge
+ * and can be quickly stepped across small or large gaps in the
+ * sample grid
+ */
+
+typedef struct {
+    xFixed   x;
+    xFixed   e;
+    xFixed   stepx;
+    xFixed   signdx;
+    xFixed   dy;
+    xFixed   dx;
+
+    xFixed   stepx_small;
+    xFixed   stepx_big;
+    xFixed   dx_small;
+    xFixed   dx_big;
+} RenderEdge;
+
+/*
+ * Step across a small sample grid gap
+ */
+#define RenderEdgeStepSmall(edge) { \
+    edge->x += edge->stepx_small;   \
+    edge->e += edge->dx_small;	    \
+    if (edge->e > 0)		    \
+    {				    \
+	edge->e -= edge->dy;	    \
+	edge->x += edge->signdx;    \
+    }				    \
+}
+
+/*
+ * Step across a large sample grid gap
+ */
+#define RenderEdgeStepBig(edge) {   \
+    edge->x += edge->stepx_big;	    \
+    edge->e += edge->dx_big;	    \
+    if (edge->e > 0)		    \
+    {				    \
+	edge->e -= edge->dy;	    \
+	edge->x += edge->signdx;    \
+    }				    \
+}
+
+xFixed
+RenderSampleCeilY (xFixed y, int bpp);
+
+xFixed
+RenderSampleFloorY (xFixed y, int bpp);
+
+void
+RenderEdgeStep (RenderEdge *e, int n);
+
+void
+RenderEdgeInit (RenderEdge	*e,
+		int		bpp,
+		xFixed		y_start,
+		xFixed		x_top,
+		xFixed		y_top,
+		xFixed		x_bot,
+		xFixed		y_bot);
+
+void
+RenderLineFixedEdgeInit (RenderEdge *e,
+			 int	    bpp,
+			 xFixed	    y,
+			 xLineFixed *line,
+			 int	    x_off,
+			 int	    y_off);
+
+#endif /* _RENDEREDGE_H_ */