src/line.c

   1 /*
   2  *                            COPYRIGHT
   3  *
   4  *  PCB, interactive printed circuit board design
   5  *  Copyright (C) 1994,1995,1996 Thomas Nau
   6  *  Copyright (C) 2004 harry eaton
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21  *
  22  *  Contact addresses for paper mail and Email:
  23  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  24  *  Thomas.Nau@rz.uni-ulm.de
  25  *
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif
  31
  32 #include <math.h>
  33 #include <setjmp.h>
  34 #include <stdlib.h>
  35
  36
  37 #include "global.h"
  38 #include "data.h"
  39 #include "crosshair.h"
  40 #include "find.h"
  41 #include "line.h"
  42 #include "misc.h"
  43 #include "rtree.h"
  44
  45 #ifdef HAVE_LIBDMALLOC
  46 #include <dmalloc.h>
  47 #endif
  48
  49 static double drc_lines (PointType *end, bool way);
  50
  51 /* ---------------------------------------------------------------------------
  52  * Adjust the attached line to 45 degrees if necessary
  53  */
  54 void
  55 AdjustAttachedLine (void)
  56 {
  57   AttachedLineType *line = &Crosshair.AttachedLine;
  58
  59   /* I need at least one point */
  60   if (line->State == STATE_FIRST)
  61     return;
  62   /* don't draw outline when ctrl key is pressed */
  63   if (Settings.Mode == LINE_MODE && gui->control_is_pressed ())
  64     {
  65       line->draw = false;
  66       return;
  67     }
  68   else
  69     line->draw = true;
  70   /* no 45 degree lines required */
  71   if (PCB->RatDraw || TEST_FLAG (ALLDIRECTIONFLAG, PCB))
  72     {
  73       line->Point2.X = Crosshair.X;
  74       line->Point2.Y = Crosshair.Y;
  75       return;
  76     }
  77   FortyFiveLine (line);
  78 }
  79
  80 /* ---------------------------------------------------------------------------
  81  * makes the attached line fit into a 45 degree direction
  82  *
  83  * directions:
  84  *
  85  *           4
  86  *          5 3
  87  *         6   2
  88  *          7 1
  89  *           0
  90  */
  91 void
  92 FortyFiveLine (AttachedLineType *Line)
  93 {
  94   Coord dx, dy, min, max;
  95   unsigned direction = 0;
  96   double m;
  97
  98   /* first calculate direction of line */
  99   dx = Crosshair.X - Line->Point1.X;
 100   dy = Crosshair.Y - Line->Point1.Y;
 101
 102   /* zero length line, don't draw anything */
 103   if (dx == 0 && dy == 0)
 104     return;
 105
 106   if (dx == 0)
 107     direction = dy > 0 ? 0 : 4;
 108   else
 109     {
 110       m = (double)dy / (double)dx;
 111       direction = 2;
 112       if (m > TAN_30_DEGREE)
 113         direction = m > TAN_60_DEGREE ? 0 : 1;
 114       else if (m < -TAN_30_DEGREE)
 115         direction = m < -TAN_60_DEGREE ? 4 : 3;
 116     }
 117   if (dx < 0)
 118     direction += 4;
 119
 120   dx = abs (dx);
 121   dy = abs (dy);
 122   min = MIN (dx, dy);
 123   max = MAX (dx, dy);
 124
 125   /* now set up the second pair of coordinates */
 126   switch (direction)
 127     {
 128     case 0:
 129       Line->Point2.X = Line->Point1.X;
 130       Line->Point2.Y = Line->Point1.Y + max;
 131       break;
 132
 133     case 4:
 134       Line->Point2.X = Line->Point1.X;
 135       Line->Point2.Y = Line->Point1.Y - max;
 136       break;
 137
 138     case 2:
 139       Line->Point2.X = Line->Point1.X + max;
 140       Line->Point2.Y = Line->Point1.Y;
 141       break;
 142
 143     case 6:
 144       Line->Point2.X = Line->Point1.X - max;
 145       Line->Point2.Y = Line->Point1.Y;
 146       break;
 147
 148     case 1:
 149       Line->Point2.X = Line->Point1.X + min;
 150       Line->Point2.Y = Line->Point1.Y + min;
 151       break;
 152
 153     case 3:
 154       Line->Point2.X = Line->Point1.X + min;
 155       Line->Point2.Y = Line->Point1.Y - min;
 156       break;
 157
 158     case 5:
 159       Line->Point2.X = Line->Point1.X - min;
 160       Line->Point2.Y = Line->Point1.Y - min;
 161       break;
 162
 163     case 7:
 164       Line->Point2.X = Line->Point1.X - min;
 165       Line->Point2.Y = Line->Point1.Y + min;
 166       break;
 167     }
 168 }
 169
 170 /* ---------------------------------------------------------------------------
 171  *  adjusts the insert lines to make them 45 degrees as necessary
 172  */
 173 void
 174 AdjustTwoLine (bool way)
 175 {
 176   Coord dx, dy;
 177   AttachedLineType *line = &Crosshair.AttachedLine;
 178
 179   if (Crosshair.AttachedLine.State == STATE_FIRST)
 180     return;
 181   /* don't draw outline when ctrl key is pressed */
 182   if (gui->control_is_pressed ())
 183     {
 184       line->draw = false;
 185       return;
 186     }
 187   else
 188     line->draw = true;
 189   if (TEST_FLAG (ALLDIRECTIONFLAG, PCB))
 190     {
 191       line->Point2.X = Crosshair.X;
 192       line->Point2.Y = Crosshair.Y;
 193       return;
 194     }
 195   /* swap the modes if shift is held down */
 196   if (gui->shift_is_pressed ())
 197     way = !way;
 198   dx = Crosshair.X - line->Point1.X;
 199   dy = Crosshair.Y - line->Point1.Y;
 200   if (!way)
 201     {
 202       if (abs (dx) > abs (dy))
 203         {
 204           line->Point2.X = Crosshair.X - SGN (dx) * abs (dy);
 205           line->Point2.Y = line->Point1.Y;
 206         }
 207       else
 208         {
 209           line->Point2.X = line->Point1.X;
 210           line->Point2.Y = Crosshair.Y - SGN (dy) * abs (dx);
 211         }
 212     }
 213   else
 214     {
 215       if (abs (dx) > abs (dy))
 216         {
 217           line->Point2.X = line->Point1.X + SGN (dx) * abs (dy);
 218           line->Point2.Y = Crosshair.Y;
 219         }
 220       else
 221         {
 222           line->Point2.X = Crosshair.X;
 223           line->Point2.Y = line->Point1.Y + SGN (dy) * abs (dx);;
 224         }
 225     }
 226 }
 227
 228 struct drc_info
 229 {
 230   LineType *line;
 231   bool bottom_side;
 232   bool top_side;
 233   jmp_buf env;
 234 };
 235
 236 static int
 237 drcVia_callback (const BoxType * b, void *cl)
 238 {
 239   PinType *via = (PinType *) b;
 240   struct drc_info *i = (struct drc_info *) cl;
 241
 242   if (!TEST_FLAG (FOUNDFLAG, via) && PinLineIntersect (via, i->line))
 243     longjmp (i->env, 1);
 244   return 1;
 245 }
 246
 247 static int
 248 drcPad_callback (const BoxType * b, void *cl)
 249 {
 250   PadType *pad = (PadType *) b;
 251   struct drc_info *i = (struct drc_info *) cl;
 252
 253   if (TEST_FLAG (ONSOLDERFLAG, pad) == i->bottom_side &&
 254       !TEST_FLAG (FOUNDFLAG, pad) && LinePadIntersect (i->line, pad))
 255     longjmp (i->env, 1);
 256   return 1;
 257 }
 258
 259 static int
 260 drcLine_callback (const BoxType * b, void *cl)
 261 {
 262   LineType *line = (LineType *) b;
 263   struct drc_info *i = (struct drc_info *) cl;
 264
 265   if (!TEST_FLAG (FOUNDFLAG, line) && LineLineIntersect (line, i->line))
 266     longjmp (i->env, 1);
 267   return 1;
 268 }
 269
 270 static int
 271 drcArc_callback (const BoxType * b, void *cl)
 272 {
 273   ArcType *arc = (ArcType *) b;
 274   struct drc_info *i = (struct drc_info *) cl;
 275
 276   if (!TEST_FLAG (FOUNDFLAG, arc) && LineArcIntersect (i->line, arc))
 277     longjmp (i->env, 1);
 278   return 1;
 279 }
 280
 281 /* drc_lines() checks for intersectors against two lines and
 282  * adjusts the end point until there is no intersection or
 283  * it winds up back at the start. If way is false it checks
 284  * straight start, 45 end lines, otherwise it checks 45 start,
 285  * straight end.
 286  *
 287  * It returns the straight-line length of the best answer, and
 288  * changes the position of the input point to the best answer.
 289  */
 290
 291 static double
 292 drc_lines (PointType *end, bool way)
 293 {
 294   double f, s, f2, s2, len, best;
 295   Coord dx, dy, temp, last, length;
 296   Coord temp2, last2, length2;
 297   LineType line1, line2;
 298   Cardinal group;
 299   struct drc_info info;
 300   bool two_lines, x_is_long, blocker;
 301   PointType ans;
 302
 303   f = 1.0;
 304   s = 0.5;
 305   last = -1;
 306   line1.Flags = line2.Flags = NoFlags ();
 307   line1.Thickness = Settings.LineThickness + 2 * (PCB->Bloat + 1);
 308   line2.Thickness = line1.Thickness;
 309   line1.Clearance = line2.Clearance = 0;
 310   line1.Point1.X = Crosshair.AttachedLine.Point1.X;
 311   line1.Point1.Y = Crosshair.AttachedLine.Point1.Y;
 312   dy = end->Y - line1.Point1.Y;
 313   dx = end->X - line1.Point1.X;
 314   if (abs (dx) > abs (dy))
 315     {
 316       x_is_long = true;
 317       length = abs (dx);
 318     }
 319   else
 320     {
 321       x_is_long = false;
 322       length = abs (dy);
 323     }
 324
 325   group = GetLayerGroupNumberByNumber (INDEXOFCURRENT);
 326   info.bottom_side = (GetLayerGroupNumberBySide (BOTTOM_SIDE) == group);
 327   info.top_side = (GetLayerGroupNumberBySide (TOP_SIDE) == group);
 328
 329   temp = length;
 330   /* assume the worst */
 331   best = 0.0;
 332   ans.X = line1.Point1.X;
 333   ans.Y = line1.Point1.Y;
 334   while (length != last)
 335     {
 336       last = length;
 337       if (x_is_long)
 338         {
 339           dx = SGN (dx) * length;
 340           dy = end->Y - line1.Point1.Y;
 341           length2 = abs (dy);
 342         }
 343       else
 344         {
 345           dy = SGN (dy) * length;
 346           dx = end->X - line1.Point1.X;
 347           length2 = abs (dx);
 348         }
 349       temp2 = length2;
 350       f2 = 1.0;
 351       s2 = 0.5;
 352       last2 = -1;
 353       blocker = true;
 354       while (length2 != last2)
 355         {
 356           if (x_is_long)
 357             dy = SGN (dy) * length2;
 358           else
 359             dx = SGN (dx) * length2;
 360           two_lines = true;
 361           if (abs (dx) > abs (dy) && x_is_long)
 362             {
 363               line1.Point2.X = line1.Point1.X +
 364                 (way ? SGN (dx) * abs (dy) : dx - SGN (dx) * abs (dy));
 365               line1.Point2.Y = line1.Point1.Y + (way ? dy : 0);
 366             }
 367           else if (abs (dy) >= abs (dx) && !x_is_long)
 368             {
 369               line1.Point2.X = line1.Point1.X + (way ? dx : 0);
 370               line1.Point2.Y = line1.Point1.Y +
 371                 (way ? SGN (dy) * abs (dx) : dy - SGN (dy) * abs (dx));
 372             }
 373           else if (x_is_long)
 374             {
 375               /* we've changed which axis is long, so only do one line */
 376               line1.Point2.X = line1.Point1.X + dx;
 377               line1.Point2.Y =
 378                 line1.Point1.Y + (way ? SGN (dy) * abs (dx) : 0);
 379               two_lines = false;
 380             }
 381           else
 382             {
 383               /* we've changed which axis is long, so only do one line */
 384               line1.Point2.Y = line1.Point1.Y + dy;
 385               line1.Point2.X =
 386                 line1.Point1.X + (way ? SGN (dx) * abs (dy) : 0);
 387               two_lines = false;
 388             }
 389           line2.Point1.X = line1.Point2.X;
 390           line2.Point1.Y = line1.Point2.Y;
 391           if (!two_lines)
 392             {
 393               line2.Point2.Y = line1.Point2.Y;
 394               line2.Point2.X = line1.Point2.X;
 395             }
 396           else
 397             {
 398               line2.Point2.X = line1.Point1.X + dx;
 399               line2.Point2.Y = line1.Point1.Y + dy;
 400             }
 401           SetLineBoundingBox (&line1);
 402           SetLineBoundingBox (&line2);
 403           last2 = length2;
 404           if (setjmp (info.env) == 0)
 405             {
 406               info.line = &line1;
 407               r_search (PCB->Data->via_tree, &line1.BoundingBox, NULL,
 408                         drcVia_callback, &info);
 409               r_search (PCB->Data->pin_tree, &line1.BoundingBox, NULL,
 410                         drcVia_callback, &info);
 411               if (info.bottom_side || info.top_side)
 412                 r_search (PCB->Data->pad_tree, &line1.BoundingBox, NULL,
 413                           drcPad_callback, &info);
 414               if (two_lines)
 415                 {
 416                   info.line = &line2;
 417                   r_search (PCB->Data->via_tree, &line2.BoundingBox, NULL,
 418                             drcVia_callback, &info);
 419                   r_search (PCB->Data->pin_tree, &line2.BoundingBox, NULL,
 420                             drcVia_callback, &info);
 421                   if (info.bottom_side || info.top_side)
 422                     r_search (PCB->Data->pad_tree, &line2.BoundingBox, NULL,
 423                               drcPad_callback, &info);
 424                 }
 425               GROUP_LOOP (PCB->Data, group);
 426               {
 427                 info.line = &line1;
 428                 r_search (layer->line_tree, &line1.BoundingBox, NULL,
 429                           drcLine_callback, &info);
 430                 r_search (layer->arc_tree, &line1.BoundingBox, NULL,
 431                           drcArc_callback, &info);
 432                 if (two_lines)
 433                   {
 434                     info.line = &line2;
 435                     r_search (layer->line_tree, &line2.BoundingBox,
 436                               NULL, drcLine_callback, &info);
 437                     r_search (layer->arc_tree, &line2.BoundingBox,
 438                               NULL, drcArc_callback, &info);
 439                   }
 440               }
 441               END_LOOP;
 442               /* no intersector! */
 443               blocker = false;
 444               f2 += s2;
 445               len = (line2.Point2.X - line1.Point1.X);
 446               len *= len;
 447               len += (double) (line2.Point2.Y - line1.Point1.Y) *
 448                 (line2.Point2.Y - line1.Point1.Y);
 449               if (len > best)
 450                 {
 451                   best = len;
 452                   ans.X = line2.Point2.X;
 453                   ans.Y = line2.Point2.Y;
 454                 }
 455 #if 0
 456               if (f2 > 1.0)
 457                 f2 = 0.5;
 458 #endif
 459             }
 460           else
 461             {
 462               /* bumped into something, back off */
 463               f2 -= s2;
 464             }
 465           s2 *= 0.5;
 466           length2 = MIN (f2 * temp2, temp2);
 467         }
 468       if (!blocker && ((x_is_long && line2.Point2.X - line1.Point1.X == dx)
 469                        || (!x_is_long
 470                            && line2.Point2.Y - line1.Point1.Y == dy)))
 471         f += s;
 472       else
 473         f -= s;
 474       s *= 0.5;
 475       length = MIN (f * temp, temp);
 476     }
 477
 478   end->X = ans.X;
 479   end->Y = ans.Y;
 480   return best;
 481 }
 482
 483 void
 484 EnforceLineDRC (void)
 485 {
 486   PointType r45, rs;
 487   bool shift;
 488   double r1, r2;
 489
 490   /* Silence a bogus compiler warning by storing this in a variable */
 491   int layer_idx = INDEXOFCURRENT;
 492
 493   if ( gui->mod1_is_pressed() || gui->control_is_pressed () || PCB->RatDraw
 494       || layer_idx >= max_copper_layer)
 495     return;
 496
 497   rs.X = r45.X = Crosshair.X;
 498   rs.Y = r45.Y = Crosshair.Y;
 499   /* first try starting straight */
 500   r1 = drc_lines (&rs, false);
 501   /* then try starting at 45 */
 502   r2 = drc_lines (&r45, true);
 503   shift = gui->shift_is_pressed ();
 504   if (XOR (r1 > r2, shift))
 505     {
 506       if (PCB->Clipping)
 507         PCB->Clipping = shift ? 2 : 1;
 508       Crosshair.X = rs.X;
 509       Crosshair.Y = rs.Y;
 510     }
 511   else
 512     {
 513       if (PCB->Clipping)
 514         PCB->Clipping = shift ? 1 : 2;
 515       Crosshair.X = r45.X;
 516       Crosshair.Y = r45.Y;
 517     }
 518 }