As a user of EAGLE for a number of years, I’ve often run into its limitations. This summer, I was trying to design an odd-shaped board and I realized there was no good way to do so within EAGLE.
I was hoping for some way of drawing bezier curves, but EAGLE only offers straight lines and arcs for drawing board outlines. I looked into EAGLE User Language Programs (ULPs) and ended up writing a program capable of drawing complicated shapes within EAGLE, utilizing EAGLE’s built-in bitmap ULP.
Importing bitmaps
EAGLE has a useful bitmap importing tool which is very useful for adding images to board silkscreens. The import-bmp.ulp program works by drawing small 1px high rectangles that form the shape of the bitmap drawing. Given the finite silkscreen resolution offered by board fabs, you can import a bitmap with a high enough resolution that the rectangles are indistinguishable on the printed board.
When I started designing the PCB with a complicated shape, I imported the shape using import-bmp.ulp then began to trace the outline manually. I soon realized this was an extremely slow process and knew that a programmatic approach could save me a lot of time down the road. For example, if I needed to scale the board size, I would have to draw it all over again but a program could do it very quickly in comparison.
As I began looking into the possibility of writing a ULP to do this task, I quickly knew import-bmp.ulp would be helpful. First, it provided a simple way to import a complex shape into EAGLE. Second, reading through the program itself was a good primer on how to write a ULP.
From bitmap to board outline
I planned to write a program that would look at the rectangles drawn by import-bmp.ulp and trace an appropriate outline. I quickly abandoned more complicated ideas such as specifying padding around the bitmap or ensuring that only the outermost silhouette of a bitmap would be added to the outline layer. The only goal for this ULP was to precisely trace out each shape in the bitmap; everything else could be done by manipulating the bitmap images as necessary outside of EAGLE.
I began by looking at some online ULP writing guides (example), but eventually found that reading through official ULPs and referencing the official ULP documentation pdf were the most useful ways of making sense of this new language.
Since this program was tracing shapes that existed within EAGLE as a bunch of rectangles, it would need to loop through the rectangles within the EAGLE board file. While the ULP language looks a lot like C, there is some custom syntax involved. Here’s how to loop through all rectangles in a board:
if (board) { // Makes sure board is open
board(B) { // Board is now accessible under name 'B'
B.rectangles(R) { // Loops through all rectangles on board 'B'
// Do stuff with each rectangle 'R'
}
}
}
Each UL_RECTANGLE object has a number of “data members”. The angle from 0 - 359.9 specifies the angle of rotation. The layer specifies which layer the object is on. Two sets of coordinates are used to define the rectangle location. x1 and y1 specify the lower left corner while x2 and y2 specify the upper right corner.
With the x1, y1, x2, and y2 coordinates, all four lines making up the rectangle edges can be deciphered. For example, the upper horizontal line goes from (x1, y2) to (x2, y2).
Not every line segment forming each rectangle is part of the shape outline though. Wherever rectangle edges overlap, those portions of the line should not be included in the outline.
One of the first things I noticed was that each vertical line of a rectangle should be included in the outline. Since import-bmp.ulp processes the bitmap row by row, rectangles are 1px high slices of the larger shape. The left and right sides of each rectangle signify the ends of each shape within the bitmap, so these sides will never overlap with other rectangle edges in the shape.
I still needed a way to calculate which horizontal lines make up the outline, but it turns out there’s a simple way to do so.
The script that import-bmp.ulp generates adds rectangles to the EAGLE brd file in a specific order, row by row from bottom to top. My program could take advantage of this, looping through the rectangles in the board file knowing that they are in order by row. Iterating through each row while storing the previous row in memory, the program now had all the information needed to generate horizontal lines between each adjacent pair of rows.
This created a much simpler problem, but I still needed to come up with a way of detecting which parts of the rectangle faces were not overlapping. As it turns out, the problem can also be thought of as generating horizontal lines that connect nearby vertical lines. For each set of adjacent rows, we identify all of the vertical lines. Working left to right, we simply draw a horizontal line from the first vertical line to the second vertical line, from the third to the fourth, and so on.
The algorithm for generating the necessary horizontal lines is as follows:
- For each set of rectangles within adjacent rows:
- Place both x-coordinates of each rectangle into an array
- Sort array
- Iterate through the sorted array, reading 2 horizontal coordinates at a time:
- At the height where the 2 rows meet, define a line between each of the 2 horizontal coordinates
- Discard line if the length is 0
If the bitmap has a straight vertical edge, horizontal lines are not needed at those spots, but the algorithm generates 0-length lines there. This is why the algorithm specifically checks for 0-length lines and discards them.
Trace BMP
Building off of this algorithm, I created trace-bmp.ulp. In order to use it, first run import-bmp.ulp to import the bitmap shape into EAGLE. Then run trace-bmp.ulp, specifying the layer that the bitmap was added to. trace-bmp.ulp then loops through all of the rectangles on that layer, finding the edges of the shape and creating a script that draws the necessary lines into the board. The program then prompts the user to run this script.
Performance
When testing this ULP, I quickly ran into performance issues. Working originally with a 2400 x 2097 px bitmap, I noticed that when the script ran, the lower lines would draw very quickly but the script would quickly slow down to a crawl. This drop-off in speed seemed to be exponential.
As far as I can tell, adding n lines to the dimension layer row by row is a O(n2) complexity problem. It seems that connecting a line to a set of other connected lines on the dimension layer causes EAGLE to run some algorithm that has to iterate through all of the connected lines. This is likely related to how EAGLE determines which parts of the display grid are inside or outside of the board outline. It checks this in order to color the board and non-board areas differently. This means that adding a line to a large set of connected lines is much slower than adding a line to a small set of connected lines.
Specifically, the problem grows like this: 1 + 2 + 3 + ... + n. When the first line is added, 1 line is checked. When the second line is added, 2 lines are checked. When the n‘th line is added, n lines must be checked. The summation 1 + 2 + 3 + ... + n is equal to n(n+1)/2 which has O(n2) complexity.
With this in mind, I set out to lower the runtime of the script generated by my program. The easiest way of ordering line commands in the script is row-by-row. As the program processes a new row, it appends the necessary lines to the end of the script. As the script traces out the shape, the first few lines will run quickly. However, except in rare cases each new line will be appended to a set of already connected lines, meaning the problem of adding a new line quickly becomes slow.
One idea for reducing this problem’s time complexity is to implement a divide-and-conquer methodology. Instead of drawing lines that are connected to other lines, first draw every other line such that no lines are connected. Then run another pass, filling in the missing lines so that there are many sets of 3 connected lines. Keep running these passes, connecting sets of connected lines into larger connected sets until finally the last line is added which connects the remaining 2 sets.
I wasn’t able to find an easy way of modifying the program to generate a script with line commands in such a divide-and-conquer order. However, I did make a change which lowered the runtime. Specifically, the program would attempt to split the outline into approximately sqrt(n) smaller connected sections by skipping one line every sqrt(n) lines, placing those lines at the end of the script.
With this modification, I saw a reduction in runtime with an 800x699 pixel bitmap:
- Time with approximate
sqrtstrategy: 50 seconds - Time with no strategy: 117 seconds
Another problem I quickly realized was that opening a file with a complex outline would also take a long time. Interestingly though, for both strategies it took the same time (56 seconds) to open the file. It was about this time that I realized there was a nifty EAGLE setting that could make all of this optimization pointless.
Disabling “Detect Board Shape”
In the User Interface options window of EAGLE, there is a checkbox option for Detect Board Shape. Unchecking this setting stops EAGLE from performing the inefficient line processing, which is much better than the hacky solution that I put together for optimizing the line-drawing process. In a test, this brought the 800x699 pixel bitmap outline-drawing time down to 21 seconds.
While my line splitting algorithm did speed up the script runtime, it still scaled extremely poorly with bitmap size. I removed this complicated and ultimately unnecessary functionality and the script now suggests that users disable the Detect Board Shape option.
Download
You can download the ULP from Github.