miwideline.c

linux下电话本所依赖的一些图形库

/* $TOG: miwideline.c /main/60 1998/03/07 17:40:23 kaleb $ */
/*

Copyright 1988, 1998  The Open Group

All Rights Reserved.

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of The Open Group shall
not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization
from The Open Group.

*/
/* $XFree86: xc/programs/Xserver/mi/miwideline.c,v 1.7 1999/10/13 22:33:13 dawes Exp $ */

/* Author:  Keith Packard, MIT X Consortium */

/*
 * Mostly integer wideline code.  Uses a technique similar to
 * bresenham zero-width lines, except walks an X edge
 */

#include <config.h>
#include <stdio.h>
#ifdef _XOPEN_SOURCE
#include <math.h>
#else
#define _XOPEN_SOURCE	/* to get prototype for hypot on some systems */
#include <math.h>
#undef _XOPEN_SOURCE
#endif

#include "mi.h"
#include "miwideline.h"

#ifdef ICEILTEMPDECL
ICEILTEMPDECL
#endif

static void
miLineArc (GdkDrawable *pDraw, GdkGC *pGC, GdkColor *pixel, SpanDataPtr spanData,
	LineFacePtr leftFace, LineFacePtr rightFace, double xorg, double yorg, gboolean isInt);

/*
 * spans-based polygon filler
 */

void
miFillPolyHelper (GdkDrawable *pDrawable, GdkGC *pGC, GdkColor *pixel,
                  SpanDataPtr spanData, int y, int overall_height,
		  PolyEdgePtr left, PolyEdgePtr right, int left_count,
                  int right_count)
{
    register int left_x = 0, left_e = 0;
    int	left_stepx = 0;
    int	left_signdx = 0;
    int	left_dy = 0, left_dx = 0;

    register int right_x = 0, right_e = 0;
    int	right_stepx = 0;
    int	right_signdx = 0;
    int	right_dy = 0, right_dx = 0;

    int	height = 0;
    int	left_height = 0, right_height = 0;

    register GdkSpan* ppt;
    GdkSpan* pptInit = NULL;
    GdkColor		oldPixel;
    int		xorg;
    Spans	spanRec;

    left_height = 0;
    right_height = 0;
    
    if (!spanData)
    {
    	pptInit = (GdkSpan*) ALLOCATE_LOCAL (overall_height * sizeof(*ppt));
    	if (!pptInit)
	    return;
	ppt = pptInit;
    	oldPixel = GDK_GC_FBDATA(pGC)->values.foreground;
    	if (pixel->pixel != oldPixel.pixel)
    	{
	  gdk_gc_set_foreground(pGC, pixel);
    	}
    }
    else
    {
	spanRec.points = (GdkSpan*) g_malloc (overall_height * sizeof (*ppt));
	if (!spanRec.points)
	    return;
	ppt = spanRec.points;
    }

    xorg = 0;
    while ((left_count || left_height) &&
	   (right_count || right_height))
    {
	MIPOLYRELOADLEFT
	MIPOLYRELOADRIGHT

	height = left_height;
	if (height > right_height)
	    height = right_height;

	left_height -= height;
	right_height -= height;

	while (--height >= 0)
	{
	    if (right_x >= left_x)
	    {
		ppt->y = y;
		ppt->x = left_x + xorg;
		ppt->width = right_x - left_x + 1;
		ppt++;
	    }
    	    y++;
    	
	    MIPOLYSTEPLEFT

	    MIPOLYSTEPRIGHT
	}
    }
    if (!spanData)
    {
      gdk_fb_fill_spans(pDrawable, pGC, pptInit, ppt - pptInit, TRUE);
      DEALLOCATE_LOCAL (pptInit);
      if (pixel->pixel != oldPixel.pixel)
    	{
	  gdk_gc_set_foreground(pGC, &oldPixel);
    	}
    }
    else
    {
	spanRec.count = ppt - spanRec.points;
	AppendSpanGroup (pGC, pixel, &spanRec, spanData)
    }
}

static void
miFillRectPolyHelper (GdkDrawable *pDrawable, GdkGC *pGC, GdkColor *pixel,
                      SpanDataPtr spanData, int x, int y, int w, int h)
{
    register GdkSpan* ppt;
    GdkColor	oldPixel;
    Spans	spanRec;

    if (!spanData)
    {
    	oldPixel = GDK_GC_FBDATA(pGC)->values.foreground;
    	if (pixel->pixel != oldPixel.pixel)
    	{
	  gdk_gc_set_foreground(pGC, pixel);
    	}
        gdk_fb_draw_rectangle(pDrawable, pGC, TRUE, x, y, w, h);
    	if (pixel->pixel != oldPixel.pixel)
    	{
	  gdk_gc_set_foreground(pGC, &oldPixel);
    	}
    }
    else
    {
	spanRec.points = (GdkSpan*) g_malloc (h * sizeof (*ppt));
	if (!spanRec.points)
	    return;
	ppt = spanRec.points;

	while (h--)
	{
	    ppt->x = x;
	    ppt->y = y;
	    ppt->width = w;
	    ppt++;
	    y++;
	}
	spanRec.count = ppt - spanRec.points;
	AppendSpanGroup (pGC, pixel, &spanRec, spanData)
    }
}

/* static */ int
miPolyBuildEdge (double x0, double y0, double k, register int dx,
                 register int dy, int xi, int yi, int left,
                 register PolyEdgePtr edge)
{
    int	    x, y, e;
    int	    xady;

    if (dy < 0)
    {
	dy = -dy;
	dx = -dx;
	k = -k;
    }

#ifdef NOTDEF
    {
	double	realk, kerror;
    	realk = x0 * dy - y0 * dx;
    	kerror = Fabs (realk - k);
    	if (kerror > .1)
	    printf ("realk: %g k: %g\n", realk, k);
    }
#endif
    y = ICEIL (y0);
    xady = ICEIL (k) + y * dx;

    if (xady <= 0)
	x = - (-xady / dy) - 1;
    else
	x = (xady - 1) / dy;

    e = xady - x * dy;

    if (dx >= 0)
    {
	edge->signdx = 1;
	edge->stepx = dx / dy;
	edge->dx = dx % dy;
    }
    else
    {
	edge->signdx = -1;
	edge->stepx = - (-dx / dy);
	edge->dx = -dx % dy;
	e = dy - e + 1;
    }
    edge->dy = dy;
    edge->x = x + left + xi;
    edge->e = e - dy;	/* bias to compare against 0 instead of dy */
    return y + yi;
}

#define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr)))

/* static */ int
miPolyBuildPoly (register PolyVertexPtr vertices, register PolySlopePtr slopes,
                 int count, int xi, int yi, PolyEdgePtr left, PolyEdgePtr right,
                 int *pnleft, int *pnright, int *h)
{
    int	    top, bottom;
    double  miny, maxy;
    register int i;
    int	    j;
    int	    clockwise;
    int	    slopeoff;
    register int s;
    register int nright, nleft;
    int	    y, lasty = 0, bottomy, topy = 0;

    /* find the top of the polygon */
    maxy = miny = vertices[0].y;
    bottom = top = 0;
    for (i = 1; i < count; i++)
    {
	if (vertices[i].y < miny)
	{
	    top = i;
	    miny = vertices[i].y;
	}
	if (vertices[i].y >= maxy)
	{
	    bottom = i;
	    maxy = vertices[i].y;
	}
    }
    clockwise = 1;
    slopeoff = 0;

    i = top;
    j = StepAround (top, -1, count);

    if (slopes[j].dy * slopes[i].dx > slopes[i].dy * slopes[j].dx)
    {
	clockwise = -1;
	slopeoff = -1;
    }

    bottomy = ICEIL (maxy) + yi;

    nright = 0;

    s = StepAround (top, slopeoff, count);
    i = top;
    while (i != bottom)
    {
	if (slopes[s].dy != 0)
	{
	    y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
			slopes[s].k,
			slopes[s].dx, slopes[s].dy,
			xi, yi, 0,
			&right[nright]);
	    if (nright != 0)
	    	right[nright-1].height = y - lasty;
	    else
	    	topy = y;
	    nright++;
	    lasty = y;
	}

	i = StepAround (i, clockwise, count);
	s = StepAround (s, clockwise, count);
    }
    if (nright != 0)
	right[nright-1].height = bottomy - lasty;

    if (slopeoff == 0)
	slopeoff = -1;
    else
	slopeoff = 0;

    nleft = 0;
    s = StepAround (top, slopeoff, count);
    i = top;
    while (i != bottom)
    {
	if (slopes[s].dy != 0)
	{
	    y = miPolyBuildEdge (vertices[i].x, vertices[i].y,
			   slopes[s].k,
		       	   slopes[s].dx,  slopes[s].dy, xi, yi, 1,
		       	   &left[nleft]);
    
	    if (nleft != 0)
	    	left[nleft-1].height = y - lasty;
	    nleft++;
	    lasty = y;
	}
	i = StepAround (i, -clockwise, count);
	s = StepAround (s, -clockwise, count);
    }
    if (nleft != 0)
	left[nleft-1].height = bottomy - lasty;
    *pnleft = nleft;
    *pnright = nright;
    *h = bottomy - topy;
    return topy;
}

static void
miLineOnePoint (GdkDrawable *pDrawable, GdkGC *pGC, GdkColor *pixel,
                SpanDataPtr spanData, int x, int y)
{
    GdkColor oldPixel;
    GdkSpan  span;

    MILINESETPIXEL (pDrawable, pGC, pixel, oldPixel);
    span.x = x;
    span.y = y;
    span.width = 1;

    gdk_fb_fill_spans(pDrawable, pGC, &span, 1, TRUE);
    MILINERESETPIXEL (pDrawable, pGC, pixel, oldPixel);
}

static void
miLineJoin (GdkDrawable *pDrawable, GdkGC *pGC, GdkColor *pixel,
            SpanDataPtr spanData, LineFacePtr pLeft, LineFacePtr pRight)
{
    double	    mx, my;
    double	    denom = 0.0;
    PolyVertexRec   vertices[4];
    PolySlopeRec    slopes[4];
    int		    edgecount;
    PolyEdgeRec	    left[4], right[4];
    int		    nleft, nright;
    int		    y, height;
    int		    swapslopes;
    int		    joinStyle = GDK_GC_FBDATA(pGC)->values.join_style;
    int		    lw = GDK_GC_FBDATA(pGC)->values.line_width;

    if (lw == 1 && !spanData) {
	/* Lines going in the same direction have no join */
	if (pLeft->dx >= 0 == pRight->dx <= 0)
	    return;
	if (joinStyle != GDK_JOIN_ROUND) {
    	    denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy;
    	    if (denom == 0)
	    	return;	/* no join to draw */
	}
	if (joinStyle != GDK_JOIN_MITER) {
	    miLineOnePoint (pDrawable, pGC, pixel, spanData, pLeft->x, pLeft->y);
	    return;
	}
    } else {
    	if (joinStyle == GDK_JOIN_ROUND)
    	{
	    miLineArc(pDrawable, pGC, pixel, spanData,
		      pLeft, pRight,
		      (double)0.0, (double)0.0, TRUE);
	    return;
    	}
    	denom = - pLeft->dx * (double)pRight->dy + pRight->dx * (double)pLeft->dy;
    	if (denom == 0.0)
	    return;	/* no join to draw */
    }

    swapslopes = 0;
    if (denom > 0)
    {
	pLeft->xa = -pLeft->xa;
	pLeft->ya = -pLeft->ya;
	pLeft->dx = -pLeft->dx;
	pLeft->dy = -pLeft->dy;
    }
    else
    {
	swapslopes = 1;
	pRight->xa = -pRight->xa;
	pRight->ya = -pRight->ya;
	pRight->dx = -pRight->dx;
	pRight->dy = -pRight->dy;
    }

    vertices[0].x = pRight->xa;
    vertices[0].y = pRight->ya;
    slopes[0].dx = -pRight->dy;
    slopes[0].dy =  pRight->dx;
    slopes[0].k = 0;

    vertices[1].x = 0;
    vertices[1].y = 0;
    slopes[1].dx =  pLeft->dy;
    slopes[1].dy = -pLeft->dx;
    slopes[1].k = 0;

    vertices[2].x = pLeft->xa;
    vertices[2].y = pLeft->ya;

    if (joinStyle == GDK_JOIN_MITER)
    {
    	my = (pLeft->dy  * (pRight->xa * pRight->dy - pRight->ya * pRight->dx) -
              pRight->dy * (pLeft->xa  * pLeft->dy  - pLeft->ya  * pLeft->dx )) /
	      denom;
    	if (pLeft->dy != 0)
    	{
	    mx = pLeft->xa + (my - pLeft->ya) *
			    (double) pLeft->dx / (double) pLeft->dy;
    	}
    	else
    	{
	    mx = pRight->xa + (my - pRight->ya) *
			    (double) pRight->dx / (double) pRight->dy;
    	}
	/* check miter limit */
	if ((mx * mx + my * my) * 4 > SQSECANT * lw * lw)
	    joinStyle = GDK_JOIN_BEVEL;
    }

    if (joinStyle == GDK_JOIN_MITER)
    {
	slopes[2].dx = pLeft->dx;
	slopes[2].dy = pLeft->dy;
	slopes[2].k =  pLeft->k;
	if (swapslopes)
	{
	    slopes[2].dx = -slopes[2].dx;
	    slopes[2].dy = -slopes[2].dy;
	    slopes[2].k  = -slopes[2].k;
	}
	vertices[3].x = mx;
	vertices[3].y = my;
	slopes[3].dx = pRight->dx;
	slopes[3].dy = pRight->dy;
	slopes[3].k  = pRight->k;
	if (swapslopes)
	{
	    slopes[3].dx = -slopes[3].dx;
	    slopes[3].dy = -slopes[3].dy;
	    slopes[3].k  = -slopes[3].k;
	}
	edgecount = 4;
    }
    else
    {
	double	scale, dx, dy, adx, ady;

	adx = dx = pRight->xa - pLeft->xa;
	ady = dy = pRight->ya - pLeft->ya;
	if (adx < 0)
	    adx = -adx;
	if (ady < 0)
	    ady = -ady;
	scale = ady;
	if (adx > ady)
	    scale = adx;
	slopes[2].dx = (dx * 65536) / scale;
	slopes[2].dy = (dy * 65536) / scale;
	slopes[2].k = ((pLeft->xa + pRight->xa) * slopes[2].dy -
		       (pLeft->ya + pRight->ya) * slopes[2].dx) / 2.0;
	edgecount = 3;
    }

    y = miPolyBuildPoly (vertices, slopes, edgecount, pLeft->x, pLeft->y,