nuclear@9: #include "lines.h"
nuclear@9: 
nuclear@9: enum {
nuclear@9: 	IN		= 0,
nuclear@9: 	LEFT	= 1,
nuclear@9: 	RIGHT	= 2,
nuclear@9: 	TOP		= 4,
nuclear@9: 	BOTTOM	= 8
nuclear@9: };
nuclear@9: 
nuclear@9: static int outcode(int x, int y, int minx, int miny, int maxx, int maxy)
nuclear@9: {
nuclear@9: 	int code = 0;
nuclear@9: 
nuclear@9: 	if(x < minx) {
nuclear@9: 		code |= LEFT;
nuclear@9: 	} else if(x > maxx) {
nuclear@9: 		code |= RIGHT;
nuclear@9: 	}
nuclear@9: 	if(y < miny) {
nuclear@9: 		code |= TOP;
nuclear@9: 	} else if(y > maxy) {
nuclear@9: 		code |= BOTTOM;
nuclear@9: 	}
nuclear@9: 	return code;
nuclear@9: }
nuclear@9: 
nuclear@9: #define FIXMUL(a, b)	(((a) * (b)) >> 8)
nuclear@9: #define FIXDIV(a, b)	(((a) << 8) / (b))
nuclear@9: 
nuclear@9: #define LERP(a, b, t)	((a) + FIXMUL((b) - (a), (t)))
nuclear@9: 
nuclear@9: int clip_line2d(int *x0, int *y0, int *x1, int *y1, const int *vp)
nuclear@9: {
nuclear@9: 	int oc_out;
nuclear@9: 	int minx = vp[0];
nuclear@9: 	int miny = vp[1];
nuclear@9: 	int maxx = vp[0] + vp[2] - 1;
nuclear@9: 	int maxy = vp[1] + vp[3] - 1;
nuclear@9: 
nuclear@9: 	int oc0 = outcode(*x0, *y0, minx, miny, maxx, maxy);
nuclear@9: 	int oc1 = outcode(*x1, *y1, minx, miny, maxx, maxy);
nuclear@9: 
nuclear@9: 	int32_t fx0, fy0, fx1, fy1, fminx, fminy, fmaxx, fmaxy;
nuclear@9: 
nuclear@9: 	if(!(oc0 | oc1)) return 1;	/* both points are inside */
nuclear@9: 
nuclear@9: 	fx0 = *x0 << 8;
nuclear@9: 	fy0 = *y0 << 8;
nuclear@9: 	fx1 = *x1 << 8;
nuclear@9: 	fy1 = *y1 << 8;
nuclear@9: 	fminx = minx << 8;
nuclear@9: 	fminy = miny << 8;
nuclear@9: 	fmaxx = maxx << 8;
nuclear@9: 	fmaxy = maxy << 8;
nuclear@9: 
nuclear@9: 	for(;;) {
nuclear@9: 		int32_t x, y, t;
nuclear@9: 
nuclear@9: 		if(oc0 & oc1) return 0;		/* both have points with the same outbit, not visible */
nuclear@9: 		if(!(oc0 | oc1)) break;		/* both points are inside */
nuclear@9: 
nuclear@9: 		oc_out = oc0 ? oc0 : oc1;
nuclear@9: 
nuclear@9: 		if(oc_out & TOP) {
nuclear@9: 			t = FIXDIV(fminy - fy0, fy1 - fy0);
nuclear@9: 			x = LERP(fx0, fx1, t);
nuclear@9: 			y = fminy;
nuclear@9: 		} else if(oc_out & BOTTOM) {
nuclear@9: 			t = FIXDIV(fmaxy - fy0, fy1 - fy0);
nuclear@9: 			x = LERP(fx0, fx1, t);
nuclear@9: 			y = fmaxy;
nuclear@9: 		} else if(oc_out & LEFT) {
nuclear@9: 			t = FIXDIV(fminx - fx0, fx1 - fx0);
nuclear@9: 			x = fminx;
nuclear@9: 			y = LERP(fy0, fy1, t);
nuclear@9: 		} else if(oc_out & RIGHT) {
nuclear@9: 			t = FIXDIV(fmaxx - fx0, fx1 - fx0);
nuclear@9: 			x = fmaxx;
nuclear@9: 			y = LERP(fy0, fy1, t);
nuclear@9: 		}
nuclear@9: 
nuclear@9: 		if(oc_out == oc0) {
nuclear@9: 			fx0 = x;
nuclear@9: 			fy0 = y;
nuclear@9: 			oc0 = outcode(fx0 >> 8, fy0 >> 8, minx, miny, maxx, maxy);
nuclear@9: 		} else {
nuclear@9: 			fx1 = x;
nuclear@9: 			fy1 = y;
nuclear@9: 			oc1 = outcode(fx1 >> 8, fy1 >> 8, minx, miny, maxx, maxy);
nuclear@9: 		}
nuclear@9: 	}
nuclear@9: 
nuclear@9: 	*x0 = fx0 >> 8;
nuclear@9: 	*y0 = fy0 >> 8;
nuclear@9: 	*x1 = fx1 >> 8;
nuclear@9: 	*y1 = fy1 >> 8;
nuclear@9: 	return 1;
nuclear@9: }
nuclear@9: 
nuclear@9: void draw_line(uint32_t *fb, int fbwidth, uint32_t col, int x0, int y0, int x1, int y1)
nuclear@9: {
nuclear@9: 	int i, dx, dy, x_inc, y_inc, error;
nuclear@9: 
nuclear@9: 	fb += y0 * fbwidth + x0;
nuclear@9: 
nuclear@9: 	dx = x1 - x0;
nuclear@9: 	dy = y1 - y0;
nuclear@9: 
nuclear@9: 	if(dx >= 0) {
nuclear@9: 		x_inc = 1;
nuclear@9: 	} else {
nuclear@9: 		x_inc = -1;
nuclear@9: 		dx = -dx;
nuclear@9: 	}
nuclear@9: 	if(dy >= 0) {
nuclear@9: 		y_inc = fbwidth;
nuclear@9: 	} else {
nuclear@9: 		y_inc = -fbwidth;
nuclear@9: 		dy = -dy;
nuclear@9: 	}
nuclear@9: 
nuclear@9: 	if(dx > dy) {
nuclear@9: 		error = dy * 2 - dx;
nuclear@9: 		for(i=0; i<=dx; i++) {
nuclear@9: 			*fb = col;
nuclear@9: 			if(error >= 0) {
nuclear@9: 				error -= dx * 2;
nuclear@9: 				fb += y_inc;
nuclear@9: 			}
nuclear@9: 			error += dy * 2;
nuclear@9: 			fb += x_inc;
nuclear@9: 		}
nuclear@9: 	} else {
nuclear@9: 		error = dx * 2 - dy;
nuclear@9: 		for(i=0; i<=dy; i++) {
nuclear@9: 			*fb = col;
nuclear@9: 			if(error >= 0) {
nuclear@9: 				error -= dy * 2;
nuclear@9: 				fb += x_inc;
nuclear@9: 			}
nuclear@9: 			error += dx * 2;
nuclear@9: 			fb += y_inc;
nuclear@9: 		}
nuclear@9: 	}
nuclear@9: }