#include <math.h>
#include "skeleton.h"

/* animate primitives */

int strokes(line_ptr line)
{
    int n;

    n = 1;
    while(line->next!=NULL)
    {
        n++;
        line = line->next;
    }

    return(n);
}

void addsegs(line_ptr seg,int n,int req)
{
    int rs,rt,i,j,k=0,l;
    int x1,y1,dx,dy;

    if(n/POINTS != req/POINTS)	
        seg->pts=(struct pts *)realloc((void *)seg->pts,
         sizeof(struct pts)*POINTS*(req/POINTS+1),
	 sizeof(struct pts)*POINTS*(n/POINTS+1));
    seg->number = req+1;

    if(n==0)
    {
        x1 = seg->pts->p[0][0];
        y1 = seg->pts->p[0][1];

	
	for(i=1;i<=req;i++)
	{
		seg->pts->p[i][0]=x1;
		seg->pts->p[i][1]=y1;
	}
	return;
    }

    rt = req/n;
    rs = req%n;

    for(i=n;i>=0;i--)
    {
	if(i>rs)
		j = rs + rt*i;
	else
		j = (rt+1)*i;
		
	seg->pts->p[j][0] = seg->pts->p[i][0];
	seg->pts->p[j][1] = seg->pts->p[i][1];
	
		
	if(i!=n)
	{
	        x1 = seg->pts->p[j][0];
       		y1 = seg->pts->p[j][1];
       		dx = seg->pts->p[k][0] - seg->pts->p[j][0];
       		dy = seg->pts->p[k][1] - seg->pts->p[j][1];

		for(l=1;l<k-j;l++)
		{
			seg->pts->p[j+l][0] = (dx*l)/(k-j)+x1;
			seg->pts->p[j+l][1] = (dy*l)/(k-j)+y1;

		}
	}
	k = j;
    }
}

void breakstroke(line_ptr seg,int n)
{
    int step;
    line_ptr newseg;


    if(n<=1) return;

    if(seg->number-1<n)
        addsegs(seg,seg->number-1,n);

    step = (seg->number-1)/n;

    for(;n>1;n--)
    {
        newseg = cutseg(seg,step);

	newseg->next = seg->next;
	seg->next = newseg;

        seg = newseg;
    }
}

void addstrokes(line_ptr line,int n,int req)
{
    int rs,rt,i;
    line_ptr nextline;

    rt = req/n;
    rs = req%n;

    for(i=1;i<=rs;i++)
    {
	nextline = line->next;
        breakstroke(line,rt+1);
        line = nextline;
    }
    while(line!=NULL)
    {
	nextline = line->next;
        breakstroke(line,rt);
        line = nextline;
    }
}


void preprocess(line_ptr l1,line_ptr l2)
{
    int n1,n2;

    if((l1==NULL)||(l2==NULL)) return;


    n1 = strokes(l1);
    n2 = strokes(l2);

    if(n1>n2) addstrokes(l2,n2,n1);
    else if(n2>n1) addstrokes(l1,n1,n2);

    while(l1!=NULL)
    {
        n1 = l1->number-1;
        n2 = l2->number-1;

        if(n1>n2) addsegs(l2,n2,n1);
        else if(n2>n1) addsegs(l1,n1,n2);

        l1 = l1->next;
        l2 = l2->next;
    }
}

int relative(int x ,int y ,int x1,int y1,int x2,int y2,
             int x3,int y3,int x4,int y4,int *l,int *w)
{
    double L,W,dist2,tdist2;
    int a,b,c,d,e,f,g,h;
    int A,B,C;
    int temp,cross1,cross2;

    a = x-x1; b = x2-x1; c = y-y1; d = y2-y1;
    e = x-x3; f = x4-x3; g = y-y3; h = y4-y3;

    cross1 = a*d - c*b;	/* psuedo cross products */
    cross2 = e*h - g*f;
    
    if((cross1>0 && cross2>0)||(cross1<0 && cross2<0))
    	return(FALSE);
	
    cross1 = (a-e)*c - (c-g)*a;	/* another cross product */
    cross2 = (x4-x2)*(y-y2) - (y4-y2)*(x-x2);

    if((cross1>0 && cross2>0)||(cross1<0 && cross2<0))
    	return(FALSE);

    A = b*h - d*f;
    B = c*f + d*e - a*h - b*g;	/* I won't soon forget this one */
    C = a*g - c*e;

    if(A==0)
    {
	if(B!=0)
		L = -(double)C/B;
	else
	{
		return(FALSE);
	}
    }
    else
    {
	temp = B*B - 4*A*C;
	
	if(temp<0)
	{
		return(FALSE);
	}
	
	L = ((double)(-B) - sqrt((double)temp))/(2*A);
    	if(L>1.0 || L<0.0)
		L = ((double)(-B) + sqrt((double)temp))/(2*A);
   	if(L>1.0 || L<0.0)
	{
		return(FALSE);
	}
    }

    tdist2 = (a-e-(b-f)*L)*(a-e-(b-f)*L) + (c-g-(d-h)*L)*(c-g-(d-h)*L);
    if(tdist2==0.0)
    {
    	return(FALSE);
    }	
    dist2 = (a-b*L)*(a-b*L) + (c-d*L)*(c-d*L);

    W = sqrt(dist2/tdist2);
    if(W>1.0 || W<0.0)
    {
	 return(FALSE);
    }

    *l = (int)(L*256);
    *w = (int)(W*256);

    return(TRUE);
}

line_ptr makerelative(obj_ptr object)
{
    int i,j,k,p;
    int l,w;
    line_ptr seg,rel,head;

    seg = object->image;
    rel = head = NULL;

    while(seg!=NULL)
    {
	p = 0;
        for(i=0;i<seg->number;i++)
        {
            for(j=0;j<object->skeleton->number;j++)
            {
                for(k=0;k<=1;k++)
                {
		    if((j*2+k+2<object->outline->number) &&
		     (j+1<object->skeleton->number))
		    {
                    	if(relative(seg->pts->p[i][0],seg->pts->p[i][1],
                    	 object->skeleton->pts->p[j][0],
                    	 object->skeleton->pts->p[j][1],
                    	 object->skeleton->pts->p[j+1][0],
                    	 object->skeleton->pts->p[j+1][1],
                    	 object->outline->pts->p[j*2+k][0],
                    	 object->outline->pts->p[j*2+k][1],
                    	 object->outline->pts->p[j*2+k+2][0],
                    	 object->outline->pts->p[j*2+k+2][1],
                    	 &l,&w)==TRUE)
                    	{
	                     	if(rel==NULL)
                        	{
					rel=(line_ptr)malloc(sizeof(struct line));
        				rel->pts=(struct pts *)
					 malloc(sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));

					head = rel;
					rel->next = NULL;
					rel->linec = seg->linec;
					rel->fillc = seg->fillc;
                        	}
                        	else if(p==0)
                        	{
					rel->next=(line_ptr)malloc(sizeof(struct line));
        				rel = rel->next;
					rel->pts=(struct pts *)
					 malloc(sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));

					rel->next = NULL;
                            		rel->linec = seg->linec;
					rel->fillc = seg->fillc;
                        	}

                       		rel->pts->p[p][0] = l+(j<<8);
				rel->pts->p[p][1] = ((k)?(-1):(1))*w;
				p++;

				k = 1;
				j = object->skeleton->number;
			}
                    }
                }
            }
        }
	if(p!=0)
	{
        	rel->number=p;
		if((p-1)/POINTS!=(seg->number-1)/POINTS)
			rel->pts=(struct pts *)
			 realloc((void *)rel->pts,
         		 sizeof(struct pts)*POINTS*((p-1)/POINTS+1),
			 sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));
		if(p==1)
		{
               		rel->pts->p[1][0] = rel->pts->p[0][0];
			rel->pts->p[1][1] = rel->pts->p[0][1];
		}
	}
        seg = seg->next;
    }
    return(head);
}

void makeimage(obj_ptr object,line_ptr relative)
{
    int i,j,k,p;
    int l,w,x1,y1,x2,y2;
    line_ptr seg,derel;

    seg = relative;
    derel = NULL;
    deleteline(object->image);

    while(seg!=NULL)
    {
	p = 0;
        for(i=0;i<seg->number;i++)
        {
            l = seg->pts->p[i][0];
            w = seg->pts->p[i][1];

            j = l>>8;
            k = ((w<0)?(1):(0));

            l = l - (j<<8);
            w = abs(w);

            if((j+1<object->skeleton->number) &&
	     (k+j*2+2<object->outline->number))
	    {
		x1 = ((object->skeleton->pts->p[j+1][0] -
            	 object->skeleton->pts->p[j][0]) * l)/256 +
            	 object->skeleton->pts->p[j][0];
            	y1 = ((object->skeleton->pts->p[j+1][1] -
            	 object->skeleton->pts->p[j][1]) * l)/256 +
            	 object->skeleton->pts->p[j][1];
            	x2 = ((object->outline->pts->p[j*2+k+2][0] -
            	 object->outline->pts->p[j*2+k][0]) * l)/256 +
            	 object->outline->pts->p[j*2+k][0];
            	y2 = ((object->outline->pts->p[j*2+k+2][1] -
             	 object->outline->pts->p[j*2+k][1]) * l)/256 +
             	 object->outline->pts->p[j*2+k][1];

            	x1 = ((x2-x1) * w)/256 + x1;
            	y1 = ((y2-y1) * w)/256 + y1;

	        if(derel==NULL)
        	{
			derel=(line_ptr)malloc(sizeof(struct line));
        		derel->pts=(struct pts *)
			 malloc(sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));

			derel->next = NULL;

			derel->linec = seg->linec;
			derel->fillc = seg->fillc;
			object->image = derel;
                }
            	else if(p==0)
            	{
			derel->next=(line_ptr)malloc(sizeof(struct line));
        		derel = derel->next;
			derel->pts=(struct pts *)
			 malloc(sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));

			derel->next = NULL;

			derel->linec = seg->linec;
			derel->linec = seg->linec;
			derel->fillc = seg->fillc;
                }

       		derel->pts->p[p][0] = x1;
		derel->pts->p[p][1] = y1;

		p++;
	    }
        }
	if(p!=0)
	{
        	derel->number=p;
		if((p-1)/POINTS!=(seg->number-1)/POINTS)
			derel->pts=(struct pts *)
			 realloc((void *)derel->pts,
         		 sizeof(struct pts)*POINTS*((p-1)/POINTS+1),
			 sizeof(struct pts)*POINTS*((seg->number-1)/POINTS+1));
		setbox(derel);
		if(p==1)
		{
               		derel->pts->p[1][0] = derel->pts->p[0][0];
			derel->pts->p[1][1] = derel->pts->p[0][1];
		}
	}
        seg = seg->next;
    }
}

void inbetween(int xi,int yi,int xo,int yo,int frame,int frames,
               int law,int *x,int *y)
{
    if((law & XACCEL) && (law & XDECEL))
        *x = (int)((xo-xi)*(1.0-cos((double)PI*frame/frames))/2)+xi;
    else if(law & XACCEL)
        *x = (int)((xo-xi)*(1.0-cos((double)PI*frame/frames/2)))+xi;
    else if(law & XDECEL)
        *x = (int)((xo-xi)*sin((double)PI*frame/frames/2))+xi;
    else
        *x = (int)((xo-xi)*(double)frame/frames)+xi;

    if((law & YACCEL) && (law & YDECEL))
        *y = (int)((yo-yi)*(1.0-cos((double)PI*frame/frames))/2)+yi;
    else if(law & YACCEL)
        *y = (int)((yo-yi)*(1.0-cos((double)PI*frame/frames/2)))+yi;
    else if(law & YDECEL)
        *y = (int)((yo-yi)*sin((double)PI*frame/frames/2))+yi;
    else
        *y = (int)((yo-yi)*(double)frame/frames)+yi;
}

line_ptr imagebetween(line_ptr linein,line_ptr lineout,
                      int frame,int frames,int law)
{
    line_ptr start, line;
    int i;
    int x,y,n;

    start = NULL;
    
    while(linein!=NULL && lineout!=NULL)
    {
    if(linein->number>lineout->number)
    	n = lineout->number;
    else
    	n = linein->number;
	
        for(i=0;i<n;i++)
        {
            inbetween(linein->pts->p[i][0],linein->pts->p[i][1],
             lineout->pts->p[i][0],lineout->pts->p[i][1],
             frame,frames,law,&x,&y);
            if(start==NULL)
            {
                line = (line_ptr)malloc(sizeof(struct line));
		line->pts = malloc(sizeof(struct pts)*POINTS*((n-1)/POINTS+1));
		
		line->linec = linein->linec;
		line->fillc = linein->fillc;
		line->next = NULL;
		
		start = line;
            }
            else if(i==0)
            {
                line->next = (line_ptr)malloc(sizeof(struct line));
		line = line->next;
		line->pts = malloc(sizeof(struct pts)*POINTS*((n-1)/POINTS+1));
		
                line->linec = linein->linec;
		line->fillc = linein->fillc;
		line->next = NULL;
            }
	    
    	    line->pts->p[i][0] = x;
	    line->pts->p[i][1] = y;
        }
	
	line->number = n;
	setbox(line);

	if(n==1)
	{
		line->pts->p[1][0] = line->pts->p[0][0];
		line->pts->p[1][1] = line->pts->p[0][1];
	}

        linein = linein->next;
        lineout = lineout->next;
    }
    return(start);
}

obj_ptr findtype(obj_ptr object,int flags,int *n)
{
    *n = 0;
    if(flags!=0)
    {
    	while((object!=NULL)&&((object->entry&flags)!=flags))
    	{
        	object=object->next;
        	(*n)++;
    	}
    }
    else
    {
    	while((object!=NULL)&&(object->entry==0))
    	{
        	object=object->next;
        	(*n)++;
    	}
    }
    return(object);
}

obj_ptr findtypeback(obj_ptr object,int flags,int *n)
{
    *n = 0;
    if(flags!=0)
    {
    	while((object!=NULL)&&((object->entry&flags)!=flags))
    	{
        	object=object->prev;
        	(*n)++;
    	}
    }
    else
    {
    	while((object!=NULL)&&(object->entry==0))
    	{
        	object=object->prev;
        	(*n)++;
    	}
    }

    return(object);
}

/*
void makeoutline(obj_ptr with,obj_ptr without)
{
    double length,a1i,a1f,a2i,a2f,aoi,aof;
    int x10,y10,x11,y11,x12,y12,x1o,y1o,x20,y20,x21,y21,x22,y22,x2o,y2o;
    int i;

    deleteline(without->outline);
    without->outline = NULL;

    for(i=0;i<with->outline->number;i++)
    {
        x10 = with->skeleton->pts->p[i/2][0];
        y10 = with->skeleton->pts->p[i/2][1];
        x1o = with->outline->pts->p[i][0];
        y1o = with->outline->pts->p[i][1];
        if(i>1)
        {
            x11 = with->skeleton->pts->p[i/2-1][0];
            y11 = with->skeleton->pts->p[i/2-1][1];
        }
        if(i<with->outline->number-2)
        {
            x12 = with->skeleton->pts->p[i/2+1][0];
            y12 = with->skeleton->pts->p[i/2+1][1];
        }

        x20 = without->skeleton->pts->p[i/2][0];
        y20 = without->skeleton->pts->p[i/2][1];
        if(i!=0)
        {
            x21 = without->skeleton->pts->p[i/2-1][0];
            y21 = without->skeleton->pts->p[i/2-1][1];
        }
        if(i!=with->outline->number-1)
        {
            x22 = without->skeleton->pts->p[i/2+1][0];
            y22 = without->skeleton->pts->p[i/2+1][1];
        }

        length = sqrt((double)(x10-x11)*(x10-x11) +
         (double)(y10-y11)*(y10-y11));

        a1i = atan2((double)(x11-x10),(double)(y11-y10));
        a2i = atan2((double)(x12-x10),(double)(y12-y10));
        aoi = atan2((double)(x1o-x10),(double)(y1o-y10));
        a1f = atan2((double)(x21-x20),(double)(y21-y20));
        a2f = atan2((double)(x22-x20),(double)(y22-y20));

        if(i==0)
            aof = aoi + (a2f-a2i);
        else if(i==with->outline->number-1)
            aof = aoi + (a1f-a1i);
        else
            aof = aoi + ((a1f-a1i) + (a2f-a2i))/2;

        x2o = x21 + (int)(length*cos(aof));
        y2o = y21 + (int)(length*sin(aof));

        without->outline = addpoint(without->outline,x2o,y2o);
    }
}


void derelative(obj_ptr firstimage,int n)
{
    obj_ptr nextskel,image;
    int f,acc,i;

    nextskel = findtype(firstimage->next,SKELETON,&f);
    f = f + 1;
    acc = f;
    while(nextskel!=NULL && acc < n)
    {
        if(nextskel->entry & XOUTLINE != XOUTLINE)
            makeoutline(firstimage,nextskel);
        image = firstimage->next;
        for(i=1;i<=f;i++)
        {
            image->skeleton = imagebetween(firstimage->skeleton,
             nextskel->skeleton,i,f,firstimage->ilaw);
            image->outline = imagebetween(firstimage->outline,
             nextskel->outline,i,f,firstimage->ilaw);
            makeimage(image);
            image = image->next;
        }
        firstimage = nextskel;
        nextskel = findtype(firstimage->next,SKELETON,&f);
        acc = acc + f;
    }
}
 */
 
void animate(obj_ptr object)
{
    obj_ptr firstimage, nextimage, firstskel, nextskel, image;
    line_ptr firstrel,nextrel, rel, firstcopy, nextcopy;
    int f,n,i,j;
    int skelable;

    if(object==NULL) return;
    firstrel = nextrel = NULL;

    firstimage = findtype(object,IMAGE,&f);
    
    if(firstimage==NULL) return;
    
    if((firstimage->entry&(SKELETON|XOUTLINE))==(SKELETON|XOUTLINE))
    {
    	skelable=TRUE;
	firstrel = makerelative(firstimage);
    }
    else
    {
     	skelable = FALSE;
    }
    
    nextimage = findtype(firstimage->next,IMAGE,&n);

    while(nextimage!=NULL)
    {
        if(skelable==TRUE)
	{
		if((nextimage->entry&(SKELETON|XOUTLINE))==(SKELETON|XOUTLINE))
		{
			nextrel = makerelative(nextimage);
			nextcopy = copyline(nextrel);
			firstcopy = copyline(firstrel);
			preprocess(firstcopy,nextcopy);
		}
		else
		{
			skelable = FALSE;
		}
		
		j = 0;
		firstskel = firstimage;
		nextskel = findtype(firstskel->next,SKELETON|XOUTLINE,&f);
		while((j+f<=n) && (nextskel!=NULL))
		{
			if((skelable==TRUE) && (nextskel!=nextimage))
			{
                		rel = imagebetween(firstcopy,
                	 		nextcopy,j+f+1,n+1,firstskel->ilaw);
				makeimage(nextskel,rel);	
				deleteline(rel);
			}
			else if(nextskel!=nextimage)
			{
				makeimage(nextskel,firstrel);
			}

			image = firstskel->next;
			for(i=1;i<=f;i++)
			{
				deleteline(image->skeleton);
       	        		image->skeleton = imagebetween(firstskel->skeleton,
               			 nextskel->skeleton,i,f+1,firstskel->ilaw);
				deleteline(image->outline);
       	        		image->outline = imagebetween(firstskel->outline,
               			 nextskel->outline,i,f+1,firstskel->ilaw);

				if(skelable==TRUE)
				{
                			rel = imagebetween(firstcopy,
                	 		 nextcopy,j+i,n+1,firstskel->ilaw);
					makeimage(image,rel);	
					deleteline(rel);
				}
				else
				{
					makeimage(image,firstrel);
				}
               			image = image->next;
			}
			
			j = j+f+1;
			firstskel = nextskel;

			nextskel = findtype(firstskel->next,SKELETON|XOUTLINE,&f);
		}

		if(skelable==TRUE)
		{
			deleteline(firstcopy);
			deleteline(nextcopy);
		}
		else
			nextrel=NULL;
			
		deleteline(firstrel);
		firstrel = nextrel;
		
		if(j<n)
		{
			n = n - j;
			firstcopy = copyline(firstskel->image);
			nextcopy = copyline(nextimage->image);
			preprocess(firstcopy,nextcopy);
        	    	image = firstskel->next;
            		for(i=1;i<=n;i++)
            		{
				deleteline(image->image);
                		image->image = imagebetween(firstcopy,
                		 nextcopy,i,n+1,firstskel->ilaw);
                		image = image->next;
            		}
			deleteline(firstcopy);
			deleteline(nextcopy);
		}
	}
	else
	{
		/* inbetweening of images */
		firstcopy = copyline(firstimage->image);
		nextcopy = copyline(nextimage->image);
		
		preprocess(firstcopy,nextcopy);
            	image = firstimage->next;
            	for(i=1;i<=n;i++)
            	{
			deleteline(image->image);
                	image->image = imagebetween(firstcopy,
                	 nextcopy,i,n+1,firstimage->ilaw);
                	image = image->next;
            	}
		deleteline(firstcopy);
		deleteline(nextcopy);
		
		if((nextimage->entry&(SKELETON|XOUTLINE))==(SKELETON|XOUTLINE))
		{
			skelable = TRUE;
			deleteline(firstrel);
			firstrel = makerelative(nextimage);
		}
        }

        firstimage = nextimage;
	
        nextimage = findtype(firstimage->next,IMAGE,&n);
     }

     if((firstimage->next!=NULL) && (skelable==TRUE))
     {
	firstskel = firstimage;
	nextskel = findtype(firstimage->next,SKELETON|XOUTLINE,&f);
	while(nextskel!=NULL)
	{

		makeimage(nextskel,firstrel);
		
		image = firstskel->next;
		for(i=1;i<=f;i++)
		{
			deleteline(image->skeleton);
       	        	image->skeleton = imagebetween(firstskel->skeleton,
               		 nextskel->skeleton,i,f+1,firstskel->ilaw);
			deleteline(image->outline);
       	        	image->outline = imagebetween(firstskel->outline,
               		 nextskel->outline,i,f+1,firstskel->ilaw);
			makeimage(image,firstrel);
               		image = image->next;
		}

		firstskel = nextskel;
		nextskel = findtype(firstskel->next,SKELETON|XOUTLINE,&f);
	}
     }
     deleteline(firstrel);
}