mark's blog

TOAD & Fischland on Mac OS X

I've spend too much time trying to play guitar lately but here's an update: I began integrating the boolean path operations into the TOAD library, added some unit tests, build a little free hand drawing demo, which handles pressure and rotation... it looks okay but there are still some errors to hunt down.

TOAD & Fischland on Mac OS X

Porting the code for boolean operations on paths in Paper.js to C++ turned out too hard.

But there are quite a few documented algorithms available for this:

1974 "Reentrant polygon clipping", Sutherland and Hodgemann (convex clip polygon)
1980 "Polygon comparison using graph representation", Weiler
1982 "Plane-sweep algorithms for intersecting geometric figures", Nievergelt and Preparata
1983 "An analysis and algorithm for polygon clipping", Liang and Barsky
1989 "An algorithm for computing the union, intersection or different of two polygons", Margalit and Knott
1989 "Algorithm for clipping arbitrary polygons", Andereev
1992 "A generic solution to polygon clipping", Vatti
1998 "Efficient clipping of arbitrary polygons", Greiner and Hormann
2005 "A new algorithm for Boolean operations on general polygons", Yu Peng et al.
2007 "An algorithm for polygon clipping, for determining polygon intersections and unions", Liu et al.
2009 "A new algorithm for computing Boolean operations on polygons", F. Martínez et al.
2012 "An efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique", Wang et al.
2013 "A simple Algorithm for Boolean operations on polygons", F. Martínez et al.

And I picked the most recent and F. Martínez was kind enough to mail me a copy of their C++ library which I'm now going to adapt to TOAD's data structures and bézier splines.

TOAD & Fischland on Mac OS X

No screenshots this time.

  • I've added a routine to subdivide a path using a raster. This is to approximate non-affine transformations of vector graphics the using the same strategy I used for bitmaps.
  • To get reduce the subdivisions and their artifacts after the transformation I've added Philip J. Schneider's FitCurve algorithm from Graphic Gems I, which is the same one as used by Paper.js and Xara Xtreme for Linux.

This feels like cheating. But the goal is still getting the architecture right, not finding the best algorithms.

Which is also why I'm putting the transformation stuff aside and began to implement a nib pen (aka. calligraphic brush). Basically it's an elliptical shape, influenced by pressure and rotation. Which means

  • I will have to store all these informations along with the path and
  • calculate the boundary of the brush sweep.

A convex hull algorithm and an union operation on paths should be sufficient to calculate the boundary. (Which means I'm also adding boolean path operations from Paper.js.)
My goal is to get a good emulation of Nikko's G-Pen nib, maybe even with a graphical representation of the pen itself so that one can see

  • how much pressure is applied to the nib and
  • what the zoom factor is.

I might be overdoing it but I do love putting lines down on paper with a physical pen. But then what happens afterwards, the occasional smearing or waiting for the ink to dry and the tedious ways to correct mistakes. I can live without those.

TOAD & Fischland on Mac OS X

Well, this took less than an hour. It is crude but enough to start working on combined transformations of bitmap and vector graphics.

TOAD & Fischland on Mac OS X

The proof of concept for the text editor looks good enough: One can move the cursor and select text but not modify it yet. Modifying is going to be another obstacle because I need an algorithm which handles nested tags and I want it to be able to operate on a subset of the text.

But now it's back to the non-affine transformations. This requires intersecting Bézier splines and the algorithm I (re-)invented for that some years ago for the flood fill algorithm didn't feel good enough. So I found the Bézier Clipping algorithm by T.W.Sederberg and T.Nishita but the end of their paper wasn't clear enough and neither it's implementation in Inkscape nor Andy Finnel's VectorBoolean were easy reads.

Much to my surprise I found it wonderfully implemented in a JavaScript library named Paper.js by Jürg Lehni and Jonathan Puckey. And I'm going to steal some more algorithms from their code like curve-line intersections, distance to curve or boundary of curves.

Now I wonder how long it will take me to squeeze an image into a Bézier deformation:

TOAD & Fischland on Mac OS X

I finally came up with a strategy to extend TTextArea with HTML support: Keep it simple and start with an editor which just edits a single line and displays the internal and rendered representations at once. About two years ago I tried to do the same directly with TTextArea and ended up in debugging hell.
This time it looks like I'm going have something I can easily integrate into TTextArea, replace THTMLView with, use it in the vector graphics editor for text fields and speech bubbles, a collaborative real-time editor, a screenwriting app, ...
And additional data structures might only be required for the paragraphs displayed on the screen.

TOAD & Fischland on Mac OS X

I was so happy about coming up with a design for non-affine transformations in Fischland, that I almost forgot that I don't just need these for vector paths, but also for bitmaps. I did a first crude experiment without anti-aliasing nor sophisticated algorithms which people might usually use for this. Next step will be adding subdivisions for more complicated transformations.

TOAD & Fischland on Mac OS X

  • Fixes to the mouse enter/leave handling solved the menubar issues.
  • I began to implement non-affine transformations:
    • Transformations will be implemented as groups, which retrieve the paths from the figures they contain and return transformed paths in turn. This will allow non-destructive transformations which can be nested, removed and parametrized with text fields, e.g. to specify a rotation of, say, 90° and later change that to 120°. This could also be exploited to turn Fischland into an animation program.
    • I haven't decided yet whether figures will return paths or if a special TPen class will convert drawing operations into paths. I thinks it's going to be the later as it provides a more intuitive interface.

TOAD & Fischland on Mac OS X

Started experimenting on how to implement a free form deformation. For this I am going to drop the transformation matrix from TFigure and replace it with an interface to manipulate all points of a figure. This also means I need an algorithm to divide figures like rectangles so that they will be affected by the deformation.

TOAD & Fischland on Mac OS X

After lying dormant for another year... starts to look promising:


Subscribe to RSS - mark's blog