generators.c

miniucgui1.30版本的源码

/*
** $Id: generators.c,v 1.8 2003/09/04 06:02:53 weiym Exp $
**
** generators.c: general line, circle, ellipse, arc generators.
**
** Copyright (C) 2003 Feynman Software
** Copyright (C) 2001 ~ 2002 Wei Yongming.
**
** The line clipping algorithm comes from GGI.
** Copyright (C) 1998 Alexander Larsson <[e-mail]>
**
** The line generator comes from MicroWindows.
** Copyright (C) 1999 Greg Haerr <[e-mail]>
**
** All other generators come from Allegro by Shawn Hargreaves and others. 
** Thank for their great work and good license.
**
** "Allegro is a gift-software"
**
** Current maintainer: Wei Yongming.
**
** Create date: 2001/10/12, derived from original draw.c
*/

/*
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

/*
** TODO:
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "common.h"
#include "minigui.h"
#include "gdi.h"
#include "fixedmath.h"

/* Line clipper */
/*
  This is a line-clipper using the algorithm by cohen-sutherland.

  It is modified to do pixel-perfect clipping. This means that it
  will generate the same endpoints that would be drawn if an ordinary
  bresenham line-drawer where used and only visible pixels drawn.

  It can be used with a bresenham-like linedrawer if it is modified to
  start with a correct error-term.
*/

#define OC_LEFT 1
#define OC_RIGHT 2
#define OC_TOP 4
#define OC_BOTTOM 8

/* Outcodes:
+-> x
|       |      | 
V  0101 | 0100 | 0110
y ---------------------
   0001 | 0000 | 0010
  ---------------------
   1001 | 1000 | 1010
        |      | 
 */
#define outcode(code, xx, yy) \
{\
  code = 0;\
 if (xx < cliprc->left)\
    code |= OC_LEFT;\
  else if (xx >= cliprc->right)\
    code |= OC_RIGHT;\
  if (yy < cliprc->top)\
    code |= OC_TOP;\
  else if (yy >= cliprc->bottom)\
    code |= OC_BOTTOM;\
}

/*
  Calculates |_ a/b _| with mathematically correct floor
  */
static int FloorDiv(int a, int b)
{
    int floor;
    if (b>0) {
        if (a>0) {
            return a /b;
        } else {
            floor = -((-a)/b);
            if ((-a)%b != 0)
                floor--;
        }
        return floor;
    } else {
        if (a>0) {
            floor = -(a/(-b));
            if (a%(-b) != 0)
                floor--;
            return floor;
        } else {
            return (-a)/(-b);
        }
    }
}
/*
  Calculates |^ a/b ^| with mathamatically correct floor
  */
static int CeilDiv(int a,int b)
{
    if (b>0)
        return FloorDiv(a-1,b)+1;
    else
        return FloorDiv(-a-1,-b)+1;
}

BOOL GUIAPI LineClipper (const RECT* cliprc, int *_x0, int *_y0, int *_x1, int *_y1)
{
    int first, last, code;
    int x0, y0, x1, y1;
    int x, y;
    int dx, dy;
    int xmajor;
    int slope;
    
    if (*_x0 == *_x1 && *_y0 == *_y1) { /* a pixel*/
        return PtInRect (cliprc, *_x0, *_y0);
    }
    else if (*_x0 == *_x1) { /* a vertical line */
        int sy, ey;

        if (*_y1 > *_y0) {
            sy = *_y0;
            ey = *_y1;
        }
        else {
            sy = *_y1;
            ey = *_y0;
        }

        if ( (*_x0 >= cliprc->right) || (sy >= cliprc->bottom) || 
                    (*_x0 < cliprc->left) || (ey < cliprc->top) )
            return FALSE;

        if ( (*_x0 >= cliprc->left) && (sy >= cliprc->top) && 
                    (*_x0 < cliprc->right) && (ey < cliprc->bottom) )
            return TRUE;
                    
        if (sy < cliprc->top)
            sy = cliprc->top;
        if (ey >= cliprc->bottom)
            ey = cliprc->bottom - 1;

        if (ey < sy)
            return FALSE;

        *_y0 = sy;
        *_y1 = ey;
        return TRUE;
    }
    else if (*_y0 == *_y1) { /* a horizontal line */
        int sx, ex;

        if (*_x1 > *_x0) {
            sx = *_x0;
            ex = *_x1;
        }
        else {
            sx = *_x1;
            ex = *_x0;
        }

        if ( (sx >= cliprc->right) || (*_y0 >= cliprc->bottom) || 
                    (ex < cliprc->left) || (*_y0 < cliprc->top) )
            return FALSE;

        if ( (sx >= cliprc->left) && (*_y0 >= cliprc->top) && 
                    (ex < cliprc->right) && (*_y0 < cliprc->bottom) )
            return TRUE;
                    
        if (sx < cliprc->left)
            sx = cliprc->left;
        if (ex >= cliprc->right)
            ex = cliprc->right - 1;

        if (ex < sx)
            return FALSE;

        *_x0 = sx;
        *_x1 = ex;
        return TRUE;
    }

    first = 0;
    last = 0;
    outcode (first, *_x0, *_y0);
    outcode (last, *_x1, *_y1);

    if ((first | last) == 0) {
        return TRUE; /* Trivially accepted! */
    }

    if ((first & last) != 0) {
        return FALSE; /* Trivially rejected! */
    }

    x0 = *_x0; y0 = *_y0;
    x1 = *_x1; y1 = *_y1;

    dx = x1 - x0;
    dy = y1 - y0;
  
    xmajor = (ABS (dx) > ABS (dy));
    slope = ((dx>=0) && (dy>=0)) || ((dx<0) && (dy<0));
  
    while (TRUE) {
        code = first;
        if (first == 0)
            code = last;

        if (code & OC_LEFT) {
            x = cliprc->left;
            if (xmajor) {
                y = *_y0 + FloorDiv (dy * (x - *_x0) * 2 + dx, 2 * dx);
            } else {
                if (slope) {
                    y = *_y0 + CeilDiv (dy * ((x - *_x0) * 2 - 1), 2 * dx);
                } else {
                    y = *_y0 + FloorDiv (dy * ((x - *_x0) * 2 - 1), 2 * dx);
                }
            }
        } else if (code & OC_RIGHT) {
            x = cliprc->right - 1;
            if (xmajor) {
                y = *_y0 +  FloorDiv (dy * (x - *_x0) * 2 + dx, 2 * dx);
            } else {
                if (slope) {
                    y = *_y0 + CeilDiv (dy * ((x - *_x0) * 2 + 1), 2 * dx) - 1;
                } else {
                    y = *_y0 + FloorDiv (dy * ((x - *_x0) * 2 + 1), 2 * dx) + 1;
                }
            }
        } else if (code & OC_TOP) {
            y = cliprc->top;
            if (xmajor) {
                if (slope) {
                    x = *_x0 + CeilDiv (dx * ((y - *_y0) * 2 - 1), 2 * dy);
                } else {
                    x = *_x0 + FloorDiv (dx * ((y - *_y0) * 2 - 1), 2 * dy);
                }
            } else {
                x = *_x0 +  FloorDiv (dx * (y - *_y0) * 2 + dy, 2 * dy);
            }
        } else { /* OC_BOTTOM */
            y = cliprc->bottom - 1;
            if (xmajor) {
                if (slope) {
                    x = *_x0 + CeilDiv (dx * ((y - *_y0) * 2 + 1), 2 * dy) - 1;
                } else {
                    x = *_x0 + FloorDiv (dx * ((y - *_y0) * 2 + 1), 2 * dy) + 1;
                }
            } else {
                x = *_x0 +  FloorDiv (dx * (y - *_y0) * 2 + dy, 2 * dy);
            }
        }

        if (first) {
            x0 = x;
            y0 = y;
            outcode (first, x0, y0);
        } else {
            x1 = x;
            y1 = y;
            last = code;
            outcode (last, x1, y1);
        }
    
        if ((first & last) != 0) {
            return FALSE; /* Trivially rejected! */
        }

        if ((first | last) == 0) {
            *_x0 = x0; *_y0 = y0;
            *_x1 = x1; *_y1 = y1;
            return TRUE; /* Trivially accepted! */
        }
    }
}

/* Breshenham line generator */
void GUIAPI LineGenerator (void* context, int x1, int y1, int x2, int y2, CB_LINE cb)
{
    int xdelta;     /* width of rectangle around line */
    int ydelta;     /* height of rectangle around line */
    int xinc;       /* increment for moving x coordinate */
    int yinc;       /* increment for moving y coordinate */
    int rem;        /* current remainder */
    
    cb (context, 0, 0);

    if (x1 == x2 && y1 == y2) { /* a pixel */
        return;
    }
    else if (x1 == x2) { /* a vertical line */
        int dir = (y2 > y1) ? 1 : -1;

        do {
            cb (context, 0, dir);
            y1 += dir;
        } while (y1 != y2);
        return;
    }
    else if (y1 == y2) { /* a horizontal line */
        int dir = (x2 > x1) ? 1 : -1;

        do {
            cb (context, dir, 0);
            x1 += dir;
        } while (x1 != x2);
        return;
    }

    xdelta = x2 - x1;
    ydelta = y2 - y1;
    if (xdelta < 0) xdelta = -xdelta;
    if (ydelta < 0) ydelta = -ydelta;

    xinc = (x2 > x1) ? 1 : -1;
    yinc = (y2 > y1) ? 1 : -1;

    if (xdelta >= ydelta) {
        rem = xdelta >> 1;
        while (x1 != x2) {
            x1 += xinc;
            rem += ydelta;
            if (rem >= xdelta) {
                rem -= xdelta;
                y1 += yinc;
                cb (context, xinc, yinc);
            }
            else
                cb (context, xinc, 0);
        }
    } else {
        rem = ydelta >> 1;
        while (y1 != y2) {
            y1 += yinc;
            rem += xdelta;
            if (rem >= ydelta) {
                rem -= ydelta;
                x1 += xinc;
                cb (context, xinc, yinc);
            }
            else
                cb (context, 0, yinc);