Friday, February 25, 2011

Performance Invariants (Part II)

A few days ago I wrote a post about performance invariants. The basic idea behind them, is that there should be an easy way to declare performance constraints at the source code level, and that you should be able to check them every time you run your unit tests. To make a long story short, I have been a busy little bee for the last few days and managed to build a reasonable proof-of-concept.

Let's start with simple example:
import performance.annotation.Expect;
...
class Test {
    @Expect("InputStream.read == 0")
    static void process(List<String> list) {
        //...
    }
}
What we're asserting here is that we want to make sure that the number of calls to methods called read defined in classes named InputStream should be exactly zero.

If we want to exclude basically all IO, we can change the expectation to:
import performance.annotation.Expect;
...
class Test {
    @Expect("InputStream.read == 0 && OutputStream.write == 0")
    static void process(List<String> list) {
        //...
    }
}
Note that these are checked even for code that is called indirectly by the method process.

If we add an innocent looking println:
    @Expect("InputStream.read == 0 && OutputStream.write == 0")
    static void process(List<String> list) {
        System.out.println("Hi!");
        //...
    }

And run it with the agent enabled by using:
~>java -javaagent:./performance-1.0-SNAPSHOT-jar-with-dependencies.jar \
       -Xbootclasspath/a:./performance-1.0-SNAPSHOT-jar-with-dependencies.jar Test
You should get something like the following output:
Hi!
Exception in thread "main" java.lang.AssertionError: Method 'Test.process' did not fulfil: InputStream.read == 0 && OutputStream.write == 0
         Matched: [#OutputStream.write=7, #InputStream.read=0]
         Dynamic: []
        at performance.runtime.PerformanceExpectation.validate(PerformanceExpectation.java:69)
        at performance.runtime.ThreadHelper.endExpectation(ThreadHelper.java:52)
        at performance.runtime.Helper.endExpectation(Helper.java:61)
        at Test.process(Test.java:17)
        at Test.main(Test.java:39)
This is witchraft, I say! ... well kind of.

Let's stop a moment and consider what's going on here. Notice the first line of the output. It contains the text "Hi!" that we printed. This happens because the check is performed after the method process finishes. In the fourth line, you can see how many times each method matched during the execution of the process method. Ignore the "Dynamic" list for just a second.

Let's try something a bit more interesting:
    class Customer { /*... */}
    //...
    @Expect("Statement.executeUpdate < ${customers.size}")
    void storeCustomers(List<Customer> customers) {
        //...
    }
Note the ${customers.size} in the expression, what this intuitively mean is that we want to take the size of the list as an upper bound. It's like the poor programmer's big-O notation. If we were to run this, but assuming that we execute two updates for each customer (instead of one as asserted), we would get:
Exception in thread "main" java.lang.AssertionError: Method 'Test.storeCustomers' did not fulfil: Statement.executeUpdate < ${customers.size}
         Matched: [#Statement.executeUpdate=50]
         Dynamic: [customers.size=25.0]
        at performance.runtime.PerformanceExpectation.validate(PerformanceExpectation.java:69)
        at performance.runtime.ThreadHelper.endExpectation(ThreadHelper.java:52)
        at performance.runtime.Helper.endExpectation(Helper.java:61)
        at Test.storeCustomers(Test.java:19)
        at Test.main(Test.java:42)
Check the third line, this time, the "Dynamic" list contains the length of the list. In general, expressions of the form ${a.b.c.d} are called dynamic values. They refer to arguments, instance variables or static variables. For example:
  • ${static.CONSTANT} refers to a variable named CONSTANT in the current class.
  • ${this.instance} refers to a variable named 'instance' in the current object (only valid for instance methods).
  • ${n} refers to an argument named 'n' (this only works if the class has debug information)
  • ${3} refers to the fourth argument from the left (zero based indexing)
All dynamic values MUST yield a numeric value, otherwise a failure will be reported at runtime. Currently the library will complain if any dynamic value is null.

Although this is an early implementation, it is enough to start implementing performance invariants that can be checked every time you run your unit tests.
Enough for today, in a followup post I'll go into the internals of the agent. If you want to browse the source code or try it out, go and grab a copy from github.

Tuesday, February 22, 2011

Performance Invariants

UPDATE A newer post on this subject can be found here

Let's start with a problem: How do you make unit tests that test for performance?

It might seem simple, but consider that:
  • Test must be stable across hardware/software configurations
  • Machine workload should not affect results (at least on normal situations)

A friend of mine (Fernando Rodriguez-Olivera if you must know) thought of the following (among many other things):
For each test run, record interesting metrics, such as:
  • specific method calls
  • number of queries executed
  • number of I/O operations
  • etc.
And after the test run, assert that these values are under a certain threshold. If they're not, fail the test.
He even implemented a proof-of-concept using BeanShell to record these stats to a file during the test run, and it would check the constraints after the fact.

Yesterday I was going over these ideas while preparing a presentation on code quality and something just clicked: annotate methods with performance invariants.
The concept is similar to pre/post conditions. Each annotation is basically a post condition on the method call that states which performance "promises" the method makes.

For example you should be able to do something like:
@Ensure("queryCount <= 1")
public CustomerInfo loadCustomerInfo() {...}
Or maybe something like this:
@Ensure("count(java.lang.Comparable.compareTo) < ceil(log(this.customers.size()))")
public CustomerInfo findById(String id) {...}

These promises are enabled only during testing since checking for them might be a bit expensive for a production system.

As this is quite recent I don't have anything working (yet), but I think it's worth exploring.
If I manage to find some time to try and build it, I'll post some updates here.

Monday, February 21, 2011

gluUnProject for iPhone/iOS

I had a hard time finding a suitable implementation of gluUnProject for an iPhone project I was working on, so I decided to port the original implementation by SGI.

This is the header file (I called it "project.h"):
#ifndef __GLU_PROJECT_IOS
#define __GLU_PROJECT_IOS

#include <OpenGLES/ES1/gl.h>
#include <OpenGLES/ES1/glext.h>

void
gluPerspective(GLfloat fovy, GLfloat aspect, GLfloat zNear, GLfloat zFar);

void
gluLookAt(GLfloat eyex, GLfloat eyey, GLfloat eyez, GLfloat centerx,
    GLfloat centery, GLfloat centerz, GLfloat upx, GLfloat upy,
    GLfloat upz);

GLint
gluProject(GLfloat objx, GLfloat objy, GLfloat objz, 
     const GLfloat modelMatrix[16], 
     const GLfloat projMatrix[16],
     const GLint viewport[4],
     GLfloat *winx, GLfloat *winy, GLfloat *winz);

GLint
gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
    const GLfloat modelMatrix[16], 
    const GLfloat projMatrix[16],
    const GLint viewport[4],
    GLfloat *objx, GLfloat *objy, GLfloat *objz);


GLint
gluUnProject4(GLfloat winx, GLfloat winy, GLfloat winz, GLfloat clipw,
     const GLfloat modelMatrix[16], 
     const GLfloat projMatrix[16],
     const GLint viewport[4],
     GLclampf nearVal, GLclampf farVal,      
     GLfloat *objx, GLfloat *objy, GLfloat *objz,
     GLfloat *objw);

void
gluPickMatrix(GLfloat x, GLfloat y, GLfloat deltax, GLfloat deltay,
     GLint viewport[4]);

#endif
And the source code:
#include "project.h"
#include <math.h>


/*
** Make m an identity matrix
*/
static void __gluMakeIdentityf(GLfloat m[16])
{
    m[0+4*0] = 1; m[0+4*1] = 0; m[0+4*2] = 0; m[0+4*3] = 0;
    m[1+4*0] = 0; m[1+4*1] = 1; m[1+4*2] = 0; m[1+4*3] = 0;
    m[2+4*0] = 0; m[2+4*1] = 0; m[2+4*2] = 1; m[2+4*3] = 0;
    m[3+4*0] = 0; m[3+4*1] = 0; m[3+4*2] = 0; m[3+4*3] = 1;
}

#define __glPi 3.14159265358979323846

void
gluPerspective(GLfloat fovy, GLfloat aspect, GLfloat zNear, GLfloat zFar)
{
    GLfloat m[4][4];
    float sine, cotangent, deltaZ;
    float radians = fovy / 2 * __glPi / 180;

    deltaZ = zFar - zNear;
    sine = sin(radians);
    if ((deltaZ == 0) || (sine == 0) || (aspect == 0)) {
 return;
    }
    cotangent = cos(radians) / sine;

    __gluMakeIdentityf(&m[0][0]);
    m[0][0] = cotangent / aspect;
    m[1][1] = cotangent;
    m[2][2] = -(zFar + zNear) / deltaZ;
    m[2][3] = -1;
    m[3][2] = -2 * zNear * zFar / deltaZ;
    m[3][3] = 0;
    glMultMatrixf(&m[0][0]);
}

static void normalize(float v[3])
{
    float r;

    r = sqrt( v[0]*v[0] + v[1]*v[1] + v[2]*v[2] );
    if (r == 0.0) return;

    v[0] /= r;
    v[1] /= r;
    v[2] /= r;
}

static void cross(float v1[3], float v2[3], float result[3])
{
    result[0] = v1[1]*v2[2] - v1[2]*v2[1];
    result[1] = v1[2]*v2[0] - v1[0]*v2[2];
    result[2] = v1[0]*v2[1] - v1[1]*v2[0];
}

void
gluLookAt(GLfloat eyex, GLfloat eyey, GLfloat eyez, GLfloat centerx,
   GLfloat centery, GLfloat centerz, GLfloat upx, GLfloat upy,
   GLfloat upz)
{
    float forward[3], side[3], up[3];
    GLfloat m[4][4];

    forward[0] = centerx - eyex;
    forward[1] = centery - eyey;
    forward[2] = centerz - eyez;

    up[0] = upx;
    up[1] = upy;
    up[2] = upz;

    normalize(forward);

    /* Side = forward x up */
    cross(forward, up, side);
    normalize(side);

    /* Recompute up as: up = side x forward */
    cross(side, forward, up);

    __gluMakeIdentityf(&m[0][0]);
    m[0][0] = side[0];
    m[1][0] = side[1];
    m[2][0] = side[2];

    m[0][1] = up[0];
    m[1][1] = up[1];
    m[2][1] = up[2];

    m[0][2] = -forward[0];
    m[1][2] = -forward[1];
    m[2][2] = -forward[2];

    glMultMatrixf(&m[0][0]);
    glTranslatef(-eyex, -eyey, -eyez);
}

static void __gluMultMatrixVecf(const GLfloat matrix[16], const GLfloat in[4],
        GLfloat out[4])
{
    int i;

    for (i=0; i<4; i++) {
 out[i] = 
     in[0] * matrix[0*4+i] +
     in[1] * matrix[1*4+i] +
     in[2] * matrix[2*4+i] +
     in[3] * matrix[3*4+i];
    }
}

/*
** Invert 4x4 matrix.
** Contributed by David Moore (See Mesa bug #6748)
*/
static int __gluInvertMatrixf(const GLfloat m[16], GLfloat invOut[16])
{
    float inv[16], det;
    int i;

    inv[0] =   m[5]*m[10]*m[15] - m[5]*m[11]*m[14] - m[9]*m[6]*m[15]
             + m[9]*m[7]*m[14] + m[13]*m[6]*m[11] - m[13]*m[7]*m[10];
    inv[4] =  -m[4]*m[10]*m[15] + m[4]*m[11]*m[14] + m[8]*m[6]*m[15]
             - m[8]*m[7]*m[14] - m[12]*m[6]*m[11] + m[12]*m[7]*m[10];
    inv[8] =   m[4]*m[9]*m[15] - m[4]*m[11]*m[13] - m[8]*m[5]*m[15]
             + m[8]*m[7]*m[13] + m[12]*m[5]*m[11] - m[12]*m[7]*m[9];
    inv[12] = -m[4]*m[9]*m[14] + m[4]*m[10]*m[13] + m[8]*m[5]*m[14]
             - m[8]*m[6]*m[13] - m[12]*m[5]*m[10] + m[12]*m[6]*m[9];
    inv[1] =  -m[1]*m[10]*m[15] + m[1]*m[11]*m[14] + m[9]*m[2]*m[15]
             - m[9]*m[3]*m[14] - m[13]*m[2]*m[11] + m[13]*m[3]*m[10];
    inv[5] =   m[0]*m[10]*m[15] - m[0]*m[11]*m[14] - m[8]*m[2]*m[15]
             + m[8]*m[3]*m[14] + m[12]*m[2]*m[11] - m[12]*m[3]*m[10];
    inv[9] =  -m[0]*m[9]*m[15] + m[0]*m[11]*m[13] + m[8]*m[1]*m[15]
             - m[8]*m[3]*m[13] - m[12]*m[1]*m[11] + m[12]*m[3]*m[9];
    inv[13] =  m[0]*m[9]*m[14] - m[0]*m[10]*m[13] - m[8]*m[1]*m[14]
             + m[8]*m[2]*m[13] + m[12]*m[1]*m[10] - m[12]*m[2]*m[9];
    inv[2] =   m[1]*m[6]*m[15] - m[1]*m[7]*m[14] - m[5]*m[2]*m[15]
             + m[5]*m[3]*m[14] + m[13]*m[2]*m[7] - m[13]*m[3]*m[6];
    inv[6] =  -m[0]*m[6]*m[15] + m[0]*m[7]*m[14] + m[4]*m[2]*m[15]
             - m[4]*m[3]*m[14] - m[12]*m[2]*m[7] + m[12]*m[3]*m[6];
    inv[10] =  m[0]*m[5]*m[15] - m[0]*m[7]*m[13] - m[4]*m[1]*m[15]
             + m[4]*m[3]*m[13] + m[12]*m[1]*m[7] - m[12]*m[3]*m[5];
    inv[14] = -m[0]*m[5]*m[14] + m[0]*m[6]*m[13] + m[4]*m[1]*m[14]
             - m[4]*m[2]*m[13] - m[12]*m[1]*m[6] + m[12]*m[2]*m[5];
    inv[3] =  -m[1]*m[6]*m[11] + m[1]*m[7]*m[10] + m[5]*m[2]*m[11]
             - m[5]*m[3]*m[10] - m[9]*m[2]*m[7] + m[9]*m[3]*m[6];
    inv[7] =   m[0]*m[6]*m[11] - m[0]*m[7]*m[10] - m[4]*m[2]*m[11]
             + m[4]*m[3]*m[10] + m[8]*m[2]*m[7] - m[8]*m[3]*m[6];
    inv[11] = -m[0]*m[5]*m[11] + m[0]*m[7]*m[9] + m[4]*m[1]*m[11]
             - m[4]*m[3]*m[9] - m[8]*m[1]*m[7] + m[8]*m[3]*m[5];
    inv[15] =  m[0]*m[5]*m[10] - m[0]*m[6]*m[9] - m[4]*m[1]*m[10]
             + m[4]*m[2]*m[9] + m[8]*m[1]*m[6] - m[8]*m[2]*m[5];

    det = m[0]*inv[0] + m[1]*inv[4] + m[2]*inv[8] + m[3]*inv[12];
    if (det == 0)
        return GL_FALSE;

    det = 1.0 / det;

    for (i = 0; i < 16; i++)
        invOut[i] = inv[i] * det;

    return GL_TRUE;
}

static void __gluMultMatricesf(const GLfloat a[16], const GLfloat b[16],
    GLfloat r[16])
{
    int i, j;

    for (i = 0; i < 4; i++) {
 for (j = 0; j < 4; j++) {
     r[i*4+j] = 
  a[i*4+0]*b[0*4+j] +
  a[i*4+1]*b[1*4+j] +
  a[i*4+2]*b[2*4+j] +
  a[i*4+3]*b[3*4+j];
 }
    }
}

GLint
gluProject(GLfloat objx, GLfloat objy, GLfloat objz, 
       const GLfloat modelMatrix[16], 
       const GLfloat projMatrix[16],
              const GLint viewport[4],
       GLfloat *winx, GLfloat *winy, GLfloat *winz)
{
    float in[4];
    float out[4];

    in[0]=objx;
    in[1]=objy;
    in[2]=objz;
    in[3]=1.0;
    __gluMultMatrixVecf(modelMatrix, in, out);
    __gluMultMatrixVecf(projMatrix, out, in);
    if (in[3] == 0.0) return(GL_FALSE);
    in[0] /= in[3];
    in[1] /= in[3];
    in[2] /= in[3];
    /* Map x, y and z to range 0-1 */
    in[0] = in[0] * 0.5 + 0.5;
    in[1] = in[1] * 0.5 + 0.5;
    in[2] = in[2] * 0.5 + 0.5;

    /* Map x,y to viewport */
    in[0] = in[0] * viewport[2] + viewport[0];
    in[1] = in[1] * viewport[3] + viewport[1];

    *winx=in[0];
    *winy=in[1];
    *winz=in[2];
    return(GL_TRUE);
}

GLint
gluUnProject(GLfloat winx, GLfloat winy, GLfloat winz,
  const GLfloat modelMatrix[16], 
  const GLfloat projMatrix[16],
                const GLint viewport[4],
         GLfloat *objx, GLfloat *objy, GLfloat *objz)
{
    float finalMatrix[16];
    float in[4];
    float out[4];

    __gluMultMatricesf(modelMatrix, projMatrix, finalMatrix);
    if (!__gluInvertMatrixf(finalMatrix, finalMatrix)) return(GL_FALSE);

    in[0]=winx;
    in[1]=winy;
    in[2]=winz;
    in[3]=1.0;

    /* Map x and y from window coordinates */
    in[0] = (in[0] - viewport[0]) / viewport[2];
    in[1] = (in[1] - viewport[1]) / viewport[3];

    /* Map to range -1 to 1 */
    in[0] = in[0] * 2 - 1;
    in[1] = in[1] * 2 - 1;
    in[2] = in[2] * 2 - 1;

    __gluMultMatrixVecf(finalMatrix, in, out);
    if (out[3] == 0.0) return(GL_FALSE);
    out[0] /= out[3];
    out[1] /= out[3];
    out[2] /= out[3];
    *objx = out[0];
    *objy = out[1];
    *objz = out[2];
    return(GL_TRUE);
}

GLint
gluUnProject4(GLfloat winx, GLfloat winy, GLfloat winz, GLfloat clipw,
       const GLfloat modelMatrix[16], 
       const GLfloat projMatrix[16],
       const GLint viewport[4],
       GLclampf nearVal, GLclampf farVal,      
       GLfloat *objx, GLfloat *objy, GLfloat *objz,
       GLfloat *objw)
{
    float finalMatrix[16];
    float in[4];
    float out[4];

    __gluMultMatricesf(modelMatrix, projMatrix, finalMatrix);
    if (!__gluInvertMatrixf(finalMatrix, finalMatrix)) return(GL_FALSE);

    in[0]=winx;
    in[1]=winy;
    in[2]=winz;
    in[3]=clipw;

    /* Map x and y from window coordinates */
    in[0] = (in[0] - viewport[0]) / viewport[2];
    in[1] = (in[1] - viewport[1]) / viewport[3];
    in[2] = (in[2] - nearVal) / (farVal - nearVal);

    /* Map to range -1 to 1 */
    in[0] = in[0] * 2 - 1;
    in[1] = in[1] * 2 - 1;
    in[2] = in[2] * 2 - 1;

    __gluMultMatrixVecf(finalMatrix, in, out);
    if (out[3] == 0.0) return(GL_FALSE);
    *objx = out[0];
    *objy = out[1];
    *objz = out[2];
    *objw = out[3];
    return(GL_TRUE);
}

void
gluPickMatrix(GLfloat x, GLfloat y, GLfloat deltax, GLfloat deltay,
    GLint viewport[4])
{
    if (deltax <= 0 || deltay <= 0) { 
 return;
    }

    /* Translate and scale the picked region to the entire window */
    glTranslatef((viewport[2] - 2 * (x - viewport[0])) / deltax,
     (viewport[3] - 2 * (y - viewport[1])) / deltay, 0);
    glScalef(viewport[2] / deltax, viewport[3] / deltay, 1.0);
}

I'm thinking on porting the entire GLUT library to the iPhone and sharing it on github. Anyone interested?

Wednesday, December 02, 2009

Naive Brainf**k to Java compiler

Some time ago the brainf**k language caught my eye (I still don't feel comfortable spelling it right).

It's a turing tarpit, but one not very complicated at that (for something more esoteric see Malbolge or Whitespace).

The language is very simple, it has eight instructions. So I had to write a compiler for it. It turns out to be quite easy to do:

import static java.lang.System.out;

public class BrainFk
{
 public static void main(String[] args) {
 out.println("public class " + args[0] + "{");
 out.println("public static void main(String args[]) throws Throwable {");
 out.println("int[] memory = new int[30000];");
 out.println("int data = 0;");
 final String code = args[1];
 for(int i = 0; i < code.length(); i++) {
  char c = code.charAt(i);
  switch(c) {
   case '>':
    out.println("++data;");
    break;
   case '<':
    out.println("--data;");
    break;
   case '+':
    out.println("++memory[data];");
    break;
   case '-':
    out.println("--memory[data];");
    break;
   case '.':
    out.println("System.out.print((char)(0xFF & memory[data]));");
    break;
   case ',':
    out.println("memory[data] = System.in.read();");
    break;
   case '[':
    out.println("while(memory[data] != 0) {");
    break;
   case ']':
    out.println("}");
    break;
   }
  }
  out.println("}}");
 }
}

You can use it to compile the hello world sample from the Wikipedia page:
~>java BrainFk Hello "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>." > Hello.java
~>javac Hello.java
~>java Hello
Hello World!

Sometime I'll have to post the Forth interpreter in Java I wrote (I know some might consider sacrilege to use both languages in the same sentence, but you can't please everyone!).

Wednesday, November 25, 2009

Building 3D models using a Web Cam

Incredible technology to build a 3D model from a video of the desired object. Just watch the video:



You can go to the project site for more details.

Friday, October 02, 2009

Image Downscaling

A few days ago, a friend contacted me because he needed good image downscaling for a project he's working on.
I remebered reading an article about the types of issues when downsampling an image (and specifically a difficult one). After a few tests, I settled for a gaussian pre-blur.
I think I got pretty good results:
Go to the original article to get the source image.
The code also tries to fit and center the image in the target. That means it will return an image with the exact size you request. It will center and rescale the source image and leav transparent background for filler space.
import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.geom.AffineTransform;
import java.awt.image.*;
import java.io.File;
import java.io.IOException;

public class FitImage {

 public static BufferedImage fitImage(final BufferedImage input, final int width, final int height) {
  final int inputWidth = input.getWidth();
  final int inputHeight = input.getHeight();

  final double hScale = width/(double)inputWidth;
  final double vScale = height/(double)inputHeight;

  final double scaleFactor = Math.min(hScale, vScale);

  //Create a temp image
  final BufferedImage temp = new BufferedImage(inputWidth,inputHeight, BufferedImage.TYPE_INT_ARGB);

  if(scaleFactor < 1) {
   //Create a gaussian kernel with a raduis proportional to the scale factor and convolve it with the image
   final Kernel kernel = make2DKernel((float) (1 / scaleFactor));
   final BufferedImageOp op = new ConvolveOp(kernel);
   op.filter(input, temp);
  } else {
   temp.createGraphics().drawImage(input, null, 0,0);
  }


  final BufferedImage output = new BufferedImage(width,height, BufferedImage.TYPE_INT_ARGB);
  final Graphics2D g = output.createGraphics();
  g.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_QUALITY);
  g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BICUBIC);
  g.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE);
  g.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
  g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

  final int xOffset = (int) Math.max(0, (width - inputWidth * scaleFactor) / 2);
  final int yOffset = (int) Math.max(0, (height - inputHeight * scaleFactor) / 2);
  final AffineTransform scaleInstance = AffineTransform.getScaleInstance(scaleFactor, scaleFactor);
  final AffineTransformOp transformOp = new AffineTransformOp(scaleInstance, AffineTransformOp.TYPE_BICUBIC);
  g.drawImage(temp, transformOp, xOffset, yOffset);
  return output;
 }

 public static Kernel make2DKernel(float radius) {
  final int r = (int)Math.ceil(radius);
  final int size = r*2+1;
  float standardDeviation = radius/3; //Guess a standard dev from the radius

  final float center = (float) (size/2);
  float sigmaSquared = standardDeviation * standardDeviation;

  final float[] coeffs = new float[size*size];

  for(int x = 0; x < size; x++ ) {
   for(int y = 0; y < size; y++ ) {
   double distFromCenterSquared = ( x - center ) * (x - center ) + ( y - center ) * ( y - center );
   double baseEexponential = Math.pow( Math.E, -distFromCenterSquared / ( 2.0f * sigmaSquared ) );
   coeffs[y*size+x]= (float) (baseEexponential / (2.0f*Math.PI*sigmaSquared ));
   }
  }

  return new Kernel(size, size, coeffs);
 }

 public static void main(String[] args)
  throws IOException
 {
  BufferedImage out = fitImage(ImageIO.read(new File("Rings1.gif")), 200, 200);
  ImageIO.write(out, "png", new File("test.png"));
 }


}

Tuesday, February 03, 2009

Great Quotes

"My definition of an expert in any field is a person who knows enough about what's really going on to be scared." - P. J. Plauger, Computer Language, March 1983


From Stackoverflow.

Tuesday, August 12, 2008

Phrase of the Day

"The devil is in the details, but exorcism is in implementation, not theory." - (author unknown)

Wednesday, February 06, 2008

Juggling Chainsaws

Andrew writes probably one of the funniest and most elocuent articles I've read about thread programming. His opening line:
 Writing multithreaded code is like juggling chainsaws; amazing when it works and truly sucky when it doesn't.

Truly summarizes the feeling when you've had to deal with a multithreaded system. He argues that probably one of the most difficult thing to achieve is "avoiding doing nothing". I agree with his thoughts in the sense that if you are even considering multithreading something, you are trying to achieve maximum utilization (i.e. not wasting resources). But I'm not sure that getting maximum utilization is the hardest part by itself.

Besides the usual problems, like avoiding deadlocks or protecting shared data, I always found that the hardest part was, to paraphrase Andrew, "avoid doing something".

What I mean is that in multithreaded applications (it also applies to distributed applications), probably the hardest part is coming up with ways to avoid needing synchronization.

At least in my experience, figuring out ways to make the system exhibit consistent and predictable behavior without relying on atomicity, has always been the part that most of the design effort is invested in, and if done properly, where the greatest gains in scalability is achieved.

Take for example the Google File System, a massive, multi-petabyte storage filesystem. It is designed to work on clusters of several thousand machines, distibuted across several datacenters (even on different countries).

To achieve the expected performance, they had to throw away the usual file semantics, and think completely out-of-the box. But don't take my word for it, go, fetch the paper (if you haven't already done so), and read it yourself.

Monday, November 05, 2007

A better way to do concurrent programming (Part 1)

A while ago (I think round 2005), some guys from Microsoft Research published a paper about Composable Memory Transactions.

After reading it, I began doing a small implementation in Java (quite ugly, btw), and I was astonished by the possibilities. So quite naturally (being the geek I am), I started toying with the idea of implementing a set of extensions for Java.

In this and other posts, I'll try to make an introduction to the basic idea. Note that I will probably change existing posts quite often to correct mistakes or ommissions. In this post I'll focus on an overview of the basic idea, in a future post I'll address composition of transactions (the C in CMT), static checking for side effects, and alternatives to implement the runtime part of this. If you're really curious, I recommend reading the original paper.

The gist of the idea is to replace common locking based semantics with in-memory transactions, so instead of writing complex locking semantics, you rely on optimistic locking handled by the runtime.

The following example shows how a producer-consumer problem can be solved with a queue of fixed size using Java with CMT:

public class BufferedQueue {
private LinkedList list;
public BufferedQueue() {
list = new LinkedList();
}
public Object consume() {
Object value;
atomic {
if(list.isEmpty()) {
retry;
}
value = list.removeFirst();
}
return value;
}
public void produce(Object value) {
atomic {
if(list.size() > 10) {
retry;
}
list.add(value);
}
}
public Object peek() {
Object value;
atomic {
if(list.isEmpty()) {
retry;
}
value = list.getFirst();
} else {
value = null;
}
return value;
}
}

Take a look at two keywords: atomic and retry

The atomic keyword demarcates a transaction. That means that this block is all-or-nothing (well get to the else later). For example let's take a closer look at the consume method.

public Object consume() {
Object value;
atomic {
if(list.isEmpty()) {
retry;
}
value = list.removeFirst();
}
return value;
}

The atomic statement starts a transaction. In this transaction we first check to see if the list is empty. If it is, we issue a retry statement.
The retry statement, rolls-back all changes and suspends the transaction until at least one of the fields used in the block (either directly or indirectly) is modified by another transaction committing. When this happens, the execution is restarted in a new transaction at the beginning of the enclosing atomic block.
If this time the list is not empty, the first element is removed from the list, and the transaction is committed. If at the time of the commit there is a conflict with another transaction, the execution is rolled back and retried.

Note that it is very important that the atomic blocks do not have side-effects (such as creating files, etc.) outside of the control of the transaction manager.

(to be continued...)

13949712720901ForOSX - Java for OSX

In a blog post henry resumes the sad state of affairs of Java in OSX.

So here I am, joining this campaign by posting this entry in protest! Apple, please don't let us down!

Thursday, June 15, 2006

How the Wii-mote works

I know this is pure speculation, but I've been following the Revolution/Wii for a while, and one thing that kept me intrigued is how would Nintendo build such a fantastic controller in a cost effective manner.

After much thought I think I get it.

There are two distinct control schemes in the Wii-mote:
  • Orientation and acceleration
  • Pointing

Orientation and Acceleration

The orientation and acceleration is quite easy, it only needs an accelerometer. This only tells you the orientation relative to the ground (if you're swinging, the 'perceived' ground shifts).

Pointing

This is the hard part.

There are some observations I (and several others) made:

  • The Wii-mote has a dark plastic window in the front
  • You have to place a 'Sensor Bar' under or over the TV
  • The Wii can track multiple remotes with high acuracy
  • There is an image sensor in the remote
  • It has been mentioned of a problem with halogen lights
  • The remote has to be pointed to the sensor bar for precision aiming

Keeping those in mind, let me explain how it all makes sense:

First of all, the dark window in the wii-mote, is a visible-light filter. Very similar to the window in front of most remote controls. But instead of having a IR led behind it, it has an image sensor.

This image sensor only 'sees' infrared images, probably in fairly low resolution. It uses this to see the sensor bar, which is basically a row of IR leds.

The wii-mote captures an image of what's in front of it (basically a bright line on a dark background), and looks for the sensor bar (which should be the brightest IR thing in the image).

Since the size of the sensor bar is fixed, you can acurately calculate the distance of the wii-mote from the sensor bar, the rotation (the image sensor sees a line rotated), and the angle of the wii-mote in relation to the center of the sensor bar (the line is off-center in the image).

This approach is quite easy to implement, but it has several drawbacks:

  • If you are too close to the bar, you cannot acurately estimate the angle or position
  • If you are too far, the precision also suffers, since the resolution of the image sensor limits how far you can be
  • Halogen lights (or any other light source with lots of IR light, such as direct sunlight) can effectively blind the image sensor

It also is very cost effective since low resolution image sensors are quite cheap in bulk, and image tracking is also very well understood for this scenario (think of optical mice, for example).

Hope you enjoyed this.

Thursday, September 01, 2005

Quote of the day

"Puctuality is the virtue of the bored"

- Evelyn Waugh

(given that I seem to be unable to blog about something more interesting, I'll keep it simple)

Thursday, August 25, 2005

Quote of the day

"... You are free to fold, spindle or mutilate for the betterment of your proprietary closed-source product that makes you zillions of dollars, without penalty ..."

from Drools Licensing.

Talking about Drools' liberal open source license. LOL!

Friday, August 19, 2005

Fixed and Floating point for J2ME

As you probably know, J2ME in its most basic form doesn't support floating point operations. This can be a problem if you are trying to develop games for it.

I've been looking around for alternatives, and found that most sites reference you to MathFP (the link I had seems to be broken, google for it), which is a fast library to do fixed point math. The problem with it is that for certain types of calculations, fixed point can be complicated, given that it is hard to represent numbers that are too small or too large, and mix those in the same calculation.

Browsing around I found MicroFloat, which is a very nice floating point library written entirely in Java. The only gotcha is that it requires long support from the KVM.

There are other libraries around (which I havent tested) such as Real Java.

Well, now to start that doom clone for my cell phone...

Monday, August 08, 2005

Impressive DOM scripting

If you happen to have a few minutes of spare time, check out "Interactive DOM Scripting" which is simply awesome.

The most impressive pages are IE only (don't blame me). This site has the spirit of the old demos built for machines such as the Commodore Amiga 500. A bit of nostalgia is unavoidable.

Thursday, August 04, 2005

Quote of the day

"In a perfect world, reading code would be like reading a book. Unfortunately, code is written for computers to execute, not for humans to read. You can’t just read code from start to finish—they’re like those choose-your-own-ending books, forcing you to go all over the place to figure out how not to kill your main character. "

From Successful Strategies for Commenting Code - By Ryan Campbell

The quote is great, but I disagree with some of the statements in the article. I'm more of the idea that code comments should explain why you are doing something, not how. Anyway, as with any imperative guidelines, it is more important the spirit of the law, than the law itself.

In spirit, I think the idea of code comments is to make code more understandable for other people or for a future version of yourself.

Tuesday, August 02, 2005

Not much time left

It has been a while since my last post, I've been really busy lately because a new version of our product is in the pipeline, and development is picking up speed.

I'll continue the regular posts soon (hopefully!).

Wednesday, July 20, 2005

Intersecting a QuadCurve2D (Part II)

(continued from part one)
So far we have the parametric equation of quadratic bezier curve:

Q(t) = P1 (1 - t)^2 + P2 (2t(1-t)) + P3 (t^2)

All we have to do now is devise an efficient way to check the intersection with a rectangle. We have three cases of intersection:
  • If one of the endpoints of the curve is contained in the rectangle, the curve intersects the rectangle
  • If the curve intersects one of the line segments that delimit the rectangle, the curve intersects the rectangle
  • If neither of these is true, there is no intersection.
The first case is the easiest to check, we just have to check if the rectangle contains either one of the endpoints (P1 and P3).
The second one is a bit trickier. First, let me make one observation: the sides of a rectangle are always parallel to one of the coordinate axis (I know this sounds obvious in this context, but bear with me).
What this means is that the top and bottom edges of the rectangle are contained by a line of the form:

y = c

with c = rect.getY() for the top edge and c = rect.getY() + rect.getHeight() for the bottom edge.
Analogously, the left and right edges:

x = c

with c = rect.getX() for the left edge and c = rect.getX()+rect.getWidth() for the right edge.
Let's use the top edge as an example, to check if the curve cuts that edge, we must do two checks:
  • That exists a value of t, such as 0 <= t <= 1 and c = Qy(t)
  • And that rect.getX() <= Qx(t) <= rect.getX() + rect.getWidth() is true for that value of t

Where Qx(t) and Qy(t) are the parametric ecuations of the curve for each coordinate:

Qx(t) = Px1 (1 - t)^2 + Px2 (2t(1-t)) + Px3 (t^2)

Qy(t) = Py1 (1 - t)^2 + Py2 (2t(1-t)) + Py3 (t^2)

To perform the aforementioned checks, we must solve t for:

c = Q(t)

(since Qx(t) and Qy(t) are analogous, I won't specify which one I'm referring , since the result is the same).

That yields (after some more mathemagic passes):

(P1 - 2 P2 + P3)t^2 + (2 P2-2 P1) t + (P1 - c) = 0

Which is a simple quadratic equation. As you know, quadratic equations have (potentially) two roots. So we must check both values (if present) to see if any of those yields the expected result.

To solve it in code, we can use the handy QuadCurve2D.solveQuadratic() method.

public boolean curveIntersects(QuadCurve2D curve, double rx, double ry, double rw, double rh)
  {
      /**
       * A quadratic bezier curve has the following parametric equation:
       *
       * Q(t) = P0(1-t)^2 + P1(2t(1-t)) + P2(t^2)
       *
       * Where 0 <= t <= 1 and P0 is the starting point, P1 is the control point and
       * P2 is the end point.
       *
       * Therefore, the equations for the x and y coordinates are:
       *
       * Qx(t) = Px0(1-t)^2 + Px1(2t(1-t)) + Px2(t^2)
       * Qy(t) = Py0(1-t)^2 + Py1(2t(1-t)) + Py2(t^2)
       *
       *  0 <= t <= 1
       *
       * A bezier curve intersects a rectangle if:
       *
       *  1 - Either one of its endpoints is inside of the rectangle
       *  2 - The curve intersects one of the rectangles sides (top, bottom, left or right)
       *
       * The equation for a horizontal line is:
       *
       *   y = c
       *
       * The line intersects the bezier if:
       *
       *   Qy(t) = c and 0 <= t <= 1
       *
       * We can rewrite this as:
       *
       *   -c + Py0 + (-2Py0 + 2Py1)t + (Py0 - 2Py1 + Py2) t^2 == 0
       *   and 0 <= t <= 1
       *
       * We can use the valid roots of the quadratic, to evaluate Qx(t), and see if the value
       * falls withing the rectangle bounds.
       *
       * The case for vertical lines is analogous to this one.
       * (juancn)
       */
      double y1 = curve.getY1();
      double y2 = curve.getY2();
      double x1 = curve.getX1();
      double x2 = curve.getX2();

      //If the rectangle contains one of the endpoints, it intersects the curve
      if(rectangleContains(x1, y1, rx,ry,rw,rh)  rectangleContains(x2, y2,rx,ry,rw,rh)) {
          return true;
      }

      double eqn[] = new double[3];
      double ctrlY = curve.getCtrlY();
      double ctrlX = curve.getCtrlX();

      return intersectsLine(eqn, y1, ctrlY, y2, ry, x1, ctrlX, x2, rx, rx+rw) //Top
       intersectsLine(eqn, y1, ctrlY, y2, ry + rh, x1, ctrlX, x2,rx, rx+rw) //Bottom
       intersectsLine(eqn, x1, ctrlX, x2, rx, y1, ctrlY, y2, ry, ry+rh) //Left
       intersectsLine(eqn, x1, ctrlX, x2, rx+rw, y1, ctrlY, y2, ry, ry+rh); //Right
  }

  private boolean rectangleContains(double x, double y, double rx, double ry, double rw, double rh)
  {
      return (x >= rx &&
          y >= ry &&
          x < rx + rw &&
          y < ry + rh);
  }

  /**
   * Returns true if a line segment parallel to one of the axis intersects the specified curve.
   * This function works fine if you reverse the axes.
   *
   * @param eqn a double[] of lenght 3 used to hold the quadratic equation coeficients
   * @param p0 starting point of the curve at the desired axis (i.e.: curve.getX1())
   * @param p1 control point of the curve at the desired axis  (i.e.: curve.getCtrlX())
   * @param p2 end point of the curve at the desired axis (i.e.: curve.getX2())
   * @param c where is the line segment (i.e.: in X axis)
   * @param pb0 starting point of the curve at the other axis (i.e.: curve.getY1())
   * @param pb1 control point of the curve at the other axis  (i.e.: curve.getCtrlY())
   * @param pb2 end point of the curve at the other axis (i.e.: curve.getY2())
   * @param from starting point of the line segment (i.e.: in Y axis)
   * @param to end point of the line segment (i.e.: in Y axis)
   * @return
   */
  private static boolean intersectsLine(double[] eqn, double p0, double p1, double p2, double c,
                                 double pb0, double pb1, double pb2,
                                 double from, double to)
  {
      /**
       * First we check if a line parallel to the axis we are evaluating intersects
       * the curve (the line is at c).
       *
       * Then we check if any of the intersection points is between 'from' and 'to' in the other
       * axis (wether it belongs to the rectangle)
       */

      //Fill the coefficients of the equation
      eqn[2] = p0 - 2*p1 + p2;
      eqn[1] = 2*p1-2*p0;
      eqn[0] = p0 - c;

      int nRoots = QuadCurve2D.solveQuadratic(eqn);
      boolean result;
      switch(nRoots) {
      case 1:
          result = (eqn[0] >= 0) && (eqn[0] <= 1);
          if(result) {
              double intersection = evalQuadraticCurve(pb0,pb1,pb2,eqn[0]);
              result = (intersection >= from) && (intersection <= to);
          }
          break;
      case 2:
          result = (eqn[0] >= 0) && (eqn[0] <= 1);
          if(result) {
              double intersection = evalQuadraticCurve(pb0,pb1,pb2,eqn[0]);
              result = (intersection >= from) && (intersection <= to);
          }

          //If the first root is not a valid intersection, try the other one
          if(!result) {
              result = (eqn[1] >= 0) && (eqn[1] <= 1);
              if(result) {
                  double intersection = evalQuadraticCurve(pb0,pb1,pb2,eqn[1]);
                  result = (intersection >= from) && (intersection <= to);
              }
          }

          break;
      default:
          result = false;
      }
      return result;
  }

  public static double evalQuadraticCurve(double c1, double ctrl, double c2, double t)
  {
      double u = 1 - t;
      double res = c1 * u * u + 2 * ctrl * t * u + c2 * t * t;

      return res;
  }

Wednesday, July 06, 2005

Intersecting a QuadCurve2D (Part I)


A few days ago, while I was trying to optimize the rendering code of a designer application I found something funny about Java 2D, there is no easy way to check if a rectangle intersects with a QuadCurve2D. That is with just the curve, not the area enclosed by it.
I'll try to summarize what I learned about quadratic bezier curves, and provide a fast algorithm to check for the intersection.

Quadratic bezier curves are defined by three points: a starting point, a control point, and an end point. The starting point and the end point are on the curve, the control point is outside the curve.

Bezier curves are based on the parametric equation of the line, which is of the form:

L(t) = P1 (1 - t) + P2 t

With t in [0,1]. P1 and P2 are two arbitrary points.

As I said before, a bezier curve is defined by three points. Take a look at the following diagram:


Here we have two main lines: from P1 to P2 and from P2 to P3, the curve is defined by a point in the line S0 to S1.
Using the parametric ecuation of the line I mentioned before, we can write S0 and S1 as:

S0(t) = P1(1-t) + P2 t
S1(t) = P2 (1-t) + P3 t

Then, the point on the bezier curve is defined as:

Q(t) = S0(1-t) + S1 t

Simplifying this (hocus phocus... and some mathematical mumbo jumbo) we get:

Q(t) = P1 (1 - t)^2 + P2 (2t(1-t)) + P3 (t^2)

So finally we have the basic ecuation for a quadratic bezier curve.

(Next: Curve intersection)