2d/line.c

   1 /*
   2 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   3 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   4 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   5 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   6 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   7 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   8 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
   9 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  11 COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12 */
  13 /*
  14  * Graphical routines for drawing lines.
  15  *
  16  */
  17
  18 #include <conf.h>
  19 #include <stdlib.h>
  20
  21 #include "u_mem.h"
  22
  23 #include "gr.h"
  24 #include "grdef.h"
  25 #include "fix.h"
  26
  27 #include "clip.h"
  28
  29 #ifdef __MSDOS__
  30 #include "modex.h"
  31 #endif
  32 #ifdef OGL
  33 #include "ogl_init.h"
  34 #endif
  35
  36
  37 /*
  38 Symmetric Double Step Line Algorithm
  39 by Brian Wyvill
  40 from "Graphics Gems", Academic Press, 1990
  41 */
  42
  43 /* non-zero flag indicates the pixels needing EXCHG back. */
  44 void plot(int x,int y,int flag)
  45 {   if (flag)
  46                 gr_upixel(y, x);
  47         else
  48                 gr_upixel(x, y);
  49 }
  50
  51 int gr_hline(int x1, int x2, int y)
  52 {   int i;
  53
  54         if (x1 > x2) EXCHG(x1,x2);
  55         for (i=x1; i<=x2; i++ )
  56                 gr_upixel( i, y );
  57         return 0;
  58 }
  59
  60 int gr_vline(int y1, int y2, int x)
  61 {   int i;
  62         if (y1 > y2) EXCHG(y1,y2);
  63         for (i=y1; i<=y2; i++ )
  64                 gr_upixel( x, i );
  65         return 0;
  66 }
  67
  68 void gr_universal_uline(int a1, int b1, int a2, int b2)
  69 {
  70         int dx, dy, incr1, incr2, D, x, y, xend, c, pixels_left;
  71         int x1, y1;
  72         int sign_x = 1, sign_y = 1, step, reverse, i;
  73
  74         if (a1==a2) {
  75                 gr_vline(b1,b2,a1);
  76                 return;
  77         }
  78
  79         if (b1==b2) {
  80                 gr_hline(a1,a2,b1);
  81                 return;
  82         }
  83
  84         dx = a2 - a1;
  85         dy = b2 - b1;
  86
  87         if (dx < 0) {
  88                 sign_x = -1;
  89                 dx *= -1;
  90         }
  91         if (dy < 0) {
  92                 sign_y = -1;
  93                 dy *= -1;
  94         }
  95
  96         /* decide increment sign by the slope sign */
  97         if (sign_x == sign_y)
  98                 step = 1;
  99         else
 100                 step = -1;
 101
 102         if (dy > dx) {          /* chooses axis of greatest movement (make * dx) */
 103                 EXCHG(a1, b1);
 104                 EXCHG(a2, b2);
 105                 EXCHG(dx, dy);
 106                 reverse = 1;
 107         } else
 108                 reverse = 0;
 109         /* note error check for dx==0 should be included here */
 110         if (a1 > a2) {          /* start from the smaller coordinate */
 111                 x = a2;
 112                 y = b2;
 113                 x1 = a1;
 114                 y1 = b1;
 115         } else {
 116                 x = a1;
 117                 y = b1;
 118                 x1 = a2;
 119                 y1 = b2;
 120         }
 121
 122
 123         /* Note dx=n implies 0 - n or (dx+1) pixels to be set */
 124         /* Go round loop dx/4 times then plot last 0,1,2 or 3 pixels */
 125         /* In fact (dx-1)/4 as 2 pixels are already plottted */
 126         xend = (dx - 1) / 4;
 127         pixels_left = (dx - 1) % 4;     /* number of pixels left over at the
 128                                                                  * end */
 129         plot(x, y, reverse);
 130         plot(x1, y1, reverse);  /* plot first two points */
 131         incr2 = 4 * dy - 2 * dx;
 132         if (incr2 < 0) {        /* slope less than 1/2 */
 133                 c = 2 * dy;
 134                 incr1 = 2 * c;
 135                 D = incr1 - dx;
 136
 137                 for (i = 0; i < xend; i++) {    /* plotting loop */
 138                         ++x;
 139                         --x1;
 140                         if (D < 0) {
 141                                         /* pattern 1 forwards */
 142                                 plot(x, y, reverse);
 143                                 plot(++x, y, reverse);
 144                                 /* pattern 1 backwards */
 145                                 plot(x1, y1, reverse);
 146                                 plot(--x1, y1, reverse);
 147                                 D += incr1;
 148                         } else {
 149                                 if (D < c) {
 150                                         /* pattern 2 forwards */
 151                                         plot(x, y, reverse);
 152                                         plot(++x, y += step, reverse);
 153                                         /* pattern 2 backwards */
 154                                         plot(x1, y1, reverse);
 155                                         plot(--x1, y1 -= step, reverse);
 156                                 } else {
 157                                         /* pattern 3 forwards */
 158                                         plot(x, y += step, reverse);
 159                                         plot(++x, y, reverse);
 160                                         /* pattern 3 backwards */
 161                                         plot(x1, y1 -= step, reverse);
 162                                         plot(--x1, y1, reverse);
 163                                 }
 164                                 D += incr2;
 165                         }
 166                 }               /* end for */
 167
 168                 /* plot last pattern */
 169                 if (pixels_left) {
 170                         if (D < 0) {
 171                                 plot(++x, y, reverse);  /* pattern 1 */
 172                                 if (pixels_left > 1)
 173                                         plot(++x, y, reverse);
 174                                 if (pixels_left > 2)
 175                                         plot(--x1, y1, reverse);
 176                         } else {
 177                                 if (D < c) {
 178                                         plot(++x, y, reverse);  /* pattern 2  */
 179                                         if (pixels_left > 1)
 180                                                 plot(++x, y += step, reverse);
 181                                         if (pixels_left > 2)
 182                                                 plot(--x1, y1, reverse);
 183                                 } else {
 184                                   /* pattern 3 */
 185                                         plot(++x, y += step, reverse);
 186                                         if (pixels_left > 1)
 187                                                 plot(++x, y, reverse);
 188                                         if (pixels_left > 2)
 189                                                 plot(--x1, y1 -= step, reverse);
 190                                 }
 191                         }
 192                 }               /* end if pixels_left */
 193         }
 194         /* end slope < 1/2 */
 195         else {                  /* slope greater than 1/2 */
 196                 c = 2 * (dy - dx);
 197                 incr1 = 2 * c;
 198                 D = incr1 + dx;
 199                 for (i = 0; i < xend; i++) {
 200                         ++x;
 201                         --x1;
 202                         if (D > 0) {
 203                           /* pattern 4 forwards */
 204                                 plot(x, y += step, reverse);
 205                                 plot(++x, y += step, reverse);
 206                           /* pattern 4 backwards */
 207                                 plot(x1, y1 -= step, reverse);
 208                                 plot(--x1, y1 -= step, reverse);
 209                                 D += incr1;
 210                         } else {
 211                                 if (D < c) {
 212                                   /* pattern 2 forwards */
 213                                         plot(x, y, reverse);
 214                                         plot(++x, y += step, reverse);
 215
 216                                   /* pattern 2 backwards */
 217                                         plot(x1, y1, reverse);
 218                                         plot(--x1, y1 -= step, reverse);
 219                                 } else {
 220                                   /* pattern 3 forwards */
 221                                         plot(x, y += step, reverse);
 222                                         plot(++x, y, reverse);
 223                                   /* pattern 3 backwards */
 224                                         plot(x1, y1 -= step, reverse);
 225                                         plot(--x1, y1, reverse);
 226                                 }
 227                                 D += incr2;
 228                         }
 229                 }               /* end for */
 230                 /* plot last pattern */
 231                 if (pixels_left) {
 232                         if (D > 0) {
 233                                 plot(++x, y += step, reverse);  /* pattern 4 */
 234                                 if (pixels_left > 1)
 235                                         plot(++x, y += step, reverse);
 236                                 if (pixels_left > 2)
 237                                         plot(--x1, y1 -= step, reverse);
 238                         } else {
 239                                 if (D < c) {
 240                                         plot(++x, y, reverse);  /* pattern 2  */
 241                                         if (pixels_left > 1)
 242                                                 plot(++x, y += step, reverse);
 243                                         if (pixels_left > 2)
 244                                                 plot(--x1, y1, reverse);
 245                                 } else {
 246                                   /* pattern 3 */
 247                                         plot(++x, y += step, reverse);
 248                                         if (pixels_left > 1)
 249                                                 plot(++x, y, reverse);
 250                                         if (pixels_left > 2) {
 251                                                 if (D > c) /* step 3 */
 252                                                    plot(--x1, y1 -= step, reverse);
 253                                                 else /* step 2 */
 254                                                         plot(--x1, y1, reverse);
 255                                         }
 256                                 }
 257                         }
 258                 }
 259         }
 260 }
 261
 262
 263 //unclipped version just calls clipping version for now
 264 int gr_uline(fix _a1, fix _b1, fix _a2, fix _b2)
 265 {
 266         int a1,b1,a2,b2;
 267         a1 = f2i(_a1); b1 = f2i(_b1); a2 = f2i(_a2); b2 = f2i(_b2);
 268         switch(TYPE)
 269         {
 270 #ifdef OGL
 271                 case BM_OGL:
 272                         ogl_ulinec(a1,b1,a2,b2,COLOR);
 273                         return 0;
 274 #endif
 275         case BM_LINEAR:
 276                #ifdef NO_ASM
 277                 gr_universal_uline( a1,b1,a2,b2);
 278                #else
 279                 gr_linear_line( a1, b1, a2, b2 );
 280                #endif
 281                 return 0;
 282 #ifdef __MSDOS__
 283         case BM_MODEX:
 284                 modex_line_x1 = a1+XOFFSET;
 285                 modex_line_y1 = b1+YOFFSET;
 286                 modex_line_x2 = a2+XOFFSET;
 287                 modex_line_y2 = b2+YOFFSET;
 288                 modex_line_Color = grd_curcanv->cv_color;
 289                 gr_modex_line();
 290                 return 0;
 291         default:
 292                 gr_universal_uline( a1, b1, a2, b2 );
 293                 return 0;
 294 #endif
 295         }
 296         return 2;
 297 }
 298
 299 // Returns 0 if drawn with no clipping, 1 if drawn but clipped, and
 300 // 2 if not drawn at all.
 301
 302 int gr_line(fix a1, fix b1, fix a2, fix b2)
 303 {
 304         int x1, y1, x2, y2;
 305         int clipped=0;
 306
 307         x1 = i2f(MINX);
 308         y1 = i2f(MINY);
 309         x2 = i2f(MAXX);
 310         y2 = i2f(MAXY);
 311
 312         CLIPLINE(a1,b1,a2,b2,x1,y1,x2,y2,return 2,clipped=1, FSCALE );
 313
 314         gr_uline( a1, b1, a2, b2 );
 315
 316         return clipped;
 317
 318 }
 319
 320