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

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

/*-
	Produce a set of curves from a path

	dcurvepath.c, Wed Sep 11 16:33:01 1985

 */

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

#define sfrsq(a) frsq(frrsh(a, 4))


struct shape_dcurve *
shape_dcurvepath(l)
    struct shape_arc *l;
{
    register struct shape_arc *p;
    fract       miny;
    short       globalmaxy;
    struct shape_arc *topmost;
    struct shape_dcurve *chains = 0;

    /*
     * Run through all the arcs, converting curvature to sharpness and
     * subdividing arcs which contain a vertical or horizontal minima or
     * maxima
     */
    p = l;
    do {
	if (p->sh < 0) {
	    register    denom = frlsh(sfrsq(p->C.x - p->B.x)
				      + sfrsq(p->C.y - p->B.y)
				      + sfrsq(p->A.x - p->B.x)
				      + sfrsq(p->A.y - p->B.y),
				      1);
	    if (denom)
		p->sh = frmul(-p->sh,
			      frsqrt(frdiv(sfrsq(p->A.x - p->C.x)
					   + sfrsq(p->A.y - p->C.y),
					   denom)));
	    else
		p->sh = 0 /* FRHUGE */;
	}
	if (p->sh != 0) {
	    if (p->A.y != p->B.y && p->B.y != p->C.y &&
		    (p->A.y < p->B.y) != (p->B.y < p->C.y))
		shape_subdiv(p, 1);
	    if (p->A.x != p->B.x && p->B.x != p->C.x &&
		    (p->A.x < p->B.x) != (p->B.x < p->C.x))
		shape_subdiv(p, 0);
	}
	p = p->next;
    } while (p != l);
    topmost = l;

#ifdef undef
    miny = l->A.y + 1;
    {
	register    dir = p->C.y - p->A.y;
	do {
	    register    ndir = p->A.y - p->C.y;
	    if ((dir ^ ndir) < 0) {
		if (miny >= p->A.y) {	/* Find the topmost arc */
		    miny = p->A.y;
		    topmost = p;
		}
		if (miny >= p->C.y) {
		    miny = p->C.y;
		    topmost = p;
		}
	    }
	    dir = ndir;
	    p = p->next;
	} while (p != l);
    }
#endif

    miny = l->A.y;
    if (l->C.y < miny)
	miny = l->C.y;
    while (1)
	if (miny > topmost->next->A.y) {	/* Find a topmost arc */
	    miny = topmost->next->A.y;
	    topmost = topmost->next;
	}
	else if (miny > topmost->next->C.y) {
	    miny = topmost->next->C.y;
	    topmost = topmost->next;
	}
	else
	    break;
    p = topmost;
    assert(p != 0 /* && p->next != p */ );
    globalmaxy = roundfr(p->A.y);
    {
	do {
	    register    dir = p->A.y - p->C.y;	/* upwards or downwards */
	    register struct shape_arc *nchain;
	    register struct shape_dcurve *ch;
	    fract       miny;
	    fract       minyx;
	    fract       maxy;
	    fract       maxyx;
	    if (p->A.y < p->C.y) {
		miny = p->A.y;
		minyx = p->A.x;
		maxy = p->C.y;
		maxyx = p->C.x;
	    }
	    else {
		miny = p->C.y;
		minyx = p->C.x;
		maxy = p->A.y;
		maxyx = p->A.x;
	    }
	    nchain = p->next;
	    while (nchain != topmost) {
		register    ndir = nchain->A.y - nchain->C.y;
		if ((ndir ^ dir) < 0 || ndir == 0 || dir == 0)
		    break;
		if (ndir < 0) {
		    if (nchain->A.y < miny)
			if (nchain->C.y != miny)
			    break;
			else
			    miny = nchain->A.y, minyx = nchain->A.x;
		    else if (nchain->C.y > maxy)
			if (nchain->A.y != maxy)
			    break;
			else
			    maxy = nchain->C.y, maxyx = nchain->C.x;
		    else
			break;
		}
		else {
		    if (nchain->C.y < miny)
			if (nchain->A.y != miny)
			    break;
			else
			    miny = nchain->C.y, minyx = nchain->C.x;
		    else if (nchain->A.y > maxy)
			if (nchain->C.y != maxy)
			    break;
			else
			    maxy = nchain->A.y, maxyx = nchain->A.x;
		    else
			break;
		}
		nchain = nchain->next;
	    };
	    assert(miny <= maxy);
	    {
		register    size = roundfr(maxy - miny) + 3;
		if (size > 4000 || size <= 0) {
		    p = nchain;
		    continue;
		}
		size = sizeof(struct shape_dcurve) + size * sizeof(short);
		QALLOC(ch, size, (struct shape_dcurve *));
	    }
	    ch->y0 = roundfr(miny);
	    ch->x0 = roundfr(minyx);
	    ch->y1 = roundfr(maxy);
	    ch->x1 = roundfr(maxyx);
	    ch->x = (short *) (((char *) ch) + sizeof(struct shape_dcurve));
	    ch->left = ch->right = ch->x0;
	    if (ch->y0 == ch->y1 && ch->x0 == ch->x1) {
		QFREE(ch);
		p = nchain;
	    }
	    else {
		ch->x[ch->y1 - ch->y0 + 1] = ch->x1;
		if (ch->y1 > globalmaxy)
		    globalmaxy = ch->y1;
		ch->direction = dir < 0 ? -1 : 1;
		ch->next = chains;
		chains = ch;
		if (dir == 0) {
		    ch->x[0] = ch->x0;
		    if (ch->x1 >= ch->right)
			ch->right = ch->x1+1;
		    if (ch->x1 < ch->left)
			ch->left = ch->x1;
		    p = p->next;
		}
		else
		    do {
			extern      arc_subdivision_depth;
			arc_subdivision_depth = 0;
			if (dir > 0) {
			    struct fpoint T;
			    T = p->A;
			    p->A = p->C;
			    p->C = T;
			}
			if (cfloorfr(p->A.x) < ch->left)
			    ch->left = cfloorfr(p->A.x);
			if (cfloorfr(p->C.x) < ch->left)
			    ch->left = cfloorfr(p->C.x);
			if (cfloorfr(p->A.x) > ch->right)
			    ch->right = cfloorfr(p->A.x);
			if (cfloorfr(p->C.x) > ch->right)
			    ch->right = cfloorfr(p->C.x);
			arc_to_chain(p, ch);
			p = p->next;
		    } while (p != nchain);
	    }
	} while (p != topmost);
    }
    freearc(topmost);
    return chains;
}

shape_freecurve(e)
    register struct shape_dcurve *e;
{
    register struct shape_dcurve *p, *n;
    if (e)
	for (p = e; p; p = n) {
	    n = p->next;
	    QFREE(p);
	    if (n == e)
		return;
	}
}

/*
 * Given an arc a1 subdivide it and form a second arc, linked to it, that
 * is broken at the horizontal or vertical minima or maxima, which is
 * presumed to exist 
 */
static
shape_subdiv(a1, hor)
    register struct shape_arc *a1;
    int         hor;
{
    register struct shape_arc *a2;
    fract       mu;
    int         swap = 0;
    {
	register fract a, c;
	if (hor) {		/* hor == 1 means find horizontal point */
	    a = a1->B.y - a1->A.y;
	    c = a1->C.y - a1->B.y;
	}
	else {
	    a = a1->B.x - a1->A.x;
	    c = a1->C.x - a1->B.x;
	}
	/*
	 * a and c have opposite signs (unless both are 0) Negate the
	 * negative one if any. 
	 */
	if (a < 0)
	    a = -a;
	if (c < 0)
	    c = -c;
	if (a > c) {
	    register fract t;
	    t = a, a = c, c = t, swap = 1;
	}
	if (c == 0)
	    return;
	/* now 0 <= a <= c, 0 < c */
	mu = frdiv(a, c);
    }
    {
	register fract s, t;
	fract       lambda, rho, Ss, St, sqrtFz, Dx, Dy, Dz, Ex, Ey, Ez, Fx, Fy, Fz;
	if (mu < fraction(1, 256) || a1->sh == 0)
	    lambda = frmul(a1->sh, mu);
	else {
	    rho = frdiv(-(fracti(1) - mu), 2 * a1->sh);
	    lambda = rho + frsqrt(frmul(rho, rho) + mu);
	}
	t = frdiv(lambda, lambda + fracti(1));
	if (swap)
	    s = t, t = fracti(1) - s;
	else
	    s = fracti(1) - t;
	qtalloc(a2, (struct shape_arc *));
	a2->next = a1->next, a1->next = a2, a2->C = a1->C;
	St = frmul(a1->sh, t), Ss = a1->sh - St;
	Dx = frmul(s, a1->A.x) + frmul(St, a1->B.x);
	Dy = frmul(s, a1->A.y) + frmul(St, a1->B.y);
	Dz = s + St;
	Ex = frmul(Ss, a1->B.x) + frmul(t, a1->C.x);
	Ey = frmul(Ss, a1->B.y) + frmul(t, a1->C.y);
	Ez = Ss + t;
	Fx = frmul(s, Dx) + frmul(t, Ex);
	Fy = frmul(s, Dy) + frmul(t, Ey);
	Fz = frmul(s, Dz) + frmul(t, Ez);
	sqrtFz = frsqrt(Fz);
	a2->A.x = frdiv(Fx, Fz);
	a2->A.y = frdiv(Fy, Fz);
	a2->sh = frdiv(Ez, sqrtFz);
	a1->sh = frdiv(Dz, sqrtFz);
	if (hor) {
	    a2->B.x = a1->B.x == a1->C.x ? a2->C.x : frdiv(Ex, Ez);
	    a2->B.y = a2->A.y;
	    a1->B.x = a1->B.x == a1->A.x ? a1->A.x : frdiv(Dx, Dz);
	    a1->B.y = a2->A.y;
	}
	else {
	    a2->B.x = a2->A.x;
	    a2->B.y = a1->B.y == a1->C.y ? a2->C.y : frdiv(Ey, Ez);
	    a1->B.x = a2->A.x;
	    a1->B.y = a1->B.y == a1->A.y ? a1->A.y : frdiv(Dy, Dz);
	    /*-	a2->B.x = !hor? a2->A.x: a1->B.x == a1->C.x? a2->C.x: frdiv(Ex,Ez);
    	    	a2->B.y =  hor? a2->A.y: a1->B.y == a1->C.y? a2->C.y: frdiv(Ey,Ez);
    	    	a1->B.x = !hor? a2->A.x: a1->B.x == a1->A.x? a1->A.x: frdiv(Dx,Dz);
    	    	a1->B.y =  hor? a2->A.y: a1->B.y == a1->A.y? a1->A.y: frdiv(Dy,Dz); */
	}
	a1->C = a2->A;
    }
}

print_arclist(a)
    register struct shape_arc *a;
{
    register struct shape_arc *p = a;
    register    n = 30;
    while (--n >= 0) {
	printf("%5.3f%12.2f%8.2f%10.2f%8.2f%10.2f%8.2f\n",
	       floatfr(p->sh),
	       floatfr(p->A.x), floatfr(p->A.y),
	       floatfr(p->B.x), floatfr(p->B.y),
	       floatfr(p->C.x), floatfr(p->C.y));
	p = p->next;
	if (p == a)
	    break;
    }
    if (n <= 0)
	printf("	Loops...\n");
}