source: abuse/trunk/src/imlib/morph.cpp @ 494 Tweet

/*
 *  Abuse - dark 2D side-scrolling platform game
 *  Copyright (c) 1995 Crack dot Com
 *  Copyright (c) 2005-2011 Sam Hocevar <sam@hocevar.net>
 *
 *  This software was released into the Public Domain. As with most public
 *  domain software, no warranty is made or implied by Crack dot Com or
 *  Jonathan Clark.
 */

/* FIXME: this file is unused */

#include "config.h"

#include "morph.h"

long trans(long x1, long x2, long frame)
{
  return (((x2-x1)<<5)*frame+(x1<<8))>>8;
}


void jmorph::show_step_frame(image *screen, int x, int y, int frame_on,
                   color_filter *fli, palette *pal)
{
  short x1,y1,x2,y2;
  unsigned char r1,g1,b1,r2,g2,b2;
  screen->get_clip(x1,y1,x2,y2);

  int i;
  long xx,yy;

  if (small)
  {
    morph_point8 *m8=(morph_point8 *)p;
    screen->lock();
    for (i=0; i<total; i++,m8++)
    {
      xx=x+trans(m8->x1,m8->x2,frame_on);
      yy=y+trans(m8->y1,m8->y2,frame_on);

      if (xx>=x1 && xx<=x2 && yy>=y1 && yy<=y2)
      {
    pal->get(m8->start_color,r1,g1,b1);
    pal->get(m8->end_color,r2,g2,b2);

    long r=trans(r1,r2,frame_on)>>3,
             g=trans(g1,g2,frame_on)>>3,
         b=trans(b1,b2,frame_on)>>3;

        *(screen->scan_line(yy)+xx)=fli->lookup_color(r,g,b);
      }
    }
    screen->unlock();
  }
}


void patched_morph::show_frame(image *screen, int x, int y,
                   int frame_on, color_filter *fli, palette *pal)
{
  jmorph::show_step_frame(screen,x,y,frame_on,fli,pal);
  int tot=pats[frame_on].patches,xx,yy;
  unsigned char *p=pats[frame_on].patch_data;
  short cx1,cy1,cx2,cy2;
  screen->get_clip(cx1,cy1,cx2,cy2);
  screen->lock();
  while (tot--)
  {
    xx=*(p++)+x;
    if (xx<cx1 || xx>cx2)
      p+=2;
    else
    {
      yy=*(p++)+y;
      if (yy<cy1 || yy>cy2)
        p++;
      else
    *(screen->scan_line(yy)+xx)=*(p++);
    }
  }
  screen->unlock();
}

void patched_morph::show_8(image *screen, int x, int y, int frame_on, color_filter *fli, palette *pal)
{
  jmorph::show_8(screen,x,y,frame_on,fli,pal);
  int tot=pats[frame_on].patches,xx,yy;
  unsigned char *p=pats[frame_on].patch_data;
  short cx1,cy1,cx2,cy2;
  screen->get_clip(cx1,cy1,cx2,cy2);
  screen->lock();
  while (tot--)
  {
    xx=*(p++)+x;
    if (xx<cx1 || xx>cx2)
      p+=2;
    else
    {
      yy=*(p++)+y;
      if (yy<cy1 || yy>cy2)
        p++;
      else
    *(screen->scan_line(yy)+xx)=*(p++);
    }
  }
  screen->unlock();
}




patched_morph::patched_morph(image *i1, image *hint1, image *i2, image *hint2, int aneal_steps,
            color_filter *fli, palette *pal, int frames) : jmorph(i1,hint1,i2,hint2,aneal_steps)
{
  int i,j,w,h,x,y,tot,r,g,b,mark_color,dist;
  unsigned char *cur_patch,*sl,ored,og,ob;

  frames=9;

  patches=frames;
  pats=(morph_patch *)malloc(sizeof(morph_patch)*patches);
  w=max(bound_x2(0),bound_x2(1));
  h=max(bound_y2(0),bound_y2(1));
  image *im=new image(w,h);


  for (i=0; i<patches; i++)
  {
    pats[i].patch_data=NULL;
    pats[i].patches=0;
    if (i!=0 && i!=patches-1)
    {
      im->clear();
      jmorph::show_step_frame(im,0,0,i,fli,pal);
      for (j=0; j<4; j++)
      {
    for (y=0; y<h; y++)
          for (sl=im->scan_line(y),x=0; x<w; x++,sl++)
      {
        mark_color=-1;

        tot=r=g=b=0;
        if (x!=0 && *(sl-1))
        { tot++;
          r+=pal->red(*(sl-1));
          g+=pal->green(*(sl-1));
          b+=pal->blue(*(sl-1));
        }
        if (x!=w-1 && *(sl+1))
        { tot++;
          r+=pal->red(*(sl+1));
          g+=pal->green(*(sl+1));
          b+=pal->blue(*(sl+1));
        }
        if (y!=0 && im->pixel(x,y-1))
        { tot++;
          r+=pal->red(im->pixel(x,y-1));
          g+=pal->green(im->pixel(x,y-1));
          b+=pal->blue(im->pixel(x,y-1));
        }
        if (y!=h-1 && im->pixel(x,y+1))
        { tot++;
          r+=pal->red(im->pixel(x,y+1));
          g+=pal->green(im->pixel(x,y+1));
          b+=pal->blue(im->pixel(x,y+1));
        }

        if (*sl && tot==0)  // kill any separate pixels
          mark_color=0;
        else if (*sl)
        {
          pal->get(*sl,ored,og,ob);       // see if we need to blur this on in
          r/=tot;
          g/=tot;
          b/=tot;

          dist=((int)ored-r)*((int)ored-r)+((int)og-g)*((int)og-g)+((int)ob-b)*((int)ob-b);
          if (i>0 && i<patches-1 && dist>3000)
          {
//        printf("adding blur at %d %d to frame %d, dist=%d\n",x,y,i,dist);
        mark_color=fli->lookup_color(r>>3,g>>3,b>>3);
          }
        }
        else if (*sl==0 && tot>=3)
          mark_color=fli->lookup_color((r/tot)>>3,(g/tot)>>3,(b/tot)>>3);
        if (mark_color>=0)
        {
          pats[i].patches++;
          pats[i].patch_data=(unsigned char *)realloc(pats[i].patch_data,3*pats[i].patches);
          cur_patch=pats[i].patch_data+  (pats[i].patches-1)*3;
          *(cur_patch++)=x;
          *(cur_patch++)=y;
          *sl=mark_color;
          *(cur_patch++)=*sl;
        }
      }
      }
    }
  }
  delete im;

}


void jmorph::show_8(image *screen, int x, int y, int frame_on, color_filter *fli, palette *pal)
{
  int pixelx,pixely,i;
  short cx1,cy1,cx2,cy2;
  unsigned char r,g,b;
  unsigned char *scolor,*ecolor,*addr=(unsigned char *)pal->addr();
  screen->get_clip(cx1,cy1,cx2,cy2);

  if (small)
  {
    morph_point8 *p_on=(morph_point8 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/8+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/8+p_on->y1+y;
      if (pixelx>=cx1 && pixely>=cy1 && pixelx<=cx2 && pixely<=cy2)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        r=(((int)*(ecolor++))-((int)*scolor))*frame_on/8+*scolor; scolor++;
        g=(((int)*(ecolor++))-((int)*scolor))*frame_on/8+*scolor; scolor++;
        b=((int)(*ecolor)-(int)(*scolor))*frame_on/8+*scolor;
        *(screen->scan_line(pixely)+pixelx)=fli->lookup_color(r>>3,g>>3,b>>3);
      }
    }
  }
  else
  {
    morph_point16 *p_on=(morph_point16 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/8+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/8+p_on->y1+y;
      if (pixelx>=cx1 && pixely>=cy1 && pixelx<=cx2 && pixely<=cy2)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        r=(((int)*(ecolor++))-((int)*scolor))*frame_on/8+*scolor; scolor++;
        g=(((int)*(ecolor++))-((int)*scolor))*frame_on/8+*scolor; scolor++;
        b=((int)(*ecolor)-(int)(*scolor))*frame_on/8+*scolor;
        *(screen->scan_line(pixely)+pixelx)=fli->lookup_color(r>>3,g>>3,b>>3);
      }
    }
  }
}


void jmorph::add_filler(int frames)
{
  int w=max(bound_x2(0),bound_x2(1)),h=max(bound_y2(0),bound_y2(1)),
      i,pixelx,pixely,k,l,frame_on;
  morph_point8 **middle_map,*other;
  unsigned char *end_map;
  CONDITION(small,"add filler not defined for 16bit morphs\n");

  if (frames<3) return ;


  // create an image of pointers
  middle_map=(morph_point8 **)malloc(w*h*sizeof(morph_point8 *));
  // maps all the ending pixels
  end_map=(unsigned char *)malloc(w*h);

  for (frame_on=2; frame_on<frames-1; frame_on++)
  {
    memset(middle_map,0,w*h*sizeof(morph_point8 *));            // initialize them middle pointers NULL
    memset(end_map,0,w*h);                                      // clear all end pixels

    morph_point8 *p_on=(morph_point8 *)p;    // p is the array of morph points
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long) frame_on  /(long) frames  +p_on->x1;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long) frame_on  /(long) frames  +p_on->y1;

      middle_map[pixelx+pixely*w]=p_on;      // map this poisiton back to the morph point
      end_map[p_on->x2+p_on->y2*w]=p_on->end_color;        // note an ending map here
    }


    int skipped=0;

    for (pixely=0; pixely<h; pixely++)
    {
      for (pixelx=0; pixelx<w; pixelx++)
      {
    if (middle_map[pixelx+pixely*w]==NULL)  // we are checking for 'duds'  (misplaced black pixels)
    {
      int tot;
      if (pixelx>0) if (middle_map[pixelx-1+pixely*w]) tot=1; else tot=0;
      if (pixelx<w-1) if (middle_map[pixelx+1+pixely*w]) tot++;
      if (pixely>0) if (middle_map[pixelx+(pixely-1)*w]) tot++;
      if (pixely<h-1) if (middle_map[pixelx+(pixely+1)*w]) tot++;

      if (tot>=3)                   // it is surronded by 3 non black squares, this is a dud
      {
        int distance,shortest_distance,shortest_end_x,shortest_end_y;
        morph_point8 *shortest=NULL;

        for (k=0; k<w; k++)
             for (l=0; l<h; l++)
          {
                other=middle_map[k+(l)*w];
        if (other)
        {
          int end_x=frames*(pixelx-other->x1)/frame_on+other->x1,
              end_y=frames*(pixely-other->y1)/frame_on+other->y1;
          if (end_x>=0 && end_y>=0 && end_x<w && end_y<h && end_map[end_x+end_y*w])
          {
                    distance=(other->x1-end_x)*(other->x1-end_x)+
                     (other->y1-end_y)*(other->y1-end_y);
            if (!shortest || shortest_distance>distance)
            {
              shortest_distance=distance;
              shortest=other;
              shortest_end_x=end_x;
              shortest_end_y=end_y;
            }
          }
        }
          }
        if (shortest)
        {
          total++;
          p=(void *)realloc(p,sizeof(morph_point8)*total);
          morph_point8 *mod=((morph_point8 *)p)+total-1;
          mod->x1=shortest->x1;
          mod->y1=shortest->y1;
          mod->start_color=shortest->start_color;

          mod->x2=shortest_end_x;
          mod->y2=shortest_end_y;
          mod->end_color=end_map[shortest_end_x+shortest_end_y*w];
        }
        else
        {
            skipped++;
          printf("skiped so far : %d (frame %d)\n",skipped,frame_on);
        }


      }
    }
      }
    }
  }

  free(middle_map);
  free(end_map);

}



jmorph::jmorph(spec_entry *e, bFILE *fp)
{
  int i;
  fp->seek(e->offset,0);
  fp->read(&total,4);
  total=long_to_local(total);
  if (e->type==SPEC_MORPH_POINTS_8 || e->type==SPEC_PATCHED_MORPH)
  {
    p=(void *)malloc(sizeof(morph_point8)*total);
    fp->read(p,sizeof(morph_point8)*total);
    small=1;
  }
  else
  {
    p=(void *)malloc(sizeof(morph_point16)*total);

    for (i=0; i<total; i++)
    {
      ((morph_point16 *)p+i)->x1=fp->read_uint16();
      ((morph_point16 *)p+i)->y1=fp->read_uint16();
      ((morph_point16 *)p+i)->x2=fp->read_uint16();
      ((morph_point16 *)p+i)->y2=fp->read_uint16();
      fp->read( &((morph_point16 *)p+i)->start_color,1);
      fp->read( &((morph_point16 *)p+i)->end_color,1);
    }

    small=0;
  }
  w[0]=fp->read_uint16();
  h[0]=fp->read_uint16();
  w[1]=fp->read_uint16();
  h[1]=fp->read_uint16();
}

void jmorph::show_frame(image *screen, int x, int y,
                      int frames, int frame_on, color_filter *fli, palette *pal)
{
  int pixelx,pixely,i;
  short cx1,cy1,cx2,cy2;
  unsigned char r,g,b;
  unsigned char *scolor,*ecolor,*addr=(unsigned char *)pal->addr();
  screen->get_clip(cx1,cy1,cx2,cy2);

  if (small)
  {
    morph_point8 *p_on=(morph_point8 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/(long)frames+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/(long)frames+p_on->y1+y;
      if (pixelx>=cx1 && pixely>=cy1 && pixelx<=cx2 && pixely<=cy2)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        r=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++;
        g=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++;
        b=((int)(*ecolor)-(int)(*scolor))*frame_on/frames+*scolor;
        *(screen->scan_line(pixely)+pixelx)=fli->lookup_color(r>>3,g>>3,b>>3);
      }
    }
  }
  else
  {
    morph_point16 *p_on=(morph_point16 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/(long)frames+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/(long)frames+p_on->y1+y;
      if (pixelx>=cx1 && pixely>=cy1 && pixelx<=cx2 && pixely<=cy2)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        r=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++;
        g=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++;
        b=((int)(*ecolor)-(int)(*scolor))*frame_on/frames+*scolor;
        *(screen->scan_line(pixely)+pixelx)=fli->lookup_color(r>>3,g>>3,b>>3);
      }
    }
  }
}

void jmorph::show_24frame(unsigned char *screen, int width, int height,
                  int x, int y, int frames, int frame_on, palette *pal)
{
    int pixelx,pixely,i;
  unsigned char *scolor,*ecolor,*addr=(unsigned char *)pal->addr(),*pix;

  if (small)
  {
    morph_point8 *p_on=(morph_point8 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/(long)frames+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/(long)frames+p_on->y1+y;

      if (pixelx>=0 && pixely>=0 && pixelx<width && pixely<height)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        pix=screen+pixelx*3+pixely*3*width;
        *pix=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++; pix++;
        *pix=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++; pix++;
        *pix=((int)(*ecolor)-(int)(*scolor))*frame_on/frames+*scolor;
      }
    }
  }
  else
  {
    morph_point16 *p_on=(morph_point16 *)p;
    for (i=0; i<total; i++,p_on++)
    {
      pixelx=(long)((int)p_on->x2-(int)p_on->x1)*(long)frame_on/(long)frames+p_on->x1+x;
      pixely=(long)((int)p_on->y2-(int)p_on->y1)*(long)frame_on/(long)frames+p_on->y1+y;

      if (pixelx>=0 && pixely>=0 && pixelx<width && pixely<height)
      {
        scolor=addr+((int)p_on->start_color)*3;
        ecolor=addr+((int)p_on->end_color)*3;
        pix=screen+pixelx*3+pixely*3*width;
        *pix=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++; pix++;
        *pix=(((int)*(ecolor++))-((int)*scolor))*frame_on/frames+*scolor; scolor++; pix++;
        *pix=((int)(*ecolor)-(int)(*scolor))*frame_on/frames+*scolor;
      }
    }
  }
}


jmorph::jmorph(image *i1, image *hint1, image *i2, image *hint2,
                          int aneal_steps)
{
  w[0]=i1->width();
  h[0]=i1->height();
  w[1]=i2->width();
  h[1]=i2->height();

  struct { int start,end; } crange[256];
  int hint_hist1[256],hint_hist2[256],x,y,total_hints=0,randp,cur_pix,
      last=0,first=0,i,j,k,findx1,findy1,findx2,findy2,total1,total2,points;
  unsigned char *sl,color;
  void *plist;


  CONDITION(i1->width()==hint1->width() && i1->height()==hint1->height() &&
            i2->width()==hint2->width() && i2->height()==hint2->height(),
            "Image sizes do not correspond with hint sizes");
  if (i1->width()>255 || i2->width()>255 || i1->height()>255 || i2->height()>255)
    small=0;
  else small=1;

  memset(hint_hist1,0,sizeof(hint_hist1));
  memset(hint_hist2,0,sizeof(hint_hist2));
  total=0;

  // first found out how many hints we have to follow
  for (y=0; y<hint1->height(); y++)
  { sl=hint1->scan_line(y);
    for (x=hint1->width(); x; x--,sl++)
      if (*sl) hint_hist1[*sl]++;
  }
  for (y=0; y<hint2->height(); y++)
  { sl=hint2->scan_line(y);
    for (x=hint2->width(); x; x--,sl++)
      if (*sl) hint_hist2[*sl]++;
  }

  // check the user and see if the mask match up
  for (x=0; x<256; x++)
  {
    if ((hint_hist1[x]!=0 && hint_hist2[x]==0) ||
        (hint_hist1[x]==0 && hint_hist2[x]!=0))
    { printf("Color %d used for hinting is prent in one hint mask, but not the other\n",x);
      exit(1);
    } else if (hint_hist1[x])
    {
      if (!first) first=x;
      total_hints++;
      if (hint_hist1[x]>hint_hist2[x])
        y=hint_hist1[x];
      else
        y=hint_hist2[x];
      total+=y;
      crange[x].start=last;
      crange[x].end=last+y-1;
      last+=y;
    }
  }
  if (small)
    plist=(void *)malloc(sizeof(morph_point8)*total);
  else
    plist=(void *)malloc(sizeof(morph_point16)*total);
  CHECK(plist);
  for (i=0,color=0; i<total_hints; i++)
  {
    color++; while (!hint_hist1[color]) color++;
    findx1=findx2=-1; findy1=findy2=0;
    total1=hint_hist1[color];
    total2=hint_hist2[color];
    if (total1>total2) points=total1; else points=total2;
    for (j=0; j<points; j++)
    {
      if (total1)  // are there any more pixels left in this image?
      { total1--;
        do {
          findx1++;
          if (findx1>=hint1->width()) { findx1=0; findy1++; }
        } while (hint1->pixel(findx1,findy1)!=color);
      }
      else
      {
        randp=rand()%j+crange[color].start;
        if (small)
        { findx1=((morph_point8 *)plist)[randp].x1;
          findy1=((morph_point8 *)plist)[randp].y1;
        } else
        { findx1=((morph_point16 *)plist)[randp].x1;
          findy1=((morph_point16 *)plist)[randp].y1;
        }
      }
      if (total2)  // are there any more pixels left in this image?
      {
        total2--;
        do {
          findx2++;
          if (findx2>=hint2->width()) { findx2=0; findy2++; }
        } while (hint2->pixel(findx2,findy2)!=color);
      }
      else
      {
        randp=rand()%j+crange[color].start;
        if (small)
        { findx2=((morph_point8 *)plist)[randp].x2;
          findy2=((morph_point8 *)plist)[randp].y2;
        } else
        { findx2=((morph_point16 *)plist)[randp].x2;
          findy2=((morph_point16 *)plist)[randp].y2;
        }
      }
      cur_pix=j+crange[color].start;
      CHECK(cur_pix<total);

      if (small)
      {
        ((morph_point8 *)plist)[cur_pix].x1=findx1;
        ((morph_point8 *)plist)[cur_pix].x2=findx2;
        ((morph_point8 *)plist)[cur_pix].y1=findy1;
        ((morph_point8 *)plist)[cur_pix].y2=findy2;
        ((morph_point8 *)plist)[cur_pix].start_color=i1->pixel(findx1,findy1);
        ((morph_point8 *)plist)[cur_pix].end_color=i2->pixel(findx2,findy2);
      }
      else
      {
        ((morph_point16 *)plist)[cur_pix].x1=findx1;
        ((morph_point16 *)plist)[cur_pix].x2=findx2;
        ((morph_point16 *)plist)[cur_pix].y1=findy1;
        ((morph_point16 *)plist)[cur_pix].y2=findy2;
        ((morph_point16 *)plist)[cur_pix].start_color=i1->pixel(findx1,findy1);
        ((morph_point16 *)plist)[cur_pix].end_color=i2->pixel(findx2,findy2);
      }
    }
  }
  int swap_point,distance,new_distance,hint_color,first_point,range,start;

  int sx2,sy2,sec;
  for (i=0; i<aneal_steps; i++)
  {
    for (j=0,first_point=0; j<total_hints; j++)
    {
      if (small)
        hint_color=hint1->pixel(((morph_point8 *)plist)[first_point].x1,((morph_point8 *)plist)[first_point].y1);
      else
        hint_color=hint1->pixel(((morph_point16 *)plist)[first_point].x1,((morph_point16 *)plist)[first_point].y1);
      start=crange[hint_color].start;
      range=crange[hint_color].end-start+1;
      for(k=crange[hint_color].start; k<=crange[hint_color].end; k++)
      {
        swap_point=rand()%range+start;
        if (small)
        {
          morph_point8 *pk,*ps;
          pk=(morph_point8 *)plist+k;
          ps=(morph_point8 *)plist+swap_point;

          distance=(pk->x2-pk->x1)*(pk->x2-pk->x1)+(pk->y2-pk->y1)*(pk->y2-pk->y1)+
                   (ps->x2-ps->x1)*(ps->x2-ps->x1)+(ps->y2-ps->y1)*(ps->y2-ps->y1);
          new_distance=(ps->x2-pk->x1)*(ps->x2-pk->x1)+(ps->y2-pk->y1)*(ps->y2-pk->y1)+
                       (pk->x2-ps->x1)*(pk->x2-ps->x1)+(pk->y2-ps->y1)*(pk->y2-ps->y1);
          if (new_distance<distance)
          {
            sx2=pk->x2;         sy2=pk->y2;
            sec=pk->end_color;
            pk->x2=ps->x2;      pk->y2=ps->y2;
            pk->end_color=ps->end_color;
            ps->x2=sx2;         ps->y2=sy2;
            ps->end_color=sec;
          }
        } else
        {
          morph_point16 *pk,*ps;
          pk=(morph_point16 *)plist+k;
          ps=(morph_point16 *)plist+swap_point;

          distance=(pk->x2-pk->x1)*(pk->x2-pk->x1)+(pk->y2-pk->y1)*(pk->y2-pk->y1)+
                   (ps->x2-ps->x1)*(ps->x2-ps->x1)+(ps->y2-ps->y1)*(ps->y2-ps->y1);
          new_distance=(ps->x2-pk->x1)*(ps->x2-pk->x1)+(ps->y2-pk->y1)*(ps->y2-pk->y1)+
                       (pk->x2-ps->x1)*(pk->x2-ps->x1)+(pk->y2-ps->y1)*(pk->y2-ps->y1);
          if (new_distance<distance)
          {
            sx2=pk->x2;         sy2=pk->y2;
            sec=pk->end_color;
            pk->x2=ps->x2;      pk->y2=ps->y2;
            pk->end_color=ps->end_color;
            ps->x2=sx2;         ps->y2=sy2;
            ps->end_color=sec;
          }
        }
      }
      first_point=crange[hint_color].end+1;
    }
  }
  p=plist;
}

int morph_width;

int morph8_compare(const void *p1, const void *p2)
{
  int pos1=((morph_point8 *)p1)->x1+((morph_point8 *)p1)->y1*morph_width;
  int pos2=((morph_point8 *)p2)->x1+((morph_point8 *)p2)->y1*morph_width;
  if (pos1<pos2) return -1;
  else if (pos1==pos2) return 0;
  else return 1;

}


int jmorph::write(bFILE *fp)
{
  int i;


  fp->write_uint32(total);
  if (small)
  {

    // if the points are put in order then they can be compressed easier
    morph_width=max(bound_x2(0),bound_x2(1));      // global used by qsort compare routine
    qsort(p,total,sizeof(morph_point8),morph8_compare);

    fp->write(p,sizeof(morph_point8)*total);
  }
  else
  {
    for (i=0; i<total; i++)
    { fp->write_uint16(((morph_point16 *)p+i)->x1);
      fp->write_uint16(((morph_point16 *)p+i)->y1);
      fp->write_uint16(((morph_point16 *)p+i)->x2);
      fp->write_uint16(((morph_point16 *)p+i)->y2);
      fp->write( &((morph_point16 *)p+i)->start_color,1);
      fp->write( &((morph_point16 *)p+i)->end_color,1);
    }
  }
  fp->write_uint16(w[0]);
  fp->write_uint16(h[0]);
  fp->write_uint16(w[1]);
  fp->write_uint16(h[1]);
  return 1;
}




step_morph::step_morph(patched_morph *mor, palette *pal, int frame_direction, int face_direction)
{
  int i;
  pm=mor;

  total=mor->total_points();
  points=(step_struct *)malloc(sizeof(step_struct)*total);

  dir=frame_direction;
  face_dir=face_direction;

  if (dir>0)
    frame_on=0;
  else
    frame_on=mor->patches-1;

  if (mor->small_morph())
  {
      int x1,y1,x2,y2;


      if (frame_direction>0)
      {
    morph_point8 *m8=mor->small_points();

    for (i=0; i<total; i++,m8++)
    {
      x1=(int)m8->x1;
      x2=(int)m8->x2;

      y1=(int)m8->y1;
      y2=(int)m8->y2;

      points[i].x=x1<<8;
      points[i].y=y1<<8;
      points[i].dx=(x2-x1)<<5;
      points[i].dy=(y2-y1)<<5;

      unsigned char r1,g1,b1,r2,g2,b2;
      pal->get(m8->start_color,r1,g1,b1);
      pal->get(m8->end_color,r2,g2,b2);
      points[i].r=r1<<8;
      points[i].g=g1<<8;
      points[i].b=b1<<8;

      points[i].dr=(long)((int)r2-(int)r1)<<5;
      points[i].dg=(long)((int)g2-(int)g1)<<5;
      points[i].db=(long)((int)b2-(int)b1)<<5;
    }
      }
      else
      {
    morph_point8 *m8=mor->small_points();
    for (i=0; i<total; i++,m8++)
    {
      x1=(int)m8->x1;
      x2=(int)m8->x2;

      y1=(int)m8->y1;
      y2=(int)m8->y2;

      points[i].x=x2<<8;
      points[i].y=y2<<8;
      points[i].dx=(x1-x2)<<5;
      points[i].dy=(y1-y2)<<5;

      unsigned char r1,g1,b1,r2,g2,b2;
      pal->get(m8->start_color,r2,g2,b2);
      pal->get(m8->end_color,r1,g1,b1);
      points[i].r=r1<<8;
      points[i].g=g1<<8;
      points[i].b=b1<<8;

      points[i].dr=(long)((int)r2-(int)r1)<<5;
      points[i].dg=(long)((int)g2-(int)g1)<<5;
      points[i].db=(long)((int)b2-(int)b1)<<5;
    }
      }
  }


}

void step_morph::show_frame(image *screen, int x, int y,  color_filter *fli)
{
  short x1,y1,x2,y2;
  screen->get_clip(x1,y1,x2,y2);

  int i,px,py,ww=max(pm->bound_x2(0),pm->bound_x2(1))-1;
  step_struct *ss;

  morph_patch *pat=pm->pats+frame_on;
  int j,tp=pat->patches;
  unsigned char *sl=pat->patch_data;

  if (face_dir>0)
  {
    for (i=0,ss=points; i<total; i++,ss++)
    {
      px=x+(ss->x>>(16-8));
      py=y+(ss->y>>(16-8));
      if (px>=x1 && px<=x2 && py>=y1 && py<=y2)
        *(screen->scan_line(py)+px)=fli->lookup_color(ss->r>>(19-8),ss->g>>(19-8),ss->b>>(19-8));

      ss->x+=ss->dx;
      ss->y+=ss->dy;
      ss->r+=ss->dr;
      ss->g+=ss->dg;
      ss->b+=ss->db;
    }

    for (j=0; j<tp; j++,sl++)
    {
      px=x+*(sl++);
      py=y+*(sl++);
      if (px>=x1 && px<=x2 && py>=y1 && py<=y2)
        *(screen->scan_line(py)+px)=*sl;
    }
  } else
  {
    for (i=0,ss=points; i<total; i++,ss++)
    {
      px=x+ww-(ss->x>>(16-8));
      py=y+(ss->y>>(16-8));
      if (px>=x1 && px<=x2 && py>=y1 && py<=y2)
        *(screen->scan_line(py)+px)=fli->lookup_color(ss->r>>(19-8),ss->g>>(19-8),ss->b>>(19-8));

      ss->x+=ss->dx;
      ss->y+=ss->dy;
      ss->r+=ss->dr;
      ss->g+=ss->dg;
      ss->b+=ss->db;
    }

    for (j=0; j<tp; j++,sl++)
    {
      px=x+(ww-(int)(*(sl++)));
      py=y+*(sl++);
      if (px>=x1 && px<=x2 && py>=y1 && py<=y2)
        *(screen->scan_line(py)+px)=*sl;
    }
  }

  frame_on+=dir;

}

void step_morph::reverse_direction()
{
  step_struct *s=points;
  int i;
  for (i=0; i<total; i++,s++)
  {
    s->dx=-s->dx;
    s->dy=-s->dy;
    s->dr=-s->dr;
    s->dg=-s->dg;
    s->db=-s->db;
  }
  dir=-dir;

}


patched_morph::patched_morph(spec_entry *e, bFILE *fp) : jmorph(e,fp)
{
  int i;

  patches=fp->read_uint16();
  pats=(morph_patch *)malloc(sizeof(morph_patch)*patches);

  for (i=0; i<patches; i++)
  {
    pats[i].patches=fp->read_uint16();
    if (pats[i].patches)
    {
      pats[i].patch_data=(unsigned char *)malloc(3*pats[i].patches);
      fp->read(pats[i].patch_data,3*pats[i].patches);
    }
    else
      pats[i].patch_data=NULL;
  }
}