Sunday, September 1, 2013

New Drawing Algorithm

I recently implemented a new drawing algorithm for morphs. The algorithm is similar to the algorithm in Pharo/Squeak and redraws only the parts of the world that changed, instead of the whole world.

When a morph issues a redraw, the world's damage recorder is notified to add the damaged area (outer shape in global pixel coordinates) to its damage area list. This is list of rectangles that defines the area to be redrawn.

The damage recorder redraws the world as fast as possible, i.e. there is a "loop" running in the background that redraws the world. This loop is created with the JavaScript function "setInterval" which takes a function (BlockClosure) and an interval (that is zero). Since JavaScript is single-threaded, the function is evaluated only when there is no other code running at the moment. Note that it not possible to replace this implementation with a "while(true)" loop, because then the browser would become unresponsive (because there is always JavaScript running and the browser does not update the content, process event and no other Smalltalk code can run).

At some point, the damage recorders issues a redraw of the damaged parts of the world (AthensWorldMorph>>redrawNow:). The damage recorder provides the list of damage rectangles. The morph first redraws itself (without submorphs) and clips the drawing area by the polygon resulting of the accumulation of all damage rectangles. Then the morph checks, for every submorph, if the submorph's outer shape intersects with at least one of the damage rectangles. If so, the submorph is redrawn recursively using the same algorithm. For every recursive call, the list of damage rectangles might become smaller, because the algorithm passes only those rectangles to the submorph which insect with its outer shape.

If you want to take a closer look at the redrawing algorithm, you can activate a graphical visualization of the redrawn parts (similar to flashing damage rects in Pharo), by executing "AthensGlobalMorphSettings instance showDamageArea: true".

Sunday, August 18, 2013

Text Morph and Morphic Tutorial

During the last week, I implemented a text area morph in Amber-Athens. The basic functionality is almost finished, and after three iterations, I can say that I am more or less satisfied with the design. It is not perfect and the implementation is still quite slow, but I know a couple of methods that could be optimized in order to boost the performance.

The text area box supports the following features.

  • Displaying and editing text without formatting

  • Multi-line strings

  • Automatic line break if a line is longer than the width of the text area box

  • Vertical scroll bar

  • Cursor and multi-character selections

  • Navigation with arrow keys

Here's a short overview of the characteristic of my implementation.

  • The content of the text area box contains of several lines. In addition, more lines might be generated if the content is changed, if a line is longer than the width of the text area box. We call all such lines ("real" and "newly-created lines") virtual lines. "AthensVirtualTextAreaLine" represents a virtual line and is responsible for handling horizontal pixel coordinates (offsets inside a line). The text are box ("AthensEditableTextMorph") is responsible for handling vertical pixel coordinates (lines). For example, given a pixel offset, "AthensEditableTextMorph" retrieves the line and "AthensVirtualTextAreaLine" retrieves the position of the cursor in that line.

  • When editing text, the new string is currently set via "text:". This re-generates all virtual lines. Actually, this is not necessary in most cases. Consider, for instance, that we added a single character to a (virtual) line. We might have to move some characters to other lines (below) even in the lines below the insertion, but it is a more or less local change. Lines before the insertion are not affected at all. In a future version, I will change the algorithm to handle small text editings in the virtual line class and use the same algorithm (recursively) for the next line, if a change is necessary (in most cases this will not be the case).

  • The text is rendered in the morph "AthensEditableTextMorph". We can specify a width for this morph, but not a height. It is always as high as the text content requires it to be. "AthensTextAreaMorph" is a subclass of "AthensScrollAreaMorph" and a decorator for "AthensEditableTextMorph". It adds the scrolling functionality to the text area box and delegates all method calls to it.

  • Text selections are represented with a "selectionStart" and a "selectionLength". If the selection length is zero, nothing is selected and we show only the cursor. The length can also be negative. The selection start is the offset of character preceding (in front of) the cursor. I.e., "selectionStart == 1" means that the first cursor is in front of the first character.

With the new text box, I could build a tutorial for the Morphic functionality (works in Chrome/Chromium only so far, I will fix that soon) that runs entirely on the Morphic stuff itself. There are only four steps at the moment, but I will add more steps in the future in order to cover the basic features.

As you can see, the tutorial is now a full-screen application, i.e. the Canvas and the world morph cover the whole page content.

Friday, August 9, 2013

Morphic Update: Scroll Bar, Scroll Area and List Box

In the last week, I implemented the AthensListBoxMorph. A list box is a rectangular container that has several list items as submorphs. A list item can be selected or unselected. The list box clips its content if it contains more list items than it can display. It provides scroll bars instead.

The image shows the demo application (Athens Tutorial) at step 39. Don't forget to execute step 33 before to create the surface and the world.

I implemented the list box by subclassing AthensScrollableArea. This is a morph that contains two scroll bars (horizontal and vertical) and a container morph called "outerContainer". The outer container contains another container called "innerContainer". The inner container's size is the bounding box of all morphs that are added to the scrollable area. We can scroll the content by moving the inner container inside the outer container. We need the outer container only for minor display reasons: the scroll area has a small rectangle in the bottom right corner that should be blank. If we had no outer container that clips the content, we might see content from the submorphs at this position. Furthermore, we do not have bother with z indices: scroll bars are always visible because they can never be overlayed by submorphs.

List items are instances of AthensListItemMorph. We can add arbitrary objects to a list box. They are automatically wrapped inside an AthensListItemMorph. The list item displays the item's string representation ("item asString").

There are only vertical scroll bars. We can generate horizontal scroll bars by rotating them by 90 degrees. Scroll bars have three important properties:

  • value: the position of the scroll bar slider (between 0 and 1)

  • buttonStepSize: defines how the value changes when clicking the up/down buttons. For example, a button step size of 0.1 increases the value by 0.1 when clicking the down button once.

  • sliderRange: the size of the slider

Thursday, August 1, 2013

First UI Morphs implemented

Here is a short status update for the Morphic implementation. So far, I implemented AthensButtonMorph, AthensRadioButtonMorph, AthensCheckBoxMorph, AthensWindowMorph, AthensTextMorph, and AthensIconMorph. The icon morph is simply a text morph that uses Font Awesome to display good-looking icons.

I made one more change to the event handling functionality. Every time we click on a morph, the according mouse event is triggered, no matter whether we clicked the morph itself or one of its submorphs. In my opinion, this is what programmers want most of the time (just one example: click a button that contains an additional image). In the event handler, we can check whether the event was triggered for the top-most morph. Therefore, we can easily check if we clicked the morph itself directly.

If you want to try the implementation yourself, open the tutorial, execute step 33 and then step 37 and/or step 38 (I will eventually change this, such that you don't have to click that often).

The following image shows step 37. It is a simple example that increases or decreases a number. The tiled background is the world morph that contains all other morphs.

This is the source code for step 37.
|window descText counter optIncrement optDecrement button|
"Step 37: [Morphic Demo] Using basic Morphs."

window := AthensWindowMorph new.
window title: 'Counter Example'.

descText := AthensTextMorph new.
descText text: 'Current value: '.
descText translateByX: 25 Y: 40.
window addMorph: descText.

counter := AthensTextMorph new.
counter text: '0'.
counter translateByX: 150 Y: 40.
window addMorph: counter.

optIncrement := AthensRadioButtonMorph new.
optIncrement text: 'Increment number'.
optIncrement translateByX: 25 Y: 70.
window addMorph: optIncrement.

optDecrement := AthensRadioButtonMorph new.
optDecrement text: 'Decrement number'.
optDecrement translateByX: 25 Y: 90.
window addMorph: optDecrement.

optIncrement onChange: [:val | optDecrement checked: val not].
optDecrement onChange: [:val | optIncrement checked: val not].
optIncrement checked: true.

button := AthensButtonMorph new.
button text: 'Do it'.
button translateByX: 25 Y: 120.
button width: 150.
button onMouseClick: [:evt | |val|
val := counter text asNumber.
optIncrement isChecked
ifTrue: [val := val + 1]
ifFalse: [val := val - 1].
counter text: val asString].

window addMorph: button.
surface world addMorph: window.

The next image shows step 38. As I mentioned in a previous post, every morph has its own transformation matrix. This allows us to rotate, scale, translate, and perform any other matrix operation on the morph. The example only contains buttons for rotation and scaling of the x axis.

Performance Issues

You will probably notice that moving windows and especially resizing windows is quite slow. So far, I did not implement any optimizations to the drawing code. Even the smallest change causes the complete world to be redrawn. I plan to optimize this by redrawing only the parts that actually changed.

More importantly, some operations like resizing a window, trigger multiple changes at once, e.g. changing the window's width, its height, and sending a layout change notification to all submorphs (which might again result in changing things). Most operations (changing height, width, transformation, colors, ...) result in a redraw. Therefore, we actually redraw the world multiple time if we just resize a window once. That's why the performance is currently so bad. I plan to optimize this by implementing a world state recorder that draws the world as fast as possible if there are changes. In the example that I just explained, the world state recorder is notified several times that something changes but only redraws the world after the resizing (and all other changes that the resizing triggers) is completed (remember: JavaScript is asyncronous). Therefore, we only redraw the world once even if the width/height of several morphs changes.

Monday, July 29, 2013

Morphic Characteristics

In the last week, I made some changes to the Morphic stuff. Here is a list of characteristics of my Morphic implementation.

  • Every Morph has an owner and a list of submorphs.

  • Morphs do not have a position/rotation/scaling anymore, but a transformation matrix. This matrix can translate, rotate, scale, ... the morph. It is possible to translate, rotate and translate the morph again.

  • Morph transformation is relative to its owner's transformation (transformation matrix multiplication).

  • It is not possible to get or set the current position of a morph. A morph can be transformed, relative to its current transformation. In order to set the morph position, we can reset the current transformation matrix (to identity) and translate it.

  • Morphs do not have a width or height. In the drawOn: method, we have to specify an "outerShape". The outer shape should contain all drawings. It is used for point-in-morph tests (mouse events) and as the clipping region. For example, a button's outer shape should be its rectangular border.

  • Submorphs are clipped at the outer shape.

Monday, July 15, 2013

Morphic-like Interface: first ideas

As a first interface to build user interfaces with Athens, I chose morph composition. Every morph is an object that contains behavior and has the ability to draw itself on the Canvas. Every morph has an owner and a list of submorphs.

The class diagram gives an overview of the current Morphic classes. "AthensHTMLMorphicSurface" and "AthensHTMLMorphicCanvas" are the Athens-HTML classes with Morphic and event support. I already presented some functionality, e.g. "onMouseDown:", in the previous post ("Mouse Event Handling").

"AthensHTMLMorphicSurface" has a bidirectional reference to a world morph. The world morph is the overall owner of all submorphs, i.e. every morph will eventually have the world morph as a supermorph (except for the world morph itself). "AthensMorph" provides basic morph functionality, e.g. submorphs handling and drawing. The method "drawOn: canvas" contains Athens code that we usually write inside a "drawDuring:" block. "drawAll" draws the receiver and all of its submorphs (and the entire transitive closure).

Every morph has a position (translation), rotation and a scaling vector. These values are encoded in "transformation" (an "AthensAffineTransform" matrix) and separate instance variables (not shown in the diagram). At first, scaling is applied, then rotation, then translation. "globalTransformation" stores the complete transformation matrix for the morph, including all transformations of owner morphs. Consider, for instance, that A is owner of B. If A is rotated by 90 degrees and B is rotated by 180 degrees, we expect B to be drawn with a rotation of 270 degrees (relative to A's owner). "globalTransformation" is used for mouse events (convert absolute coordinates to morph coordinates) and for drawing. "AthenHTMLMorphicCanvas"'s implicit transformation is set to "globalTransformation". Every time we draw something (inside "drawOn:"), the implicit transformation is applied to the path transformation. I will probably implement this differently, later: it is faster to provide a modified "AthensAffineTransform" as path transform that loads "globalTransformation" with "loadIdentity" and applies "globalTransformation" automatically when setting the matrix values.

"AthensDummyWorldMorph" is just an implementation detail: Morphs might not have an owner directly after creating them while it is still allowed to set transformations at this time. This triggers a redraw automatically and also requires the owner to be redrawn (there might be something behind the morph that now becomes visible). Of course, this does not work if the morph does not yet have an owner and was never drawn yet. "AthensDummyWorldMorph" is a null object.

There are some issues that I could not solve yet: for example, when transforming (e.g. rotating) a morph, I have to redraw the whole world because something behind the morph might become visible. This could involve a lot of rendering, but I cannot think of an easy alternative.

Step35 and step36 of the tutorial contain examples for composing and transforming morphs. You have to run step33 before, because it creates the morphic surface.

Mouse Event Handling: first ideas

For building GUI applications with Amber-Athens, mouse events are very important. HTML Canvas itself does not provide any mouse event handling, but we can use JavaScript elements (as we can on any DOM element). We can define a callback that gives us the pixel position as a parameter for mouse movement, mouse down and mouse up event.

I implemented the even-odd rule to determine if the user clicked on a shape. This only works with polygons, therefore we need to convert curves first (not implemented yet). A path might consist of several polygons (due to "moveTo:"). In that case, we run the algorithm for every polygon ("contour").

This does, however, not work as expected if two shapes intersect each other. In this case, we might want to check if we clicked the upper or the lower shape. The solution is to do the point-in-polygon tests in the inverse rendering order.

Amber-HTML-Morphic contains subclasses of AthensHTMLSurface and AthensHTMLCanvas that provide event handling functionality and some first Morphic ideas (see next post). The idea is to separate the Athens code from event handling and Morphic stuff, such that AthensHTMLSurface and AthensHTMLCanvas only contain code for rendering graphics. Since event handling is platform-specific, we need separate HTML and Cairo implementations.

We can bind events with "onMouseMove: aBlock", ..., just like DOM events in Amber. Step34 in the tutorial shows an example.
	|path poly|
"Step 34: Event handling (just a piece of the code)"

surface drawDuring: [:canvas |
path := canvas createPath: [:builder | "Create path"].
poly := path asPolygon].

surface onMouseMove: [:e | surface drawDuring: [:canvas |
surface clear: Color gray.

canvas setShape: path.
(poly includesPoint: e offsetX @ e offsetY)
ifTrue: [canvas setPaint: Color blue]
ifFalse: [canvas setPaint: Color green].

canvas draw]].

The code above shows a part of the code in step34. "path asPolygon" converts a path to a Polygon. At the moment, this works only for simple paths without curves. A path is a list of operations (e.g. "lineTo:", "moveTo:", "curveVia:", "close", ...) that can be passed to an interpreter.

We have three types of path-related classes in Athens-HTML: "AthensSimplePathBuilder" (part of Athens-Core) generates a path object (that is platform-specific, e.g. "AthensHTMLPath"); "AthensHTMLPath" is the Amber-specific path object that can draw the path by replaying/sending the path commands to itself; "AthensPolygon" is a polygon that can be built by replaying/sending the path commands to an empty instance of it (from "AthensHTMLPath").

In our case, the path is passed to a new "AthensPolygon". This class will also be responsible for flattening curves to polygons. It also provides a method for the point-in-polygon test. If we receive a lot of mouse events, we should cache the polygon when drawing the path (as we did in the example).

Friday, July 12, 2013

Status Update: Week 4

Athens is almost completely implemented in Amber. There are still some minor issues.

  • Browser compatibility: e.g. Firefox does not support line dashing, "miterLimit" is not set correctly in Chrome.

  • Drawing text: "getPreciseAscent" is not supported by Canvas. There is no nice way to get the height of a text (only dirty hacks involving reading pixels or creating DOM elements).

  • Canvas limitations: some paint modes not supported by Canvas (e.g. "colorBurn").

For now, I will not work on these issues.

The next steps will be implementing mouse events and tests. For mouse events, I have to implement an algorithm to transform paths to polygons and test if a given point is inside the polygon (probably De-Casteljau and Even-odd rule; a part of this is already implemented in Athens).

It is difficult to write automatic tests for Athens. My first idea was to render images and calculate the hash of the pixels. However, this value differs among browsers. I will probably start implementing manual tests: the tester sees a reference image and has to compare it to the actual Canvas rendering.

Athens Performance on Amber

It is no surprise that the Athens implementation in Amber is much slower than the implementation in Pharo. Athens comes with a demo application that repeatedly draws a complex vector image (consisting of many paths) and shows the frames per second (fps).

In the tutorial in Amber, you can start this benchmark by executing step32 (remember to execute step2 before!). When you click "Do it" a second time, the execution stops and print the fps to the Transcript (printing to the Transcript does currently not work correctly in my Amber version).

If you want to run the demo in Pharo, you have to execute "VGTigerDemo runDemo".

On my computer, I have 30-33 fps in the browser (Chromium 24) and 70-80 fps in Pharo. The demo is slower in Firefox (20-25 fps). I ran the benchmarks on Ubuntu 12.04.2 on a computer with an Intel i5 dual core CPU.

Athens-HTML Architecture

In this post, I will describe some important classes of Athens that are used in the Pharo implementation (Athens-Cario) and the Amber implementation (Athens-HTML).

In the diagram below, you can see that there are three kinds of packages (the diagram contains only some packages, classes and methods). Athens-Core-* packages contain classes that are shared among all Athens implementations. For example, AthensCanvas contains functionality for setting the paint and the shape that should be drawn. It also contains a "draw" methods that delegates the drawing process to the paint/shape using double dispatch. The actual drawing code is located in the Paint classes. There are Paint classes for Athens-Cairo and Athens-HTML. The Paint classes in Amber-Core are abstract, i.e. they only define the interface and all methods are subclass responsibility.

At the moment, it is not possible to share Athens-Core classes between Pharo and Amber Smalltalk. Amber has some limitations, e.g. selectors may not contain underscores and class variables are not supported (only class instance variables). However, I could copy most of the code of the core classes.

Project Description

This summer, I will port Athens, a vector graphics library for Pharo, to Amber Smalltalk, as part of my Google Summer of Code (GSoC) project. The project mentors are Nicolas Petton and Igor Stasenko.
What is Athens and Amber Smalltalk?

Athens is a vector graphics library for Pharo that uses libcairo. Athens supports drawing various shapes such as rectangles and paths. Paths can consist of lines and curves (e.g. Bezier curves). Shapes can be drawn with a stroke color and a fill color (paints). The fill color can be a solid color, a color gradient (radial and linear), a bitmap, or another surface (i.e. another drawing). The shapes and paints that I mentioned before, are only the predefined ones that are supported out of the box. You can add your own shapes and paints that use already defined ones. If you are interested in Athens for Pharo, you can find it on Smalltalk Hub.

Amber is an implementation of Smalltalk that runs entirely in the web browser. It compiles Smalltalk code to JavaScript. Amber supports writing JavaScript code, as well. This can boost the performance (e.g. Amber has to wrap all message sends in Smalltalk to support things like "doesNotUnderstand". When writing JavaScript code directly, this is not the case). At some points, I made use of JavaScript inlining.

I will port Athens to Amber Smalltalk using the HTML5 Canvas. The Canvas provides methods for defining shapes (e.g. rectangles and paths) and filling them. Some browsers implement the Canvas with libcario. Most concepts from Athens can be mapped directly to the Canvas. There are, however, some limitations in the Canvas.

  1. The Canvas specification does not support all features that are supported by libcairo and Athens. For example, Canvas supports only 12 "globalCompositeOperations", whereas Athens supports more. There is no easy way to implement the missing ones, so we will skip these for now and implement them, once there is browser support.

  2. Some browsers do not implement the entire Canvas specification or implement it wrong. For example, some browsers support all 12 "globalCompositeOperations" in theory, but they do not draw them correctly. Another example is line dashing in paths: this feature is currently not supported by Firefox. Therefore, it will not work in Firefox (my current implementation simply draws a non-dashed line in Firefox).

My vision is to provide a common vector graphics library for Pharo and Amber Smalltalk. Afterwards, we can use Athens to draw user interfaces in Pharo and Amber Smalltalk with the same Smalltalk code. This allows us to write Smalltalk applications that run both in Pharo and in the web browser.

I prepared a schedule in my project proposal. You can take a look at it in order to get an overview of the next implementation tasks. The timeline is, however, outdated. You can track the project progress in this blog and on the demo website. Athens comes with a tutorial that explains the API. The demo website contains the whole tutorial. It is important, that you always execute step 2 before executing any other step because this step creates the Canvas surface.

Please feel free to write me an email or post in this blog if you want to share your ideas (concepts, implementation, API, or whatever), report a bug, or just want to leave a comment.
Important Links

Source Code on Github
Demo Website
Project Proposal