2018-01-18

Hello !

Here's the third part of my description of Top's vector graphics renderer. It will discuss the practical aspects of passing down data to the GPU with OpenGL and trying to optimize the performance of the renderer. (it will not explain all the steps to setup and manage OpenGL, so some familiarity with OpenGL API and GLSL may be required).

In Part 1 we saw how paths were built with GraphicsMoveTo(), GraphicsLineTo() and GraphicsCurveTo() functions, and how path stroking was implemented in GraphicsStroke(). In Part 2 we discussed polygon triangulation algorithms and how they were used to fill a path with GraphicsFill(). Our vector graphics system also exposes function to create fonts and gradients, to apply transformations, and to limit drawing to a given area defined by a clipping path. We briefly discuss them in the following paragraphs before addressing the OpenGL code.

(...)

Read more →

2018-01-03

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


Intro

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 →

2017-12-22

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 →