m8ta
You are not authenticated, login. |
|
{668} |
ref: notes-0
tags: triangulation kicadocaml
date: 02-04-2009 21:40 gmt
revision:7
[6] [5] [4] [3] [2] [1] [head]
|
|
PCB copper zones using triangle meshes Abstract: Many tasks in computer-assisted design involve the removal of polygons from other polygons. Particularly, this problem is found when filling a region of a printed circuit board (PCB) with a polygonal zone or 'pour' of copper. This zone is attached to a net, perhaps ground, and hence other tracks, vias, and segments of copper not on the same net but within its region must be avoided by a clearance distance. This clearance can be observed by subtraction of expanded polygons from the original zone's outline polygon, as is done in two open-source PCB design softwares, Kicad and gEDA. Here we present a fast and scalable algorithm that works with triangles instead of polygons. The algorithm is able to mesh, add edges, and remove conflicting triangles within a few seconds for problems involving 10,000 points. Introduction: I have contributed, infrequently, to the open-source electronic design automation (EDA) suite Kicad for the past year or so. November/December of 2007 I added duplicated hierarchal support to Kicad's schematic editor, eeschema, which allows, like many commercial packages, duplicate instances of sub-schematics. This feature is used when a segment of circuitry is duplicated multiple times in a design, perhaps when there are multiple identical channels, e.g. in an audio mixer. However pcbnew (the layout editor in Kicad) is unaware of the duplication, hence for each sub-schematic the layout had to be duplicated. This involved a lot of work for the 8-channel microstimulator board that I was working on at the time, so I decided to implement a small application to help layout an array of duplicated circuitry. Ocaml was chosen to implement the software, as I wanted to learn the language. In the course of working on PCBs, learning Ocaml, and basically scratching a series of itches, the software, tentatively named "Kicadocaml", has become progressively more feature-rich, useful, and tested. It has ratsnest, DRC online and offline checking, push routing, schematic hierarchy comprehension (of course), connectivity testing, bill-of-materials generation, and a responsive OpenGL-based GUI. In my last board, pcbnew failed to fill all the zones; I'm not sure why. I tried to fix the bug, but got lazy/overwhelmed after a while, and decided to just write a zone-filling algorithm from scratch myself (to scratch the itch, so to speak). Sure it's reinventing the wheel, but reinventing is fun. In the interest of documenting the algorithm a bit for posterity, the algorithm is described below. Algorithm: A list is made of all points and segments that may be involved in the zone-fill. This includes, of course, the edges of the zone, as well as the outline of any track/via/pad cutout within the zone (and not of the same net number), expanded to allow for zone clearance and zone-edge stroking. The list of points also must include any intersections between segments. For efficiency, the lists of points and segments are culled by checking each polygon to be subtracted to make sure that at least one of it's points is within the zone polygon; this is done via the standard inside/outside polygon test. The list of points is then incrementally inserted into a linked triangle mesh via a very simple, very effective method of triangle splitting and edge-flipping. Linked triangle mesh means that each triangle stores a index (or pointer) to the triangle off each of its three edges. This is to facilitate the insertion of points: to find the triangle that a point is in, you walk over the linked mesh, crossing the edge between triangles that intersects a ray from the center of the present triangle to the target point. (Given the ordering of points within the list, this can be nearly a constant-time operation). See below.
Once a triangle is found, it is split into three triangles by the addition of the point. Then, each pair of triangles, one new and one old (bordering the triangle that was split) is checked to see if flipping the interior segment would increase the smallest angle. Remarkably, this reliably takes care of edge insertion - no specialized edge insertion routine was required (however, loops in the find triangle algorithm (figure 1) must be eliminated for a triangle to be found when a point is on an edge). I decided to simply maximize the minimum angle in each triangle, rather than observe the Delaunay criteria which doesn't matter for this application.
This algorithm only deals with finding containing triangles and inserting points; hence, it must be seeded with at least one triangle which will contain all others. I chose to use two triangles defined by a slightly-enlarged bounding box of all points to be inserted. The algorithm does not insure that all polygon segments are in the list of edges of a mesh; hence, after all points are inserted, every edge is checked to make sure if it is in the mesh -- see figure 3.
Once all points and all edges from the original list are in the mesh, then each triangle may be tested to see if it should be kept or removed. In kicadocaml this is done with DRC (design rule check) testing.
Afterword: The algorithm runs well; it takes ~ 2 seconds to mesh, edge check, and filter 10,000 points on my Core2 2.4Ghz desktop computer. Though it was written in a higher-level language (about 600 lines of Ocaml), I do not think that it would be hard to port to C++ for inclusion in other PCB layout packages. Great effort was not necessarily put into the design of the algorithm, but rather the numerical stability of it's sub-components, such as the triangle inside-outside check (computed with the cross product), and the segment intersection test. For these, please see the source, or {661}. |