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