32leaves.net
Cool, you're reading my blog. Hope you like it. You may wanna check my twitter page, too

The Hexapod’s comming to life

July 31, 2009 – 4:09 pm

As the previous post indicated I’m currently building a hexpod (together with two co-students of mine). Now as the hardware is pretty much finished (except for the power-setup and some cable stuff) I wanted to share some pictures of it. All in all it came out pretty neat. I’m sorry for the bad quality … as I did not have a camera at hand I used my mobile phone to take the pictures.




By Christian | Posted in Development | Tagged , | Comments (2)

WebKit and CSS: .world { crazy: 100% }

July 20, 2009 – 1:54 am
Today I stumbled upon the latest WebKit nightly build which has the CSS 3D transformations implemented. That is some cool technology. Eye at its best.
After having a look at the truely awesome demos; I hacked together a simplified model of the walking robot we’re currently building. Just be reminded that what you can see on the screenshots below is just HTML, CSS and JavaScript – nothing more. Thinking about what kind of a hazzle it was to get some sort of 3D in the Web using VRML and the Web3D stuff. Of course CSS can’t compete with VRML (yet), but for simple stuff? We’re getting close.
I’m pretty sure that it won’t be long until we see some 3D JavaScript libraries emerging. Something like OpenGL-JS would be cool, based on CSS. Not that this was something completely new, but all based on a W3C standard? There are beautiful times ahead – at least when it comes to eye-candy.



By Christian | Posted in Development | Tagged , | Comments (3)

Learn instead of building time machines

July 8, 2009 – 5:25 pm

Today I kinda messed up one of my exams (at least it feels like it). It’s probably not going to be an F, but not as good as I would like it to be. Because of that I felt inspired to “draw” a short comic in the style of by XKCD (altough not as pretty as the XKCD comics are):
comic

By the way, that WOOP is the sound the universe makes when it implodes.

By Christian | Posted in Fun | Tagged , | Comments (1)

Got root?

July 5, 2009 – 10:42 pm

Today I rooted my T-Mobile G1. Now I got the awesome CyanogenMod 3.6.2 (based on Android 1.5rc2) and the HTC hero theme running. Looks pretty cool and runs as hell.

Hopefully now I can connect to my universities network which requires WPA2 enterprise. One needs root access in order to modify the wpa_supplicant.conf to connect to a WPA2 enterprise network.

htc_hero

This screenshot is exactly what my phone looks like right now, but it gives you an idea.

By Christian | Posted in Fun | Tagged | Comments (0)

Spectral graph drawing

July 1, 2009 – 1:10 am
Whenever I attend a lecture about some topic, I tend to gather some more information about that particular field than the lecture itself provides. This time it’s about graph theory. While I was reading about graph drawing algorithms, I stumbled upon something called spectral graph theory [2]. In order to get the idea of what this is all about, I started looking thru the presentation on spectral graph theory [2] and reading a few [15] papers [8] on this topic.
Note: Please forgive me my formal imprecision. If anyone feels “offended” by this, she might want to read the papers instead.
The basic idea behind all this theory is to compute the eigenvectors [5] of the laplacian matrix [6] of a graph. Then sort the eigenvalues in ascending order (thus the eigenvectors are sorted, too). Then if v_0,\dots,v_n are the eigenvectors and \lambda_0,\dots,\lambda_n the according eigenvalues of the laplacian matrix of the graph G = (\{k_0,\dots,k_n\}, E) sorted that \lambda_m \leq \lambda_{m+1}, 0<m<n, the position vector for vertex k_i is \begin{bmatrix}v_1(i) \\ v_2(i)\end{bmatrix} where v_k(i) denotes the ith component of the eigenvector v_k.
Due to reasons explained in the papers [15] [8] this method of graph drawing tends to draw the graph planarily [9]. Thus large graphs (especially mesh graphs) tend to look pretty good if drawn like this.
Heaving understood the theory (at least most of it), I wanted to try things out. So I got some test data [10], wrote a small ruby script which converted the PARTY format [11] (or at least a subset of it) into a text-based matrix format, so that Octave [12] was able to read the ajency matrices [13] of the graphs. Let D denote the degree matrix [14] of the graph and A the adjency matrix, then the laplacian matrix is L=D-A. Now we may calculate the eigenvectors of D. The Octave code below loads some graph’s adjency matrix in text format and calculates the (first three) eigenvectors of the laplacian matrix (basically taken from [15]):

1
2
3
4
load graph.txt;
A = sparse(graph);
L = diag(sum(A)) - A;
[v,d] = eigs(L, 3, 'sm');

Then I plotted the graph using gnuplot (to be more precise: using gplot, Octaves built-in graph plotting functionality). The result was already pretty pleasing:

crack_graph

But I wanted things to look better, so I wrote a MEX file [16] which plotts graphs using OpenCV [17].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "mex.h"
#include <opencv/cv.h>
#include <opencv/highgui.h>

#define SCALE  40000
#define IN_ADJ prhs[0]
#define IN_XY  prhs[1]

#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))
#define XY(i)    (int)((xyOffset + xy[i]) * SCALE)

void mexFunction (int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {
   
    if(nrhs < 2) mexErrMsgTxt("expects two parameters: adjency matrix (sparse, n times n), xy vector (n times 2)");
    if(! mxIsSparse(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be sparse");
    if(mxGetM(IN_ADJ) != mxGetN(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be square");
    int n = mxGetN(IN_ADJ);
    int nz = mxGetNzmax(IN_ADJ);
   
    if(mxGetN(IN_XY) != 2 || mxGetM(IN_XY) != n) mexErrMsgTxt("XY vector must be (n times 2)");

    double *xy = mxGetPr(IN_XY);
    double *adj = mxGetPr(IN_ADJ);
   
    // get dimensions
    int i, j;
    double xyOffset = 0, maxX = 0, maxY = 0;
    for(i = 0; i < n; i++) {
        if(xy[i] < xyOffset) xyOffset = xy[i];
        if(xy[i] > maxX) maxX = xy[i];
    }
    for(i = n; i < 2*n; i++) {
        if(xy[i] < xyOffset) xyOffset = xy[i];
        if(xy[i] > maxY) maxY = xy[i];
    }
    xyOffset = -xyOffset;
    maxX += xyOffset;
    maxY += xyOffset;
   
    mexPrintf("img size: %i x %i, xyOffset: %f, maxX: %f, maxY: %f\n", (int)(maxX * SCALE), (int)(maxY * SCALE), xyOffset, maxX, maxY);
    IplImage *img = cvCreateImage(cvSize((int)(maxX * SCALE), (int)(maxY * SCALE)), IPL_DEPTH_8U, 3);

    int *ir = mxGetIr(IN_ADJ);
    int *jc = mxGetJc(IN_ADJ);
   
    int total = 0;
    CvPoint p1, p2;
   
    for (i=0; i<n; i++)  {
        p1.x = XY(i);
        p1.y = XY(n + i);
       
        int starting_row_index = jc[i];
        int stopping_row_index = jc[i+1];
        if (starting_row_index == stopping_row_index) continue;
        else {
            for (j = starting_row_index; j < stopping_row_index; j++)  {
                p2.x = XY(ir[j]);
                p2.y = XY(n + ir[j]);
               
                cvLine(img, p1, p2, cvScalar(255,128,255,0), 1, CV_AA, 0);
               
            //  mexPrintf("\t(%d,%d) = %g || (%i %i) -- (%i %i)\n", ir[j]+1, i+1, adj[total++], p1.x, p1.y, p2.x, p2.y);
            }
        }
    }
   
    if(!cvSaveImage("/tmp/gr.png", img)) mexErrMsgTxt("Unable to write /tmp/gr.png");
    cvNamedWindow("mainWin", CV_WINDOW_AUTOSIZE);
    cvShowImage("mainWin", img );
    cvWaitKey(20);
   
}

That code was used to produce the following graphs (except for the blue one, my WordPress simply can’t exclude images in a gallery):





With something looking that cool in my hands, I simply had to create posters out of that. So I postprocessed two graph images and ordered prints (the two black and white images). That stuff is fun, and extremly interessting. I’ll for sure do some further investigation on this topic.

References

By Christian | Posted in Maths, Studies | Tagged , | Comments (0)