2d/line.c

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