Add RenderAddTraps. Rewrite trapezoid rendering code.

10 files changed, 559 insertions, 261 deletions

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_ */