A world in dk(decay/denmark) http://rotand.dk Just another pointless weblog Sat, 30 Nov 2013 21:03:48 +0000 en-US hourly 1 https://wordpress.org/?v=4.3.18 Drawing circles http://rotand.dk/2013/11/30/drawing-circles/ http://rotand.dk/2013/11/30/drawing-circles/#comments Fri, 29 Nov 2013 23:00:18 +0000 http://rotand.dk/?p=256 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?


http://rotand.dk/2013/11/30/drawing-circles/feed/ 0
LED’s not sky – light http://rotand.dk/2012/03/18/leds-not-sky-light/ http://rotand.dk/2012/03/18/leds-not-sky-light/#comments Sun, 18 Mar 2012 16:31:09 +0000 http://rotand.dk/?p=221 Netto had 5m LED-light strips, Helle got the god idea, now we have this nifty light:

P1090447 P1090448 P1090449 ]]>
http://rotand.dk/2012/03/18/leds-not-sky-light/feed/ 1
Saturday eggbotting http://rotand.dk/2012/03/17/saturday-eggbotting/ http://rotand.dk/2012/03/17/saturday-eggbotting/#comments Sat, 17 Mar 2012 21:08:46 +0000 http://rotand.dk/?p=239 Eggbotting “Open Space Aarhus”

I measured the egg using the probe.

Create the path in in inkscape using gcodetools.

In a postprocess i first split the path in to short segments, then I linearly interpolate based on the measured data to follow the surface.

In this eggsperiment I used G64 to allow the machine some tolerance in following the path to gain a better feedrate. The result were at significantly different sound from the steppers, it sounds more ‘sick’. But it worked

See the video @ vimeo : http://vimeo.com/38699800

The next step is to try to make TSP art on the eggs, Nikolai Tesla made from a single line , Evil Mad scientists have nice guide: http://wiki.evilmadscience.com/TSP_art

http://rotand.dk/2012/03/17/saturday-eggbotting/feed/ 0
Eggciting data http://rotand.dk/2012/03/14/eggciting-data/ http://rotand.dk/2012/03/14/eggciting-data/#comments Tue, 13 Mar 2012 22:56:40 +0000 http://rotand.dk/?p=231

These data were made with a ‘FrakenProbe’ they represent the surface height, X(length) and A(rotational)axis.

The experience with the first test run proved that even though the penholder does have some play in the z direction, the plot could be better if the pen were to follow the surface of the egg exactly.  Now its possible to probe the surface and the next step is to interpolate the movements based on the data.

A video of the frakenprobe in action on vimeo : http://vimeo.com/38466340

The gcode to probe the data were my first experience with writing loops in gcode and making extensive use of parameters. I must admit that it not pretty, this is the main part with a nested loop:

(PROBEOPEN data.txt)
G0 Z[#<SAFEZ>]
#<J> = 0
o200 DO
G0 A[#<J> * #<ASTEP>] Z[#<SAFEZ> + <#PZ>]
#<I> = 0
o100 DO
G0 X[#<I> * #<XSTEP>] Z[#<SAFEZ> + <#PZ>]
G38.2 Z[#<PZ]
#<PZ> = [#5063]
#<I> = [#<I> + 1]
o100 WHILE [[#<I> * #<XSTEP>] lt #<W>]
#<J> = [#<J> + 1]
o200 WHILE [[#<J> * #<ASTEP>] lt 360]

Did i mention that it is really really nice to have a hackerpace, with tools, parts, club mate and geeks who can help out when you are stuck.

http://rotand.dk/2012/03/14/eggciting-data/feed/ 0
Eggbot first print http://rotand.dk/2012/03/10/eggbot-first-print/ http://rotand.dk/2012/03/10/eggbot-first-print/#comments Sat, 10 Mar 2012 20:17:23 +0000 http://rotand.dk/?p=222

A penholder was made, its basis is the insides from a CD-ROM drive the pen is molded into place using Shapelock.

An Egg was mounted and some quick test pattern were made in Inkscape.

We step back and observe the magic.

Unfortunately i dropped the first real image, the first test run were spirals and a hardboiled egg.

There are still issues to work out, but all in all we are quite satisfied with the first test.

http://rotand.dk/2012/03/10/eggbot-first-print/feed/ 0
It nice to have a hackerspace http://rotand.dk/2012/02/25/it-nice-to-have-a-hackerspace/ http://rotand.dk/2012/02/25/it-nice-to-have-a-hackerspace/#comments Sat, 25 Feb 2012 19:25:41 +0000 http://rotand.dk/?p=213

Parts laying around, access to all the necessary tools and soon this will be an eggbot. It shall be mounted on a CNC machine as a rotary axis.

We will have machine painted easter eggs  at  Open Space Aarhus


http://rotand.dk/2012/02/25/it-nice-to-have-a-hackerspace/feed/ 0
DTMF dialer got new features http://rotand.dk/2009/06/27/dtmf-dialer-got-new-features/ http://rotand.dk/2009/06/27/dtmf-dialer-got-new-features/#comments Sat, 27 Jun 2009 17:14:29 +0000 http://rotand.dk/blog/?p=198 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.


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)

http://rotand.dk/2009/06/27/dtmf-dialer-got-new-features/feed/ 0
CNC for summerproject http://rotand.dk/2009/06/06/cnc-for-summerproject/ http://rotand.dk/2009/06/06/cnc-for-summerproject/#comments Sat, 06 Jun 2009 08:24:41 +0000 http://rotand.dk/blog/?p=189 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


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.


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”

http://rotand.dk/2009/06/06/cnc-for-summerproject/feed/ 2
CLI voip calls http://rotand.dk/2009/05/03/cli-voip-calls/ http://rotand.dk/2009/05/03/cli-voip-calls/#comments Sun, 03 May 2009 08:13:27 +0000 http://rotand.dk/blog/?p=178 front1
Sometimes it would be nice to use a script call somebody and play a message.
I “needed” a wake-up-call system and since I use a voip-phone and have access to a server. I thought i would be quite nifty if I could have the server call me. Furthermore i would like to be able to script calls, so for instance the calendar could call me with reminders rather than sending an email.

I googled around but weren’t able to find such a utility. But i did find cli-sip client pjsua, based on pjsip. Its posible to use it in conjunction with a shell script.


jacob@vps:~./control.sh sip:108329@foobar.com "wake up you lazy bastard!"
Is the basic usage i wanted to have. In order to get this functionality there are two steps.

Generating wav file

I ust use text2wave, from festival, which is available as a package on ubuntu.
echo $2 | text2wave - -o message.wav

$2 to use the second argument, and pipe it to text2wave. Let text2wave read sdtin and output a file message.wav

Call and play the wav file

pjsua_app --config-file=test.conf --play-file message.wav $1
Here the magic is in the conf file. Its a rather straightforward to use, and the documentation is good.

# we don't want the host's audio device
# SIP parameters
--realm domain.com
--registrar sip:number@domain.dk # DNS SRV, or FQDN

--username USERNAME
--password PASS
# default of 55 will be rejected as being too short by sipX
--reg-timeout 3600
# auto-answer all calls with "200 OK"
--auto-answer 200
# automatically loop incoming RTP to outgoing RTP
# mix WAV file into the audio stream


This is based on a config file i found somewhere, can’t remember where. There a a lot of other options, pjsua handles nat quite nicely as well. It was easy to test it at my homebox, behind a router, just be sure to set an external ip address.

Now this will call and play the message, but it wont stop pjsua. It will just sit around waiting for someone to call. I couldn’t find any nice way to handle this, but since pjsua reads stdin for commands, it possible to pipe commands to it.
echo "sleep 60000 q" | pjsua_app --config-file=test.conf --play-file message.wav $1
So sleep for 60 seconds, then accept the next input from stdin, the “q”uit command.

Generally this configuration is set for 1 minute, it might be necessary to tweak this.


There is/were a bug in the tarball, that meant that it wouldn’t run if it couldn’t find a soundcard, since it should run on a vps this is quite annoying. But in the svn version its solved, so if you want to do something like this, use the svn version. Other than this installation is straightforward.

When working with cron, remember to use full paths. In the control.sh script the better solution were to add a cd working directory, in order to have all the paths correct. This were quite annoying to debug, as the script would run from the shell. And just fail when added to the crontab. Furthermore mails from crontab were delayed, so i couldn’t see the output. I did get someone to look over my shoulder and spot the bug.

http://rotand.dk/2009/05/03/cli-voip-calls/feed/ 2
Steppers http://rotand.dk/2009/05/02/steppers/ http://rotand.dk/2009/05/02/steppers/#comments Sat, 02 May 2009 16:49:56 +0000 http://rotand.dk/blog/2009/05/02/steppers/ Just ripped apart an old scanner and printer to get the steppermotors. Unfortunatly both seems to be bipolar steppers, hence i would need a H-bridge to drive them. I only have few darlington arrays around.

It would have been fun get a quick hack up and running today.

http://rotand.dk/2009/05/02/steppers/feed/ 0