[plt-scheme] 2htdp/image

The complaints we were getting were just with creating the bitmaps at all.

(Internally, the representation of an htdp/image bitmap is either a
function that draws the bitmap (fast for drawing, but can't do
equality) or a bitmap with all the pixel values. The bitmap was
computed when an equality test happened or when image->color-list or
similar was used. It was making the images into bitmaps that triggered
the performance problems we saw.)

Robby

On Wed, Nov 18, 2009 at 3:45 PM, Todd O'Bryan <toddobryan at gmail.com> wrote:
> In my (aborted) attempt to reproduce the functionality of the teaching
> languages in Python, I used PNG encryption for bitmaps. Since PNG is
> lossless and well understood, I just saved bitmaps as a string
> containing the base64 encoding of the PNG data (obtained by the same
> method for all bitmaps). Equality worked out to simple string
> equality.
>
> I don't know how hard it is to PNG-ify an image, but I can't imagine
> it'd be much more expensive than creating the bitmap itself. If you
> attach the PNG data to the structure, then you have an easy way to do
> bitmap comparison that's at most O(width * height), and probably much
> better assuming you do simple compression on the PNG data.
>
> Todd
>
> On Wed, Nov 18, 2009 at 4:07 PM, Robby Findler
> <robby at eecs.northwestern.edu> wrote:
>> 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.
>>
>> Robby
>>
>> 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
>>>
>>>
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>>
>