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 solder;
 232   jmp_buf env;
 233 };
 234
 235 static int
 236 drcVia_callback (const BoxType * b, void *cl)
 237 {
 238   PinType *via = (PinType *) b;
 239   struct drc_info *i = (struct drc_info *) cl;
 240
 241   if (!TEST_FLAG (FOUNDFLAG, via) && PinLineIntersect (via, i->line))
 242     longjmp (i->env, 1);
 243   return 1;
 244 }
 245
 246 static int
 247 drcPad_callback (const BoxType * b, void *cl)
 248 {
 249   PadType *pad = (PadType *) b;
 250   struct drc_info *i = (struct drc_info *) cl;
 251
 252   if (TEST_FLAG (ONSOLDERFLAG, pad) == i->solder &&
 253       !TEST_FLAG (FOUNDFLAG, pad) && LinePadIntersect (i->line, pad))
 254     longjmp (i->env, 1);
 255   return 1;
 256 }
 257
 258 static int
 259 drcLine_callback (const BoxType * b, void *cl)
 260 {
 261   LineType *line = (LineType *) b;
 262   struct drc_info *i = (struct drc_info *) cl;
 263
 264   if (!TEST_FLAG (FOUNDFLAG, line) && LineLineIntersect (line, i->line))
 265     longjmp (i->env, 1);
 266   return 1;
 267 }
 268
 269 static int
 270 drcArc_callback (const BoxType * b, void *cl)
 271 {
 272   ArcType *arc = (ArcType *) b;
 273   struct drc_info *i = (struct drc_info *) cl;
 274
 275   if (!TEST_FLAG (FOUNDFLAG, arc) && LineArcIntersect (i->line, arc))
 276     longjmp (i->env, 1);
 277   return 1;
 278 }
 279
 280 /* drc_lines() checks for intersectors against two lines and
 281  * adjusts the end point until there is no intersection or
 282  * it winds up back at the start. If way is false it checks
 283  * straight start, 45 end lines, otherwise it checks 45 start,
 284  * straight end.
 285  *
 286  * It returns the straight-line length of the best answer, and
 287  * changes the position of the input point to the best answer.
 288  */
 289
 290 static double
 291 drc_lines (PointType *end, bool way)
 292 {
 293   double f, s, f2, s2, len, best;
 294   Coord dx, dy, temp, last, length;
 295   Coord temp2, last2, length2;
 296   LineType line1, line2;
 297   Cardinal group, comp;
 298   struct drc_info info;
 299   bool two_lines, x_is_long, blocker;
 300   PointType ans;
 301
 302   f = 1.0;
 303   s = 0.5;
 304   last = -1;
 305   line1.Flags = line2.Flags = NoFlags ();
 306   line1.Thickness = Settings.LineThickness + 2 * (PCB->Bloat + 1);
 307   line2.Thickness = line1.Thickness;
 308   line1.Clearance = line2.Clearance = 0;
 309   line1.Point1.X = Crosshair.AttachedLine.Point1.X;
 310   line1.Point1.Y = Crosshair.AttachedLine.Point1.Y;
 311   dy = end->Y - line1.Point1.Y;
 312   dx = end->X - line1.Point1.X;
 313   if (abs (dx) > abs (dy))
 314     {
 315       x_is_long = true;
 316       length = abs (dx);
 317     }
 318   else
 319     {
 320       x_is_long = false;
 321       length = abs (dy);
 322     }
 323   group = GetGroupOfLayer (INDEXOFCURRENT);
 324   comp = max_group + 10;        /* this out-of-range group might save a call */
 325   if (GetLayerGroupNumberByNumber (solder_silk_layer) == group)
 326     info.solder = true;
 327   else
 328     {
 329       info.solder = false;
 330       comp = GetLayerGroupNumberByNumber (component_silk_layer);
 331     }
 332   temp = length;
 333   /* assume the worst */
 334   best = 0.0;
 335   ans.X = line1.Point1.X;
 336   ans.Y = line1.Point1.Y;
 337   while (length != last)
 338     {
 339       last = length;
 340       if (x_is_long)
 341         {
 342           dx = SGN (dx) * length;
 343           dy = end->Y - line1.Point1.Y;
 344           length2 = abs (dy);
 345         }
 346       else
 347         {
 348           dy = SGN (dy) * length;
 349           dx = end->X - line1.Point1.X;
 350           length2 = abs (dx);
 351         }
 352       temp2 = length2;
 353       f2 = 1.0;
 354       s2 = 0.5;
 355       last2 = -1;
 356       blocker = true;
 357       while (length2 != last2)
 358         {
 359           if (x_is_long)
 360             dy = SGN (dy) * length2;
 361           else
 362             dx = SGN (dx) * length2;
 363           two_lines = true;
 364           if (abs (dx) > abs (dy) && x_is_long)
 365             {
 366               line1.Point2.X = line1.Point1.X +
 367                 (way ? SGN (dx) * abs (dy) : dx - SGN (dx) * abs (dy));
 368               line1.Point2.Y = line1.Point1.Y + (way ? dy : 0);
 369             }
 370           else if (abs (dy) >= abs (dx) && !x_is_long)
 371             {
 372               line1.Point2.X = line1.Point1.X + (way ? dx : 0);
 373               line1.Point2.Y = line1.Point1.Y +
 374                 (way ? SGN (dy) * abs (dx) : dy - SGN (dy) * abs (dx));
 375             }
 376           else if (x_is_long)
 377             {
 378               /* we've changed which axis is long, so only do one line */
 379               line1.Point2.X = line1.Point1.X + dx;
 380               line1.Point2.Y =
 381                 line1.Point1.Y + (way ? SGN (dy) * abs (dx) : 0);
 382               two_lines = false;
 383             }
 384           else
 385             {
 386               /* we've changed which axis is long, so only do one line */
 387               line1.Point2.Y = line1.Point1.Y + dy;
 388               line1.Point2.X =
 389                 line1.Point1.X + (way ? SGN (dx) * abs (dy) : 0);
 390               two_lines = false;
 391             }
 392           line2.Point1.X = line1.Point2.X;
 393           line2.Point1.Y = line1.Point2.Y;
 394           if (!two_lines)
 395             {
 396               line2.Point2.Y = line1.Point2.Y;
 397               line2.Point2.X = line1.Point2.X;
 398             }
 399           else
 400             {
 401               line2.Point2.X = line1.Point1.X + dx;
 402               line2.Point2.Y = line1.Point1.Y + dy;
 403             }
 404           SetLineBoundingBox (&line1);
 405           SetLineBoundingBox (&line2);
 406           last2 = length2;
 407           if (setjmp (info.env) == 0)
 408             {
 409               info.line = &line1;
 410               r_search (PCB->Data->via_tree, &line1.BoundingBox, NULL,
 411                         drcVia_callback, &info);
 412               r_search (PCB->Data->pin_tree, &line1.BoundingBox, NULL,
 413                         drcVia_callback, &info);
 414               if (info.solder || comp == group)
 415                 r_search (PCB->Data->pad_tree, &line1.BoundingBox, NULL,
 416                           drcPad_callback, &info);
 417               if (two_lines)
 418                 {
 419                   info.line = &line2;
 420                   r_search (PCB->Data->via_tree, &line2.BoundingBox, NULL,
 421                             drcVia_callback, &info);
 422                   r_search (PCB->Data->pin_tree, &line2.BoundingBox, NULL,
 423                             drcVia_callback, &info);
 424                   if (info.solder || comp == group)
 425                     r_search (PCB->Data->pad_tree, &line2.BoundingBox, NULL,
 426                               drcPad_callback, &info);
 427                 }
 428               GROUP_LOOP (PCB->Data, group);
 429               {
 430                 info.line = &line1;
 431                 r_search (layer->line_tree, &line1.BoundingBox, NULL,
 432                           drcLine_callback, &info);
 433                 r_search (layer->arc_tree, &line1.BoundingBox, NULL,
 434                           drcArc_callback, &info);
 435                 if (two_lines)
 436                   {
 437                     info.line = &line2;
 438                     r_search (layer->line_tree, &line2.BoundingBox,
 439                               NULL, drcLine_callback, &info);
 440                     r_search (layer->arc_tree, &line2.BoundingBox,
 441                               NULL, drcArc_callback, &info);
 442                   }
 443               }
 444               END_LOOP;
 445               /* no intersector! */
 446               blocker = false;
 447               f2 += s2;
 448               len = (line2.Point2.X - line1.Point1.X);
 449               len *= len;
 450               len += (double) (line2.Point2.Y - line1.Point1.Y) *
 451                 (line2.Point2.Y - line1.Point1.Y);
 452               if (len > best)
 453                 {
 454                   best = len;
 455                   ans.X = line2.Point2.X;
 456                   ans.Y = line2.Point2.Y;
 457                 }
 458 #if 0
 459               if (f2 > 1.0)
 460                 f2 = 0.5;
 461 #endif
 462             }
 463           else
 464             {
 465               /* bumped into something, back off */
 466               f2 -= s2;
 467             }
 468           s2 *= 0.5;
 469           length2 = MIN (f2 * temp2, temp2);
 470         }
 471       if (!blocker && ((x_is_long && line2.Point2.X - line1.Point1.X == dx)
 472                        || (!x_is_long
 473                            && line2.Point2.Y - line1.Point1.Y == dy)))
 474         f += s;
 475       else
 476         f -= s;
 477       s *= 0.5;
 478       length = MIN (f * temp, temp);
 479     }
 480
 481   end->X = ans.X;
 482   end->Y = ans.Y;
 483   return best;
 484 }
 485
 486 void
 487 EnforceLineDRC (void)
 488 {
 489   PointType r45, rs;
 490   bool shift;
 491   double r1, r2;
 492
 493   /* Silence a bogus compiler warning by storing this in a variable */
 494   int layer_idx = INDEXOFCURRENT;
 495
 496   if ( gui->mod1_is_pressed() || gui->control_is_pressed () || PCB->RatDraw
 497       || layer_idx >= max_copper_layer)
 498     return;
 499
 500   rs.X = r45.X = Crosshair.X;
 501   rs.Y = r45.Y = Crosshair.Y;
 502   /* first try starting straight */
 503   r1 = drc_lines (&rs, false);
 504   /* then try starting at 45 */
 505   r2 = drc_lines (&r45, true);
 506   shift = gui->shift_is_pressed ();
 507   if (XOR (r1 > r2, shift))
 508     {
 509       if (PCB->Clipping)
 510         PCB->Clipping = shift ? 2 : 1;
 511       Crosshair.X = rs.X;
 512       Crosshair.Y = rs.Y;
 513     }
 514   else
 515     {
 516       if (PCB->Clipping)
 517         PCB->Clipping = shift ? 1 : 2;
 518       Crosshair.X = r45.X;
 519       Crosshair.Y = r45.Y;
 520     }
 521 }