/*
 *
 *	line_clip.c: homogeneous 3D line clipping
 *
 *	Philippe Bekaert	Apr, 29 1995
 *
 *      Bascially, it is Paul Heckbert's code (see poly_scan.c) 
 *	adapted for lines instead of convex polygons.
 */
#include <stdio.h>
#include "line.h"

/*
 * line_clip_to_box; Clip a line to a 3D clipping box using homogeneous
 *	screencoordinates (sx,sy,sz,sw).
 *
 * returns:
 * 	- LINE_CLIP_OUT: if the line is totally outside the clipping box
 *	- LINE_CLIP_IN: if the line is totally inside
 *	- LINE_CLIP_PARTIAL: if the line is cut by the box. The line is
 *	  modified.
 */

int line_clip_to_box(Line *lin, Poly_box *box)
{
	int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, 
	    z1out = 0;
	Poly_vert *v1 = &lin->v1, *v2 = &lin->v2;
	float t1, t2, u1, u2, t, *p1, *p2, dp;
	int mask;

/* check first vertex - note how lot's of multiplications could be avoided
 * since the box is always [-1:1] in each direction */
	if (v1->sx < box->x0*v1->sw) x0out++;	/* out on left */
	if (v1->sx > box->x1*v1->sw) x1out++;	/* out on right */
	if (v1->sy < box->y0*v1->sw) y0out++;	/* out on top */
	if (v1->sy > box->y1*v1->sw) y1out++;	/* out on bottom */
	if (v1->sz < box->z0*v1->sw) z0out++;	/* out on near */
	if (v1->sz > box->z1*v1->sw) z1out++;	/* out on far */

/* check second vertex */
	if (v2->sx < box->x0*v2->sw) x0out++;	/* out on left */
	if (v2->sx > box->x1*v2->sw) x1out++;	/* out on right */
	if (v2->sy < box->y0*v2->sw) y0out++;	/* out on top */
	if (v2->sy > box->y1*v2->sw) y1out++;	/* out on bottom */
	if (v2->sz < box->z0*v2->sw) z0out++;	/* out on near */
	if (v2->sz > box->z1*v2->sw) z1out++;	/* out on far */

/* check if all vertices inside */
	if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return LINE_CLIP_IN;

/* check if both vertices are "outside" any of the six planes */
	if (x0out==2 || x1out==2 || y0out==2 ||
	    y1out==2 || z0out==2 || z1out==2) 
	    return LINE_CLIP_OUT;

/* now find the portion of the line inside the clipping box. It is the
 * portion given by points p satisfying: p = v1 + t * (v2-v1) with
 * t in [t1..t2]. To find t1 and t2, we start with the full line and
 * cut off pieces outside the clipping box. */
	t1 = 0.; t2 = 1.;	

	if (x0out) {	/* x0out is 0 or 1: either both points are
			 * right of the plane x/w = box->x0 or one
			 * is on the left (outside) and the other on 
			 * the right (inside the clipping box */

		u1 = v1->sx - box->x0 * v1->sw;
		u2 = v2->sx - box->x0 * v2->sw;
		t = u1 / (u1-u2);	/* intersection with x/w=box->x0
					 * plane is found by filling
					 * the points in the equation of 
					 * the plane */

		if (u1 > 0) {	/* v1 is right of the plane, v2 left */
			t2 = t;
		} else {	/* v1 is left, v2 must be on the right */
			t1 = t;
		}
	}

	if (x1out) {
		u1 = v1->sx - box->x1 * v1->sw;
		u2 = v2->sx - box->x1 * v2->sw;
		t = u1 / (u1-u2);	
		if (u1 <= 0) {	/* v1 is left of the plane, v2 right */
			if (t < t2) t2 = t;
		} else {	/* v1 is right, v2 must be on the left */
			if (t > t1) t1 = t;
		}
	}

	if (y0out) {
		u1 = v1->sy - box->y0 * v1->sw;
		u2 = v2->sy - box->y0 * v2->sw;
		t = u1 / (u1-u2);	
		if (u1 > 0) {	
			if (t < t2) t2 = t;
		} else {	
			if (t > t1) t1 = t;
		}
	}

	if (y1out) {
		u1 = v1->sy - box->y1 * v1->sw;
		u2 = v2->sy - box->y1 * v2->sw;
		t = u1 / (u1-u2);	
		if (u1 <= 0) {	
			if (t < t2) t2 = t;
		} else {	
			if (t > t1) t1 = t;
		}
	}

	if (z0out) {
		u1 = v1->sz - box->z0 * v1->sw;
		u2 = v2->sz - box->z0 * v2->sw;
		t = u1 / (u1-u2);	
		if (u1 > 0) {	
			if (t < t2) t2 = t;
		} else {	
			if (t > t1) t1 = t;
		}
	}

	if (z1out) {
		u1 = v1->sz - box->z1 * v1->sw;
		u2 = v2->sz - box->z1 * v2->sw;
		t = u1 / (u1-u2);	
		if (u1 <= 0) {	
			if (t < t2) t2 = t;
		} else {	
			if (t > t1) t1 = t;
		}
	}

/* the whole line is outside the clipping box */
	if (t2 <= t1) 
		return LINE_CLIP_OUT;

/* find the new endpoints of the line */
	t2 = 1. - t2;	/* makes things simpler */
	p1 = (float *)v1; 
	p2 = (float *)v2;

	if (t1 > 0. && t2 > 0.) {
		for (mask = lin->mask; mask; mask >>= 1, p1++, p2++) 
			if (mask&1) {
				dp = *p2 - *p1;
				*p1 += t1 * dp;
				*p2 -= t2 * dp;
			}
	} else if (t1 > 0.) {
		for (mask = lin->mask; mask; mask >>= 1, p1++, p2++) 
			if (mask&1) 
				*p1 += t1 * (*p2 - *p1);
	} else if (t2 > 0.) {
		for (mask = lin->mask; mask; mask >>= 1, p1++, p2++) 
			if (mask&1) 
				*p2 += t2 * (*p1 - *p2);
	}

	return LINE_CLIP_PARTIAL;
}