Overfloater

While at work last week I decided to make a small program in the Groovy programming language. I needed to build a small file processing program that used some Java libraries built at work, but I didn’t want to code five or six Java classes to do so. Since performance wasn’t a big concern, I decided to take a look at some JVM based languages.

There are lots of programming languages targetting the JVM, so why Groovy?

Why Groovy?

Groovy is a highly dynamic language, that takes things from Python, Ruby and Smalltalk. Since these are programming languages I used before and I’m quite comfortable with, Groovy seemed like a good match.

Also, Groovy is very easy to learn, having an almost-zero learning curve. Since I had to do this in a couple of days, I didn’t want to spend a lot of time learning a programming language’s syntax and semantics. I know how to use Python and I know how to use Ruby/Smalltalk, I just want to do the same things in the JVM.

Another very interesting thing (that doesn’t concern the language itself, but it’s quite helpful) is that Groovy, along with OCaml and Perl, has a 100% completness score at PLEAC. That means that you can find complete examples of: Strings, Numbers, Arrays, Hashes, Dates and Times, Pattern Matching, File Access, File Contents, Directories, Subroutines, References and Records, Packages, Libraries and Modules, Classes and Objects, Database Access, User Interfaces and a lot more here.

Features I like about the language

Some of the features I used and liked about Groovy:

List and Hash literals
As opposed to Java, Groovy provides List and Hash literals:

//Create an empty List
emptyList = []
//Create an empty Hash
emptyHash = [:]
//Create a List
somePeople = ["John", "Jack", "Sarah"]
//Create a Hash
ext = [
  Ruby: 'rb',
  Python: 'py',
  C: 'c',
  Groovy: 'groovy'
]

List and Hash traversing and manipulation

In terms of List and Hash manipulation, Groovy offers the same expressiveness as Python and Smalltalk:

//Create a List
somePeople = ["John", "Jack", "Sarah"]

//Copy first two List elements
copy = somePeople[0..1] //["John", "Jack"]

//Grab last list element
lastElem = somePeople[-1] //"Sarah"

//Closures are first class values in Groovy, their syntax is {}.
//For unary lambdas an implicit 'it' variable is created

//Any element starting with capital letters?
somePeople.any { it[0] in 'A'..'Z' } //true

//We can also use regex a la Perl
somePeople.any { it =~ /[A-Z].*/ } //true

//Print names with new lines
somePeople.each { println it }

//Create a Hash
ext = [
  Ruby: 'rb',
  Python: 'py',
  C: 'c',
  Groovy: 'groovy'
]

//print an element
println ext.'Ruby' //rb
println ext['Ruby']//rb

//iterate through a hash elements
ext.each { key, value -> println key + ': ' + value }
//will print Ruby: rb, etc

Defining functions
Functions are defined like this:

//Define a square function
def square(val) {
 val * val
}

//Or assign a closure to a square variable:
square = { it * it }

Simple.

Java classes extensions
One of the things I find really nice about Groovy, is that it extends Java SE with useful functions.
You can find the extensions here.

Java File class extensions are pretty cool:

//Print dir file names
new File("/some/dir/").eachFile { println it.name }

//Print file text content
println new File("/some/file.txt").getText()

//Print file content with line numbers
new File("otherfile.txt").eachLine { it, line -> println line + ": " + it }

Other libraries

At work I had to deal with XML data, and found a very interesting and high level XML manipulation library called XmlSlurper:

xml = ‘‘‘
<root>
<artist name="Pearl Jam">
  <album>Ten</album>
  <album>Vs.</album>
  <album>Vitalogy</album>
  <album>Riot Act</album>
</artist>
<artist name="Soundgarden">
  <album>Down on the Upside</album>
  <album>Superunknown</album>
</artist>
</root>
‘‘‘
root = new XmlSlurper().parseText(xml)
root.artist.each {
  println it.@name.text() + ': ' +
        it.album.collect({ it.text() }).join(', ')
}
//Will print
//Pearl Jam: Ten, Vs., Vitalogy, Riot Act
//Soundgarden: Down on the Upside, Superunknown

Conclusion

Groovy is a versatile scripting language built on top of the JVM.
It provides useful features taken from Ruby, Python and Smalltalk, with full access to all Java libraries.
It also extends Java classes with useful methods and iterators.
If you aren’t that worried about performance (still runs faster than Ruby, Python 3 and Perl), I’d recommend you to take a look at it.
Hope this was helpful enough to get a feeling of the language.

In case you’re wondering what I’m up to…

I’ve been adding more features to the JavaScript InfoVis Toolkit, to be released I-don’t-know-when-yet (still a lot of work to do regarding documentation, hosting, scripts, etc.).

Anyway, this video shows only some of the features to be included:

• Custom nodes: built-in shapes are none, circle, square, rectangle, ellipse, among others
• Custom edges: built-in shapes are none, line, quadratic, bezier, arrow, among others
• Custom Animations: linear, Quart, Bounce, Elastic, Back, etc.
• Change tree orientation: already possible in 1.0.8a.

Unfortunately my video card isn’t very good, so the video quality and fps aren’t as good as I’d wanted.
Animations are pretty smooth though, as you can see for yourself, so don’t blame the library, blame my computer!

Anyway, here’s the video:

Another cool thing is that you can also create custom node and edge rendering functions

Stay tuned, there are more features to come!

I was looking for some way to easily create, read, manipulate and print cyclic or recursive data structures in some programming languages, and got to the cool concept of sharp variables.

Manipulating Recursive Structures in Python

A straightforward way of defining a recursive structure is to first assign a base (non-recursive) structure to a variable, and then alter or extend that variable with a recursive expression. For example, in Python you can write:

my_rec_var = [1, 2, 3]
my_rec_var.append(my_rec_var)

That code will create a recursive data structure: [1, 2, 3, [1, 2, 3, [...]]],
or a = [1, 2, 3, a].

Actually, Python’s print function lets you print a representation of a recursive structure without recursing indefinitely:

>>> print my_rec_var
[1, 2, 3, [...]]

Python’s pickle module lets you dump a recursive data structure into a file. You can also read that serialized structure from the file:

import pickle

#dump it to file
output = open("out.pkl", "wb")
pickle.dump(my_rec_var, output)

However, there’s no literal way of creating, reading or modifying that structure:

>>> my_rec_var = [1, 2, 3, [...]]
 ERROR

Manipulating Recursive Structures in Lisp

For manipulating/printing recursive data structures in Common Lisp we first assign T to the global variable *print-circle*

(setq *print-circle* T)

We can define a recursive structure just as we did with Python, by defining some base structure and then modifying the structure to be recursive:

(defvar *my-rec-var* (list 1 2 3 _))
;Replace the underscore placeholder with a self-reference
(setf (fourth *my-rec-var*) *my-rec-var*)

The final structure is represented with sharp variables:

>>> (print *my-rec-var*)
#1=(1 2 3 #1#)

This is just as the “Mathematical” definition we gave above:
a = [1, 2, 3, a].

What’s interesting about this “serialization format” is that expressions involving sharp variables are truly expressions: these “objects” can be read and manipulated just like any other structure:

>>> (defvar *another-rec-var* ‘#1=(1 2 3 #1#))
#1=(1 2 3 #1#)

>>> (fourth ‘#1=(1 2 3 #1#))
#1=(1 2 3 #1#)

>>> (cons 5 ‘#1=(1 2 3 #1#))
(5 . #1=(1 2 3 #1#))

Sharp variables seem like an excellent solution for creating, reading and manipulating cyclic data structures.

Sharp Variables in JavaScript

Mozilla’s JavaScript implementation has Sharp Variables. They’ve been introduced by Brendan Eich and they are inspired by Common Lisp’s syntax.
Sharp Variables can be pretty useful in JavaScript, since most of the time we’re manipulating object references and Firefox’s toSource() method is pretty useful for debugging (among other things).

var myArray = [1, 2, 3];
myArray.push(myArray);
myArray.toSource();

Try running that in your Firefox console, it should return “#1=[1, 2, 3, #1#]“.

Oh, and did I mention that you can also explicitly manipulate cyclic structures in JavaScript?

//Assign a literal recursive data structure
var anotherArray = #1=[1, 2, 3, #1#];

console.log(anotherArray.toSource());
//"#1=[1, 2, 3, #1#]"

console.log(anotherArray[0]);
//1

console.log(anotherArray[3].toSource());
//"#1=[1, 2, 3, #1#]"

I was happy to find such an interesting Lisp feature in JavaScript.

In my last post I mentioned Operator Overloading, and why I think it would be interesting to see this as a proposal for the ECMAScript 4 specification (the new JavaScript specification).
I’ve been following the ECMA discussion list and the ES 4 wiki, and I was surprised to see that I feel the same way as some people in the ECMA group do about operator overloading.
The Operator Overloading proposal has been made a couple of times before, but it was disregarded as beeing too weak to be considered.

However, this proposal has been superseeded by some other (very interesting) proposal: generic functions (a.k.a multimethods).

What are generic functions?

The first time I discovered generic functions was while playing with Common Lisp’s Object System (CLOS).
In fact, early Lisp systems worked as Smalltalk did, by implementing a send function:

(send object :foo)

instead of just doing:

(foo object)

They finally came with the solution of creating generic functions that could be implemented by methods. This design is far more expressive that the classic OO design, implemented in languages such as Java.
Since this design is far from classical OO ones, explaining by example turns out to be quite difficult: the wikipedia examples aren’t very enlightening (see the article’s discussions).

So here I go.

Java has function overloading: that means that several methods with the same name can be defined in the same class, provided that the type (or number of arguments) defined in each method is not the same.

So, for example, lets define a Java class Person with two eat methods:

  class Person {
    public void eat (Food f) { println ("eating food"); }
    public void eat(Pasta p) { println ("eating pasta"); }
  }

(Pasta extends Food)

We have succesfully overloaded the eat method. However, the overloading happens at compile time, and there’s no dynamic dispatch. So, for example this code:

  Food food = new Pasta();
  somePerson.eat(food);

Will answer “eating food”, which isn’t exactly what we want.

Now lets consider this code:

class John extends Person {
    public void eat(Food f) { println ("mmm...."); }
    public void eat(Pasta p) { println ("Yummy!"); }
  }

  Person me = new John();
  Food pasta   = new Pasta();
  me.eat(pasta);

This code will answer “mmm…”. But there’s one important thing: we’ve called a method from John’s class, instead of some eat method from Person.

This had to be decided at run time, since me is of type Person, but we assigned a John to it…

Now lets define, in pseudo-code, an abstraction of these eat methods, that could be thought as decoupled from the John and Person classes. For example, we could re-write John and Person eat methods as four independent functions:

public void function eat(John john, Food f) { ... }
public void function eat(John john, Pasta p) { ... }

public void function eat(Person person, Food f) { ... }
public void function eat(Person person, Pasta p) { ... }

What we know about these methods is that Java checks its first argument type at runtime, but all other arguments are checked at compile-time.
So, as far as dynamic dispatch concerns, Java has single dispatch, and function overloading only refers to compile-time checked types, which in general doesn’t yield the expected result. (This problem beeing solved by the visitor pattern in most cases).

A generic function can be seen as a family of functions that provide multiple dispatch, that means that all arguments of the function are checked at runtime (on invocation). Not only the first argument, but all.
Compared to Java, this approach would, in most cases, yield the expected answers without having to implement some patterns like the visitor pattern.

The four methods defined above could be redefined in CLOS as:

(defmethod eat ((john John) (f Food)) ... )
(defmethod eat ((john John) (p Pasta)) ... )

(defmethod eat ((person Person) (f Food)) ... )
(defmethod eat ((person Person) (p Pasta)) ... )

Generic Functions in JavaScript

The Generic Functions JavaScript proposal aims to solve all weaknesses existing in the Operator Overloading proposal, but it also provides a more generic way of defining and manipulating functions.
Operator Overloading should be seen as a particular case of what can be done with generic functions in JavaScript.

In JavaScript, a generic function could be defined as:

generic function f(x, y);

Since a generic function defines a family of functions, there’s no function body in it.
A generic function can also be defined with type annotations:

generic function f(x: Numeric, y: Object): MyClass;

A method is then defined over an existing generic function, using specializers:

 generic function f(x:int, y:boolean): string {
      if (y)
          return string(x);
      else
          return "37";
  }

Eventually, built-in generic functions could be defined for common operators, providing a way of overloading operators:

generic function +(a:Complex, b:Complex) {
   return new Complex(a.x + b.x, a.y + b.y);
}

For a JavaScript canvas developer, this would be wonderful, since we mess with Complex, Polar, Matrix classes all the time, and a simple interpolation expression of two complex numbers could be transformed from this:

(to.$add(from.scale(-1))).$scale(delta).$add(from)

into this:

from + (to - from) * delta

Remember Treemaps?

There was a thread at the Google Group for the JIT asking for Gradients in Treemaps.

Actually they’re called cushion treemaps, and they have been created by Ph.Ds Jarke J. van Wijk and Huub van de Wetering. Cushion Treemaps have been used in successful applications like SequoiaView and companies like MagnaView are building very interesting visualizations with cushion treemaps.

The paper is quite interesting: cushion treemaps were created by using shading to show a tree’s structure:

“How can we use shading to show the tree structure? The human visual system is trained to interpret variations in shade as illuminated surfaces [6]. Hence, we can answer the question by constructing a surface which shape encodes the tree structure.”

Shadowing is created by adding bumps to rectangles.

In the JavaScript InfoVis Toolkit, this can be done by overriding the leafBox method of the Treemap class. This method renders a leaf node (nodes which are generally colored in the Treemap).
By adding an image of a radial gradient inside that div we can emulate cushion treemaps.

Instead of creating a new class that extends TM and overrides that method, we can take advantage of JavaScript’s object mutability feature and re-implement the method in the same class.

    TM.Squarified.implement({
       leafBox: function(json, coord) {
        var config = this.config;
        var backgroundColor = config.Color.allow && this.setColor(json),
        offst = config.offset,
        width = coord.width - offst,
        height = coord.height - offst;
        var c = {
         'top': (offst / 2) + "px",
         'height':height + "px",
         'width': width + "px",
         'left': (offst / 2) + "px"
        };
        if(backgroundColor) c['background-color'] = backgroundColor;
       //Add an image to our leaf node to create a cushion treemap.
        var img = "<img src='gradient.png' style='position:absolute; z-index:2; top:0; left:0; width:" + c.width + "; height:"+ c.height +"'; />"; 

        return "<div class='leaf' style=" + this.toStyle(c) + ">" + img + json.name + "</div>";
       }
    });

And that’s it, now we have Squarified Cushion Treemaps. I must say that I love cushion treemaps, they look a lot more cool than simple treemaps.

I made a small POC where you can enable/disable the cushion feature, among other interesting things:

Disclaimer: Some of this post arguments are inspired by the great talk by Guy Steele: Growing a Language.

So I was checking out the new JavaScript spec. (ECMAScript 4) lately, and I was very surprised (and disappointed) to see that Operator Overloading wasn’t even accepted as a proposal for ECMAScript 4.
I’ve noticed last year that the proposal was denied by all browser vendors, as you can see in the ECMAScript 4 progress spreadsheet created by John Resig, under the name of “Operator Overloading”.

This is heartbreaking for me… let me explain you why.

Why Operator Overloading (in general)?

Operator Overloading is a special case of polymorphism, in which operators like +, /, *, … can be overloaded by the user.
This is very useful in languages where the user can define special types (or classes), since it allows the developer to use notation that is closer to the target domain, and allows user types to look like types built into the language.

What Guy Steele said about Operator Overloading is that:

“If we grow the language in these few ways, then we will not need to grow it in a hundred other ways; the users can take on the rest of the task.”

To see why, think about these structures:

• 2D, 3D Vectors
• Matrices
• Intervals
• Complex Numbers
• Polar Coordinates
• Rational Numbers

One thing all these structures have in common is that their sum and product operations have a different definition than the one we give to integers.

There’s also an interesting fact about these structures: a lot of people use them, but a lot of people don’t.
For example, Matrices might be used by OpenGL/Direct3D developers, but it’s not very common to use this structure for manipulating the DOM or building AJAX applications.

However, each of these structures must be considered in any programming language.
Adding them all into some standard library might be too much. However, sooner or later, some developer will want to use them.

Here’s the dilemma as exposed by Guy Steele:
“I might say “yes” to each one of these, but it is clear that I must say “no” to all of them!“.

Operator Overloading solves this problem by giving the user the power to overload built-in operations and turn a non-domain specific language into a perfect tool for a developer’s specific needs.

By using Operator Overloading a developer can define operations on any custom type and its use will blend perfectly well into the language.

Wouldn’t be just beatifull if a and b beeing Complex Numbers, we could do this:

a + b * c

instead of this? :

add (a, multiply (b,c))

Ok, so now that I made my point about the power of operator overloading, let me explain you why I think this should be more carefully considered by the new JavaScript spec.

Why Operator Overloading in JavaScript?

To see why we should take seriously Operator Overloading in JavaScript, we first have to take a look at what happened to JavaScript in the last few years.

Only one thing happened to JavaScript in the last few years, AJAX.

The XMLHTTPRequest concept was first created by Microsoft, and wasn’t part of the web standards. They first used it in the year 2000, but a couple of years later Mozilla, Safari and Opera were also implementing it.
The standards covered that topic a lot of time after it was already implemented in all major browsers, and AJAX was already in the wild.

One strong aspect of JavaScript that was pretty important and that, IMHO, made the adoption of the “AJAX paradigm” a lot easier, is that JavaScript was already compliant with the “event-driven” programming paradigm, and the use of the XMLHTTPRequest object didn’t add anything new to this paradigm.
Just as callbacks were added to respond to DOM Element’s events, callbacks were used to handle server side answers. Although AJAX changed the way web applications were created, it did that by mantaining the event-driven programming paradigm.

Oh, another thing happened to JavaScript in the last couple of years, Canvas.

Canvas is following the same trend the XMLHTTPRequest object followed. It has been adopted by most browsers (Opera, Gecko, Webkit) and despite Internet Explorer’s efforts to not adopt this new feature, libraries already exist to make Canvas compatible with IE (to a certain point).
A couple of nice libraries that used Canvas were released last year: John Resig published Processing JS. Some other libraries that make use of canvas were also released, one of them is the JavaScript InfoVis Toolkit (my library! ).
The number of Canvas related stories really grew at Ajaxian, and there were also new breakthroughs by Opera and Firefox on the implementation of Canvas 3D.

There is one caveat to this Canvas thing though, it doesn’t use extensively the event-driven paradigm. Since all these Canvas implementations are related to Cairo and also take things from OpenGL and Direct3D (this is notably the case for the Canvas’ 3D API), IMO these concepts are more related to a functional programming paradigm than anything else.
I mean, 2D/3D graphics are all about geometrical operations. And geometrical operations are mathematical functions. These concepts might be harder to grasp than the “”AJAX paradigm”", and that’s why the adoption curve won’t be as high as the AJAX one, but there’s no doubt that Canvas developers are a niche.

And do you know which objects/types/classes are related to geometrical computation, Canvas, Canvas 3D, Cairo, OpenGL and Direct3D?

• 2D, 3D Vectors
• Matrices
• Intervals
• Complex Numbers
• Polar Coordinates

That’s exactly what I mean. The next logical step to bring a easier use for Canvas related programming should be operator overloading. This is the one feature that will be extensively used by JavaScript Canvas developers, since they have to deal with points, 2D and 3D coordinates all day.

For a last example, consider an interpolation function between two complex numbers

(to.$add(from.scale(-1))).$scale(delta).$add(from)

The same thing with operator overloading would be:

from + (to - from) * delta

You would make a developer’s life happier.

A couple of days ago I released version 1.0.8a of the JavaScript InfoVis Toolkit, that introduces some API changes and nice features.
This version focus mainly on two things:

• A more stable and usable Canvas class.
• Finishing last features included in the Spacetree, Treemap and RGraph InfoVis papers.

I’m quite happy with this version of the library, since it implements all lasting features in my TODO list.
This doesn’t mean much for the library, since I’m still having lots of ideas for next releases, but at least I finished something I put up to and that makes me happy .

Canvas

I implemented a new Canvas class, focusing on performance and usability.

The Canvas class is more like a Canvas Widget, since it creates a cross-browser canvas tag and a label div container, wrapped in a main div element.
This way, labels are relative to the canvas element and not absolute positioned, like they were on previous versions. I’d like to thank the people in this thread for providing nice ideas for implementing the Canvas class.

This canvas class makes also the Spacetree visualization cross browser, working perfectly well in IE6+.

Prior to version 1.0.8a, you had to put a canvas tag and a div label container in your html to create a new visualization. From version 1.0.8a this is no longer needed: you just have to include a visualization div container, like this:

<div id="infovis"></div>

A simple canvas instantiation could be something like this:

      //Create a new canvas instance.
      var canvas = new Canvas('mycanvas', {
         //Where to inject canvas. Any HTML container will do.
         'injectInto':'infovis',
         //Set width and height, default's to 200.
         'width': 900,
         'height': 500,
        //Set canvas styles.
        'styles': {
            'fillStyle': '#ccb',
            'strokeStyle': '#ccb'
        }
      });

The first parameter in the canvas constructor is the id of the canvas widget.
This id will be the main wrapper div id, and it will serve as prefix for the ids of the other DOM elements created.
The second parameter is a canvas configuration object. Some of the object’s properties are:

• injectInto: The id of the div where you want to inject the canvas widget
• width, height: Width and height of the canvas widget. Default’s to 200
• styles: an object containing specific canvas styles. If you want to know more about canvas styles you can read this article.

The html generated by this call will be appended in the div container (#infovis) previously defined:

<div id="infovis">
  <div id="mycanvas" style="position:relative;">
    <canvas id="mycanvas-canvas" width=900 height=500
    style="position:absolute; top:0; left:0; width:900px; height:500px;" />
    <div id="mycanvas-label"
    style="overflow:visible; position:absolute; top:0; left:0; width:900px; height:0px">
    </div>
  </div>
</div>

Notice how the Canvas id is used as the id of the main div container and also as prefix for the actual canvas element and the div label container element.
If we were using the Spacetree in IE, we could use an extra backgroundColor parameter as IE hack, since excanvas does not support clipping paths, which are used by the Spacetree visualization:

      //Create a new canvas instance.
      var canvas = new Canvas('mycanvas', {
         //Where to inject canvas. Any HTML container will do.
         'injectInto':'infovis',
         //Set width and height, default's to 200.
         'width': 900,
         'height': 500,
         //Set a background color in case the browser
         //does not support clearing a specific area.
        'backgroundColor': '#222',
        //Set canvas styles.
        'styles': {
            'fillStyle': '#ccb',
            'strokeStyle': '#ccb'
        }
      });

We can define also a background Canvas.
Take for example the RGraph example, in which we plot concentric circles as background for the visualization.
Prior to version 1.0.8a, the background was rendered at each frame, since at each frame of an animation the canvas is fully cleared to plot the graph’s next position. This wasn’t very good for performance.

Defining a background canvas was the sanest choice. That way the background is rendered only once:

  //Create a new canvas instance.
  var canvas = new Canvas('mycanvas', {
    //Where to inject the canvas. Any div container will do.
    'injectInto':'infovis',
    //width and height for canvas. Default's to 200.
    'width': 900,
    'height':500,
    //Canvas styles
    'styles': {
        'fillStyle': '#ccddee',
        'strokeStyle': '#772277'
    },
    //Add a background canvas for plotting
    //concentric circles.
    'backgroundCanvas': {
        //Add Canvas styles for the bck canvas.
      'styles': {
            'fillStyle': '#444',
            'strokeStyle': '#444'
        },
        //Add the initialization and plotting functions.
        'impl': {
            'init': $empty,
            'plot': function(canvas, ctx) {
                var times = 6, d = Config.levelDistance;
                var pi2 = Math.PI*2;
                for(var i=1; i<=times; i++) {
                    ctx.beginPath();
                    ctx.arc(0, 0, i * d, 0, pi2, true);
                    ctx.stroke();
                    ctx.closePath();
                }
            }
        }
    }
 });

The background canvas created will have mycanvas-bkcanvas as id.
For more information about the canvas class you can check its object reference, the examples provided with the library and the updated quick tutorials which you can find in the documentation.

Treemap

I implemented the Strip layout for the Treemap, in addition to the Squarified and Slice and Dice layout algorithms provided in previous versions of the library.
I updated the treemap example to impement different tiling algorithms. Use the dropdown box at the left of the screen to change the current layout.

Why another tiling algorithm?
Well, as the Wikipedia explains:
To create a treemap, one must define a tiling algorithm, that is, a way to divide a rectangle into sub-rectangles of specified areas. Ideally, a treemap algorithm would create rectangles of aspect ratio close to one; would preserve some sense of the ordering of input data; and would change only slowly when the underlying data changes slowly. Unfortunately, these properties have an inverse relationship.

The Strip tiling algorithm provides a good compromise between order, stability and aspect ratio values.
More precisely, the three techniques implemented in the JIT can be classified as follows:

• Slice and Dice: Ordered, very high aspect ratios, stable
• Squarified: Unordered, lowest aspect ratios, medium stability
• Strip: Ordered, medium aspect ratios, medium stability

So the Strip algorithm is a good complement to the tiling algorithms provided.

Spacetree

I implemented two new layouts for the Spacetree, bottom and right layouts.
You can change the Spacetree layouts by using the dropdown box at the left of the visualization.

The bottom layout could be pretty useful for making family trees or things like that .
Anyway, another good thing of the Spacetree is that it works for IE6+ now (thanks to the new Canvas implementation).
Some cleanup regarding the plotting algorithms and how labels were created was done, please check the ST quick tutorial to understand exactly what changed.

RGraph

I implemented the second animation constraint mentioned in the RGraph paper: child ordering.
This constraint decreases edge crossing during animations, making animations more intuitive and graspable by the viewer.
The child ordering constraint consists in mantaining child ordering for the parent of the clicked node, that way we can decrease the edge crossing cases during animations:

I didn't make a new example for this, but you should see the difference when comparing it with the examples packaged in previous versions of the library.

Hypertree

I did some Cleanup of the Hypertree code, and stripped off the Mouse class and the prepareCanvasEvents method.
Those kind of things can be easily implemented with DOM/AJAX frameworks like Mootools or JQuery.
The hypertree example packaged with the library shows a possible workaround for prepareCanvasEvents:

  //optional: set an "onclick" event handler on the canvas tag to animate the tree.
  var mycanvas = $('mycanvas');
  var size = canvas.getSize();
  mycanvas.addEvent('click', function(e) {
    var pos = mycanvas.getPosition();
    var s = Math.min(size.width, size.height) / 2;
    ht.move({
      'x':  (e.page.x - pos.x - size.width  / 2) / s,
      'y':  (e.page.y - pos.y - size.height / 2) / s
    });
  });

Anyway, that's all for now. Please feel free to file bugs if you spot one.
Remember also that the main project page has links to documentation, google groups, browser support, updated examples and some other things

I learned this “trick” some time ago, while reading the source code for the MooTools JavaScript framework (version 1.1, I think).

I used this “trick” not so long ago, when developing the Spacetree visualization for the JavaScript InfoVis Toolkit library.

When clicking a node, the Spacetree visualization unselects all tree nodes and then selects the nodes in between the root node and the selected node. This can be implemented as a recursive function, since we have to iterate through the clicked node and its ancestors to set those nodes as selected.

I defined an anonymous recursive function that receives a node and a special value as formal parameters, and sets the selected property from this node and its ancestors to the specified value:

  (function(node, val) {
      if(node == null) return;
      node.selected = val;
      return arguments.callee(node.parent, val);
  })

arguments.callee holds a reference to the defined function.
You can check that by copying this code:

  (function(text) {
    alert(arguments.callee);
    alert(text);
  })("some text");

and running it in your Firefox console.

Unfortunately, our anonymous recursive function needs to be called more than once, since we first need to unselect previous selected nodes, and then to select the nodes in between the clicked node and the root node.
Similar to the “return this” trick to chain method calls, we can add “return arguments.callee” to chain function calls.

  (function(node, val) {
      if(node == null) return arguments.callee;
      node.selected = val;
      return arguments.callee(node.parent, val);
  })

This way, we can call our function multiple times. I’ll first pass the previous clicked node in order to unselect the previous selected path, and then I’ll pass the new clicked node in order to select our new path:

  (function(node, val) {
      if(node == null) return arguments.callee;
      node.selected = val;
      return arguments.callee(node.parent, val);
  })(nodePrev, false)(nodeNew, true);

What’s more interesting though, it’s trying to do the same thing in another language, like Lisp or OCaml.
Who knows, you might sumble upon the Y combinator.

Update 10/2009: The project is currently hosted at GitHub.
Update 01/2009: Created a new hoc3.zip file and some documentation.

A while ago Radiohead published their House of Cards video data in form of CSV files. Each CSV file contains information about the 3D position of the points for each frame.

I wrote a couple of previous posts that covered how to render and save that data with OpenGL and OCaml and also how to customize camera movement in OpenGL.

This post shows how to customize particle animations for Radiohead’s House of Cards video.
A proof of concept for camera movement + particle animation is shown in this youtube video:

If you want to generate the video, you have to download Radiohead’s HoC music video data here. Also, you can download the source code for this project here.

This small project is organized in a way that is easy to add new features, camera animations and particle transformations in order to easily code new videos with different effects using the HoC data.

Radiohead’s HoC data is a set of CSV files. Those files are rendered in OpenGL with OCaml and then saved in bmp or jpeg files to be merged into a video using ffmpeg. If you want to know more about this you should probably read part 1 of this “trilogy”.

The Camera Model class allows you to make custom camera movements that can be handled and defined in a Timeline object in the main.ml file. If you like to know more about this, you can read part 2 of this “trilogy”.

This last post shows how to customize particle interpolation and movement by using the Particle Model class, the ParticleTrans module and the Timeline object.

Particle Model

The particle_model class handles particle animations.
Somewhat like the camera class, particle_model stores the initial frame and the last frame along with some extra information about the timing of the animation.
The particle_model then performs an interpolation from the initial_frame to the last_frame, rendering the state of the transformation in the draw function.

A possible interface for the particle model could be something like this:

class particle_model :
  object
    (* starting frame *)
    val mutable start_frame : VertexType.depth_vertex list
    (* ending frame *)
    val mutable last_frame : VertexType.depth_vertex list
    (* currently loaded frame *)
    val mutable loaded_frame : VertexType.depth_vertex list
    (* if setted to true, it will load a new frame for each
    step of the animation *)
    val mutable refresh_frames : bool
    (* same as the camera_model -check that post *)
    val mutable time : float
    val mutable total_frames : float
    val mutable transition : Transition.trans * Transition.ease
    (* extend start_frame or last_frame in order to
    have same number of points *)
    method balance : unit
    (* equivalent to the camera methods *)
    method step : unit
    method draw : float -> unit
    (* set the type of the animation you want
    to perform *)
    method set_animation :
      float ->
      bool * bool *
      (ParticleTrans.transformation * float *
       (Transition.trans * Transition.ease)) ->
      unit
  end

Particle animations have a special type, that ressembles the camera model transition type.
This type is defined as follows:

type animation_op =
    ParticleTrans.transformation * float *
    (Transition.trans * Transition.ease)

Just to make a comparison, the camera model transition type is:

type camera_op_list = (camera_op list) * float * (trans * ease)

This type can be divided into three main parts:

• The float value is the total number of frames the animation will use.
• The (trans * ease) value allows you to customize different type of transitions, from Linear, None to Quad, EaseInOut. More information about this is in the camera_model post.
• ParticleTrans.transformation is a function that applies a transformation to a frame. You can define custom functions in that module and then apply them to the visualization.
  I only defined a couple of functions, but you can define any other animation you like. You just have to define a function that receives a frame as input and returns a frame as output.
  The interface for ParticleTrans is:

  type transformation =
  	| Idle
  	| Project of float * float * float
  	| Random
  
  val idle : 'a -> 'a
  
  val project :
    transformation ->
    VertexType.depth_vertex list ->
  	VertexType.depth_vertex list
  
  val random : VertexType.depth_vertex list ->
  	VertexType.depth_vertex list
  
  val get_trans :
    transformation ->
    VertexType.depth_vertex list ->
  	VertexType.depth_vertex list

Putting it all together

The timeline object (described in the previous post) holds information about the camera and particle transformations beeing applied at each stage of the animation.
This class-less object is defined in the main.ml file and looks like this:

let timeline =
  object (self)
    val mutable frame = 0.
    val camera_timeline = [
    (* operations defined in the
    camera model post *)
    ]

    val particle_timeline = [
      (* frame number,  (invert, refresh frames, instruction) *)
      (1., (true, true, (Random, 120., (Elastic, EaseOut))));
      (420., (false, false, (Random, 50., (Quad, EaseOut))));
      (471., (false, true, (Idle, 80., (Quad, EaseIn))))
      ]

    method get_frame = frame

    method tick =
      frame <- frame +. 1.;
      self#update_camera;
      self#update_animation

    method update_camera =
      try
        let camera_anim = List.assoc frame camera_timeline in
          cam#set_animations camera_anim;
        with
          | Not_found -> ()

    method update_animation =
      try
        let anim = List.assoc frame particle_timeline in
          part#set_animation frame anim;
      with
          | Not_found -> ()
end

The particle_timeline and camera_timeline variables hold the transformations to be performed at different stages of the animation.

Download and Use

You can download the project here.
You can compile the project by typing:

ocamlc -g str.cma -I +camlimages ci_core.cma ci_jpeg.cma ci_bmp.cma
-I +lablGL lablglut.cma lablgl.cma interpolate.ml transition.ml camera.ml
 loader.ml particleTrans.ml particle.ml main.ml -o main

Any comment about the Video or the OpenGL/OCaml implementation is very welcome!

This post is about performing advanced camera movement in OpenGL.
We’ll use the same Radiohead’s HoC dataset we used in the previous post.

Once again, the quality of the youtube video is pretty lame. You can right click here and save link as… to download a high quality version of the video (~100MB).
I strongly recommend you to see the high quality video

Camera Instructions

Camera movement is made of Translations and/or Rotations.
We want to provide our camera model with instructions of the type:

• [ Translate from to ]
• [ Rotate from to rotation_axis ]
• [ Translate ...; Rotate ... ]

As the last example shows, multiple transformations can be done at the same time (translations and rotations).

The definition for a transformation type is:

type camera_op =
  | Translate of Gl.point3 * Gl.point3
  | Rotate of float * float * Gl.vect3

A camera instruction is a list of these operations (camera_op) and a number specifying the number of frames this transformation should take (i.e the duration of the transformation).

So, for example, this instruction:
( [ Translate( (100., 100., 100.), (0., 0., 0.) ) ], 300. )
translates the camera from (100, 100, 100) to (0, 0, 0) in 300 frames, that is in 10 seconds (at 30 frames per second).

Translation is done by simple interpolation. The interpolation formula for translating from A to B is something like this:
A + (B – A) * delta with delta in (0, 1).

Transitions

It would be nice if camera movement, besides being linear, could also perform other advanced transitions, like the ones used in Fx.Transitions by Mootools.
Some of these transitions are: Quadratic, EaseIn, EaseOut, EaseInOut, Back, Sine, etc…

These effects are achieved by applying functions to the delta value, changing the way it increases or descreases its value.
A possible interface for a Transition module is:

type trans = Linear | Quart
type ease = None | EaseOut | EaseIn | EaseInOut

val linear : 'a -> 'a
val quart : float -> float

val ease_in : ('a -> 'b) -> 'a -> 'b
val ease_out : (float -> float) -> float -> float
val ease_in_out : (float -> float) -> float -> float

val get_transition : trans -> float -> float
val get_ease : ease -> (float -> float) -> float -> float

val get_animation : trans -> ease -> float -> float

By using Transition.get_animation Quad EaseInOut delta we can change the timing of our animation from this:

into this:

Our camera instructions are then defined as:

type camera_op_list = (camera_op list) * float * (trans * ease)

For example:
( [ Translate( (100., 100., 100.), (0., 0., 0.) ) ], 300. (Quad, EaseOut))

The Camera Model

A possible interface for the camera model is:

class camera_model :
  object
    val mutable animations : camera_op list
    val mutable time : float
    val mutable total_frames : float
    val mutable transition : Transition.trans * Transition.ease

    method get_time : float
    method step : unit
    method draw : unit
    method translate : Gl.point3 -> Gl.point3 -> float -> unit
    method rotate : float -> float -> Gl.vect3 -> float -> unit
    method set_animations :
      camera_op list * float * (trans * ease) -> unit
  end

The camera_model instance variables contain the destructured camera_op_list type elements: animations, total_frames and transition.
We also provide individual methods for handling translations and rotations. These methods simply compute a delta value, apply the interpolation and then call GlMat.translate3 or GlMat.rotate3.

The 40 line implementation looks like this:

class camera_model =
 object (self)
  val mutable total_frames = 0.
  val mutable time = 0.
  val mutable transition = (Linear, None)
  val mutable animations = []

  method get_time = time

  method set_animations ans =
    let (x, y, z) = ans in
      animations <- x;
      total_frames <- y;
      transition <- z;
      time <- 0.

  method step =
    if time < total_frames then
      time <- time +. 1.

  method translate start last delta =
    let (trans, ease) = transition in
    let delta_val = Transition.get_animation trans ease delta in
    let (x, y, z) = start in
    let (x', y', z') = last in
    let DVertex(a, b, c, d) = Interpolate.cartesian
                                (DVertex(x, y, z, 0.))
                                (DVertex(x', y', z', 0.))
                                delta_val
    in
      GlMat.translate3 (a, b, c)

  method rotate start last vec delta =
    let (trans, ease) = transition in
    let delta_val = Transition.get_animation trans ease delta in
    let ang = Interpolate.cartesian_float start last delta_val in
    GlMat.rotate3 ang vec 

    method draw =
      let delta = time /. total_frames in
        List.iter (fun anim ->
          match anim with
            | Translate(start, last) ->
               self#translate start last delta
            | Rotate(start, last, vec) ->
               self#rotate start last vec delta ) animations
end

Timeline

Now that we have our camera model, we need a “timeline” object that can pass intructions to the camera at different stages of the animation.
We define a class-less object timeline that holds a list of camera transformations to be executed at a specific frame of the animation:

let timeline =
  object (self)
    val mutable frame = 0.
    (* Starting frame number, camera_instructions *)
    val camera_timeline = [
      (1.,   (* camera_instructions *));
      (310., (* camera_instructions *));
      (631., (* camera_instructions *) ]

    method get_frame = frame

    method tick =
      frame <- frame +. 1.;
      self#update_camera;

    method update_camera =
      try
        let camera_anim = List.assoc frame camera_timeline in
          cam#set_animations camera_anim;
        with
          | Not_found -> ()
end

Download and Use

This is all I’ve done to handle camera movement.
I’m not an advanced OpenGL/OCaml developer, so any comment/suggestion about my understanding of OCaml/OpenGL is very welcome.
You can download the source here.
You can compile the source with:

ocamlc -g str.cma -I +camlimages ci_core.cma ci_jpeg.cma ci_bmp.cma
-I +lablGL lablglut.cma lablgl.cma interpolate.ml transition.ml
camera.ml loader.ml main.ml -o main

Last part of this “trilogy” will be about particle transformations in OpenGL.
Hope you enjoyed it!