[plt-scheme] 2htdp/image

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Wed Nov 18 16:07:57 EST 2009

What you describe in the first paragraph (below) is what htdp/image
did, except that it didn't provide the second equality operator, only
the bitmap-based one. One of the things we found is that doing a full
bitmap comparison for equality was too expensive for systems and that
was part of the impetus for 2htdp/image.

So far, all of the trickyness in 2htdp/image is in setting up the
precise data definition for images to make equality match what one
would expect (and still be linear time (usually)).

Finally, what you say about matrices (in a followup message) doesn't
really work for rotation because you need to compute the bounding box
of the shape (to be prepared for future overlays and stuff) and thus
you actually need to do a linear time computation to find that bound
box (ie, apply the matrix to all of the points in the shape)-- it
isn't just (constant time) matrix multiply. But yes, thinking thru all
of these issues is what we've been doing recently.


On Wed, Nov 18, 2009 at 9:13 AM, Stephen Bloch <sbloch at adelphi.edu> wrote:
> I think this is a reasonable approach to images: by default, store them in
> terms of drawing primitives (so rotation, scaling, etc. work nicely) but for
> display and some other purposes, "flatten" them to bitmaps.  It also makes
> sense to have two different equality operators on images: do they have the
> same bit-map representation right now, and would they continue to have the
> same bit-map representation after rotation, reflection, scaling, etc?
> So what should the drawing primitives be?  The obvious base cases (to me)
> are ellipses (filled or outline), polygons (filled or outline), line
> segments, and bitmaps.  And maybe text in a specified font.  The obvious
> operators, off the top of my head, are vertical and horizontal
> concatenation, overlay (with translation), rotation, reflection, scaling,
> and clipping.  Concatenation is the composition of an overlay and a
> translation.  Conveniently enough, rotation, reflection, translation, and
> scaling (as well as skewing) can all be represented as matrix
> multiplication, and matrix multiplication (at least in a pure, exact
> mathematical world) is associative, so any SEQUENCE of rotations,
> translations, reflections, scalings, and skews can be represented as a
> single matrix multiplication.  Overlay, and clipping to an arbitrary
> rectangular region aligned with the current coordinate system, should be
> trivial (although they can't be represented as matrix multiplication).
> Now, about exactness.  It would be nice if (reflect-horiz (rotate 72 (rotate
> 200 (rotate 88 (reflect-horiz blah))))) were exactly equal to blah.  If you
> represent rotation, reflection, scaling, and skewing by matrix
> multiplication with floating-point matrix entries, it may not be.  On the
> other hand, if you represent each of these operations by separate tree nodes
> even when they're in sequence, flattening (and therefore displaying) becomes
> needlessly expensive, especially after you've run an animation of a spinning
> star for a few minutes.  Obviously, images coming from photographs should by
> rights be considered inexact, as should anything stored in a lossy format
> like JPEG... and for display on a physical monitor, we don't need exact
> images anyway.  Why don't we just cut the Gordian knot and say that ALL
> images and ALL functions on them are inexact, and you can't reasonably rely
> on the equality I mentioned at the top of this paragraph?  At low
> magnification, they may turn out to have equal bitmaps, just as the result
> of a floating-point computation may be within a large delta of another
> floating-point value, but one would no more expect exact equality on
> computed images than on computed inexact numbers.
> Most of what I've said above applies to 3-D "images" too, of course, but
> that's another bucket of worms....
> Stephen Bloch
> sbloch at adelphi.edu

Posted on the users mailing list.