libctsupport/clip.cpp

   1 /*****************************************************************************
   2 ** FILE IDENTIFICATION
   3 **
   4 **   Name:         clip.c
   5 **   Purpose:      Line clipping routines
   6 **   Programmer:   Kevin Rosenberg
   7 **   Date Started: 1984
   8 **
   9 ** OVERVIEW
  10 **      Routines to clip lines against objects
  11 **      All routines get the endpoints of the line, and
  12 **      the SNARK size of the object (u,v)
  13 **
  14 **  This is part of the CTSim program
  15 **  Copyright (c) 1983-2009 Kevin Rosenberg
  16 **
  17 **  This program is free software; you can redistribute it and/or modify
  18 **  it under the terms of the GNU General Public License (version 2) as
  19 **  published by the Free Software Foundation.
  20 **
  21 **  This program is distributed in the hope that it will be useful,
  22 **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23 **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24 **  GNU General Public License for more details.
  25 **
  26 **  You should have received a copy of the GNU General Public License
  27 **  along with this program; if not, write to the Free Software
  28 **  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  29 ******************************************************************************/
  30
  31 #include "ctsupport.h"
  32
  33
  34 /* NAME
  35  *    clip_segment              Clip against a segment of a circle
  36  *
  37  * SYNOPSIS
  38  *    clip_segment (x1, y1, x2, y2, u, v)
  39  *    double& x1,*y1,*x2,*y2    Endpoints of line
  40  *    double u,v                Dimensions of segment
  41  */
  42
  43 bool
  44 clip_segment (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
  45 {
  46   double xc1 = x1 * u;
  47   double yc1 = y1 * v;
  48   double xc2 = x2 * u;
  49   double yc2 = y2 * v;
  50
  51   if (yc1 > 0. && yc2 > 0.)     // reject lines above y-axis
  52     return false;
  53
  54   double radius = sqrt (u * u + v * v);
  55
  56   if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
  57     return false;
  58
  59   if (yc1 > 0. && yc2 > 0.)     // trivial reject above y-axis
  60     return false;
  61
  62   // clip above x-axis
  63   if (yc1 > 0.) {
  64     xc1 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
  65     yc1 = 0.0;
  66   } else if (yc2 > 0.) {
  67     xc2 = xc1 + (xc2-xc1)*(0.0-yc1)/(yc2-yc1);
  68     yc2 = 0.0;
  69   }
  70
  71   x1 = xc1 / u;
  72   y1 = yc1 / v;
  73   x2 = xc2 / u;
  74   y2 = yc2 / v;
  75
  76   return true;
  77 }
  78
  79
  80 /* NAME
  81  *    clip_sector               Clip a line against a sector of a circle
  82  *
  83  * SYNOPSIS
  84  *    clip_sector (x1, y1, x2, y2, u, v)
  85  *    double& x1,*y1,*x2,*y2    Endpoints of line
  86  *    double u,v                Size of sector
  87  */
  88
  89 bool
  90 clip_sector (double& x1, double& y1, double& x2, double& y2, const double u, const double v)
  91 {
  92   double xc1 = x1 * u;
  93   double yc1 = y1 * v;
  94   double xc2 = x2 * u;
  95   double yc2 = y2 * v;
  96
  97   double radius = sqrt (u * u + v * v);
  98
  99   if (clip_circle (xc1, yc1, xc2, yc2, 0.0, v, radius, 0.0, 0.0) == false)
 100     return false;
 101
 102   if (clip_triangle (xc1, yc1, xc2, yc2, u, v, false) == false)
 103     return false;
 104
 105   x1 = xc1 / u;
 106   y1 = yc1 / v;
 107   x2 = xc2 / u;
 108   y2 = yc2 / v;
 109
 110   return true;
 111 }
 112
 113
 114 /* NAME
 115  *    clip_circle               Clip a line against a circle
 116  *
 117  * SYNOPSIS
 118  *    clip_circle (x1,y1,x2,y2,cx,cy,radius,t1,t2)
 119  *    double& x1,*y1,*x2,*y2    Endpoints of line to be clipped
 120  *    double cx,cy              Center of circle
 121  *    double radius             Radius of circle
 122  *    double t1,t2              Starting & stopping angles of clipping
 123  */
 124
 125 bool
 126 clip_circle (double& x1, double& y1, double& x2, double& y2, const double cx, const double cy, const double radius, double t1, double t2)
 127 {
 128   double xc1 = x1;
 129   double yc1 = y1;
 130   double xc2 = x2;
 131   double yc2 = y2;
 132   double ccx = cx;
 133   double ccy = cy;
 134
 135   double xtrans = -xc1;                 // move (x1,y1) to origin
 136   double ytrans = -yc1;
 137
 138   xc1 += xtrans;
 139   yc1 += ytrans;
 140   xc2 += xtrans;
 141   yc2 += ytrans;
 142   ccx += xtrans;
 143   ccy += ytrans;
 144
 145   double theta = -atan2 (yc2, xc2);     // rotate line to lie on x-axis
 146   GRFMTX_2D rotmtx;
 147   rot_mtx2 (rotmtx, theta);     // xc1,yc1 is at origin, no need to rot
 148   xform_mtx2 (rotmtx, xc2, yc2);
 149   xform_mtx2 (rotmtx, ccx, ccy);
 150   t1 += theta;                  // rotate start and stop angles
 151   t2 += theta;
 152   t1 = normalizeAngle (t1);
 153   t2 = normalizeAngle (t2);
 154
 155   if (xc2 < -D_EPSILON || fabs(yc2) > F_EPSILON) {
 156     sys_error (ERR_SEVERE, "Internal error in clip_circle\n x1=%6.2f, y1=%6.2f, x2=%6.2f, y2=%6.2f, xc2=%6.2f, yc2=%6.2f, theta=%6.2f", x1, y1, x2, y2, xc2, yc2, theta);
 157     return false;
 158   }
 159
 160   if (fabs(ccy) > radius)               /* check if can reject */
 161     return false;
 162
 163   double temp = sqrt (radius * radius - ccy * ccy);
 164   double xcmin = ccx - temp;
 165   double xcmax = ccx + temp;
 166
 167   if (fabs(t2 - t1) < D_EPSILON) {
 168     if (xc1 < xcmin)
 169       xc1 = xcmin;
 170     if (xc2 > xcmax)
 171       xc2 = xcmax;
 172   } else if (t1 < t2) {
 173     if (t1 < PI && t2 > PI)
 174       if (xc1 < xcmin)
 175         xc1 = xcmin;
 176   } else if (t1 > t2) {
 177     if (t1 < PI)
 178       if (xc1 < xcmin)
 179         xc1 = xcmin;
 180     if (xc2 > xcmax)
 181       xc2 = xcmax;
 182   }
 183
 184   rot_mtx2 (rotmtx, -theta);
 185   xform_mtx2 (rotmtx, xc1, yc1);
 186   xform_mtx2 (rotmtx, xc2, yc2);
 187   xc1 += -xtrans;
 188   yc1 += -ytrans;
 189   xc2 += -xtrans;
 190   yc2 += -ytrans;
 191
 192   x1 = xc1;
 193   y1 = yc1;
 194   x2 = xc2;
 195   y2 = yc2;
 196
 197   return true;
 198 }
 199
 200
 201 /* NAME
 202  *    clip_triangle             Clip a line against a triangle
 203  *
 204  * SYNOPSIS
 205  *    clip_triangle (x1, y1, x2, y2, u, v, clip_xaxis)
 206  *    double& x1, *y1, *x2, *y2 Endpoints of line
 207  *    double u, v               Size of 1/2 base len & height
 208  *    int clip_xaxis            Boolean flag whether to clip against x axis
 209  *                              (Use true for all triangles)
 210  *                              (false if used internally by sector clipping routine)
 211  *
 212  * DESCRIPTION
 213  *              x
 214  *             /|\              Note that vertices of triangle are
 215  *            / | \                 (-u, 0)
 216  *           /  |  \                (u, 0)
 217  *          /   |   \               (0, v)
 218  *         /    | v  \
 219  *        /     |     \
 220  *       +------+------+
 221  *            (0,0)  u
 222  *
 223  * NOTES
 224  *   1) Inside of this routine, values of (u,v) are assumed to be (1,1)
 225  *
 226  *   2) Derivation of clipping equations:
 227  *      Using parametric equations for the line
 228  *          xv = x1 + t * (x2 - x1)
 229  *          yv = y1 + t * (y2 - y1)
 230  *      so,
 231  *          t  = (xv - x1) / (x2 - x1)
 232  *          yv = y1 + (xv - x1) * (y2 - y1) / (x2 - x1)
 233  *          yv = y1 + (xv - x1) * dy / dx
 234  *
 235  *      Now, find the intersections with the following clipping boundries:
 236  *          yv = v - (v/u) * xv         (yv = mx + b)
 237  *          yv = v + (v/u) * xv         (m = v/u, b = v);
 238  */
 239
 240 static int tcode (const double x, const double y, const double m, const double b, const int clip_xaxis);
 241
 242 bool
 243 clip_triangle (double& x1, double& y1, double& x2, double& y2, const double u, const double v, const int clip_xaxis)
 244 {
 245   double m = v / u;      // slope of triangle lines
 246   double b = v;          // y-intercept of triangle lines
 247
 248   int c1 = tcode (x1, y1, m, b, clip_xaxis);
 249   int c2 = tcode (x2, y2, m, b, clip_xaxis);
 250
 251 #if 0
 252   printf ("x1:%6.2f  y1:%6.2f  code1:%2d  x2:%6.2f  y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
 253 #endif
 254   while ( c1 || c2 ) {
 255     if ( c1 & c2 ) {
 256       return false;                     // trivial reject
 257     }
 258     int c = c1;
 259     if (c1 == 0)
 260       c = c2;
 261
 262     double x = 0, y = 0;
 263     if (c & 1) {                        // below
 264       x = x1 + (x2-x1)*(0.0-y1)/(y2-y1);
 265       y = 0.0;
 266     } else if (c & 2) {                 // right
 267       double dx, dy;
 268       dx = x2 - x1;
 269       dy = y2 - y1;
 270       if (fabs(dx) > D_EPSILON)
 271         x = (-y1 + b + x1 * dy/dx) / (m + dy/dx);
 272       else
 273         x = x1;
 274       y = -m * x + b;
 275     } else if (c & 4) {                 /* left */
 276       double dx, dy;
 277       dx = x2 - x1;
 278       dy = y2 - y1;
 279       if (fabs(dx) > D_EPSILON) {
 280         x = (y1 - b - x1 * dy/dx);
 281         x /= (m - dy/dx);
 282       } else
 283         x = x1;
 284       y = m * x + b;
 285     }
 286
 287     if (c == c1) {
 288       x1=x; y1=y; c1=tcode (x1,y1,m,b,clip_xaxis);
 289     } else {
 290       x2=x; y2=y; c2=tcode (x2,y2,m,b,clip_xaxis);
 291     }
 292 #if 0
 293     printf ("x1:%6.2f  y1:%6.2f  code1:%2d  x2:%6.2f  y2:%6.2f code2:%2d\n", x1, y1, c1, x2, y2, c2);
 294 #endif
 295   }
 296
 297   return true;          /* we have clipped the line, and it is good */
 298 }
 299
 300
 301 /* compute region code */
 302 static int
 303 tcode (const double x, const double y, const double m, const double b, const int clip_xaxis)
 304 {
 305   int c = 0;
 306
 307   if (clip_xaxis && y < 0.)     // below triange
 308     c = 1;
 309
 310   if (y > -m * x + b + D_EPSILON)               // right of triangle
 311     c += 2;
 312   if (y > m * x + b + D_EPSILON)                // left of triangle
 313     c += 4;
 314
 315   return (c);
 316 }
 317
 318
 319 /* NAME
 320  *    clip_rect                 Clip a line against a rectangle
 321  *
 322  * SYNOPSIS
 323  *    clip_rect (x1, y1, x2, y2, rect)
 324  *    double& x1, *y1, *x2, *y2 Endpoints of line
 325  *    double rect[4]            Rectangle to clip against
 326  *                              ordered xmin, ymin, xmax, ymax
 327  */
 328
 329 static int rectcode (double x, double y, const double rect[4]);
 330
 331 bool
 332 clip_rect (double& x1, double& y1, double& x2, double& y2, const double rect[4])
 333 {
 334   double x = 0, y = 0;
 335
 336   int c1 = rectcode (x1, y1, rect);
 337   int c2 = rectcode (x2, y2, rect);
 338
 339   while (c1 || c2) {
 340     if (c1 & c2)
 341       return false;                     // trivial reject
 342     int c = c1;
 343     if (c1 == 0)
 344       c = c2;
 345     if (c & 1) {                        // left
 346       y = y1 + (y2-y1)*(rect[0]-x1)/(x2-x1);
 347       x = rect[0];
 348     } else if (c & 2) {                 // right
 349       y = y1 + (y2-y1)*(rect[2]-x1)/(x2-x1);
 350       x = rect[2];
 351     } else if (c & 4) {                 // bottom
 352       x = x1 + (x2-x1)*(rect[1]-y1)/(y2-y1);
 353       y = rect[1];
 354     } else if (c & 8) {                 // top
 355       x = x1 + (x2-x1)*(rect[3]-y1)/(y2-y1);
 356       y = rect[3];
 357     }
 358
 359     if (c == c1) {
 360       x1=x; y1=y; c1=rectcode(x1,y1,rect);
 361     } else {
 362       x2=x; y2=y; c2=rectcode(x2,y2,rect);
 363     }
 364   }
 365   return true;          // we have clipped the line, and it is good
 366 }
 367
 368
 369 /* NAME
 370  *   rectcode                   INTERNAL routine to return position of
 371  *                              point relative to a rectangle
 372  *
 373  * SYNOPSIS
 374  *    c = rectcode (x, y, rect)
 375  *    int c                     Position of point relative to the window
 376  *    double x, y               Point to test against window
 377  *    double rect[4]            Coordinates of rectangle extent
 378  *                              Ordered [xmin, ymin, xmax, ymax]
 379  */
 380
 381 static int
 382 rectcode (double x, double y, const double rect[4])
 383 {
 384   int c = 0;
 385
 386   if (x < rect[0])
 387     c = 1;
 388   else if (x > rect[2])
 389     c = 2;
 390   if (y < rect[1])
 391     c += 4;
 392   else if (y > rect[3])
 393     c += 8;
 394   return (c);
 395 }