Personal tools

Diagrams/Dev/Freezing

From HaskellWiki

Jump to: navigation, search

Some rough notes/explanations on freezing and how it relates to optimizing the backend API. Eventually these notes should go into the user manual.

Contents

1 The issue

Most often one wants to be able to describe a diagram consisting of a collection of shapes, some of them obtained by transforming (e.g. rotating, shearing, scaling, translating) other shapes, and then draw the whole thing using a consistent line width. It would be strange if, say, a large circle was drawn with a thicker line just because it happened to be generated by scaling a smaller circle. Diagrams are supposed to be scale-invariant but in actuality it would be surprising for them to be truly scale-invariant with regards to line width.

Another way of thinking about it is that we want to think of diagrams as 'abstract geometric entities' (e.g. perfect circles, etc.) with the details of how they are actually drawn being a separate issue.

...On the other hand, sometimes we really do want, say, scaling a diagram to scale the line width proportionally! It really depends on the situation.

Note that other things in addition to line width may have the same issue, e.g. patterns/textures like gradients, fill patterns, etc. (once we add support for those).

2 Solution #1: transformations always affect attributes

One possible "solution" is to say, in essence, "To heck with thinking of diagrams as abstract geometric entities; transformations will always transform attributes, period." This forces the user to place attribute annotations carefully in order to produce the desired behavior. For example, in order to produce a scene consisting of variously scaled shapes, all drawn with a consistent line width, the user must apply the line width attribute after doing all the requisite scaling.

Put more simply, the following snippets of code would produce different output:

 foo # scale 2 # lw 1
 foo # lw 1 # scale 2

This is certainly possible, but has some drawbacks. Most notable is that if a user obtains several diagrams, each of which has already had a line width applied to it, it may be practically impossible to assemble them into a single diagram with consistent-looking lines.

3 Solution #2: 'freeze'

Another solution (the one currently adopted by diagrams) is to have a primitive operation called freeze such that transformations normally do not affect attributes such as line width, but after applying freeze, they do. Intuitively, freeze can be thought of as taking a "snapshot" of the physical realization of a diagram, and from then on transformations apply to the realization/drawing rather than to the abstract geometric ideal underlying it.

For example, under this scheme

 foo # scale 2 # lw 1
 foo # lw 1 # scale 2

have the same meaning, but

 foo # lw 1 # freeze # scale 2

is different.

4 Semantics of 'freeze'

One issue is that some backends may not support the ability to do stroking in the context of some transformation (so that e.g. lines come out fatter in some places and thinner in others). It might be nice to define an alternate semantics defined in terms of, e.g. an "average scale factor" for a given transformation, which can be applied directly to the line width attribute itself. The issue would be coming up with a definition which is compositional.

However, cairo and SVG, at least, both support stroking within transformed contexts, so this hasn't become an issue yet.

5 Implementation of 'freeze'

freeze introduces quite a bit of difficulty into any backend implementation. The reason this is difficult is that some of the transformations should apply to styles and some shouldn't. But the transformations and styles occur in the tree all mixed up. (Also, transformations can affect some attributes!) The way we handled this in the past was to never give any transformations directly to a backend. We only gave fully transformed primitives. For example, the cairo backend's implementation of withStyle works by first performing the given rendering operation with no transformations in effect (since it is given fully transformed primitives), then it applies just the transformations occuring above freeze (the ones which should affect the line width and so on) before doing the actual stroking.

However, if we want to be able to apply transformations incrementally while walking down the tree this gets tricky. We can incrementally apply transformations occurring above freeze with no issues, but below a freeze things become problematic since the transformations should apply to primitives but not attributes.

Even just continuing to fully apply the transformations to primitives and allowing styles to be applied early would go a long way, I think. We could also do some work to coalesce styles. e.g. consider

 foo1 = hcat (map (fc blue . circle) [1,2,3,4,5])
 foo2 = hcat (map circle [1,2,3,4,5]) # fc blue

It would be nice if these actually generated the same output, i.e. the programmer didn't have to worry about making such changes to their code in order to "optimize" it.

6 Possible re-implementation of 'freeze'

Not only does freeze adds a significant amount of difficulty into the implementation of backends (although with the new tree based backends, this is somewhat mitigated) but also to the implementation of gradients and patterns as well. Here we discuss a possible alternative to the implementation of freeze that would hopefully simplify dealing with freezing.

The first step is to eliminate the Split monoid. Then we would rewrite the freeze function so that:

1. freeze traverses the tree and applies all transformations to styles and primitives leaving a tree with no transform annotations.

2. Replace attributes that are affected by freeze, e.g. line width with a twin attribute that is Transformable.

The result is a diagram tree that will respond as expected to all transforms applied after the freeze. One downside is that this implementation may not support non-uniform scaling of line width (although it may be possible by accumulating the transform alongside of line width). One the other hand, the implementation of gradients and patterns should be more straight forward. Furthermore the implementation of an unfreeze function is now possible by traversing the tree and replacing all occurrences of the transformable version of line width by the un-transformable one. The feasibility of this implementation seems plausible, but there remain some issues that need to be addressed including how to handle transforming scale invariant primitives.

7 Units, and getting rid of split transformations

Another possible approach: the key observation is that the heart of the matter is **units**. That is, when we specify that a circle has a radius of 2, or a line has width 0.01, what do these numbers mean---with respect to what are they measured? Right now, the answer is that the 2 is measured with respect to the local coordinate system, and the 0.01 is measured with respect to the final, "absolute" coordinate system. There are at least two other frames of reference with respect to which one could wish to make measurements, and at least for line width, one might wish to specify which reference frame one would like to use to measure it, rather than being forced to use one particular one.

  • A "logical" coordinate system, given by specifying that every diagram has a certain, set, arbitrary size (e.g. 100x100). In fact, it actually makes more sense to measure line width with respect to this logical reference frame by default than with respect to the final coordinate system, since e.g. saying that lines have a default width of 1 (in logical units) would mean that lines are always drawn 1/100 the width of the diagram -- lines would look consistent across all diagrams. Currently, the actual size of the lines depends on the absolute size of the diagram, meaning you often have to adjust the line width to get them to look good.
  • The output coordinate system, i.e. the requested physical output size. One could imagine a situation, for example, where you always want lines that are five pixels wide, no matter how big the diagram is actually rendered.

The idea is that now each measurement is transformed in some way inherent to its semantics, so freeze can be implemented by a simple traversal which converts some units to others. We can also implement unfreeze easily, and we don't need split transformations anymore. I think this does mean giving up on transforming frozen lines---but I don't feel too bad about that, since (1) I don't know of anyone ever using it, and (2) now that we have path offsets you could always just transform one of those to get the same effect.

There are a lot of details still to be worked out here, but at the very least I believe that starting to **think** in terms of these different measurement frames of reference will be useful.

In order to help make this idea more concrete, lets compare the line width of the square in following program using these 4 different units: Absolute, Local, Logical (using an arbitrary size of 1 x 1), and Output. Assume that the diagram is generated with an output width of w and the resulting line width is in output units.

 square x # lw y # scale s

The line widths of each unit would be:

Absolute: (y * w) / (s * x)

Local: (y * w) / x

Logical: y * w

Output: y

Note that the type of y would actually have to change to something like:

   data Measurement 
       = Absolute Double 
       | Local    Double 
       | Logical  Double 
       | Output   Double