Archive for January 2006

Unifying and generalizing spatial transformation

(Edit 2008-01-14: updated formatting.)

I’m trying out an idea I had a while back for unifying and generalizing different notions of spatial transformation in Pan (and spatial & temporal transformation in Fran. The three notions are transforming a point, an image (which is a function from point to alpha), and an image filter (which is a function from image to image). A basic “transform” is a function from points to points. To transform a point, just apply the function. To transform an image, inversely transform the points fed into the image. To transform a filter, inversely transform the source image and forward transform the result image.

type VectorE       = (DoubleE,DoubleE)
type PointE        = (DoubleE, DoubleE)
type Image c       = PointE -> c
type HyperFilter c = Filter c -> Filter c

Then for instance, scaling has these three variants:

scaleP :: VectorE -> TransformE
scaleP (sx,sy) = \ (x,y) -> (sx * x, sy * y)

scale :: VectorE -> Filter c
scale (sx,sy) = (. scaleP (1/sx, 1/sy))

atScale :: VectorE -> HyperFilter c
atScale (sx,sy) xf =
  scale (sx,sy) . xf . scale(1/sx,1/sy)

Hyperfilters allow some beautifully modular formulations of filters.

Note how in scale and atScale, I’m inverting the scaling. Exactly this pattern of inversion happens for other types of transformations as well (translation, rotation, swirl, etc). The new idea is to capture this inversion pattern once in a general rule for transforming functions. A type class specifies types that can be spatially transformed, which is direct for points, a do-nothing for numbers and booleans, distributes over tupling, and works similarly to atScale above for functions. To make this fly, I’m changing my representation of points and vectors from pairs to data types, which makes the code less succinct but is more strongly typed.

There’s a big catch in this plan: I only know how to handle invertible transformations, which rules out, e.g., tiling.

Here’s the class of transformable values:

class ITrans a where
  iTrans :: ITransformE -> a -> a

and the handling of functions:

instance (ITrans a, ITrans b) => ITrans (a->b) where
iTrans xf f = iTrans xf . f . iTrans (invIT xf)

The type of invertible transforms simply has a pair of transforms:

data ITransformE =
  ITransformE { itForward  :: TransformE
              , itBackward :: TransformE }

invIT :: ITransformE -> ITransformE
invIT (ITransformE forw back) = ITransformE back forw

Besides doing what I already do more uniformly, this generalized approach to transformation should be just the thing for interactive images, which may be neatly formulated again, as functions.


I am working on a new implementation, called Pajama, of the image synthesis embedded language Pan, this time generating Java applets. The advantages over Pan will be

  • Easy to run examples. Anyone with Java 1.5 or better can simply visit a web page to see and interact with the examples.
  • Examples run on all major platforms (wherever Java 1.5 runs), while Pan ran on Windows only.
  • The Pajama compiler runs on all platforms supporting GHC and the java compiler. In contrast, the Pan compiler ran only under Windows and only with Microsoft’s Visual C++ compiler. Worse yet, Pan used a GUI library (WTL) that Microsoft no longer supports. I haven’t been able to run the Pan compiler for quite a while now.

The disadvantage of Pajama over Pan is speed. Trig speed is quite a bit slower, and I suspect array accesses are also. Mustang (Java 1.6) improves trig performance considerably, though only with the server JVM, but almost everyone would be using the client JVM. I hope speed improves over time.

Quite a lot of Pajama is already working. I have first examples running here. More on the way.

April 13 edit: Pajama now runs on Java 1.4 and up, not just 1.5, thanks to Retroweaver, a class file rewriter.