MSACKS@IBM.COM (Michael Sacks) (05/09/89)
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
tmb@wheaties.ai.mit.edu (Thomas M. Breuel) (05/18/89)
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. [... some solutions ...]
There is yet another solution to your problem, in fact one which
lets you undo graphics in arbitray order.
Essentially you want to count for each pixel how often it has been
drawn. Well, this is relatively straightforward to do with BITBLT:
(1) allocate a number of bitmaps (say 10) on the server
(2) when you draw a new item, draw it inside its own clean bitmap
(3) consider the 10 bitmaps on the server bits of a counter;
add "1" to the counter wherever your new item want to draw.
You can do this using perhaps 4*10 BITBLT operations
(you need another temporary bitmap for the carries).
(4) OR together the 10 bitmaps and display the result
If you want to undo, you subtract rather than add.
On an Amiga, talking to the BLIT directly, this takes perhaps 100ms;
a LIFE game that someone hacked up some time ago worked this way.
I don't know how well X11 would deal with this.
Thomas.peter@ficc.uu.net (Peter da Silva) (05/19/89)
[keep a count of the number of times the bit has been set] This doesn't work if you ever draw anything with color 0 (i.e., erase). Let's say you draw a black square, and then erase a letter 'A' in the middle of it. What do you do with the bits you cleared? Either you leave the count alone (and have no record of the 'A'), or you decrement it (and have an inaccurate record of the resulting square). -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: uunet.uu.net!ficc!peter, peter@ficc.uu.net, +1 713 274 5180. Personal: ...!texbell!sugar!peter, peter@sugar.hackercorp.com.
tmb@wheaties.ai.mit.edu (Thomas M. Breuel) (05/20/89)
In article <4243@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes:
[keep a count of the number of times the bit has been set]
This doesn't work if you ever draw anything with color 0 (i.e., erase).
Obviously. However, if you have a system that is built on the paradigm
of putting up individual "objects" on the screen such that you can
remove them or manipulate them individually, it doesn't even really
make sense just to draw a rectangle in the background color.
However, you can repeat the same trick of counting pixels for several
"layers" or several "colors" (with the obvious semantics of one layer
shadowing another).peter@ficc.uu.net (Peter da Silva) (05/22/89)
In article <2532@wheat-chex.ai.mit.edu>, tmb@wheaties.ai.mit.edu (Thomas M. Breuel) writes: > In article <4243@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: > > [keep a count of the number of times the bit has been set] > > This doesn't work if you ever draw anything with color 0 (i.e., erase). > Obviously. However, if you have a system that is built on the paradigm > of putting up individual "objects" on the screen such that you can > remove them or manipulate them individually, it doesn't even really > make sense just to draw a rectangle in the background color. Sure it does. Let's say you want to draw a circle with a square hole in it. How do you do this? You draw a circle and then you draw a square in the background color. So how do you undo the square? > However, you can repeat the same trick of counting pixels for several > "layers" or several "colors" (with the obvious semantics of one layer > shadowing another). Except that you lose ordering information, unless you do something like adding a new layer every time you change colors. This would probably save some space, but still wouldn't be able to deal with xor-mode drawing. That would require each xor-mode operation to be cut up into a separate color-1 and color-1 (or whatever pair of colors you select) operation... which would actually increase the memory required if you do a lot of xor-ing... not to mention slowing drawing down quite a bit. You might be able to save some space with a scheme like this. But not more, I think, than something more conventional like run-length-encoded deltas. -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Business: uunet.uu.net!ficc!peter, peter@ficc.uu.net, +1 713 274 5180. Personal: ...!texbell!sugar!peter, peter@sugar.hackercorp.com.
madd@bu-cs.BU.EDU (Jim Frost) (06/05/89)
At the company I worked for just a few short months ago, we had the
task of porting a very object-oriented graphical application to X
Windows. Since the application was object-oriented, and the objects
could be manipulated (scaled, moved, drawn, undrawn, etc), we had
basically the problem you have. Since we were porting to a Sun X
server, we had a tremendous incentive to make the resulting code be
pretty efficient, and I think we did fairly well at that.
What we did was keep a tree of objects. We had three kinds of
objects: shapes, which were obvious primitives such as point, line,
circle, rectangle, and text; objects, which were composed of shapes
and which could be opaque or transparent, active ("touchable") or
inactive, and some other properties; and surfaces, which were
basically windows (but which had properties such as transparency,
floatability, and "touchability" which are difficult to impossible to
do under X) which could have either objects or shapes drawn on them.
To get reasonable draw speeds, we did two things. First, we always
drew on a pixmap rather than directly on the display window, with
drawn areas copied in a single block to the window. X refresh
requests could therefore be satisfied with merely a copy, which was a
huge gain considering the complexity of the displays we were dealing
with (50,000 shapes were not uncommon). Second, no drawing was done
until an explicit or implicit refresh was done (implicit meant that an
input routine was called, obviously requiring the display to be
updated). A list of areas where the display needed to be updated was
kept, and only those areas which were affected were ever redrawn. To
keep things simple, anything that was in an affected area was redrawn
whenever that area needed to be redrawn, and *only* those things were
redrawn. There are many cases where you can loose a lot of
performance that way (eg when adding things but not removing them),
but we had limitations which caused me to leave it as it was.
This technique was very successful, and turned out to be very portable
as well. We moved the application from the X environment to the SGI
GL environment in two days (it screamed on the SGIs).
jim frost
software tool & die
madd@bu-it.bu.edu