32leaves.net

The Hexapod’s comming to life

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.

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

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.

Learn instead of building time machines

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.

Got root?

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.

Spectral graph drawing

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

    \[i\]

th 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

Fork me on GitHub