home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1990 / 06 / allen.lst < prev    next >
File List  |  1990-05-02  |  10KB  |  428 lines
  1. _A PIXEL ORDERING ALGORITHM_
  2. by Norton T. Allen
  3.  
  4.  
  5. [LISTING ONE]
  6.  
  7. /* points.c    Copyright (c) 1989 by Norton T. Allen */
  8.  
  9. #include "points.h"
  10.  
  11. int nbits(int i) {
  12.   int nb;
  13.  
  14.   for (nb = 0; i != 0; nb++) i >>= 1;
  15.   return(nb);
  16. }
  17.  
  18. static int focus_x, focus_y, focus_width, focus_height;
  19.  
  20. /* zeros in map correspond to x bits, 1's to y bits */
  21. static long int z, map, zlim;
  22. static int tbits, xor_y;
  23.  
  24. void init_points(int left, int top, int width, int height) {
  25.   int nbits_w, nbits_h;
  26.   long int mask;
  27.  
  28.   focus_x = left;
  29.   focus_y = top;
  30.   focus_width = width;
  31.   focus_height = height;
  32.   nbits_w = nbits(focus_width);
  33.   nbits_h = nbits(focus_height);
  34.   tbits = nbits_w + nbits_h;
  35.   xor_y = nbits_w < nbits_h;
  36.   z = 0L;
  37.   zlim = 1L << tbits;
  38.   map = 0L;
  39.   for (mask = 1L; nbits_w || nbits_h; ) {
  40.     if (nbits_w > nbits_h || (nbits_w == nbits_h && xor_y)) {
  41.       nbits_w--;
  42.       mask <<= 1;
  43.     }
  44.     if (nbits_h > 0 &&
  45.     (nbits_h > nbits_w || (nbits_w == nbits_h && !xor_y))) {
  46.       nbits_h--;
  47.       map |= mask;
  48.       mask <<= 1;
  49.     }
  50.   }
  51. }
  52.  
  53. int next_point(int *dx, int *dy) {
  54.   int x, y, n;
  55.   long int m, rz;
  56.  
  57.   for (;;) {
  58.     if (z == zlim) return(1);
  59.     m = map; rz = z; n = tbits;
  60.     x = y = 0;
  61.     while (n-- > 0) {
  62.       if (m & 1) { /* this is a ybit */
  63.         y <<= 1;
  64.         if (rz & 1) y++;
  65.       } else {
  66.         x <<= 1;
  67.         if (rz & 1) x++;
  68.       }
  69.       m >>= 1; rz >>= 1;
  70.     }
  71.     z++;
  72.     if (xor_y) y = x ^ y;
  73.     else x = x ^ y;
  74.     if (x >= focus_width) continue;
  75.     if (y >= focus_height) continue;
  76.     break;
  77.   }
  78.   *dx = x + focus_x;
  79.   *dy = y + focus_y;
  80.   return(0);
  81. }
  82.  
  83.  
  84.  
  85.  
  86. [LISTING TWO]
  87.  
  88. /* mandel.c will handle the actual Mandelbrot set calculations.
  89.    Copyright (c) 1989 by Norton T. Allen */
  90.  
  91. #include "grafix.h"
  92.  
  93. /* This is the aspect ratio calculated on my screen: */
  94. #define ASPECT 0.739
  95.  
  96. static double xscale, yscale, xo, yo;
  97.  
  98. /* set_range() is similar to setcoords() except that it guarantees
  99.    equal x and y scales, taking the aspect ratio into account.
  100.    The axis with the smaller scale is adjust so the specified
  101.    range will be centered on the screen.  Another reason for
  102.    not using setcoords() is that I need the inverse functions
  103.    mapping device coordinates to virtual coordinates.
  104. */
  105. void set_range(double xmin, double ymin, double xmax, double ymax) {
  106.   double delta;
  107.  
  108.   yscale = (ymax-ymin)/vp_height();
  109.   xscale = (xmax-xmin)/vp_width();
  110.   if (yscale*ASPECT > xscale) {
  111.     xscale = yscale*ASPECT;
  112.     delta = (xmin + xscale * vp_width() - xmax)/2.;
  113.     xmin -= delta;
  114.     xmax += delta;
  115.   } else {
  116.     yscale = xscale/ASPECT;
  117.     delta = (ymin + yscale * vp_height() - ymax)/2.;
  118.     ymin -= delta;
  119.     ymax += delta;
  120.   }
  121.   xo = xmin;
  122.   yo = ymin;
  123. } /* ---------------------------------------------------------------- */
  124.  
  125. double vx (int dx)        /* convert device x to virtual x */
  126. {
  127.   return ((double) dx * xscale + xo);
  128. } /* ---------------------------------------------------------------- */
  129.  
  130. double vy (int dy)        /* convert device y to virtual y */
  131. {
  132.   return ((double) dy * yscale + yo);
  133. } /* ---------------------------------------------------------------- */
  134.  
  135. /* Membership in the Mandelbrot set is determined by an
  136.    iterative function.  Given the complex starting
  137.    coordinate C the function is:
  138.         Z(0) = 0.
  139.         Z(n+1) = Z(n)^2 + C
  140.    A point is deemed to be in the set if NLOOP iterations fails
  141.    to produce a point with absolute value greater than LIMIT.
  142.    Points within the set are colored black.  Points outside the
  143.    set are colored based on how many iterations passed before
  144.    exceeding LIMIT.  Miriad other schemes are possible.  Other
  145.    values for NLOOP and LIMIT are probably desirable, depending
  146.    on how deep you go.
  147. */
  148. #define NLOOP 100
  149. #define LIMIT 10000.
  150. #define NCOLORS 15
  151.  
  152. int mandel_color(double cx, double cy) {
  153.   int k;
  154.   double zx, zy, zx2, zy2;
  155.  
  156.   zx = zy = 0.;
  157.   for (k = 0; k < NLOOP; k++) {
  158.     zx2 = zx*zx;
  159.     zy2 = zy*zy;
  160.     if (zx2+zy2 > LIMIT) break;
  161.     zy = 2*zx*zy + cy;
  162.     zx = zx2 - zy2 + cx;
  163.   }
  164.   if (k < NLOOP) return((k % NCOLORS)+1);
  165.   return(0);
  166. }
  167.  
  168.  
  169.  
  170.  
  171. [LISTING THREE]
  172.  
  173. /* generate.c    Copyright (c) 1989 by Norton T. Allen */
  174.  
  175. #include <stdio.h>
  176. #include <stdlib.h>
  177. #include <dos.h>
  178. #include "points.h"
  179. #include "grafix.h"
  180.  
  181. /* This structure defines a rectangular box which we can move around the
  182.    screen using the cursor keys.  fbox.on is TRUE if the box is
  183.    currently displayed.  fbox.mode takes the values:
  184.         0    Not active
  185.         1    Cursor keys move the whole box
  186.         2    Cursor keys change box's size
  187. */
  188. struct bx {
  189.   int x, y, dx, dy, on, mode;
  190. } fbox = {300, 160, 50, 40, 0, 0};
  191.     
  192. void flip_box(void) {
  193.   set_write_mode(WM_XOR);
  194.   set_color1(15);
  195.   draw_rect(fbox.x, fbox.y, fbox.dx, fbox.dy);
  196.   set_write_mode(WM_REPLACE);
  197.   fbox.on = !fbox.on;
  198. }
  199.  
  200. void help(void) {
  201.   printf("'Esc'    to exit\n");
  202.   printf("?     for this message\n");
  203.   printf("m     to move the focus box.(use cursor keys)\n");
  204.   printf("s     to size the focus box.(use cursor keys)\n");
  205.   printf("f     to focus on the focus area\n");
  206.   printf("z     to zoom in on the focus area\n");
  207.   getch();
  208. }
  209.  
  210. static int dm = 1;    /* How many pixels to move with each cursor step */
  211.  
  212. /* check_box makes sure the new box meets the following requirements:
  213.      1. It isn't off the screen.
  214.      2. It's not smaller then 2 pixels in either dimension
  215.    Check box turns off the old box, but leaves the new box off also;
  216.    menu() will turn it on when there's no more keyboard input.
  217. */
  218. void check_box(struct bx *nb) {
  219.   if (nb->x < 0 || nb->y < 0 ||
  220.       nb->x + nb->dx > vp_width() ||
  221.       nb->y + nb->dy > vp_height() ||
  222.       nb->dx < 2 || nb->dy < 2 ||
  223.       (nb->x == fbox.x && nb->y == fbox.y &&
  224.        nb->dx == fbox.dx && nb->dy == fbox.dy))
  225.     return;
  226.   if (fbox.on) flip_box();
  227.   fbox = *nb;
  228.   fbox.on = 0;
  229. }
  230.  
  231. /* These are scan codes for cursor keys: */
  232. #define EX_UP 72
  233. #define EX_DOWN 80
  234. #define EX_RIGHT 77
  235. #define EX_LEFT 75
  236.  
  237. /* Menu supports the following keys:
  238.     ESC        Exit
  239.     M        suspend calculations and put box on the screen in
  240.             mode 1 for 'moving'.
  241.     S        As with M, but mode 2 for 'sizing'.
  242.     C        Remove box and continue calculations as before
  243.     F        Focus on boxed region.
  244.     Z        Zoom in on boxed region.
  245.     Cursor keys    Move or size box
  246.     0-9        Change step size for cursor keys
  247. */
  248. void menu(void) {
  249.   int c;
  250.   struct bx new_box;
  251.   double xmin, ymin, xmax, ymax;
  252.  
  253.   for (;;) {
  254.     while (kbhit()) {
  255.       c = getch();
  256.       switch (c) {
  257.     case '\033':
  258.       exit(0);
  259.     case 'c':
  260.     case 'C':
  261.       fbox.mode = 0;
  262.       break;
  263.     case 'm':
  264.     case 'M':
  265.       fbox.mode = 1;
  266.       break;
  267.     case 's':
  268.     case 'S':
  269.       fbox.mode = 2;
  270.       break;
  271.     case 'f': /* Focus on boxed region */
  272.     case 'F':
  273.       if (fbox.mode == 0) break;
  274.       init_points(fbox.x, fbox.y, fbox.dx, fbox.dy);
  275.       fbox.mode = 0;
  276.       break;
  277.     case 'z': /* Zoom in on boxed region */
  278.     case 'Z':
  279.       if (fbox.mode == 0) break;
  280.       xmin = vx(fbox.x);
  281.       ymin = vy(fbox.y+fbox.dy);
  282.       ymax = vy(fbox.y);
  283.       xmax = vx(fbox.x+fbox.dx);
  284.       set_range(xmin, ymin, xmax, ymax);
  285.       init_points(0, 0, vp_width(), vp_height());
  286.       pc_textmode();    /* Kluge to clear screen */
  287.       init_video(EGA);
  288.       fbox.mode = fbox.on = 0;
  289.       break;
  290.     case '1':
  291.     case '2':
  292.     case '3':
  293.     case '4':
  294.     case '5':
  295.     case '6':
  296.     case '7':
  297.     case '8':
  298.     case '9':
  299.       dm = c-'0';
  300.       break;
  301.     case 0:
  302.       c = getch();
  303.       new_box = fbox;
  304.       if (fbox.mode == 1) {    /* moving the box */
  305.         switch (c) {
  306.           case EX_UP:
  307.         new_box.y -= dm;
  308.         break;
  309.           case EX_DOWN:
  310.           new_box.y += dm;
  311.           break;
  312.           case EX_RIGHT:
  313.         new_box.x += dm;
  314.           break;
  315.           case EX_LEFT:
  316.         new_box.x -= dm;
  317.           break;
  318.           default: break;
  319.         }
  320.       } else if (fbox.mode == 2) {
  321.         switch (c) {
  322.           case EX_UP:
  323.         new_box.dy -= dm;
  324.           break;
  325.           case EX_DOWN:
  326.         new_box.dy += dm;
  327.           break;
  328.           case EX_RIGHT:
  329.         new_box.dx += dm;
  330.           break;
  331.           case EX_LEFT:
  332.         new_box.dx -= dm;
  333.           break;
  334.           default: break;
  335.         }
  336.       }
  337.       check_box(&new_box);
  338.       break;
  339.     default:
  340.       break;
  341.       }
  342.     }
  343.     if (fbox.mode == 0) break;
  344.     else if (!fbox.on) flip_box();
  345.   }
  346.   if (fbox.on) flip_box();
  347. }
  348.  
  349. /* Generate cycles through all the pixels, possibly starting over as
  350.    dictated by menu().  Generate never returns.
  351. */
  352. void generate(void) {
  353.   int c, x, y;
  354.   double fx, fy;
  355.  
  356.   for (;;) {
  357.     while (next_point(&x, &y) == 0) {
  358.       fx = vx(x);
  359.       fy = vy(y);
  360.       c = mandel_color(fx, fy);
  361.       set_color1(c);
  362.       draw_point(x, y);
  363.       if (kbhit()) menu();
  364.     }
  365.     menu();
  366.   }
  367. }
  368.  
  369. void main(int argc, char **argv) {
  370.   if (init_video (EGA)) {
  371.     init_points(0, 0, vp_width(), vp_height());
  372.     set_range(-2., -.95, .75, .95);
  373.     generate();
  374.   } else printf("Cannot select graphics mode");
  375. }
  376.  
  377.  
  378.  
  379. [LISTING FOUR]
  380.  
  381. /* points.h include file for pixel ordering program. */
  382.  
  383. void init_points(int left, int top, int width, int height);
  384.  
  385. int next_point(int *dx, int *dy);
  386.  
  387. int mandel_color(double cx, double cy);
  388.  
  389. void set_range(double xmin, double ymin, double xmax, double ymax);
  390.  
  391. double vx (int dx);        /* convert device x to virtual x */
  392.  
  393. double vy (int dy);        /* convert device y to virtual y */
  394.  
  395.  
  396.  
  397.  
  398.  
  399. [LISTING FIVE] 
  400.  
  401. To be included in grafix.h 
  402.  
  403.  
  404. /* Added by Norton Allen */
  405. /* --------------------- */
  406. void set_write_mode(int mode);
  407.  
  408. #define WM_REPLACE 0
  409. #define WM_XOR 0x18
  410.  
  411.  
  412.  
  413.  
  414.  
  415. [LISTING SIX]
  416.  
  417. /* wmode.c for DDJ grafix library Copyright (c) 1989 by Norton T. Allen */
  418.  
  419. #include <dos.h>
  420. #include "grafix.h"
  421.  
  422. int write_mode = WM_REPLACE;
  423.  
  424. void set_write_mode(int mode) {
  425.   write_mode = mode;
  426. }
  427.  
  428.