9: Three case studies in graphics

9.1: First case study: drawing a fractal

9.1.1: Defining the Mandelbrot set

SML Mandelbrot
(* in_Mandelbrot : Complex.complex -> bool *)
fun in_Mandelbrot c
    = let
         open Complex
         val MAXSTEPS = 31
         fun step i z
             = let
                  val z' = complex_sub (complex_multiply z z) c
               in
                  if complex_distance z > 1.0
                     then false
                     else if i > MAXSTEPS
                             then true
                             else step (i+1) z'
               end
      in
         step 0 (0.0,0.0)
      end ;
C Mandelbrot implementation
#include <stdio.h>
#include "mandelbrot.h"
#include "complex.h"
#include "bool.h"

#define MAXSTEPS 31

bool in_Mandelbrot( complex x ) {
  complex z = {0,0} ;
  int i = 0 ;

  while( true ) {
    if( complex_distance( z ) > 1.0 ) {
      return false ;
    } else if( i > MAXSTEPS ) {
      return true ;
    }
    z = complex_multiply( z, z ) ;
    z = complex_sub( z, x ) ;
    i++ ;
  }
}
C Mandelbrot interface
#ifndef MANDELBROT_H
#define MANDELBROT_H

#include "bool.h"
#include "complex.h"
extern bool in_Mandelbrot( complex x ) ;

#endif

9.1.2: Drawing the fractal on the screen

C window to complex function
static
complex window_to_complex( int X, int Y,
                           int WIDTH, int HEIGHT,
                           double x, double y,
                           double width, double height ) {
  complex c ;
  c.re = x + width  * X / WIDTH  - width/2 ;
  c.im = y + height * Y / HEIGHT - height/2 ;
  return c ;
}
C priorities
width * ( X / WIDTH )
C priorities 2
width * X / (double) WIDTH
C X rectangle
void XFillRectangle( Display *d, Window w, GC gc,
                     int x, int y,
                     int width, int height ) ;
C draw a pixel in X-windows
static
void draw_pixel( Display *theDisplay, Window theWindow,
                 long colour,
                 int x, int y ) {
  GC gc = XCreateGC( theDisplay, theWindow, 0, NULL ) ;
  XSetForeground( theDisplay,            gc, colour ) ;
  XFillRectangle( theDisplay, theWindow, gc, x, y, 1, 1);
  XFreeGC( theDisplay, gc ) ;           /* Inefficient */
}
C filling a window
static
void draw_Mandelbrot( Display *theDisplay, Window theWindow,
                      long black, long white,
                      int WIDTH, int HEIGHT,
                      double x, double y,
                      double width, double height) {
  int X, Y ;
  complex c ;
  for( X=0 ; X<WIDTH ; X++ ) {
    for( Y=0 ; Y<HEIGHT ; Y++ ) {
      c = window_to_complex( X,Y,WIDTH,HEIGHT,
                             x,y,width,height ) ;
      if( in_Mandelbrot( c ) ) {
        draw_pixel( theDisplay, theWindow, black, X, Y ) ;
      } else {
        draw_pixel( theDisplay, theWindow, white, X, Y ) ;
      }
    }
  }
}
C main X function
#define WIDTH  100
#define HEIGHT 100

int main( int argc , char *argv[] ) {
  XtAppContext context ;
  int          theScreen ;
  Display      *theDisplay ;
  Window       theWindow ;
  long         white, black ;
  double       x, y, width, height ;
  Widget widget = XtVaAppInitialize( &context, "XMandel",
                      NULL, 0, &argc, argv, NULL, NULL ) ;
  XtVaSetValues( widget, XtNheight, HEIGHT,
                         XtNwidth,  WIDTH, NULL ) ;
  XtRealizeWidget( widget ) ;
  theDisplay = XtDisplay( widget ) ;
  theWindow  = XtWindow( widget ) ;
  theScreen  = DefaultScreen( theDisplay ) ;
  white      = WhitePixel( theDisplay, theScreen ) ;
  black      = BlackPixel( theDisplay, theScreen ) ;
  printf("Enter originx, y, width and height: " ) ;
  if( scanf( "%lf%lf%lf%lf", &x,&y,&width,&height ) != 4 ) {
    printf("Sorry, cannot read these numbers\n" ) ;
  } else {
    draw_Mandelbrot( theDisplay, theWindow, black, white,
                     WIDTH, HEIGHT, x, y, width, height ) ;
    XtAppMainLoop( context ) ;
  }
  return 0 ;
}
SH test values
0 0 2.5 2.5
C infinite loop
while( true ) { ... }
C Complete module that interfaces with X
#include <stdio.h>
#include <X11/Intrinsic.h>
#include <X11/StringDefs.h>
#include "complex.h"
#include "mandelbrot.h"
MAKE the makefile for Mandelbrot
OBJECTS= main.o complex.o mandelbrot.o

mandelbrot: $(OBJECTS)
        $(CC) -o mandelbrot $(OBJECTS) -lXt -lX11 -lm

depend:
        makedepend $(CFLAGS) main.c complex.c mandelbrot.c

Answer to exercise 9.1

C before substitution of [[WIDTH]] and [[HEIGHT]]
complex window_to_complex( int X, int Y, int WIDTH,
                           int HEIGHT, double x, double y,
                           double width, double height )
C after substitution of WIDTH and HEIGHT
complex window_to_complex( int X, int Y, int 100,
                           int 100, double x, double y,
                           double width, double height )

9.1.3: Shortening the argument lists

C prototypes of functions
complex window_to_complex( int X, int Y,
                           int WIDTH, int HEIGHT,
                           double x, double y,
                           double width, double height ) ;

void draw_pixel( Display *theDisplay, Window theWindow,
                 long colour,
                 int x, int y ) ;

void draw_Mandelbrot( Display *theDisplay, Window theWindow,
                      long black, long white,
                      int WIDTH, int HEIGHT,
                      double x, double y,
                      double width, double height) ;
C display declaration
static Display *theDisplay ;
C static variables that are needed
static Display *theDisplay ;
static Window   theWindow ;
static long     black, white ;

#define WIDTH   100
#define HEIGHT  100
C window to complex function, fewer arguments
static
complex window_to_complex( int X, int Y,
                           double x, double y,
                           double width, double height ) {
  complex c ;
  c.re = x + width  * X / WIDTH  - width/2 ;
  c.im = y + height * Y / HEIGHT - height/2 ;
  return c ;
}
C improved code to draw a pixel
static
void draw_pixel( GC gc, long colour, int x, int y ) {
  XSetForeground( theDisplay,            gc, colour ) ;
  XFillRectangle( theDisplay, theWindow, gc, x, y, 1, 1);
}
C improved code to fill the whole window
static
void draw_Mandelbrot( double x, double y,
                      double width, double height) {
  int X, Y ;
  GC gc = XCreateGC( theDisplay, theWindow, 0, NULL ) ;
  for( X=0 ; X<WIDTH ; X++ ) {
    for( Y=0 ; Y<HEIGHT ; Y++ ) {
      if( in_Mandelbrot( window_to_complex( X,Y,x,y,
                                     width,height ) ) ) {
        draw_pixel( gc, black, X, Y ) ;
      } else {
        draw_pixel( gc, white, X, Y ) ;
      }
    }
  }
  XFreeGC( theDisplay, gc ) ;
}
C main X function, shorter argument lists
int main( int argc , char *argv[] ) {
  XtAppContext context ;
  int      theScreen ;
  double   x, y, width, height ;
  Widget widget = XtVaAppInitialize( &context, "XMandel",
                      NULL, 0, &argc, argv, NULL, NULL ) ;
  XtVaSetValues( widget, XtNheight, HEIGHT,
                         XtNwidth,  WIDTH, NULL ) ;
  XtRealizeWidget( widget ) ;
  theDisplay = XtDisplay( widget ) ;
  theWindow  = XtWindow( widget ) ;
  theScreen  = DefaultScreen( theDisplay ) ;
  white      = WhitePixel( theDisplay, theScreen ) ;
  black      = BlackPixel( theDisplay, theScreen ) ;
  printf("Enter originx, y, width and height: " ) ;
  if( scanf( "%lf%lf%lf%lf", &x,&y,&width,&height ) != 4 ) {
    printf("Sorry, cannot read these numbers\n" ) ;
  } else {
    draw_Mandelbrot( x, y, width, height ) ;
    XtAppMainLoop( context ) ;
  }
  return 0 ;
}

9.1.4: Handling events

C handle Expose event
XtAddEventHandler( widget, ExposureMask, false,
                   draw_Mandelbrot, NULL ) ;
C structure to pass the arguments to draw_Mandelbrot
typedef struct {
  double x, y ;
  double width, height ;
} rectangle ;
C code to handle the Expose event
void handle_expose( Widget w, XtPointer data,
                    XEvent *e, Boolean *cont ) {
  rectangle *r = data ;
  draw_Mandelbrot( r->x, r->y, r->width, r->height ) ;
}
C main X function, handling expose
int main( int argc , char *argv[] ) {
  XtAppContext context ;
  int          theScreen ;
  rectangle    r ;
  Widget widget = XtVaAppInitialize( &context, "XMandel",
                      NULL, 0, &argc, argv, NULL, NULL ) ;
  XtVaSetValues( widget, XtNheight, HEIGHT,
                         XtNwidth,  WIDTH, NULL ) ;
  XtRealizeWidget( widget ) ;
  theDisplay = XtDisplay( widget ) ;
  theWindow  = XtWindow( widget ) ;
  theScreen  = DefaultScreen( theDisplay ) ;
  white      = WhitePixel( theDisplay, theScreen ) ;
  black      = BlackPixel( theDisplay, theScreen ) ;
  printf("Enter originx, y, width and height: " ) ;
  if( scanf( "%lf%lf%lf%lf", &r.x, &r.y, &r.width,
                                   &r.height ) != 4 ) {
    printf("Sorry, cannot read these numbers\n" ) ;
  } else {
    XtAddEventHandler( widget, ExposureMask, false,
                       handle_expose, &r ) ;
    XtAppMainLoop( context ) ;
  }
  return 0 ;
}
C handle a button press
XtAddEventHandler( widget, ButtonPressMask, false,
                   handle_button, NULL ) ;
C quit the application
void handle_button( Widget w, XtPointer data,
                    XEvent *e, Boolean *cont ) {
  exit( 0 ) ;
}

Exercise 9.2

C example colour map
#define NCOLOURS 1
static unsigned long cells[NCOLOURS] ;

void setcolours( Display *d, int screen ) {
  XColor colour ;
  Colormap c = DefaultColormap( d, screen ) ;
  XAllocColorCells( d, c, 1, NULL, 0, cells, NCOLOURS ) ;
  colour.flags = DoRed | DoGreen | DoBlue ;
  colour.red   = 65535 ;
  colour.green = 55255 ;
  colour.blue  = 0     ;
  colour.pixel = cells[0] ;
  XStoreColor( d, c, &colour ) ;
}

9.2: Second case study: device independent graphics

9.2.1: PostScript

9.2.2: Monolithic interface design

C line X
XDrawLine( display, window, gc, x1, y1, x2, y2 ) ;
C data structures
#include <X11/Intrinsic.h>
#include <X11/StringDefs.h>
#include <stdio.h>

#define X11HEIGHT 100
#define X11WIDTH  100

typedef enum { X11, PS } Devicetype ;
typedef struct {
  Devicetype tag ;
  union {
    struct {
      Display *d ;
      Window w ;
      GC gc ;
      XtAppContext context ;
      Widget widget ;
    } X11 ;
    struct {
      FILE *out ;
    } PS ;
  } c ;
} Device ;
C line function
void draw_line( Device *d,
                int x0, int y0, int x1, int y1 ) {
  switch( d->tag ) {
    case X11:
      XDrawLine( d->c.X11.d, d->c.X11.w, d->c.X11.gc,
                 x0, X11HEIGHT-1-y0, x1, X11HEIGHT-1-y1 ) ;
      break ;
    case PS:
      fprintf( d->c.PS.out, "newpath\n" ) ;
      fprintf( d->c.PS.out, "%d %d moveto\n", x0, y0 ) ;
      fprintf( d->c.PS.out, "%d %d lineto\n", x1, y1 ) ;
      fprintf( d->c.PS.out, "closepath\n" ) ;
      fprintf( d->c.PS.out, "stroke\n" ) ;
      break ;
    default:
      abort() ;
  }
}
C box function
void draw_box( Device *d,
               int x0, int y0, int x1, int y1 ) {
  switch( d->tag ) {
    case X11:
      XDrawRectangle( d->c.X11.d, d->c.X11.w, d->c.X11.gc,
                      x0, X11HEIGHT-1-y0, x1-x0, y1-y0 ) ;
      break ;
    case PS:
      fprintf( d->c.PS.out, "newpath\n" ) ;
      fprintf( d->c.PS.out, "%d %d moveto\n", x0, y0 ) ;
      fprintf( d->c.PS.out, "%d %d lineto\n", x0, y1 ) ;
      fprintf( d->c.PS.out, "%d %d lineto\n", x1, y1 ) ;
      fprintf( d->c.PS.out, "%d %d lineto\n", x1, y0 ) ;
      fprintf( d->c.PS.out, "%d %d lineto\n", x0, y0 ) ;
      fprintf( d->c.PS.out, "closepath\n" ) ;
      fprintf( d->c.PS.out, "stroke\n" ) ;
      break ;
    default:
      abort() ;
  }
}

9.2.3: Modular interface design

SML device driver functions datatype
datatype 'a graphics
    = DrawBox of     ('a * int * int * int * int -> 'a)
    | DrawLine of    ('a * int * int * int * int -> 'a)
    | DrawCircle of  ('a * int * int * int -> 'a)
    | DrawEllipse of ('a * int * int * int * int -> 'a) ;
SML complete device driver functions datatype
datatype ('a,'b,'c) graphics
    = Open of        ('b -> 'a)
    | DrawBox of     ('a * int * int * int * int -> 'a)
    | DrawLine of    ('a * int * int * int * int -> 'a)
    | DrawCircle of  ('a * int * int * int -> 'a)
    | DrawEllipse of ('a * int * int * int * int -> 'a)
    | Close of       ('a -> 'c) ;
C device driver structure
typedef struct {
  void *(*open)( void *what ) ;
  void  (*draw_line)( void *g, int x0, int y0,
                               int x1, int y1 ) ;
  void  (*draw_box)( void *g,  int x0, int y0,
                               int x1, int y1 ) ;
  /*  Other elements of device driver */
  void  (*close)( void *g ) ;
} graphics_driver ;

Answer to exercise 9.3

C Other elements of device driver
  void  (*draw_circle)( void *g, int x0, int y0, int r ) ;
  void  (*draw_ellipse)( void *g, int x0, int y0, int r, int dx ) ;
C X11 device driver implementation
#include "X11driver.h"
#include <X11/Intrinsic.h>
#include <X11/StringDefs.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  Display *d ;
  Window w ;
  GC gc ;
  XtAppContext context ;
  Widget widget ;
} X11Info ;

#define HEIGHT 100
#define WIDTH  100

void *X11_open( void *what ) {
  X11Info *i = malloc( sizeof( X11Info ) ) ;
  X11Open *args = what ;
  long black ;
  XSetWindowAttributes attrib ;
  i->widget = XtVaAppInitialize( &i->context, "XProg", NULL,
                                 0, args->argc, args->argv,
                                 NULL, NULL ) ;
  XtVaSetValues( i->widget, XtNheight, HEIGHT,
                         XtNwidth, WIDTH, NULL ) ;
  XtRealizeWidget( i->widget ) ;
  i->d = XtDisplay( i->widget ) ;
  i->w  = XtWindow( i->widget ) ;
  i->gc = XCreateGC( i->d, i->w, 0, NULL ) ;
  black = BlackPixel( i->d, DefaultScreen( i->d ) ) ;
  XSetForeground( i->d, i->gc, black ) ;
  attrib.backing_store = Always ;
  XChangeWindowAttributes( i->d, i->w, CWBackingStore, &attrib) ;
  return (void *) i ;
}

void X11_draw_line( void *g,
                    int x0, int y0, int x1, int y1 ) {
  X11Info *i = g ;
  XDrawLine( i->d, i->w, i->gc, x0, HEIGHT-1-y0,
                                x1, HEIGHT-1-y1 ) ;
}

void X11_draw_box( void *g,
                   int x0, int y0, int x1, int y1) {
  X11Info *i = g ;
  XDrawRectangle( i->d, i->w, i->gc, x0, HEIGHT-1-y0,
                                     x1-x0, y1-y0 ) ;
}

void X11_close( void *g ) {
  X11Info *i = g ;
  XFreeGC( i->d, i->gc ) ;
  XtAppMainLoop( i->context ) ;
  free( i ) ;
}

graphics_driver X11Driver = {
  X11_open,
  X11_draw_line,
  X11_draw_box,
  /*  other functions of the driver */
  X11_close
} ;
C X11 device driver interface
#ifndef X11_DRIVER_H
#define X11_DRIVER_H

extern graphics_driver X11Driver ;

typedef struct {
  int *argc ;
  char **argv ;
} X11Open ;

#endif /* X11_DRIVER_H */

Answer to exercise 9.6

C PS device driver implementation
#include "PSdriver.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  FILE *file ;
} PSInfo ;

void *PS_open( void *what ) {
  PSInfo *i = malloc( sizeof( PSInfo ) ) ;
  char *filename = what ;
  i->file = fopen( filename, "w" ) ;
  if( i->file == NULL ) {
    return NULL ;
  }
  fprintf( i->file, "%%!PS\n" ) ;
  return (void *) i ;
}

void PS_draw_line(void *g, int x0, int y0, int x1, int y1) {
  PSInfo *i = g ;
  fprintf( i->file, "newpath\n" ) ;
  fprintf( i->file, "%d %d moveto\n", x0, y0 ) ;
  fprintf( i->file, "%d %d lineto\n", x1, y1 ) ;
  fprintf( i->file, "closepath\n" ) ;
  fprintf( i->file, "stroke\n" ) ;
}

void PS_draw_box(void *g, int x0, int y0, int x1, int y1) {
  PSInfo *i = g ;
  fprintf( i->file, "newpath\n" ) ;
  fprintf( i->file, "%d %d moveto\n", x0, y0 ) ;
  fprintf( i->file, "%d %d lineto\n", x0, y1 ) ;
  fprintf( i->file, "%d %d lineto\n", x1, y1 ) ;
  fprintf( i->file, "%d %d lineto\n", x1, y0 ) ;
  fprintf( i->file, "%d %d lineto\n", x0, y0 ) ;
  fprintf( i->file, "closepath\n" ) ;
  fprintf( i->file, "stroke\n" ) ;
}

void PS_close( void *g ) {
  PSInfo *i = g ;
  fprintf( i->file, "%%%%Eof\n" ) ;
  fclose( i->file ) ;
  free( i ) ;
}

graphics_driver PSDriver = {
  PS_open,
  PS_draw_line,
  PS_draw_box,
  /*  other functions of the driver */
  PS_close
} ;
C program that draws a cross
void draw_cross( graphics_driver *g, void *openinfo ) {
  void *driver = (*g->open)( openinfo ) ;
  (*g->draw_line)( driver, 0, 0, 100, 100 ) ;
  (*g->draw_line)( driver, 100, 0, 0, 100 ) ;
  (*g->close)( driver ) ;
}

int main( int argc, char *argv[] ) {
  X11Open arguments ;
  arguments.argc = &argc;
  arguments.argv = argv ;
  draw_cross( &PSDriver, "out.ps" ) ;
  draw_cross( &X11Driver, &arguments ) ;
  return 0 ;
}

9.3: Third case study: a graphics language

gp itself
 .PS
 circle "file" ;
 line ;
 box "gp" ;
 line ;
 circle "device"
 .PE

9.3.1: Lexical analysis

SML token
datatype token = Number of real
               | Ident  of string
               | Text   of string
               | Symbol of string
               | Error ;

9.3.2: Parsing

SML primitive
datatype primitive = Box | Circle | Line ;
SML expression
datatype expression = Ident  of string
                    | Number of real ;
SML attribute
datatype attribute = Height of expression
                   | Width  of expression
                   | Radius of expression
                   | Text   of string ;
SML element
datatype element = Up
                 | Down
                 | Right
                 | Left
                 | Assign of string * expression
                 | Prim   of primitive * attribute list ;
SML box primitive
val box_primitive = Prim(Box,[Text "a box",
                              Height (Number 3.0)]);
SML box tokens
val box_tokens = [Ident  ".PS",
                  Ident  "box",
                  Text   "\"a box\"",
                  Ident  "height",
                  Number 3.0,
                  Ident  ".PE" ];

9.3.3: Interpretation

gp default
 .PS
 boxht     = 0.5  ;
 boxwid    = 0.75 ;
 circlerad = 0.25 ;
 lineht    = 0.5  ;
 linewid   = 0.5  ;
 moveht    = 0.5  ;
 movewid   = 0.5  ;
 textht    = 0.0  ;
 textwid   = 0.0
 .PE
gp square
 .PS
 boxwid = boxht ;
 box
 .PE

Summary

Further exercises

Exercise 9.21

gp for program
 .PS
 for i = 1 to 6 do {
   box width 0.1 height 0.2 ;
   right (0.05*i*i) ;
   up 0.1
 }
 box width 0.1 height 0.2 ;
 .PE

Exercise 9.22

gp ellipse program
 .PS
 ellipseht  = 0.5  ;
 ellipsewid = 0.75 ;
 ellipse "an" "ellipse"
 .PE