/*

	The following C code is for a fast Mandelbrot Algorithm
called Contour Crawling, invented by Scott Sherman in 1986 while a
math student at Western Washington Univ.  The algorithm	works by 
scanning across the Mandelbrot Set point by point, looking
for regions of the same color.  Once a "Contour" is detected, the
algorithm bounces back and forth along the boundary of the contour
until it finds its way back to its starting point, and then fills the
interior.  Intuitively and in practice it is far more efficient than
the normal pixel by pixel method or Mariani's Method.  The following
code should demonstrate that it is also simple.  Scott and I (John
Gossman) have written an article about Contour Crawling that covers
the theoretical aspects and such concerns as "Islands", the connected
nature of the level sets around the Mandelbrot Set, and the practical
issues of Contour Crawling on a discrete lattice.  I will post this
article somewhere soon, and leave a note here about getting hold of
it.  The best argument is to code up a version of this program and
look at the results.  Another nice thing is that all the optimization
tricks for calculating the count (assembly, fixed-point etc.) can still 
be applied to this method in order to further increase the speed. 
 
              Copyright 1988,1989 by Scott Sherman
                        and John Gossman
 
                            LISTING 1
Keywords to be defined :
	MINX,	; These four define the resolution
	MINY,
	MAXX,
	MAXY,
	BIGGESTCOUNT,	; the maximum iterations for GetCount
	BLANK,		; normally 0
	LIMIT		; Use 4 or 5.  Used to recognize contours.
	GETPIXEL(),     ; A function to read a pixel value
	PUTPIXEL(),	; A function to set a pixel value
 
        Note: Above is the original header of this file, which the
        authors distributed on USENET. I have added two more keywords:
         
        SETVIDEO(),	; Set graphics mode
        RESETVIDEO(),	; Reset text mode
        
        I have done a rather minimal port to Microsoft C, and have hard
        coded the VGA 320x200x256 mode. I haven't touched the boundary
        tracing logic at all. Note that if the MIN/MAX values completely
        surround the Mandelbrot set, the algorithm fails. Pick values
        that cut through the escape-time stripes.

        Compiles via "cl /AM btm.c graphics.lib" (needs medium model). 
                
        Tim Wegner
*/

/* defines for 320x200x256 Microsoft C */
#define MINX    0
#define	MINY	0
#define	MAXX	319
#define	MAXY    199
#define BIGGESTCOUNT 150
#define	BLANK	0
#define	LIMIT   5

GETPIXEL(int x, int y)
{
   int out;
   out = _getpixel(x,y);
   return(out);
}

PUTPIXEL(int x, int y, int color)
{
   _setcolor(color);
   _setpixel(x,y);
   return(0);
}

SETVIDEO()
{
   _setvideomode(19);
}
RESETVIDEO()
{
   _setvideomode(3);
}
#define TRUE	1
#define FALSE   0

/* 
   code below this point is completely unchanged, except for insertion
   of SETVIDEO/RESETVIDEO and getch() calls in main()
*/

int maxcount;
int new;
float xr[MAXX+1];
float yr[MAXY+1];
int color[BIGGESTCOUNT];

/* (x_coord,y_coord) contain the screen coordinates of the point
   return the count of the point */
int GetCount(x_coord,y_coord)
int x_coord,y_coord;
{
   float x,y;
   float cx,cy;
   float x2,y2;
   int count;

   count = 1;
   x = xr[x_coord];
   y = yr[y_coord];
   cx = x;	
   cy = y;
   x2 = x*x;
   y2 = y*y;

   while ((x2 + y2 < 4) && (count < maxcount))
   {
      y = 2*x*y + cy;
      x = x2-y2 + cx;
      x2 = x*x;
      y2 = y*y;
      count = count + 1;
   }
   return (count);
}


/* (x,y) contain the screen coordinates of a point
   return its color
	if the point is off the screen, return BLANK
	if the point was freshly calculated, display it & new = TRUE
*/
int GetColor(x,y)
int x,y;
{
   int temp,GetCount();
   int GETPIXEL();

   if ((x<MINX) || (x>MAXX) || (y<MINY) || (y>MAXY))
       return (BLANK);
   temp = GETPIXEL(x,y);
   if (temp == BLANK)
       {
      new = TRUE;
      temp = GetCount(x,y);
      temp = color[temp];
      PUTPIXEL(x,y,temp);
   }
   else new = FALSE;
   return (temp);
}



/* (x,y) contain the screen coordinates of the point
   If this point hasn't been calculated before, return TRUE */
int IsBlank(x,y)
int x,y;
{
   if ((x<MINX) || (x>=MAXX) || (y<MINY) || (y>=MAXY))
       return FALSE;
   return (GETPIXEL(x,y) == BLANK);
}

/* (x,y) is the start point and 'dir' the direction to travel in
	'thecount' is the value to fill with
   a line will be drawn until something is run into */
void FillLine(x,y,dir,thecount)
int x,y,dir,thecount;
{
   while (GETPIXEL(x,y) == BLANK)
       {
      PUTPIXEL(x,y,thecount);
      x = x - dir;
   }
}

/* (x,y) contain the screen coordinates of a point on a contour
	'thecount' contains the value of the contour
   if 'fill' is FALSE, crawl the region
	if 'fill' is TRUE, fill the region */
void Crawl(x,y,thecount,fill)
int x,y;
int thecount;
int fill;
{
   int xinc,yinc;		/* direction to travel */
   int firstx,firsty;		/* the starting & ending point */
   int done;			/* we've reached the end */
   int GetColor(),IsBlank();

   firstx = x;
   firsty = y;
   xinc = 1;
   done = FALSE;

   while (!done)
       {
      if (GetColor(x+xinc,y) == thecount)
          {
         x = x + xinc;
         yinc = -xinc;
         done = (x==firstx) && (y==firsty);
         if (fill && IsBlank(x-yinc,y))
             FillLine(x-yinc,y,yinc,thecount);
      }
      else yinc = xinc;
      if (!done && (GetColor(x,y+yinc) == thecount))
          {
         y = y + yinc;
         xinc = yinc;
         done = (x==firstx) && (y==firsty);
         if (fill && IsBlank(x-yinc,y))
             FillLine(x-yinc,y,yinc,thecount);
      }
      else xinc = -yinc;
   }
   if (!fill)
       Crawl(firstx,firsty,thecount,TRUE);
}

/* (leftx,topy) contain the real coordinates of the upper left
	corner of the region - 'gap' is the length of a side
   calculate the cooresponding region of the Mandelbrot Set */
DisplaySet(leftx,topy,gap)
float leftx,topy,gap;
{
   float smallgap;		/* real width of a pixel */
   int last,count;		/* last count & present count */
   int edge,edgex,edgey;	/* screen coords of edge of contour
   */
   int x,y;			/* current screen coordinates */
   int GetColor();

   smallgap = gap/MAXY;
   for (x=MINX; x<=MAXX; x++)
      xr[x] = leftx + (x-MINX) * smallgap;
   for (y=MINY; y<=MAXY; y++)
      yr[y] = topy - (y-MINY) * smallgap;

   edge = 0;
   last = BLANK;

   for (x=MINX; x<=MAXX; x++)
   {
      if(kbhit())
      {
	 RESETVIDEO();
	 exit(0);
      }
      for (y=MINY; y<=MAXY; y++)
      {
         count = GetColor(x,y);
         if (count == last)
             edge++;
         else	{
            last = count;
            edge = 0;
            edgex = x;
            edgey = y;
         }
         if (new && edge>=LIMIT)
             Crawl(edgex,edgey,count,FALSE);
      }
      edge = 0;
      last = BLANK;
   }
}

/* To make contour crawling faster and generate prettier pictures
with less "noise" near the edge of the Mandelbrot Set, you can
combine level sets.  The following fragment combines every other
band on a 16 color system.  A more sophisticated approach is to
combine bands logarithmically, so that outer bands do not get 
combined and narrow bands near the MandelBrot set get clumped
together in groups of hundreds.  IMPORTANT: This not only makes the
algorithm faster it makes better looking pictures. */

/* a sample of how the bands could be combined */
GENERATECOUNTS(color,maxcount)
int color[];
int maxcount;
{
   int i;

   for (i=0; i<maxcount; i++)
      color[i] = (i/2 % 15)+1;
   color[maxcount] = 8;
}



/* this is the function that actually gets called to run the
program */
main()
{
   float leftx,topy;	/* coordinates of a corner of display box */
   float gap;		/* length of the height of the box */

   printf("Enter the left coordinate : ");
   scanf("%f",&leftx);
   printf("Enter the top coordinate : ");
   scanf("%f",&topy);
   printf("Enter the height of the box : ");
   scanf("%f",&gap);
   printf("Enter the maximum count : ");
   scanf("%d",&maxcount);
   SETVIDEO();
   GENERATECOUNTS(color,maxcount);
   DisplaySet(leftx,topy,gap);
   getch();
   RESETVIDEO();
}