home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 144.lha / Leach_v1.3 / octant.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-21  |  13.2 KB  |  515 lines
  1. /******************************************************************************
  2.  * OCTANT.C                                                        \ 3 | 2 /
  3.  * This group of routines draws a line using the Octantal         \    |  /
  4.  * Digital Differential Analyser algorithm described on page    4 \ | / 1
  5.  * 25 of "Microcomputer Displays, Graphics and Animation". Its     \|/
  6.  * advantage over the system line drawing routines is that it  -----+-----
  7.  * saves the color register values of the pixels that it draws       /|\
  8.  * over, so that they can be restored as the line is erased.    5 / | \ 8
  9.  *                                                                 /    |  \
  10.  * These routines are optimized for speed not compactness.        / 6 | 7    \
  11.  * When a line is drawn, the original pixels and their coordinates are saved.
  12.  * Thus, the line can be erased rather quickly but severl K of ram can be 
  13.  * required. If necessary, the line drawing speed can be increased some what
  14.  * by including the plot() routine as in line code of the octant routines,
  15.  * thus eliminating the function call overhead.
  16.  *
  17.  * These routines do not perform clipping.
  18.  *
  19.  * For normal use, the entry points to this file are draw_line() and
  20.  * restore_line().
  21.  *
  22.  ******************************************************************************/
  23.  
  24.  
  25. /* Some of these include files are not necessary.    */
  26.  
  27. #include    <functions.h>
  28. #include    <exec/types.h>
  29. #include     <exec/nodes.h>
  30. #include    <exec/memory.h>
  31. #include    <exec/libraries.h>
  32. #include    <graphics/gfx.h>
  33. #include    <graphics/rastport.h>
  34. #include    <intuition/intuitionbase.h>
  35. #include     <stdio.h>
  36. /* #include    <exec/tasks.h>            */
  37. /* #include    <graphics/text.h>        */
  38.  
  39.  
  40. /* This struct keeps track of the image pixels blotted out by the line    */
  41.  
  42. static struct saved_line
  43. {
  44.     struct RastPort    *RPort;        /* RastPort the line was drawn in.        */
  45.     UBYTE            *storage;    /* Color registers of drawn over pixels    */
  46.     USHORT            *x;            /* X screen coordinates of line points.    */
  47.     USHORT            *y;            /* Y screen coordinates of line points.    */
  48.     USHORT            points;        /* Num of elements in the allocated        */
  49. }line;                            /* array. Eq the max index plus 1.        */
  50.  
  51. /************************  Error messages  ************************************/
  52.  
  53. static char alloc_err[] = "Can't alloc pixel arrays.";
  54. static char rp_err[]    = "ERROR READING PIXEL";
  55. static char wp_err[]    = "ERROR WRITINGING PIXEL";
  56. static char line_err[]    = "Plot() called before array allocation.";
  57. static char rest_err[]    = "Tried to restore nonexistant line.";
  58.  
  59. /*****************************************************************************
  60.  * Allocate arrays pointed to by members of the save_line structure and init 
  61.  * the struct members. Arrays are allocated from Fast RAM if possible.
  62.  *****************************************************************************/
  63.  
  64. static alloc_line(RPort, length)
  65. struct RastPort    *RPort;
  66. short            length;                /* Number of pixels in the line.    */
  67. {
  68. ULONG    size;
  69.  
  70. size = length * sizeof(*line.storage);
  71. line.storage = (UBYTE *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);
  72.  
  73. size    = length * sizeof(*line.x);
  74. line.x    = (USHORT *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);
  75. line.y    = (USHORT *)AllocMem(size, MEMF_CLEAR | MEMF_PUBLIC);
  76.  
  77.  
  78. if (line.storage == NULL || line.x == NULL || line.y == NULL)
  79. {
  80.     free_line();
  81.     return(FALSE);
  82. }
  83. line.RPort  = RPort;
  84. line.points = length;    /* This value can't be altered til arrays are freed. */
  85.  
  86. return(TRUE);
  87.  
  88. } /*  End of alloc_line()    */
  89.  
  90.  
  91. /******************************************************************************
  92.  * Release arrays pointed to by members of the line struct.
  93.  ******************************************************************************/
  94.  
  95. static free_line()
  96. {
  97.  
  98. if (line.storage)
  99. {
  100.     FreeMem(line.storage, (long)line.points * sizeof(*line.storage) );
  101.     line.storage = NULL;
  102. }
  103. if (line.x)
  104. {
  105.     FreeMem(line.x, (long)line.points * sizeof(*line.x) );
  106.     line.x = NULL;
  107. }
  108. if (line.y)
  109. {
  110.     FreeMem(line.y, (long)line.points * sizeof(*line.y) );
  111.     line.y = NULL;
  112. }
  113. line.RPort    = NULL;
  114. line.points    = 0;
  115.  
  116. return;
  117.  
  118. } /*  End of free_line()  */
  119.  
  120.  
  121. /******************************************************************************
  122.  * Save image pixel and replace it with a line pixel. This routine does not 
  123.  * waste time checking index to see if it is within the range of the allocated
  124.  * array. The client routine better not fuck up the index calculation.
  125.  ******************************************************************************/
  126.  
  127. static plot(index, x, y)
  128. short        index, x, y;
  129. {
  130. long        result;
  131.  
  132. if (!line.points)                    /* A major error.    */
  133. {
  134.     puts(line_err);
  135.     return(FALSE);
  136. }
  137. result = ReadPixel(line.RPort, (long)x, (long)y );
  138.  
  139. line.storage[index] = result;
  140. line.x[index]        = x;
  141. line.y[index]        = y;
  142.  
  143. WritePixel(line.RPort, (long)x, (long)y );
  144.  
  145. } /*  End of plot()  */
  146.  
  147.  
  148. /******************************************************************************
  149.  * First (and fourth) octant.     Dy < 0       |Dy| < |Dx|
  150.  ******************************************************************************/
  151.  
  152. static octant1(RPort, x, y, deltax, deltay)
  153. struct RastPort    *RPort;
  154. short            x, y, deltax, deltay;
  155. {
  156. register short countdown;    /* Number of pixels still to be drawn.    */
  157. register short err;            /* Running error term.                    */
  158. register short index;        /* Index of current point.                */
  159.  
  160. countdown    = deltax + 1;
  161. err            = -deltax / 2;    /* err starts out being less than zero.    */
  162. index        = 0;
  163.  
  164. if ( !alloc_line(RPort, countdown) )
  165. {
  166.     puts(alloc_err);
  167.     return(FALSE);
  168. }
  169.  
  170. /*----------------------------------------------------------------------*
  171.  * While there are more points to plot... There must be something wrong
  172.  * with an algorythm that requires both assending and decending counters.
  173.  *----------------------------------------------------------------------*/
  174.  
  175. while (countdown--)
  176. {
  177.     plot(index++, x++, y);
  178.     err -= deltay;            /* err gradually becomes positive.    */
  179.     if (err >= 0)
  180.     {
  181.         --y;                /* Moving up screen.                */
  182.         err -= deltax;        /* err goes negative again.            */
  183.     }
  184. }
  185. return(TRUE);
  186.  
  187. } /*  End of octant1()  */
  188.  
  189.  
  190. /*****************************************************************************
  191.  * Second (and third) octant.        |Dy| > |Dx|
  192.  *****************************************************************************/
  193.  
  194. static octant2(RPort, x, y, deltax, deltay)
  195. struct RastPort    *RPort;
  196. short            x, y, deltax, deltay;
  197. {
  198. register short countdown;    /* Number of pixels still to be drawn.    */
  199. register short err;            /* Running error term.                    */
  200. register short index;        /* Index of current point.                */
  201.  
  202. countdown    = -deltay + 1;
  203. err            = deltay / 2;
  204. index        = 0;
  205.  
  206. if ( !alloc_line(RPort, countdown) )
  207. {
  208.     puts(alloc_err);
  209.     return(FALSE);
  210. }
  211. while (countdown--)
  212. {
  213.     plot(index++, x, y--);
  214.     err += deltax;            /* err growing positive.    */
  215.     if (err >= 0)
  216.     {
  217.         ++x;
  218.         err += deltay;        /* err goes negative.        */
  219.     }
  220. }
  221. return(TRUE);
  222.  
  223. } /*  End of octant2()  */
  224.  
  225.  
  226. /******************************************************************************
  227.  * Seventh (and sixth) octant.   Dy > Dx > 0
  228.  ******************************************************************************/
  229.  
  230. static octant7(RPort, x, y, deltax, deltay)
  231. struct RastPort    *RPort;
  232. short            x, y, deltax, deltay;
  233. {
  234. register short countdown;    /* Number of pixels still to be drawn.    */
  235. register short err;            /* Running error term.                    */
  236. register short index;        /* Index of current point.                */
  237.  
  238. countdown    = deltay + 1;
  239. err            = -deltay / 2;
  240. index        = 0;
  241.  
  242. if ( !alloc_line(RPort, countdown) )
  243. {
  244.     puts(alloc_err);
  245.     return(FALSE);
  246. }
  247. while (countdown--)
  248. {
  249.     plot(index++, x, y++);
  250.     err += deltax;            /* err growing positive    */
  251.     if (err >= 0)
  252.     {
  253.         ++x;
  254.         err -= deltay;        /* err goes negative.    */
  255.     }
  256. }
  257. return(TRUE);
  258.  
  259. } /*  End of octant7()  */
  260.  
  261.  
  262. /*****************************************************************************
  263.  * Eighth (and fifth) octant.      Dx > Dy > 0.
  264.  *****************************************************************************/
  265.  
  266. static octant8(RPort, x, y, deltax, deltay)
  267. struct RastPort    *RPort;
  268. short            x, y, deltax, deltay;
  269. {
  270. register short countdown;    /* Number of pixels still to be drawn.    */
  271. register short err;            /* Running error term.                    */
  272. register short index;        /* Index of current point.                */
  273.  
  274. countdown    = deltax + 1;
  275. err            = -deltax / 2;
  276. index        = 0;
  277.  
  278. if ( !alloc_line(RPort, countdown) )
  279. {
  280.     puts(alloc_err);
  281.     return(FALSE);
  282. }
  283. while (countdown--)
  284. {
  285.     plot(index++, x++, y);    /* Moving left to right.    */
  286.     err += deltay;            /* err growing positive.    */
  287.     if (err >= 0)
  288.     {
  289.         ++y;                /* Move down screen next time.    */
  290.         err -= deltax;        /* err goes negative.        */
  291.     }
  292. }
  293. return(TRUE);
  294.  
  295. } /*  End of octant8()  */
  296.  
  297.  
  298. /*****************************************************************************
  299.  *    A quicker vertical line stroker. The end point supplied by client must be
  300.  *  the one with the smallest y value.
  301.  *****************************************************************************/
  302.  
  303. static vert_line(RPort, x, y, len)
  304. struct RastPort    *RPort;
  305. short            x, y, len;
  306. {
  307.  
  308. register short index;        /* Index of current point.                */
  309.  
  310. index = 0;
  311.  
  312. if ( !alloc_line(RPort, len) )
  313. {
  314.     puts(alloc_err);
  315.     return(FALSE);
  316. }
  317. while (index < len)
  318.     plot(index++, x, y++);
  319.  
  320. return(TRUE);
  321.  
  322. } /*  End of vert_line()  */
  323.  
  324.  
  325. /*****************************************************************************
  326.  * Quick horizontal line draw. The end point supplied must be the one with 
  327.  * the smallest x value.
  328.  *****************************************************************************/
  329.  
  330. static horiz_line(RPort, x, y, len)
  331. struct RastPort    *RPort;
  332. USHORT            x, y, len;
  333. {
  334.  
  335. register USHORT index;        /* Index of current point.                */
  336.  
  337. index = 0;
  338.  
  339. if ( !alloc_line(RPort, len) )
  340. {
  341.     puts(alloc_err);
  342.     return(FALSE);
  343. }
  344.  
  345. while (index < len)
  346.     plot(index++, x++, y);
  347.  
  348. return(TRUE);
  349.  
  350. } /*  End of horiz_line()  */
  351.  
  352.  
  353. /*****************************************************************************
  354.  * Quicker diagonal line drawer. For line with a negative slope
  355.  *****************************************************************************/
  356.  
  357. static diagdn_line(RPort, x, y, len)
  358. struct RastPort    *RPort;
  359. short            x, y, len;
  360. {
  361.  
  362. register short index;        /* Index of current point.                */
  363.  
  364. index        = 0;
  365.  
  366. if ( !alloc_line(RPort, len) )
  367. {
  368.     puts(alloc_err);
  369.     return(0);
  370. }
  371.  
  372. while (index < len)
  373.     plot(index++, x++, y++);
  374.  
  375. return(1);
  376.  
  377. } /*  End of diagdn_line()  */
  378.  
  379.  
  380. /*****************************************************************************
  381.  * Quicker diagonal line drawer. For line with a positive slope
  382.  *****************************************************************************/
  383.  
  384. static diagup_line(RPort, x, y, len)
  385. struct RastPort    *RPort;
  386. short            x, y, len;
  387. {
  388.  
  389. register short index;        /* Index of current point.                */
  390.  
  391. index = 0;
  392.  
  393. if ( !alloc_line(RPort, len) )
  394. {
  395.     puts(alloc_err);
  396.     return(FALSE);
  397. }
  398.  
  399. while (index < len)
  400.     plot(index++, x++, y--);
  401.  
  402. return(TRUE);
  403.  
  404. } /*  End of diagup_line()  */
  405.  
  406.  
  407. /******************************************************************************
  408.  * This function is the normal entry point for line drawing. It determins 
  409.  * which octant the line is in and calls the appropriate line drawing routine.
  410.  * the screen's coordinate system is used. Thus, Y values increase as you move
  411.  * down the screen. Lines are always drawn from left to right, swapping end
  412.  * points if necessary.
  413.  *
  414.  *    RPort        Pointer to the RastPort of the window being drawn in.
  415.  *  (x1, y1)    First end point.
  416.  *  (x2, y2)    Other end point.
  417.  *
  418.  ******************************************************************************/
  419.  
  420. draw_line(RPort, color, x1, y1, x2, y2)
  421. struct RastPort    *RPort;
  422. USHORT            color;
  423. USHORT            x1, y1, x2, y2;
  424. {
  425.  
  426. short            deltax, deltay;
  427. short            rc;
  428. short            temp;
  429. BYTE            save_color;
  430.  
  431. if (x1 > x2)
  432. {
  433.     temp = x1;    x1 = x2;  x2 = temp;
  434.     temp = y1;    y1 = y2;  y2 = temp;
  435. }
  436. deltax = x2 - x1;
  437. deltay = y2 - y1;
  438.  
  439. save_color = RPort->FgPen;            /* Save pen color for later restoration. */
  440. SetAPen(RPort, (long)color);
  441.  
  442. /* Trap hoizontal and vertical lines for special treatment.    */
  443.  
  444. if (!deltay)
  445. {
  446.     rc = horiz_line(RPort, x1, y1, deltax + 1);
  447. }
  448. else if (!deltax)
  449. {
  450.     if (deltay > 0)
  451.         rc = vert_line(RPort, x1, y1, deltay + 1);
  452.     else
  453.         rc = vert_line(RPort, x2, y2, 1 - deltay);
  454. }
  455. else if (deltay > 0)                                /* Fourth Quadrant    */
  456. {
  457.     if (deltax == deltay)
  458.         rc = diagdn_line(RPort, x1, y1, deltax + 1);
  459.     else if (deltay > deltax)
  460.         rc = octant7(RPort, x1, y1, deltax, deltay);
  461.     else
  462.         rc = octant8(RPort, x1, y1, deltax, deltay);
  463. }
  464. else                                                /* First Quadrant    */
  465. {
  466.     if ( !(deltax + deltay) )
  467.         rc = diagup_line(RPort, x1, y1, deltax + 1);
  468.     else if (-deltay > deltax)
  469.         rc = octant2(RPort, x1, y1, deltax, deltay);
  470.     else
  471.         rc = octant1(RPort, x1, y1, deltax, deltay);
  472. }
  473.  
  474. SetAPen(RPort, (long)save_color);    /* Restore original pen color. */
  475.  
  476. return(rc);
  477.  
  478. } /*  End of draw_line()  */
  479.  
  480.  
  481. /******************************************************************************
  482.  * Restore image pixels that have been overdrawn by the line. This is the 
  483.  * entry point for line erasure. This routine can not mess with the value of 
  484.  * line.points because it will be needed to release the arrays. Note that if
  485.  * line.points is initially zero, this routine is a nop.
  486.  ******************************************************************************/
  487.  
  488. restore_line()
  489. {
  490. register short    index;
  491. BYTE            save_color;
  492.  
  493. if (!line.points)
  494. {
  495.     puts(rest_err);
  496.     return(FALSE);
  497. }
  498.  
  499. save_color = line.RPort->FgPen;
  500.  
  501. index = line.points;        /* Index of last point + 1.    */
  502.  
  503. while (index--)
  504. {
  505.     SetAPen(line.RPort, (ULONG)line.storage[index] );
  506.  
  507.     /* if (!line.x[index]) puts("Restored point with zero X value."); */
  508.  
  509.     WritePixel(line.RPort, (ULONG)line.x[index], (ULONG)line.y[index] );
  510. }
  511. SetAPen(line.RPort, (ULONG)save_color);
  512. free_line();
  513.  
  514. } /*  End of restore_line()  */
  515.