#ifndef lint
static char sccsid[] = "@(#)subdiv_crv.c 9.2 88/01/19 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc.
 */

/*-
	Clip a curve by subdivision

	subdiv_crv.c, Tue Mar  4 09:57:13 1986

		James Gosling,
		Sun Microsystems
 */

#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "shape.h"
#include <stdio.h>
#include "fract.h"

sh_subdivide_curve(fb, shape, curve, op, texture, phase, t)
    register struct pixrect *fb;
    register struct shape_dcurve *curve;
    struct shape *shape;
    short      *texture;
    fract       phase;
    struct shape_trapezon *t;
{
    register short temp;
    register struct shape_trapseg *tps;
    struct shape_dcurve cu;
    short       leftout = 0,
                leftin = 0,
                rightin = fb->pr_width,
                rightout = rightin;
    short       top = 0;
    short       bottom = fb->pr_height;
    struct shape_trapseg *tps0;
    if (shape == 0)
	return 0;
    cu = *curve;
    if (cu.y0 == cu.y1) {	/* special case for horizontal segments */
	struct shape tshape;
	tshape = *shape;
	if (cu.x0 < cu.x1) {
	    tshape.pos.x = cu.x0;
	    tshape.size.x = cu.x1 - cu.x0;
	}
	else {
	    tshape.pos.x = cu.x1;
	    tshape.size.x = cu.x0 - cu.x1;
	}
	tshape.pos.y = cu.y0;
	tshape.size.y = 1;
	pr_shaperop(fb, &tshape, op, 0, 0, 0);
	if (curve->next)
	    return sh_subdivide_curve(fb, shape, curve->next, op,
				      texture, phase,
				      shape->trapset);
    }
    cu.next = 0;
    if (shape->is_rect || t == 0)
	abort();
    if ((temp = shape->pos.x) > leftout) {
	leftout = temp;
	leftin = temp;
    }
    if ((temp = shape->pos.x + shape->size.x) < rightin) {
	rightin = temp;
	rightout = temp;
    }
    if ((temp = shape->pos.y) > top)
	top = temp;
    if ((temp = shape->pos.y + shape->size.y) < bottom)
	bottom = temp;
    {
	register    min1,
	            max1,
	            min2,
	            max2;
	if (t->top > top)
	    top = t->top;
	if (t->bottom < bottom)
	    bottom = t->bottom;
	if ((min1 = t->top - cu.y0) >= 0) {
	    cu.x += min1;
	    cu.y0 = t->top;
	    cu.x0 = *cu.x;
	    tps = t->segs;
	}
	else {
	    register    lo,
	                hi;
	    lo = 0;
	    hi = t->used - 1;
	    while (lo < hi) {
		register    mid;
		mid = (hi + lo + 1) >> 1;
		if (t->segs[mid].y <= cu.y0)
		    lo = mid;
		else
		    hi = mid - 1;
	    }
	    tps = &t->segs[lo];
	}
	if (cu.y1 >= bottom) {
	    cu.y1 = bottom - 1;
	    cu.x1 = cu.x[cu.y1 - cu.y0];
	}
	tps0 = tps;
	min1 = tps->x1;
	max1 = min1;
	min2 = tps->x2;
	max2 = min2;
	while ((++tps)->y <= cu.y1) {
	    if ((temp = tps->x1) < min1)
		min1 = temp;
	    if (temp > max1)
		max1 = temp;
	    if ((temp = tps->x2) < min2)
		min2 = temp;
	    if (temp > max2)
		max2 = temp;
	}
	if (max1 >= min2) {
	    if (min1 > leftout)
		leftout = min1;
	    if (max2 < rightin)
		rightin = max2;
	    leftin = rightin;
	    rightout = rightin;
	}
	else {
	    leftout = min1;
	    leftin = max1;
	    rightin = min2;
	    rightout = max2;
	}
    }
    if (leftout >= rightout
	    || cu.y0 >= bottom
	    || cu.y1 < top
	    || cu.right <= leftout
	    || cu.left >= rightout) {	/* Completely outside this trapezon */
	if (t->next)
	    phase += sh_subdivide_curve(fb, shape, &cu, op,
					texture, phase, t->next);
	if (curve->next)
	    return sh_subdivide_curve(fb, shape, curve->next, op,
				      texture, phase,
				      shape->trapset);
	return phase;
    }
    if (leftin <= cu.left && cu.right <= rightin) {
	struct shape tsh;	/* Completely inside this trapezon */
	tsh = InfiniteShape;
	tsh.pos.y = top;
	if ((tsh.size.y = bottom - top) > 0)
	    phase += pr_shapecurve(fb, &InfiniteShape, &cu, op | PIX_DONTCLIP,
				   texture, phase);
	if (curve->next)
	    return sh_subdivide_curve(fb, shape, curve->next, op,
				      texture, phase,
				      shape->trapset);
	return phase;
    }
    /* May interact with the edges */
    if (cu.y0 < top) {
	if (texture && *texture)
	    printf("Texture adjustment\n");
	cu.x += top - cu.y0;
	cu.y0 = top;
	cu.x0 = cu.x[0];
    }
    if (cu.y1 > bottom) {
	if (texture && *texture)
	    printf("Deferred texture adjustment\n");
	cu.y1 = bottom;
    }
    tps = tps0;
    if (cu.y0 > cu.y1) {
	if (t->next) {		/* Pieces may dangle elsewhere */
	    cu = *curve;
	    cu.next = 0;
	    sh_subdivide_curve(fb, shape, &cu, op,
			       texture, phase, t->next);
	}
	if (curve->next)	/* The rest of the curve: this is yet another
				 * candidate for tail recursion elimination */
	    return sh_subdivide_curve(fb, shape, curve->next, op,
				      texture, phase,
				      shape->trapset);
	return phase;
    }
    /* WRITE_AROUND */
    while (tps[0].y == tps[1].y && tps[0].y <= bottom)
	tps++;
    /* assert(tps[0].y <= cu.y0 && cu.y0 < tps[1].y); */
    {
	register short *x = cu.x + 1,
	            y = cu.y0,
	            ylimit = cu.y1,
	            x0,
	            x1;
	while (y < ylimit) {
	    assert(x - 1 == cu.x);
	    assert(y == cu.y0);
	    if (tps->x1 <= x[-1] && x[-1] < tps->x2
		    || tps->x1 < x[0] && x[0] < tps->x2) {
		x0 = x[-1];
		if (x[-1] < tps->x1)
		    x[-1] = tps->x1;
		if (x[-1] >= tps->x2)
		    x[-1] = tps->x2 - 1;
		while (tps->x1 <= *x && *x < tps->x2 && y < ylimit) {
		    if (tps->x1 <= cu.left && cu.right <= tps->x2) {
			tps++;
			if (tps->y > ylimit) {
			    x += ylimit - y;
			    y = ylimit;
			    tps--;
			}
			else {
			    x += tps->y - y;
			    y = tps->y;
			}
		    }
		    else {
			x++;
			y++;
			if (y >= tps[1].y)
			    tps++;
		    }
		}
		x1 = *x;
		cu.y1 = y;
		if (y == tps->y && y > cu.y0) {
		    if (*x < tps[-1].x1)
			*x = tps[-1].x1;
		    if (*x >= tps[-1].x2)
			*x = tps[-1].x2 - 1;
		    if (x[-1] < tps->x1 || x[-1] >= tps->x2)
			cu.y1--;
		}
		else {
		    if (*x < tps->x1)
			*x = tps->x1;
		    if (*x >= tps->x2)
			*x = tps->x2 - 1;
		}
		cu.x0 = *cu.x;
		if (cu.x0 < cu.x[1])
		    cu.x0++;
/*-		else if (cu.x0 > cu.x[1])
		    cu.x0--; */
		cu.x1 = *x;
		pr_shapecurve(fb, &InfiniteShape, &cu, op,
			      texture, phase);
		*cu.x = x0;
		*x = x1;
	    }
	    if (tps->x1 >= *x) {
		do {
		    if (cu.right <= tps->x1) {
			tps++;
			if (tps->y >= ylimit) {
			    x += ylimit - y;
			    y = ylimit;
			}
			else {
			    x += tps->y - y;
			    y = tps->y;
			}
		    }
		    else {
			x++;
			y++;
			if (y >= tps[1].y)
			    tps++;
		    }
		} while (tps->x1 > *x && y < ylimit);
	    }
	    else
		while (tps->x2 <= *x && y < ylimit) {
		    if (tps->x2 <= cu.left) {
			tps++;
			if (tps->y >= ylimit) {
			    x += ylimit - y;
			    y = ylimit;
			}
			else {
			    x += tps->y - y;
			    y = tps->y;
			}
		    }
		    else {
			x++;
			y++;
			if (y >= tps[1].y)
			    tps++;
		    }
		}
	    cu.x = x - 1;
	    cu.y0 = y;
	}
    }
    if (t->next) {		/* Pieces may dangle elsewhere */
	cu = *curve;
	cu.next = 0;
	sh_subdivide_curve(fb, shape, &cu, op,
			   texture, phase, t->next);
    }
    if (curve->next)		/* The rest of the curve: this is yet another
				 * candidate for tail recursion elimination */
	return sh_subdivide_curve(fb, shape, curve->next, op,
				  texture, phase,
				  shape->trapset);
    return phase;
}