pcb

The autorouter is incompatible with the trace optimiser

Bug #699312 reported by eschabor on 2010-02-04
10
This bug affects 2 people
Affects Status Importance Assigned to Milestone
gEDA project
Medium
Unassigned
pcb
Medium
Unassigned

Bug Description

The autorouter creates traces that are incompatible with the trace optimiser mitering function. The attached PCB file shows the problem.

Affected versions:
20091103 compiled from source on Linux
GIT head downloaded 4th Feb 2010 & compiled on Linux

Steps to reproduce:
1. Load attached file
2. Trace Optimiser -> miter
3. Observe failure to miter

Alternate steps to reproduce:
1. Load attached file
2. Delete existing traces
3. Optimise rats
4. Select rat
5. Autoroute selected rat
6. Trace Optimiser -> miter
7. Observe failure to miter

Initial diagnosis
The autorouter creates traces that have tiny gaps (around 0.01 mils) that prevent mitering. Loading the attached PCB file shoes that the autorouter creates
vertical and horizontal lines *mostly* lie on a 1.00 mil grid, but occasionally the lines are off grid by 0.01 or 0.02 mil. These gaps are generally too small to see,
but are big enough to prevent the trace optimiser from mitering.

eschabor (eschabor) wrote :
eschabor (eschabor) wrote :

Better diagnosis:
I've checked further and found that the problem is not that the autorouter makes tiny gaps, it is actually the opposite problem - the autorouter often makes small "overhangs" where a line segment slightly "overshoots" the intersection with another segment. These overhangs are tiny - typically 0.01 thou. Unfortunately these overhangs are enough to prevent mitering.

Workaround
The following patch against the head of the repository extends the trace optimiser "simple" optimization function to remove the overhangs. This means that mitering becomes possible by performing "trace optimiser -> simple optimisations" after autorouting operations.

diff --git a/src/djopt.c b/src/djopt.c
index 68b3641..8422a20 100644
--- a/src/djopt.c
+++ b/src/djopt.c
@@ -75,6 +75,10 @@ RCSID ("$Id$");
 #define ORIENT(x) ((x) & 0xf0)
 #define DIRECT(x) ((x) & 0x0f)

+/* square of the length of the longest "freckle" */
+#define LONGEST_FRECKLE 3
+#define SQ(x) ((x) * (x))
+
 struct line_s;

 typedef struct corner_s
@@ -1230,6 +1234,18 @@ simple_optimize_corner (corner_s * c)
        }
     }
   check (c, 0);
+ if (c->n_lines == 1 && !c->via)
+ {
+ /* see if it is a "freckle" */
+ corner_s *c0 = other_corner (c->lines[0], c);
+ if (SQ(c->x - c0->x) + SQ(c->y - c0->y) < LONGEST_FRECKLE)
+ {
+ dprintf ("freckle %d,%d to %d,%d\n",
+ c->x, c->y, c0->x, c0->y);
+ move_corner (c, c0->x, c0->y);
+ }
+ }
+ check (c, 0);
   return rv;
 }

rikster (rikster-users) wrote :

I used the attached patch against the release 20091103 and it fixed the mitering problem. This should probably be committed to the git code base.

eschabor (eschabor) wrote :

Here's an updated patch. The only difference from the previous patch is that I've provided a more detailed explanatory comment to the code.

diff --git a/src/djopt.c b/src/djopt.c
index 68b3641..3e85a62 100644
--- a/src/djopt.c
+++ b/src/djopt.c
@@ -75,6 +75,10 @@ RCSID ("$Id$");
 #define ORIENT(x) ((x) & 0xf0)
 #define DIRECT(x) ((x) & 0x0f)

+/* square of the length of the longest "freckle" */
+#define LONGEST_FRECKLE 3
+#define SQ(x) ((x) * (x))
+
 struct line_s;

 typedef struct corner_s
@@ -1230,6 +1234,33 @@ simple_optimize_corner (corner_s * c)
  }
     }
   check (c, 0);
+ if (c->n_lines == 1 && !c->via)
+ {
+ corner_s *c0 = other_corner (c->lines[0], c);
+ if (SQ(c->x - c0->x) + SQ(c->y - c0->y) < LONGEST_FRECKLE)
+ {
+ /*
+ * Remove this line, as it is a "freckle". A freckle is an extremely
+ * short line (around 0.01 thou) that is unconnected at one end.
+ * Freckles are almost insignificantly small, but are annoying as
+ * they prevent the mitering optimiser from working.
+ * Freckles sometimes arise because of a bug in the autorouter that
+ * causes it to create small overshoots (typically 0.01 thou) at the
+ * intersections of vertical and horizontal lines. These overshoots
+ * are converted to freckles as a side effect of canonicalize_line().
+ * Note that canonicalize_line() is not at fault, the bug is in the
+ * autorouter creating overshoots.
+ * The autorouter bug arose some time between the 20080202 and 20091103
+ * releases.
+ * This code is probably worth keeping even if the autorouter bug is
+ * fixed, as "freckles" could conceivably arise in other ways.
+ */
+ dprintf ("freckle %d,%d to %d,%d\n",
+ c->x, c->y, c0->x, c0->y);
+ move_corner (c, c0->x, c0->y);
+ }
+ }
+ check (c, 0);
   return rv;
 }

Bert Timmerman (bert-timmerman) wrote :

Hi,

I can still reproduce this bug on git HEAD with the attached problem.pcb example file (git HEAD @ commit aa7ffb86d772d599238e527a718e415b01f10b69, as of 2012-07-15).

There are still freckles left on some corners, and miter still fails.

The updated patch as of 2010-03-09 still applies:

<quote>
patch -p1 < updated_patch.diff
patching file src/djopt.c
Hunk #1 succeeded at 75 with fuzz 2.
Hunk #2 succeeded at 1217 with fuzz 1 (offset -17 lines).
</quote>

But does not solve the problem.

Kind regards,

Bert Timmerman.

Changed in pcb:
status: New → Confirmed
Traumflug (mah-jump-ing) on 2015-09-27
Changed in geda-project:
importance: Undecided → Medium
status: New → Confirmed
tags: added: autorouter
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers