20131205

Thread-safe Java Swing initialization in Jython

Java's Swing API is not thread-safe: initialization and manipulation of Swing components must be done only from the event dispatch thread (EDT). Programmers must use verbose idioms to initialize Swing components on the EDT.

Jython is a Python interpreter which runs on top of Java. It provides the functionality of Python, plus a "pythonic" way to interact with existing Java APIs.

Consider initializing a Swing application in Jython. According to specifications, even constructing Swing components on the Main thread like this can be unsafe.
 from javax.swing import *  
 jf = JFrame("Hi")  
 jf.contentPane.add(JButton("does nothing"))  
 # more unsafe initialization here  
 # ...  
 jf.pack()  
 jf.visible = 1  
This code might seem OK, or it might crash intermittently and only on some platforms. The only way to conform to specifications is to move this initialization onto the event dispatch thread. The classic Java idiom to achieve this is to wrap the initialization code in a new subclass of Runnable, and pass this Runnable to the event dispatch thread to be executed. In Jython, this looks something like
 from javax.swing import *  
 from java.awt import EventQueue  
 from java.lang import Runnable  
 class initializeApp(Runnable):  
   def run(self):  
     global jf  
     jf = JFrame("Hi")  
     jf.contentPane.add(JButton("does nothing"))  
     # more unsafe initialization here  
     jf.pack()  
     jf.visible = 1  
 EventQueue.invokeAndWait(initializeApp())  
This is a little verbose in Python, and would be significantly verbose in Java, to the point where programmers would prefer some sort of macro to simplify the process. The Python language feature of "decorators" provides this. In Python, decorators are functions which enhance or modify other functions. They are implemented as a Python function that accepts and returns functions as an argument. Here is a Python decorator that will transform any function into a version which is thread-safe for Swing:
 from java.awt import EventQueue  
 from java.lang import Runnable  
 def EDTsafe(function):  
     def safe(*args,**kwargs):  
         if EventQueue.isDispatchThread():  
             return function(*args,**kwargs)  
         else:  
             class foo(Runnable):  
                 def run(self):  
                     self.result = function(*args,**kwargs)  
             f = foo()  
             EventQueue.invokeAndWait(f)  
             return f.result  
     safe.__name__ = function.__name__  
     safe.__doc__ = function.__doc__  
     safe.__dict__.update(function.__dict__)  
     return safe  
Using this decorator, we can do thread-safe Swing initialization succinctly
 from javax.swing import *  
 @EDTsafe  
 def initializeApp():  
     global jf  
     jf = JFrame("Hi")  
     jf.contentPane.add(JButton("does nothing"))  
     # more unsafe initialization here  
     jf.pack()  
     jf.visible = 1  
 initializeApp()  
There is also the option of using the decorator in one-line lambda functions, for example
 EDTsafe( lambda: jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE) )()  

20130722

Small, pure Javascript video feedback demonstration

Sorry, your browser does not support canvas.
The demonstration should load (above), on most browsers. You may need to whitelist Javascript for crawlingrobotfortress.blogspot.com to view it. I must admit I'm not 100% certain how to embedd javascript on Blogger posts reliably. Let's see if it works. Mouse over the canvass to adjust the feedback controls.
Here is the source code:
<center>
<canvas height="1" id="feedbackcanvas" width="1"> Sorry, your browser does not support canvas and/or Javascript. </canvas> 

<script type="application/javascript"> 
function feedback(){
    var N = 512;
    var N2 = N/2;
    
    // Initialize canvas data structures
    var feedbackcanvas = document.getElementById('feedbackcanvas');
    feedbackcanvas.width = N;
    feedbackcanvas.height = N;
    var ctx = feedbackcanvas.getContext('2d');
    var imageData = ctx.getImageData(0, 0, N, N);
    
    // Initialize color map
    var colormap = new Uint32Array( 256 );
    for (var i=0; i<256; i++) {
        var hue = 6.0*i/256;
        var r=0;
        var g=0;
        var b=0;
        var C=250;
        if (hue<1) { r+=C; g+=C*hue; } 
        else if (hue<2) { r+=C*(2-hue); g+=C; } 
        else if (hue<3) { g+=C; b+=C*(hue-2); } 
        else if (hue<4) { g+=C*(4-hue); b+=C; } 
        else if (hue<5) { r+=C*(hue-4); b+=C; } 
        else { r+=C; b+=C*(6-hue); } 
        r = Math.round(r);
        g = Math.round(g);
        b = Math.round(b);
        color = 0xff000000 | (r<<16)|(g<<8)|b;
        colormap[i] = color;
    } 
    
    // Compute lookup table map
    var map = new Uint32Array( N*N*2 );
    for (var y = 0; y < N; ++y) {
        for (var x = 0; x < N; ++x) {
            var real = (x-N2)*4.0/N;
            var imag = (y-N2)*4.0/N;
            var real2 = real;
            var imag2 = imag;
            var x2 = Math.round((real2*N/4+N2)*256);
            var y2 = Math.round((imag2*N/4+N2)*256);
            var index = y*N + x;
            map[index*2 ] = x2;
            map[index*2+1] = y2;
        } 
    } 
    var recurrentBuffer1 = new Uint8Array( N*N + 1);
    var recurrentBuffer2 = new Uint8Array( N*N + 1);
    recurrentBuffer1[N*N] = 255;
    recurrentBuffer2[N*N] = 255;
    for (var y = 0; y < N; ++y) 
    for (var x = 0; x < N; ++x) 
    recurrentBuffer1[y*N + x] = x & 0xff;
    offsetx = 64*256;
    offsety = 32*256;
    costheta = 0;
    sintheta = 0;
    function iterate() {
        for (var y = 0; y < N2; ++y) 
        for (var x = 0; x < N2; ++x) {
            var index = y*N + x;
            var x2 = map[index*2 ] - N2*256;
            var y2 = map[index*2+1] - N2*256;
            var x3 = (costheta * x2 + sintheta * y2 >> 8) + N2*256 + offsetx;
            var y3 = (costheta * y2 - sintheta * x2 >> 8) + N2*256 + offsety;
            var xi = x3 >> 8;
            var yi = y3 >> 8;
            var xf = x3 & 0xff;
            var yf = y3 & 0xff;
            var index = xi+yi*N;
            var colorA = recurrentBuffer1[index & 262143];
            var colorB = recurrentBuffer1[index+1 & 262143];
            var colorC = recurrentBuffer1[index+N & 262143];
            var colorD = recurrentBuffer1[index+N+1 & 262143];
            var colorE = colorA*(256-xf)+colorB*xf >> 8;
            var colorF = colorC*(256-xf)+colorD*xf >> 8;
            var color = colorE*(256-yf)+colorF*yf >> 8;
            if (xi>=0 && yi>=0 && xi<n && yi<N) {color += 10;}
            else {color = ~color;} 
            recurrentBuffer2[y*N + x] = color;
            recurrentBuffer2[(N-1-y)*N + x] = color;
            recurrentBuffer2[(N-1-y)*N + (N-1-x)] = color;
            recurrentBuffer2[y*N + (N-1-x)] = color;
        } 
        var temp = recurrentBuffer2;
        recurrentBuffer2 = recurrentBuffer1;
        recurrentBuffer1 = temp;
    } 
    var buf = new ArrayBuffer(imageData.data.length);
    var buf8 = new Uint8ClampedArray(buf);
    var data = new Uint32Array(buf);
    
    // Mouse listener callback
    feedbackcanvas.onmousemove = function(e) {
        var mouseX, mouseY;
        if(e.offsetX) {
            mouseX = e.offsetX;
            mouseY = e.offsetY;
        } 
        else if(e.layerX) {
            mouseX = e.layerX;
            mouseY = e.layerY;
        } 
        mouseX -= N2;
        mouseY -= N2;
        offsetx = mouseX*256;
        offsety = mouseY*256;
        mouseTheta = Math.atan2(mouseX,mouseY);
        mouseRadius = 300;
        costheta = Math.cos(mouseTheta)*mouseRadius;
        sintheta = Math.sin(mouseTheta)*mouseRadius;
    };
    
    function render() {
        iterate();
        for (var y = 0;y < N;++y) {
            for (var x = 0;x < N;++x) {
                var value = recurrentBuffer2[y*N+x];
                data[y*N + x] = colormap[value];
            } 
        } 
        imageData.data.set(buf8);
        ctx.putImageData(imageData, 0, 0);
        setTimeout(render, 10);
    } 
    setTimeout(render, 66);
} 
</script> 
<body onload="feedback()"></body>
</center>

20130615

Optimizing a hue rotation operator

This post covers hue-rotation as a rotation in 3D color space, and optimizes this rotation to minimize floating point multiplications using a trick borrowed from Gauss' algorithm for multiplying complex numbers.

Hue rotation is a shift of the hue in a HSV or HSL color model, example: 


I am interested in implementing a hue rotation for Java. The colors are input in RGB format, with each component ranging from 0 to 255.

The first implementation I tested uses HSV color space. It combines an RGB to HSV conversion, hue shifting, and HSV to RGB conversion, into a single series of operations:
float min    = r&ltb?g&ltr?g:r:g&ltb?g:b; 
float value  = r&gtb?g&gtr?g:r:g&gtb?g:b; 
float C= value - min;
if (C!=0.f) { //with no saturation, hue is undefined
        float hue;
        // CONVERT FROM RGB TO HSV
        if      (value==r) hue = 6+(g-b)/C;
        else if (value==g) hue = 2+(b-r)/C;
        else               hue = 4+(r-g)/C;
        // ROTATE THE HUE
        hue += fhuerotate; 
        hue %= 6.f;
        // CONVERT FROM HSV TO RGB
        r=g=b=min;
        switch((int)hue) {
                case 0: r+=C; g+=C*hue; break;
                case 1: r+=C*(2-hue); g+=C; break;
                case 2: g+=C; b+=C*(hue-2); break;
                case 3: g+=C*(4-hue); b+=C; break;
                case 4: r+=C*(hue-4); b+=C; break;
                case 5: r+=C; b+=C*(6-hue); break;
        }
}
This approach is decent. The branching associated with the different hues is cheap on the CPU, and there aren't that many floating point multiplications or divisions. The hue space is mapped to [0,6) rather than [0,2π), which simplifies the computation.

It is also possible to implement HSV rotation as a linear transformation of the RGB color components. To start, it is possible to derive a notion of hue and chroma that relates to the RGB components without casing on hue. This is taken directly from Wikipedia and more information can be found there.

\[\alpha=\frac{1}{2}(2R - G - B)\] \[\beta =\frac{\sqrt{3}}{2}(G - B)\] \[H_2 =\operatorname{atan2}(\beta, \alpha)\] \[C_2 =\sqrt{\alpha^2 + \beta^2}\]

This gives us a Cartesian representation of hue and chroma. To complete this color space, we need a notion of "brightness". The "value" and "lightness" of HSV and HSL color spaces are defined in terms of the brightest and dimmest color component. Another notion of brightness is simply the average of the three RGB color components, termed "intensity". Intensity facilitates representing hue rotation as a linear transform in RGB space. The intensity value, combined with the cartesian hue and chroma ( or $\alpha$ and $\beta$ ), form a complete colorspace. We can do hue rotation by rotating the Cartesian ($\alpha$,$\beta$) plane, without ever explicitly converting to hue and chroma.

Once you write hue rotation as a transform in the ($\alpha$,$\beta$) plane, and combine that with converting from RGB to our HCI color-space and back, you are left with a linear transformation on the RGB color components. This transformation can be simplified to reduce the number of floating point multiplications. Expensive constants (Q1 and Q2 below) related to the rotation can be computed before iterating over the image.

Compute these as a function of the hue rotation "th" ahead of time, before iterating over the image:
Q1 = sin(th)/sqrt(3)
Q2 = (1-cos(th))/3
Then, for each RGB pixel, the hue rotation is:
rb = r-b;
gr = g-r;
bg = b-g;
r1 = Q2*(gr-rb)-Q1*bg+r;
Z  = Q2*(bg-rb)+Q1*gr;
g += Z + (r-r1);
b -= Z;
r = r1;

Using intermediate constants r1 and Z reduces the number of multiplications, at the expense of adding more additions/subtractions (and possibly reducing numerical stability). It is inspired by Gauss' trick for multiplying complex numbers.

One major difference between the HSV hue rotation and this one is how it treats the chroma component. Subjectively, the brightness of yellow, magenta, and cyan, are kept more equal to red, green, and blue, using this operator. In cases where you want to preserve subjective brightness, this is a good thing. However, this also makes yellows seem less colorful than one might expect for a hue rotation operator. This is related to how chroma is represented in the HCI color space. To paraphrase Wikipedia

The two definitions of chroma ($C$ and $C_2$) differ substantially: they are equal at the corners of our hexagon, but at points halfway between two corners, such as $H=H_2=30^o$, we have $C=1$, but $C_2\approx 0.866$, a difference of about 13.4%.

One patch is to restore the maximum color value after hue rotation. This preserves the "value" of the HSV color model and makes yellows brighter:

max = r&gtb?g&gtr?g:r:g&gtb?g:b;
rb = r-b;
gr = g-r;
bg = b-g;
r1 = Q2*(gr-rb)-Q1*bg+r;
Z  = Q2*(bg-rb)+Q1*gr;
g += Z + (r-r1);
b -= Z;
r = r1;
adjust = max / ( r&gtb?g&gtr?g:r:g&gtb?g:b );
r *= adjust;
g *= adjust;
b *= adjust;

Representing hue rotation as a linear transform is slightly faster on my system, and could be substantially faster in other environments ( e.g. where division is very costly). The subjective performance of these algorithms are comparable. The image at the start of this post was generated using the ($\alpha$,$\beta$) rotation approach without correcting for value.

20130511

Space-filling 3D honeycomb lattices with a laser cutter

The 3D equivalent of a 2D tiling or tesselation is called a honeycomb. (Actual bee honeycombs consist of rhombic dodecahedra, and correspond to the densest possible sphere packing.)

If you have access to a laser cutter (or other way of making precise cuts, or even a 3D printer in a pinch), you can buld your own honeycomb structures. These are attractive design elements and a fun construction toy. This post outlines the general approach and gives two specific examples.

3D honeycombs consist of packed arrangements of polyhedra (tetrahedra, cubes, etc.). To design laser-cut pieces:

  • Build honeycombs by arranging flat pieces according to the faces of these polyhedra. (Generate a set of pieces for each face of the polyhedra in the honeycomb.)
  • Join polyhedron faces in 3D by using additional (flat) notched pieces. Where the edges of different polyhedra meet, calculate the dihedral angles of the joining faces. Create notched joining pieces with these angles.

For most polyhedra, one can simple look up the dihedral angles. But, there is also some nice geometric reasoning behind this: Joining polyhedral faces with flat connecting pieces is equivalent to constructing the dual honeycomb

A dual honeycomb is conceptually similar to a dual tiling or dual polyhedron. In a dual honeycomb, one places a vertex at the center of every polyhedron, and connects these vertices with edges that pass perpendicularly through each face in the original honeycomb. For example, the dual of the rhombic dodecahedral honeycomb (used by bees) is the tetrahedral-octahedral honeycomb

 

Here are two examples: the rhombic dodecahedral honeycomb and the rectified cubic honeycomb.

 

Rhombic dodecahedral honeycomb

 

The rhombic dodecahedra consists of 12 rhombic facets with the long diagonal $\sqrt{2}$ times the length of the short diagonal, creating an acute angle of $\operatorname{arccos}(1/3)$ and obtuse angle of $\pi-\operatorname{arccos}(1/3)$.

The rhombic dodecahedra has two types of vertices: (a) one where the acute angles of 4 rhombi meet, and (b) one where the obtuse angles of 3 rhombi meet. In a honeycomb, (a) connects the 4-rhombus points from 6 dodecahedra, and (b) connects the 3-rhombus points from 4 dodecahedra.

This hints at the structure of the dual honeycomb: we should expect a dual lattice that consits of (1) polyhedra with six vertices, and (2) polyhedra with 4 vertices. Indeed, these correspond to the octahedra and tetrahedra of the tetrahedral-octahedral honeycomb.

The faces of each of the polyhedra in the dual lattice are equilateral triangles. The rhombic dodecahedral honeycomb can therefore be built from the rhombi described above, and equilateral triangles. (we also could have simply looked up that the rhombic dodecahedron has a dihedral angle of 120°)

 

 

Rectified cubic honeycomb

 

The rectified cubic honeycomb (cool rendering) can be constructed from cuboctahedra and octrahedra. The facets of these polyhedra are squares and equilateral triangles, and are easy to construct.

The dual lattice (joining pieces) is slightly trickier. Each angle joins two cuboctahedra and one octahedron, which have dihedral angles $\operatorname{arccos}(−1/\sqrt{3})$ and $\operatorname{arccos}(−​1/3)$, respectively (125.26°, and 109.5°). This corresponds to a triangle with angles 62.6°, 62.6°, and 54.7°. The dual honeycomb is the square bipyramidal honeycomb.

The rectified cubic honeycomb can therefore be build with three pieces: squares, equilateral triangles, and the above-described isosceles triangle.