(A clunky tool I made to marΧ up blog posts)


Groucho is a little tool to generate an HTML file from a text containing simplified and non-intrusive markup codes.

It was written in order to ease writing blog posts for my website. Its goal is to allow to write content along with formatting instructions, aiming at the least friction, thus avoiding the need to do a second pass manually adding html tags or using a more complex editing tool, a process that is repetitive and tedious, and makes the source text less readable.

As the content I'm writting on these posts is mainly technical, Groucho is built around three main goals :

  • Easy presentation of normal content, including sections titles, paragraphs, lists, images, links.
  • Formatting of basic maths or physics formulas, supporting maths symbols and notations.
  • Syntax highlighting of C source code.

Some examples :

*this is some text*   will print in bold : this is some text.
/this is some text/   will print in italics : this is some text.
_this is some text_   will print underlined : this is some text.

[m]x_+ = \frac{{-b+\sqrt{b^2-4ac}}{2a}}[/m]   will print this well-known maths formula :

x +   =   − b +  b2 − 4ac 2a


Read more →


Hello !

This is the second part to my series of posts describing the 2D vector graphics system behind Top's user interface. This one will focus on the triangulation of polygons, an essential operation when filling user-defined paths.

As we saw in the previous post, the user can describe a path using line segments and cubic Bezier curves. But as we can approximate those curves with series of line segments, the paths we have to fill are really polygons. Currently, my implementation of the fill function imposes the constraint that those polygons must not self-intersect and don't have holes. That's a reasonable assumption for a gui, and if we ever needed a self intersecting polygon it could be achieved by splitting the path at the intersections to create a set of non intersecting polygons. Except for this limitation, paths can represent any polygon, convex or concave, in any winding convention.

We want to triangulate said polygon, which means split it in no overlapping triangles to be sent to the GPU for rendering. Such a triangulation always exists and the number of triangles for n-gon is n-2. This theorem can be proved by a simple induction :

  • Base case : n = 3. Obviously we can triangulate a triangle and the number of triangles in that triangulation is one.
  • Now consider a n-gon P and suppose we know the theorem holds for all m < n. We chose a convex vertex p of P and q and r the previous and next vertices in a given winding order.
  • If [q;r] is a diagonal, split P along [q;r]. It gives us a triangle and a (n-1)-gon. We now have a triangulation of P with (n-1)-2+1 = n-2  triangles.
  • If [q;r] is not a diagonal, let s be the concave vertex inside triangle (p,q,r) which is farthest form (q;r). [p;s] is a diagonal, so we can split P in two polygons with j and k vertices, and we know they can be triangulated with j-2 and k-2 triangles. Furthermore, we now that n = j + k - 2. So P can be triangulated with j-2+k-2 = n-2 triangles.

This demonstration also gives us a first approach to implement the triangulation, which is called ear-clipping (at each step we can find a diagonal and clip one “ear”, ie one triangle). This approach is in O(n2) time, because we recursively find diagonals in O(n) time. But there are better approach performance-wise, one good compromise in terms of simplicity vs performance being in O(n.log(n)), which I will describe here.

Fig. 1 : Triangulating a monotone polygon. Green lines are valid diagonals. Red dotted lines are invalid diagonals. Red dots are vertices on the stack.


Read more →



This month I have been pretty busy replacing the whole rendering system of Top's user interface, which was based on Cairo Graphics, with my own handmade vector graphics renderer, using OpenGL. I discussed in a previous post the reasons why I wanted to drop Cairo, but in short : it's adding a bunch of dependencies we don't fully use, it complexifies the building and bundling of the application, and it's quite slow using either the software or the Quartz backend.

I'm pretty happy with the new renderer, and I will put a new build online after tightening the few last bolts, probably in the first week of January. It's currently supporting all features that we needed from Cairo, with only a slightly better performance, but there's a lot more room for optimization and I now have complete control over what's going on. Hopefully we will be able to redirect all the CPU horsepower freed in the process to a nice DSP engine !
In the meantime I'm going to make a few posts about that vector graphics system, covering how I handle path stroking, filling, text rendering, and performance issues.


Read more →