Archive for the ‘Programming’ Category.

Drawing circles

300 random spheres added and normalized

300 random spheres added and normalized

As part of my PhD research I had to implement discrete Sibson interpolation , to do some nifty interpolation. Sibson interpolation is a scheme based on areas of Voroni regions which can be quite complex. But for the discrete case Park et al presents a nice and simple scheme.

  1. For each pixel find the nearest neighbor ( of the points you are interpolating between)
    1. Draw a circle with radius = distance(this, nearest neighbor)
  2. Normalize, divide each raster color with the number of circles that contributed.

The first, and very importantly functional, implementation of the circle drawing routine was a simple double loop. It worked, but it nagged me that it was slow and it seemed like a fun problem. So I went home an wrote a small program to draw circles and test the speed. The top image show such a case.

You can find the code on github:  https://github.com/jtpedersen/draw-circles

I made a small test framework just to have some fun trying to optimize the drawing. The authors of the paper use a shader and somewhat similar to this transforms each point into a quad and only draws within the circle. I needed to do it on CPU for now.

Drawing 512^2 random circles in this manner takes my laptop around 10 seconds.  It is obviously to slow and inefficient. The method it self is not good, as it access the same pixels multiple times to addColor. So the first trick was to turn it in to a two-stage algorithm. First note where each circle starts and ends on each row.  Now the central loop does not depend on the area but the circumference of the circle.  The second stage is scanning through the temporary buffer and accumulating the results.

To calculate the start and end point we scan the y axis and for each row we determine the x-offset. The formula for the circle is (x – x0)^2 + (y-yo)^2 = r^2. We can assume x0 and y0 is zero, the circle is centered at (0,0) for the calculation and then do the offset calculation afterwards. Since we now y we just have to solve for x, diff = sqrt(r^2-x^2). In the extra buffer we then store color at (y, xo -diff) and -color ar (y, xo+diff+1), so scanning is adding the value in the extra buffer into an accumulator and writing it into the same place in  output buffer. I also made a version with two extra buffers, one for enterPixel the other for exit, but this is not necessary.

 

The circumference of circles, before the scan.

The circumference of circles, before the scan.

Even though this is a two-stage algorithm it is much faster. It is down to  655 msec. For the case with 512^2 random circles. It is worth noting that the radius of the circles is restricted to 10% of the width of the image, as this seemed like a fairly large value, yet still realistic.

I could not come up with a better algorithm, maybe you can?

A little complexity analysis. Assume that worst case is all circles have a radius that is so large that we have to paint all pixels in a n*n grid. The naive version will then for m updates do m * n^2 and the smarter version will only do m * 2 *n + n^2 work. if we assume that m ~ n^2 we have that the naive algorithm runs in O(n^2 * n^2) = O(n^4) and the smart in just O( n^2 * 2 * n + n^2) = O(n^3).

Since I ran out of good ideas I went for the next best thing, trying to optimize. This would be the ideal time to start a profiler, I like Kcachegrind. But i had inserted timings and an idea of a culprit, the square root. So I did the next best thing commented the line out and observed the incredible speed up. Down to 200 msec. However we still have to calculate the value.

There are clever algorithms for integer square root, but I did have the advantage of knowing the range and that it was rather small. All values would be less than the largest radius^2, for these test cases that would be < (512 * .1)^2 = 2621.4< 2^13 = 8192. So the simple thing to try was to use a lookup table low and behold we are up to 277 msec but we actually calculate the right value.

Since memory access is always best to do in order and the randomness of the input really destroys locality, i thought that it could be interesting to see what would happen if the points were in order. So as i quick hack i sorted the points based on the y coordinate of the center of the circles. This cut off another 100 msecs and yet sorting took only 20 msecs, so a net gain of 80 msecs. (for the interpolation case the input will actually be sorted)

This is where i stopped, but what should be the next step? I compile with gcc and use -O3. I quick look at the assembly shows that gcc uses sse instructions, but this could perhaps be pursued? I initially thought that i could get a speed up from scanning in parallel, but my timings says that scanning only takes few msecs. I would like to parallelize the setting the values, but it is not as trivial as there are obvious concurrency issues. Maybe just a mutex pr row and everything would be fine.

Anyhow down from 10 secs to just shy of .2 sec is quite alright in my book. Could it be improved? What would be the next step? generate all events (start /stop) put them in a list, sort and scan through this instead of a n*n buffer?

 

DTMF dialer got new features

I got a comment from a reader who used my DTMF dialer but missed a feature.

It was the ability to change what prefix to remove. As i live in Denmark, whenever i make a call on a land-line there is no reason to dial +45, which is the danish country code. Actually the plus is converted into 00 as well.

But Eli needed the prefix 08 to be removed.

And i guess that there are a lot of other prefixes that could be removed and + shouldn’t always be converted to 00. So I decided to implement this feature.

Whats new

  • It now remembers your settings
  • It possible to choose a prefix to remove
  • its possible to decide what + should be replaced by.
  • I slapped a GPL V3 license on it

The files

dtmfdialer jad file

dtmfdialer jar file

dtmfdialer source code

Unfortunately it wasn’t just a 5 min hack. There were two major challenges.

Persistence

In J2me access to the filesystem is restricted and requires all sorts of security permissions, but every application has access to a “RecordStore”. The RecordStore (RMS) only allows byte[] to be stored, so you have to marshall/unmarshall every piece of data at quite a low level. I haven’t persisted any data in the first version, as this is indeed tedious to work with. But not having persistence for a prefix remover functionality wouldn’t be of any use. You would have to enter the same data every time you used the application and then it would be faster to just edit the number to call.

Netbeans mobility pack

It was supposed to be so eays.

But the floweditor somehow did mess up and didn’t generate the code, so the flow diagram and the sourcecode were out of sync, and i didn’t see any way to “resync”/”regenerate code/diagram”. This was cause for a lot of frustrations.

Originally i made it with netbeans so compiling and editing the generated code were best done in netbeans. But if i ever were to mess with it again i would seriosly consider “porting” it to J2me Polish or just “vanillia” j2me. As i really really don’t like the netbeans editor.

update : Eli found a bug in the prefix substitution, i fixed and uploaded the new version (June 27, 2009, 21:17)

CNC for summerproject

I have decided to build a CNC machine in the summer vacation. As soon as I finish the last exams i’ll start building / hacking. For the moment I’m looking into building plans and cnc in general. At first I wanted to build a reprap using a kit, but my funds are limited, so it will be a three axis cnc router which hopefully will be able to act as an repstrap.

The project as it looks so far :
I ordered a set with steppers, motor-control and psu from ebay, and I’m waiting for it to arrive(The seller said 10-12 days, so maybe if I am lucky next week). It should be 1.7NM motors and a more or less “plug’n’play” set.

I intend to drive the motors using a old computer running linuxcnc. linuxcnc looks real neat, but might prove to be hard to set up.

The construction

I am looking at two set of plans at the moment

How-to-Make-a-Three-Axis-CNC-Machine-Cheaply

This was the building plan that made me decide that this was a possible task. But there are some issues with the construction I don’t like, especially that it uses belts. They are hard to find and they are not cheap.

JGRO’s plans

This is a free diy plan. it can be found here : http://www.cncroutersource.com/cnc-router-plans.html

It uses threaded rod instead of belts. And the overall construction looks simpler.

Materials

Although I do want to do “fabbing” using a extruder at first I think that there will be enough work for a couple of days getting the mechanics and electronics up and running. Just as there is a lot to learn about g-code and all sorts of 3dmodelling.

To begin with I want to cut using a dremel tool, maybe a more powerful spindle(?) to be able to cut wood – if I have enough power in the steppers.

You might ask what do you want to make / “fab” with a 3 axis cnc machine?  I can come up with a lot of different small things like “coat hanger”, “coffee filter”, “PCBs” but I guess that it just boils down to: ” I think its a very fascinating technology and want to play with it”