Path: utzoo!attcan!uunet!seismo!sundc!pitstop!texsun!sun-barr!rutgers!tut.cis.ohio-state.edu!bloom-beacon!IBM.COM!MSACKS
From: MSACKS@IBM.COM (Michael Sacks)
Newsgroups: comp.windows.x
Subject: Fast, infinitely undoable graphics.
Message-ID: <050989.100845.msacks@ibm.com>
Date: 9 May 89 14:08:45 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: msacks@ibm.com
Organization: The Internet
Lines: 68

Fast Infinitely Undoable Graphics...

Problem:
An application requires the capability to display complex pictures
( > 1000 graphic primitives such as lines, polygons, text etc. )
in such a way that an arbitrary number of individual graphic primitives
may be chronologically and quickly undone, one by one, all the way to
the very first primitive drawn. The undoing process must occur with
the same rapidity as the drawing process and be visible to the end user.
In short we are faced with the problem that graphic operations while
additive are not subtractive.

The problem is how can I do this using Xlib. There are a number of
possibilities, listed below, some of which have been implemented on
other graphic systems( eg: suntools). However the client/server
model in X poses unique design constraints in this problem.

There are 3 obvious solutions:
(1)
Maintain a client data structure which is traversed for redisplay
each time a primitive is undone.
(2)
Before each primitive is drawn, obtain and store in the client application
the set of pixels that the primitive would would be written into,
and on undoing restore these pixels effectively erasing the primitive.
The pixels are stored in the application, and periodically compressed
to conserve space.
(3)
Before each primitive is drawn, associate a set of Pixmaps in the server
covering the pixels that the primitive would be drawn into, and on
undoing, restore these pixmaps, effectively erasing the primitive.

Comments on X solutions:
(1) an obvious approach, but for large pictures is too inefficient.
Consider picture with 1000 primitives and a conservative 5 bytes overhead
to be sent to server per primitive drawing operation.
To draw the complete picture requires 5 x 1000 bytes to be sent to
server. To undo a graphics operation requires redrawing the whole picture and
would cost on average 2500 bytes.
However to undo the complete picture requires 5000 + 4995 + 4990 ....+ 10 + 5 =
2.5 Meg to be sent to server!.
For fast undo of complex pictures this approach is impractical as
time spent actually redrawing the whole picture is too great.

(2) This approach previously implemented on Suntools.
Worked very well and was quick, undoing was faster than doing!.
Typically to save pixels under a line requred a
number of 10 by 10 blocks of pixels, say 20 of them. Thus to undo each line element
requires constant 2000 bytes associated with it.
Undoing the total picture requires 2 meg of data to be
saved, which after compression or run-length encoding could be easily reduced 50%.
A graphic undo requires a constant 2000bytes to restore pixels. To undo complete
picture requires 2Meg of data to be sent to server.
Undoing is fast as the blocks of pixels get restored efficiently using pixblt
operations.
In X however, this requires creation and repeated transmision of Images accross
network.

(3) An X'ish approach. Store pixmaps on server, save pixmap id's in client and copy
pixmaps back to window on undoing.  Undoing primitive costs 5bytes to be sent to
server and undo total picture requires 5k to be sent to server.
While plausable in theory, how would current X servers handle the creation of 20,000
pixmaps?

Any comments on this problem, similar experiences, alternative approaches,
efficiency issues that I as an X novice may not be aware of.

thanks in advance ... michael sacks