1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/lines.c	Thu Apr 10 02:31:31 2014 +0300
     1.3 @@ -0,0 +1,146 @@
     1.4 +#include "lines.h"
     1.5 +
     1.6 +enum {
     1.7 +	IN		= 0,
     1.8 +	LEFT	= 1,
     1.9 +	RIGHT	= 2,
    1.10 +	TOP		= 4,
    1.11 +	BOTTOM	= 8
    1.12 +};
    1.13 +
    1.14 +static int outcode(int x, int y, int minx, int miny, int maxx, int maxy)
    1.15 +{
    1.16 +	int code = 0;
    1.17 +
    1.18 +	if(x < minx) {
    1.19 +		code |= LEFT;
    1.20 +	} else if(x > maxx) {
    1.21 +		code |= RIGHT;
    1.22 +	}
    1.23 +	if(y < miny) {
    1.24 +		code |= TOP;
    1.25 +	} else if(y > maxy) {
    1.26 +		code |= BOTTOM;
    1.27 +	}
    1.28 +	return code;
    1.29 +}
    1.30 +
    1.31 +#define FIXMUL(a, b)	(((a) * (b)) >> 8)
    1.32 +#define FIXDIV(a, b)	(((a) << 8) / (b))
    1.33 +
    1.34 +#define LERP(a, b, t)	((a) + FIXMUL((b) - (a), (t)))
    1.35 +
    1.36 +int clip_line2d(int *x0, int *y0, int *x1, int *y1, const int *vp)
    1.37 +{
    1.38 +	int oc_out;
    1.39 +	int minx = vp[0];
    1.40 +	int miny = vp[1];
    1.41 +	int maxx = vp[0] + vp[2] - 1;
    1.42 +	int maxy = vp[1] + vp[3] - 1;
    1.43 +
    1.44 +	int oc0 = outcode(*x0, *y0, minx, miny, maxx, maxy);
    1.45 +	int oc1 = outcode(*x1, *y1, minx, miny, maxx, maxy);
    1.46 +
    1.47 +	int32_t fx0, fy0, fx1, fy1, fminx, fminy, fmaxx, fmaxy;
    1.48 +
    1.49 +	if(!(oc0 | oc1)) return 1;	/* both points are inside */
    1.50 +
    1.51 +	fx0 = *x0 << 8;
    1.52 +	fy0 = *y0 << 8;
    1.53 +	fx1 = *x1 << 8;
    1.54 +	fy1 = *y1 << 8;
    1.55 +	fminx = minx << 8;
    1.56 +	fminy = miny << 8;
    1.57 +	fmaxx = maxx << 8;
    1.58 +	fmaxy = maxy << 8;
    1.59 +
    1.60 +	for(;;) {
    1.61 +		int32_t x, y, t;
    1.62 +
    1.63 +		if(oc0 & oc1) return 0;		/* both have points with the same outbit, not visible */
    1.64 +		if(!(oc0 | oc1)) break;		/* both points are inside */
    1.65 +
    1.66 +		oc_out = oc0 ? oc0 : oc1;
    1.67 +
    1.68 +		if(oc_out & TOP) {
    1.69 +			t = FIXDIV(fminy - fy0, fy1 - fy0);
    1.70 +			x = LERP(fx0, fx1, t);
    1.71 +			y = fminy;
    1.72 +		} else if(oc_out & BOTTOM) {
    1.73 +			t = FIXDIV(fmaxy - fy0, fy1 - fy0);
    1.74 +			x = LERP(fx0, fx1, t);
    1.75 +			y = fmaxy;
    1.76 +		} else if(oc_out & LEFT) {
    1.77 +			t = FIXDIV(fminx - fx0, fx1 - fx0);
    1.78 +			x = fminx;
    1.79 +			y = LERP(fy0, fy1, t);
    1.80 +		} else if(oc_out & RIGHT) {
    1.81 +			t = FIXDIV(fmaxx - fx0, fx1 - fx0);
    1.82 +			x = fmaxx;
    1.83 +			y = LERP(fy0, fy1, t);
    1.84 +		}
    1.85 +
    1.86 +		if(oc_out == oc0) {
    1.87 +			fx0 = x;
    1.88 +			fy0 = y;
    1.89 +			oc0 = outcode(fx0 >> 8, fy0 >> 8, minx, miny, maxx, maxy);
    1.90 +		} else {
    1.91 +			fx1 = x;
    1.92 +			fy1 = y;
    1.93 +			oc1 = outcode(fx1 >> 8, fy1 >> 8, minx, miny, maxx, maxy);
    1.94 +		}
    1.95 +	}
    1.96 +
    1.97 +	*x0 = fx0 >> 8;
    1.98 +	*y0 = fy0 >> 8;
    1.99 +	*x1 = fx1 >> 8;
   1.100 +	*y1 = fy1 >> 8;
   1.101 +	return 1;
   1.102 +}
   1.103 +
   1.104 +void draw_line(uint32_t *fb, int fbwidth, uint32_t col, int x0, int y0, int x1, int y1)
   1.105 +{
   1.106 +	int i, dx, dy, x_inc, y_inc, error;
   1.107 +
   1.108 +	fb += y0 * fbwidth + x0;
   1.109 +
   1.110 +	dx = x1 - x0;
   1.111 +	dy = y1 - y0;
   1.112 +
   1.113 +	if(dx >= 0) {
   1.114 +		x_inc = 1;
   1.115 +	} else {
   1.116 +		x_inc = -1;
   1.117 +		dx = -dx;
   1.118 +	}
   1.119 +	if(dy >= 0) {
   1.120 +		y_inc = fbwidth;
   1.121 +	} else {
   1.122 +		y_inc = -fbwidth;
   1.123 +		dy = -dy;
   1.124 +	}
   1.125 +
   1.126 +	if(dx > dy) {
   1.127 +		error = dy * 2 - dx;
   1.128 +		for(i=0; i<=dx; i++) {
   1.129 +			*fb = col;
   1.130 +			if(error >= 0) {
   1.131 +				error -= dx * 2;
   1.132 +				fb += y_inc;
   1.133 +			}
   1.134 +			error += dy * 2;
   1.135 +			fb += x_inc;
   1.136 +		}
   1.137 +	} else {
   1.138 +		error = dx * 2 - dy;
   1.139 +		for(i=0; i<=dy; i++) {
   1.140 +			*fb = col;
   1.141 +			if(error >= 0) {
   1.142 +				error -= dy * 2;
   1.143 +				fb += x_inc;
   1.144 +			}
   1.145 +			error += dx * 2;
   1.146 +			fb += y_inc;
   1.147 +		}
   1.148 +	}
   1.149 +}