You are not authenticated, login.
text: sort by
tags: modified
type: chronology
hide / / print
ref: -2021 tags: gated multi layer perceptrons transformers ML Quoc_Le Google_Brain date: 08-05-2021 06:00 gmt revision:4 [3] [2] [1] [0] [head]

Pay attention to MLPs

  • Using bilinear / multiplicative gating + deep / wide networks, you can attain similar accuracies as Transformers on vision and masked language learning tasks! No attention needed, just a in-network multiplicative term.
  • And the math is quite straightforward. Per layer:
    • Z=σ(XU),,Z^=s(Z),,Y=Z^V Z = \sigma(X U) ,, \hat{Z} = s(Z) ,, Y = \hat{Z} V
      • Where X is the layer input, σ\sigma is the nonlinearity (GeLU), U is a weight matrix, Z^\hat{Z} is the spatially-gated Z, and V is another weight matrix.
    • s(Z)=Z 1(WZ 2+b) s(Z) = Z_1 \odot (W Z_2 + b)
      • Where Z is divided into two parts along the channel dimension, Z 1Z 2Z_1 Z_2 . 'circleDot' is element-wise multiplication, and W is a weight matrix.
  • You of course need a lot of compute; this paper has nice figures of model accuracy scaling vs. depth / number of parameters / size. I guess you can do this if you're Google.

Pretty remarkable that an industrial lab freely publishes results like this. I guess the ROI is that they get the resultant improved ideas? Or, perhaps, Google is in such a dominant position in terms of data and compute that even if they give away ideas and code, provided some of the resultant innovation returns to them, they win. The return includes trained people as well as ideas. Good for us, I guess!

hide / / print
ref: ODoherty-2011 tags: Odoherty Nicolelis ICMS stimulation randomly patterned gamma distribution date: 01-03-2012 06:55 gmt revision:1 [0] [head]

IEEE-6114258 (pdf) Towards a Brain-Machine-Brain Interface:Virtual Active Touch Using Randomly Patterned Intracortical Microstimulation.

  • Key result: monkeys can discriminate between constant-frequency ICMS and aperiodic pulses, hence can discriminate some fine temporal aspects of ICMS.
  • Also discussed blanking methods for stimulating and recording at the same time (on different electrodes, using the randomized stimulation patterns).


O'Doherty, J. and Lebedev, M. and Li, Z. and Nicolelis, M. Towards a Brain #x2013;Machine #x2013;Brain Interface:Virtual Active Touch Using Randomly Patterned Intracortical Microstimulation Neural Systems and Rehabilitation Engineering, IEEE Transactions on PP 99 1 (2011)

hide / / print
ref: Fitzsimmons-2007.05 tags: Fitzsimmons nicolelis stimluation ICMS owl monkeys date: 01-01-2012 00:12 gmt revision:2 [1] [0] [head]

PMID-17522304[0] Primate reaching cued by multichannel spatiotemporal cortical microstimulation.

  • Good intro and discussion. The rest of it is familiar - was there!
  • Monkeys did not immediately generalize vibration stimuli to ICMS. But then again, owl monkeys are not terribly intelligent. c.f. Romo.


[0] Fitzsimmons NA, Drake W, Hanson TL, Lebedev MA, Nicolelis MA, Primate reaching cued by multichannel spatiotemporal cortical microstimulation.J Neurosci 27:21, 5593-602 (2007 May 23)

hide / / print
ref: work-0 tags: kinarm problem mathML date: 11-03-2010 16:05 gmt revision:8 [7] [6] [5] [4] [3] [2] [head]

Historical notes from using the Kinarm... this only seems to render properly in firefox / mozilla.

To apply cartesian force fields to the arm, the original kinarm PLCC (whatever that stands for) converted joint velocities to cartesian veolocities using the jacobian matrix. All well and good. The equation for endpoint location of the kinarm is:

x^=[l 1sin(θ sho)+l 2sin(θ sho+θ elb) l 1cos(θ sho)+l 2cos(θ sho+θ elb)] \hat{x} = { \left[ \array{ l_1 sin(\theta_{sho}) + l_2 sin(\theta_{sho} + \theta_{elb} ) \\ l_1 cos(\theta_{sho}) + l_2 cos(\theta_{sho} + \theta_{elb} ) } \right] }

L_1 = 0.115 meters, l_2 = 0.195 meters in our case. The jacobian of this function is: J=[l 1sin(θ sho)l 2sin(θ sho+θ elb) l 2sin(θ elb) l 1cos(θ sho)+l 2cos(θ sho+θ elb) l 2cos(θ elb)] J = { \left[ \array{ - l_1 sin(\theta_{sho}) - l_2 sin(\theta_{sho} + \theta_{elb} ) && - l_2 sin(\theta_{elb}) \\ l_1 cos(\theta_{sho}) + l_2 cos(\theta_{sho} + \theta_{elb} ) && l_2 cos(\theta_{elb}) } \right] } v^=Jθ^ \hat{v} = J \cdot \hat{\theta} etc. and (I think!) F^=Jτ^ \hat{F} = J \cdot \hat{\tau} where tau is the shoulder and elbow torques and F is the cartesian force. The flow of the PLCC is then:

  1. convert joint angluar velocities to cartesian velocities
  2. cartesian velocities to cartesian forces by a symmetric matrix A which effects simple viscious and curl fields.
F^=Av^ \hat{F} = A \cdot \hat{v}
  1. cartesian forces to joint torques via the inverse of the jacobian.
But, and I may be wrong here, rather than inverting the jacobian, the PLCC simply takes the transform. The inverse of the jacobian and the transpose are not even close to equal. viz (from mathworld):

J=[a b c d] J = { \left[ \array{ a & b \\ c & d } \right] }

J 1=1adbc[d b c a][a c b d]=J T J^{-1} = \frac{ 1}{a d - b c} { \left[ \array{d &-b \\ -c & a} \right] } \ne { \left[ \array{a & c \\ b & d} \right] } = J^{T}

substitute to see if the matrices look similar ...

|J|[l 2cos(θ elb) l 2sin(θ elb) l 1cos(θ sho)l 2cos(θ sho+θ elb) l 1sin(θ sho)l 2sin(θ sho+θ elb)][l 1sin(θ sho)l 2sin(θ sho+θ elb) l 1cos(θ sho)+l 2cos(θ sho+θ elb) l 2sin(θ elb) l 2cos(θ elb)]{\vert J \vert} \cdot { \left[ \array{ l_2 cos(\theta_{elb}) && l_2 sin(\theta_{elb}) \\ - l_1 cos(\theta_{sho}) - l_2 cos(\theta_{sho} + \theta_{elb} ) && - l_1 sin(\theta_{sho}) - l_2 sin(\theta_{sho} + \theta_{elb} ) } \right] } \ne { \left[ \array{ - l_1 sin(\theta_{sho}) - l_2 sin(\theta_{sho} + \theta_{elb} ) && l_1 cos(\theta_{sho}) + l_2 cos(\theta_{sho} + \theta_{elb} ) \\ - l_2 sin(\theta_{elb}) && l_2 cos(\theta_{elb}) } \right] }


|J|=l 1l 2sin(θ sho)cos(θ elb)l 2 2sin(θ sho+θ elb)cos(θ elb)+l 1l 2cos(θ sho)sin(θ elb)l 2 2cos(θ sho+θ elb)sin(θ elb) {\vert J \vert} = { - l_1 l_2 sin(\theta_sho) cos(\theta_elb) - l_2^2 sin(\theta_{sho} + \theta_{elb} ) cos(\theta_elb) + - l_1 l_2 cos(\theta_sho) sin(\theta_elb) - l_2^2 cos(\theta_{sho} + \theta_{elb} ) sin(\theta_elb) }

I'm surprised that we got something even like curl and viscous forces - the matrices are not similar. This explains why the forces seemed odd and poorly scaled, and why the constants for the viscious and curl fields were so small (the units should have been N/(cm/s) - 1 newton is a reasonable force, and the monkey moves at around 10cm/sec, so the constant should have been 1/10 or so. Instead, we usually put in a value of 0.0005 ! For typical values of the shoulder and elbow angles, the determinant of the matrix is 200 (the kinarm PLCC works in centimeters, not meters), so the transpose has entries ~ 200 x too big. Foolishly we compensated by making the constant (or entries in A) 200 times to small. i.e. 1/10 * 1/200 = 0.0005 :(

The end result is that a density-plot of the space spanned by the cartesian force and velocity is not very clean, as you can see in the picture below. The horizontal line is, of course, when the forces were turned off. A linear relationship between force and velocity should be manifested by a line in these plots - however, there are only suggestions of lines. The null field should have a negative - slope line in upper left and lower right; the curl field should have a positive sloped line in the upper right and negative in the lower left (or vice-vercia).


hide / / print
ref: work-0 tags: kicadocaml zbuffer comparison picture screenshot date: 03-03-2010 16:38 gmt revision:4 [3] [2] [1] [0] [head]

Simple illustration of Kicadocaml with Z buffering enabled:

and disabled:

I normally use it with Z buffering enabled, but turn it off if, say, I want to clearly see all the track intersections, especially co-linear tracks or zero length tracks. (Probably I should write something to merge and remove these automatically.) Note that in either case, tracks and modules are rendered back-to-front, which effects a Z-sorting of sorts; it is the GPUs Z buffer that is enabled/disabled here.

hide / / print
ref: -0 tags: kicadocaml screenshot picture date: 03-03-2010 05:53 gmt revision:2 [1] [0] [head]

Aint she pretty?

More shots of the completed board (click for full resolution image):

  • whole thing, all layers.

  • Just the headstage, top and inner layer 2 only

  • Just the headstage, bottom and inner layers 2, 3 and 4.

hide / / print
ref: -0 tags: ocaml budget money date: 12-11-2009 20:02 gmt revision:1 [0] [head]

This morning i checked my bank account, and was throughly offended with what was in there. To figure out where I was spending my money, I exported a csv from the bank's website, and read it into open office to label each expense. Since I couldn't easily figure out how to sum along each label, I wrote an ocaml program to do this --

let gitline ic = (
	try input_line ic, false 
	with _ -> "", true
	) ;;
let fos = float_of_string
let ios = int_of_string
let soi = string_of_int
let sof = string_of_float
let foi = float_of_int
let iof = int_of_float
let fabs = abs_float

let read fname = 
	let eof = ref false in
	let out = ref [] in
	let ic = open_in fname in
	let tab = Str.regexp "," in
	while not !eof do (
			let line, eoff = gitline ic in
			let ar = Array.of_list (Str.split tab line) in
			if Array.length ar = 7 then ( 
				let debit = fos ar.(3) in
				let credit = fos ar.(4) in
				let wha = ar.(6) in
				out := (debit,credit,wha) :: !out ; 
			eof := eoff; 
	) done; 
	close_in_noerr ic ; 

let _ = 
	let sumht = Hashtbl.create 50 in
	List.iter (fun a -> 
		let debit,credit,wha = a in
		let m = try Hashtbl.find sumht wha with _ -> 0.0 in
		let m2 = m -. credit +. debit in
		Hashtbl.replace sumht wha m2
	) ( read "/home/tlh24/Desktop/Suntrust_History.csv"); 
	Hashtbl.iter (fun wha valu -> 
		print_endline( wha^","^(sof valu)); 
	) sumht ; 
The first half of this file is 'stock' - just helper functions for reading in the CSV file (you can copy-paste to use on your own files). After that, it's just assigning fields to variables and summing along the labels with a hash table - easy as it should be. Certainly it could be accomplished in far fewer lines with perl, but perl is not at the tip of my tongue as ocaml is now :-)

For the curious, here is the result (bar charts >> pie charts):

I spend a lot of money on food and 'parts'. Food is pretty self-explanatory; 'parts' includes electronic parts, bike parts (a fender, bike clips, new lights), a new cell phone, stuff from home depot. Tools was mostly for a cylinder of welding gas - you have to buy the cylinder; the gas is relatively cheap. The labels are sort-of amorphous, since all are directed toward the goal of fixing my (*&^%) car, which has a rusted-out crack in the frame from where the (*&^%) previous owner attached an aftermarket brace. Finally, the gas was from a 1300 mile road trip over Thanksgiving (in my other POS car, whose drivers side front wheel bearing is loose on the strut mount, oh my). Normally I don't spend that much on gas.

hide / / print
ref: work-0 tags: functional programming compilation ocaml date: 08-24-2009 14:33 gmt revision:0 [head]

The implementation of functional programming languages - book!

hide / / print
ref: -0 tags: ocaml latex metapost date: 07-23-2009 13:56 gmt revision:1 [0] [head]

http://mlpost.lri.fr/ -- allows drawing Latex or postscript figures programmatically. Interesting. Included in Debian. source

hide / / print
ref: work-0 tags: ocaml mysql programming functional date: 07-03-2009 19:16 gmt revision:2 [1] [0] [head]

Foe my work I store a lot of analyzed data in SQL databases. In one of these, I have stored the anatomical target that the data was recorded from - namely, STN or VIM thalamus. After updating the analysis programs, I needed to copy the anatomical target data over to the new SQL tables. Where perl may have been my previous go-to language for this task, I've had enuogh of its strange quiks, hence decided to try it in Ruby (worked, but was not so elegant, as I don't actually know Ruby!) and then Ocaml.

#use "topfind"
#require "mysql"

(* this function takes a query and a function that converts entries 
in a row to Ocaml tuples *)
let read_table db query rowfunc =
	let r = Mysql.exec db query in
	let col = Mysql.column r in
	let rec loop = function
		| None      -> []
		| Some x    -> rowfunc col x :: loop (Mysql.fetch r)
	loop (Mysql.fetch r)

let _ = 
	let db = Mysql.quick_connect ~host:"crispy" ~database:"turner" ~password:"" ~user:"" () in
	let nn = Mysql.not_null in
	(* this function builds a table of files (recording sessions) from a given target, then 
	uses the mysql UPDATE command to propagate to the new SQL database. *)
	let propagate targ = 
		let t = read_table db 
			("SELECT file, COUNT(file) FROM `xcor2` WHERE target='"^targ^"' GROUP BY file")
			(fun col row -> (
				nn Mysql.str2ml (col ~key:"file" ~row), 
				nn Mysql.int2ml (col ~key:"COUNT(file)" ~row) )
		List.iter (fun (fname,_) -> 
			let query = "UPDATE `xcor3` SET `target`='"^targ^
				"' WHERE STRCMP(`file`,'"^fname^"')=0" in
			print_endline query ;
			ignore( Mysql.exec db query )
		) t ;
	propagate "STN" ; 
	propagate "VIM" ; 
	propagate "CTX" ; 
	Mysql.disconnect db ;;

Interacting with MySQL is quite easy with Ocaml - though the type system adds a certain overhead, it's not too bad.

hide / / print
ref: work-0 tags: ocaml toplevel ocamlfind date: 06-24-2009 14:52 gmt revision:1 [0] [head]

Ocaml has an interactive top level, but in order to make this useful (e.g. for inspecting the types of variables, trying out code before compiling it), you need to import libraries and modules. If you have ocamlfind on your system (I think this is the requirement..), do this with: #use "topfind";; at the ocaml prompt, then #require"package names" . e.g:

tlh24@chimera:~/svn/m8ta/yushin$ ledit | ocaml
        Objective Caml version 3.10.2

# #use "topfind";;
- : unit = ()
Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

- : unit = ()
# #require "bigarray,gsl";;
/usr/lib/ocaml/3.10.2/bigarray.cma: loaded
/usr/lib/ocaml/3.10.2/gsl: added to search path
/usr/lib/ocaml/3.10.2/gsl/gsl.cma: loaded
# #require "pcre,unix,str";;
/usr/lib/ocaml/3.10.2/pcre: added to search path
/usr/lib/ocaml/3.10.2/pcre/pcre.cma: loaded
/usr/lib/ocaml/3.10.2/unix.cma: loaded
/usr/lib/ocaml/3.10.2/str.cma: loaded
# Pcre.pmatch
- : ?iflags:Pcre.irflag ->
    ?flags:Pcre.rflag list ->
    ?rex:Pcre.regexp ->
    ?pat:string -> ?pos:int -> ?callout:Pcre.callout -> string -> bool
= <fun>
# let m = Gsl_matrix.create 3 3;;
val m : Gsl_matrix.matrix = <abstr>
# m;;
- : Gsl_matrix.matrix = <abstr>
# m.{1,1};;
- : float = 6.94305623882282e-310
# m.{0,0};;
- : float = 6.94305568087725e-310
# m.{1,1} <- 1.0 ;;
- : unit = ()
# m.{2,2} <- 2.0 ;;
- : unit = ()
# let mstr = Marshal.to_string m [] ;;


hide / / print
ref: -0 tags: mathml date: 04-09-2009 22:33 gmt revision:23 [22] [21] [20] [19] [18] [17] [head]

MathML!! now it is even less likely that I'll ever get this working in Internet Explorer.

  • Check the commands.
  • tests:
  • A^ 0=[a b c d e f] \hat A_0 = {\left[ \begin{matrix} a & b & c \\ d & e & f \end{matrix} \right]}
  • [1 0 0 1][1 0 0 1]=[1 0 0 1] \left[ \array{1 & 0 \\ 0 & 1} \right] \cdot \left[ \array{1 & 0 \\ 0 & 1} \right] = \left[ \array{ 1 & 0 \\ 0 & 1} \right]
  • a bf(x)g(x)δx=0 \color{navy} sstrch \int_a^b \frac{f(x)}{g(x)} \delta x estrch = 0
    • note that to make an integral (or others?) stretchy, just delimit with sstrch and estrch (see source) - will stretch around the delimited math (if it doesn't break the XML!)
  • the quadratic formula: x=b±b 24ac2a x = \frac{-b \pm \sqrt{ b^2 -4 a c}}{2 a }

hide / / print
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


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.


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.


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.

  • Figure 1: Method of finding the triangle which contains a point. The highlighted triangle indicates the working triangle (in practice, this is an index to an array), and n is a point within that triangle (in my implementation, I chose to simply average the 3 corners of the triangle to get an interior point). p is the target point. In each iteration, each segment of the working triangle is checked to see if it intersects with the line np ; if it does, then the working triangle index is updated with the index of the triangle off the intersected edge. This continues until p is within the working triangle. The working triangle index is cached between calls of this iterative algorithm, as usually sequential calls involve points that are close.

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.

  • Figure 2: Point insertion method. After triangle ABC is split into ABP, BCP, and CAP, each pair (BFC & BCP ; CDA & CAP ; AEB & ABP) is check to see if flipping the internal segment would make the minimum internal angle between the two larger. For example, here the minimum internal angle of triangles BFP & FCP was found to be less than BFC & BCP. Indeed, all new triangles were 'flipped' in this example. Care must be taken to maintain the integrity of the linked mesh when inserting and flipping triangles - with extra caution to the fact that it is dual-linked (to and from a given triangle).

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.

  • Figure 3: Adding segment AB to the mesh. First, the segment is checked to see if it - or a sub-segment (via a parallel test), is already in the mesh. If not, a working triangle index is found that has endpoint B as a vertex. The angle between the associated edges and AB are measured; if the angle is greater, the triangle off the CCW edge becomes the working triangle (e.g. 1); if less, the triangle off the CW edge becomes the working triangle; if AB is between the two associated triangle edges, then the intersection point with the far edge is found (2). These calculations are simplified by the fact that all triangles are CCW. The intersection point is inserted into the mesh, and the segment is made shorter - the newly inserted point becomes end B of the segment, and the algorithm recurses. Note, as in 5, when inserting points the flipping rule still holds; as a result of this, all edges must be checked twice, the second time without flipping, to be certain that all edges are in the mesh. As with the triangle finding algorithm, segment checking/adding is relatively efficient with the linked-mesh data structure.

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.

  • Figure 4: Final result, after conflicting triangles are removed. Original polygon edges are shown in light gray.


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}.

hide / / print
ref: -0 tags: computational geometry triangulation ocaml kicadocaml zone fill edge date: 01-26-2009 01:47 gmt revision:3 [2] [1] [0] [head]

I have been working hard to add zone support to kicadocaml since the implementation in kicad's PCBnew is somewhat borken (at least for my boards). It is not a very easy task!

Roughly, the task is this: given a zone of copper pour, perhaps attached to the ground net, and a series of tracks, vias, and pads also on that layer of the PCB but not on the same net, form cutouts in the zone so that there is an even spacing between the tracks/vias and zone.

Currently I'm attacking the problem using triangles (not polygons like the other PCB softwares). I chose triangles since I'm using OpenGL to display the PCB, and triangles are a very native mode of drawing in OpenGL. Points are added to the triangle mesh with an incremental algorithm, where the triangles are stored as a linked-mesh : each triangle has a pointer (index#) to the triangle off edge ab,bc,ca. This allows finding the containing triangle when inserting a point a matter of jumping between triangles; since many of the points to be inserted are close to eachother, this is a relatively efficient algorithm. Once the triangle containing a point to be inserted is found, the triangle is split into three, the pointers are updated appropriately, and each triangle is tested to see if flipping with it's pair would result in a net larger smallest interior angle between the two. (This is not the same as Delaunay's criteria, but it is simpler, and it produces equally beautiful pictures.)

The problem is when two triangles are allowed to overlap or a gap is allowed - this makes the search algorithm die or get into a loop, and is a major major problem of the approach. In Guibas and Stolfi's paper, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", they use an edge data structure, rather than a triangle data structure, which I suppose avoids this problem. I was lazy when starting this project, and chose the more obvious triangle-centric way of storing the data.

The insertion of points is actually not so hard; the big problem is making sure the edges in the original list of polygons are represented in the list of edges in the triangle mesh. Otherwise, triangles will span edges, which will result in DRC violations (e.g.g copper too close to vias). My inefficient way of doing this is to calculate, for all triangles, their intersections with the polygon segments, then adding this to the mesh until all segments are represented in the list. This process, too, is prone to numerical instability.

Perhaps the solution is to move back to an edge-centric data representation, so that certain edges can be 'pinned' or frozen, and hence they are guaranteed to be in the triangle mesh's edge list. I don't know; need to think about this more.

Update: I got most of it working; at least the triangulation & making sure the edges are in the triangle mesh are working. Mostly there were issues with numerical precision with narrow / small triangles; I rewrote the inside triangle function to use the cross product, which helped (this seems like the simplest way, and it avoids divisions!):

let insidetri a b c d = 
	cross (sub b a) (sub d a) > 0.0 &&
	cross (sub c b) (sub d b) > 0.0 &&
	cross (sub a c) (sub d c) > 0.0 

as well as the segment-segment intersection algorithm:

let intersect a b c d = 
	(* see if two line segments intersect *)
	(* return the point of intersection too *)
	let ab = sub b a in
	(* a prime is the origin *)
	let bp = length ab in
	let xx = norm ab in
	let yy = (-1.) *. (snd xx) , (fst xx) in
	let project e = 
		(dot (sub e a) xx) , (dot (sub e a) yy)
	let cp = project c in
	let dp = project d in
	let cd = sub dp cp in
	let m = (fst cd) /. (snd cd) in
	let o = (fst cp) -. m *. (snd cp) in
	let e = add (scl ab (o /. bp)) a in
	(* cp and dp must span the x-axis *)
	if ((snd cp) <= 0. && (snd dp) >= 0.) || ((snd cp) >= 0. && (snd dp) <= 0.) then (
		if o >= 0. && o <= bp then ( true, e )
		else ( false, e )
	) else ( false, e )

Everything was very sensitive to ">" vs. ">=" -- all must be correct. All triangles must be CCW, too, for the inside algorithm to work - this requires that points to be inserted close to a triangle edge must be snapped to that edge to avoid any possible CW triangles. (Determining if a triangle is CW or CCW is as simple as measuring the sign of the smallest cross product between two segments). I tried, for a day or so, to include a specialized function to insert points along a triangle's edge, but that turned out not to matter; the normal flipping routine works fine. I also tried inserting auxiliary points to try to break up very small triangles, but that really didn't affect the stability of the algorithm much. It is either correct, or it is not, and my large board was a good test suite. I have, however, seeded the triangularization with a grid of (up to) 20x20 points (this depends on the aspect ratio of the region to be filled - the points are equally spaced in x and y). This adds (max) 800 triangles, but it makes the algorithm more stable - fewer very narrow triangles - and we are working with sets of 10,000 triangles anyway for the large zones of copper.

Some corrections remain to be done regarding removing triangles based on DRC violation and using the linked-mesh of triangles when calculating edge-triangle edge intersection, but that should be relatively minor. Now I have to figure out how to store it in Kicad's ".brd" file format. Kicad uses "Kbool" library for intersection polygons - much faster than my triangle methods (well, it's in C not ocaml) - and generates concave polygons not triangles. Would prefer to do this so that I don't have to re-implement gerber export. (Of course, look at how much I have re-implemented! This was originally a project just to learn ocaml - Well, gotta have some fun :-)

hide / / print
ref: -0 tags: perl xml duplicate entries james date: 11-03-2008 21:48 gmt revision:2 [1] [0] [head]

A friend has many Excel files that he converts to labels for affixing to packages to be shipped. To print the proper number of labels (rather than one label with Qty=20), he needs to duplicate rows in the source excel file based on the Qty column. If you export the excel file to XML, this script should do the trick (you'll have to import the resultant XML):

$narg = $#ARGV + 1; 
if( $narg ne 2 ){
	print "please specify the file to read followed by the file to write on the command line\n"; 
	$source = $ARGV[0]; 
	$dest = $ARGV[1]; 
	local( $/) ;
	$/ = ""; 
	open(FH, "< $source"); 
	open(FHO, "> $dest"); 
	$j = <FH>; #slurp the entire file into one string. 
	# look for the header - 
	if( $j =~ s/(.*?)<Sheet1>/<Sheet1>/s){
		print FHO $1 ; 
	while ($j =~ /(<Sheet1>.*?<\/Sheet1>)/gs ){
		$newl = $1; 
		if( $newl =~ /<Qty>(\d+)<\/Qty>/ ){
			$qty = $1; 
			$newl =~ s/<Qty>\d+<\/Qty>/<Qty>1<\/Qty>/ ; 
			for( $g=0; $g<$qty; $g++){
				print FHO $newl ; 
	print FHO "</dataroot>" ; # assume that the footer is always this 
	close FH; 
	close FHO; 
not very complicated, but worth posting, I guess. More examples on the internet = better ;-) Note that I hard-coded to split on <Sheet1> -- check your XML files!!

hide / / print
ref: notes-0 tags: ocaml run external command stdin date: 09-10-2008 19:32 gmt revision:1 [0] [head]

It is not obvious how to run an external command in ocaml & get it's output from stdin. Here is my hack, which simply polls the output of the program until there is nothing left to read. Not very highly tested, but I wanted to share, as I don't think there is an example of the same on pleac

let run_command cmd = 
	let inch = Unix.open_process_in cmd in
	let infd = Unix.descr_of_in_channel inch in
	let buf = String.create 20000 in
	let il = ref 1 in
	let offset = ref 0 in
	while !il > 0 do (
		let inlen = Unix.read infd buf !offset (20000- !offset) in
		il := inlen ; 
		offset := !offset + inlen;
	) done; 
	ignore(Unix.close_process_in inch);  
	if !offset = 0 then "" else String.sub buf 0 !offset

Note: Fixed a nasty string-termination/memory-reuse bug Sept 10 2008

hide / / print
ref: bookmark-0 tags: jocaml ocaml join calculus date: 06-17-2008 15:04 gmt revision:0 [head]

why do threads suck in ocaml? because join calculus is better! (well maybe) http://jocaml.inria.fr/

example of jocaml working well (indeed, faster than everything else): http://eigenclass.org/hiki/wide-finder-conclusions

hide / / print
ref: bookmark-0 tags: C lisp programming unix worse better XML JSON date: 04-29-2008 18:21 gmt revision:1 [0] [head]

hide / / print
ref: bookmarks-0 tags: OCaml books date: 04-05-2008 22:20 gmt revision:2 [1] [0] [head]

Ocaml books / references:

hide / / print
ref: notes-0 tags: cairo ocaml cvs date: 03-11-2008 02:36 gmt revision:3 [2] [1] [0] [head]

cairo-ocaml is broken in Debian (lenny) in that it is incompatible with liblabl-gtk2 in the repository; to compile ocaml programs (e.g. Geoproof) that depend on it, you need to :

  1. sudo apt-get install liblablgtk2-ocaml-dev
  2. get http://cairographics.org/snapshots/cairo-1.5.12.tar.gz, unpack, configure, make, make install.
  3. get the cvs version of cairo-ocaml (which apparently has not been touched in a few years..)
    1. cvs -d :pserver:anoncvs@cvs.cairographics.org:/cvs/cairo co cairo-ocaml (cvs syntax is confusing. I'm glad we have svn now)
    2. aclocal -I support
    3. autoconf
    4. ./configure (ignore complaints about LIBSVG_CAIRO)
    5. make
  4. oh, and make note of this (essential if you are using ocamlopt, the native compiler)

hide / / print
ref: bookmark-0 tags: Ocaml python paradox programming finance date: 03-10-2008 21:29 gmt revision:2 [1] [0] [head]

  • this trading firm used OCaml, apparently to exclusion: http://www.janestcapital.com/yaron_minsky-cufp_2006.pdf
  • they also reference the python paradox. interesting, I'll have to check into Ocaml.
  • or, rather, Lisp. this article is quite convincing!
    • quote: If you're trying to solve a hard problem with a language that's too low-level, you reach a point where there is just too much to keep in your head at once.
    • quote: Any sufficiently complicated C or Fortran program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp.
      • well, yes, this happened a bit in BMI with variables that were indexed by name :(
  • also see this excellent, extensive article.

hide / / print
ref: notes-0 tags: Firefox MathML fonts Linux STIX date: 0-0-2006 0:0 revision:0 [head]

okay, so i spent some time on this and eventually realized that linux doesn't (can't) have all the symbols of the windows fonts used in MathML (for example the pitchfork symbol). The general solution, as per http://mcelrath.org/Notes/MathML, is not so difficult:

  1. install the tex and Mathematica fonts
  2. install opensymbol Debian package, which includes an (incomplete) symbol.ttf font. (the symbol.ttf from windows seems not to work??)
  3. uncomment the lines in /usr/share/firefox/res/fontEncoding.properties:
encoding.symbol.ttf = Adobe-Symbol-Encoding encoding.symbol.ftcmap = mac_roman
  1. some uncommon symbols like the hat and pitchfork are still missing. however, fc-cache | grep Symbol reads:
OpenSymbol:style=Regular Standard Symbols L:style=Regular Symbol:style=Regular
  1. hmm.. .it appears that I have another symbol font.
cd /usr/X11R6/lib/X11/fonts/Type1 sudo rm Symbol* sudo mkfontscale sudo mkfontdir fc-cache ... still there (and the pitchfork still doesn't work :( ) Well, STIX fonts should be out soon, as of Jan20 2006 they have < 400 glyphs to go.