src/line.c

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