Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!stanford.edu!agate!ucbvax!bloom-beacon!dont-send-mail-to-path-lines
From: mouse@lightning.mcrcim.mcgill.EDU (der Mouse)
Newsgroups: comp.windows.x
Subject: Re:  Zooming Pixmaps (code)
Message-ID: <9103071531.AA23472@lightning.McRCIM.McGill.EDU>
Date: 7 Mar 91 15:31:52 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 84

>> What is the fastest and most convenient way to zoom (pixel
>> replication would be sufficient) a 128x128 Pixmap into a 512x512
>> pixmap (4x zoom)?

> If - and it's a big if - your server is such that 512x512 pixmaps are
> cheap, and having the server blit pixmaps around is faster than
> reading them back to the client, working there, and sending them over
> again, it's possible to do this entirely on the server.

[...]

> I think I have such an algorithm designed, but have not actually
> written it out or tested it.  I hope to do so before long; if and
> when I get it working I'll send out another note here.

I now have a program that does this.  It uses two auxiliary pixmaps and
one auxiliary bitmap.  Given the two auxiliary pixmaps and the
auxiliary bitmap, and two GCs (one the depth of the pixmaps, one only 1
bit deep, for the bitmap), the algorithm is as follows.  Numbers in
parentheses after function names are call counts in my code.

1) Load the output pixmap with 16 copies of the input pixmap.
   Cost: XSetFunction (1), XCopyArea (5).

2) Initialize the bitmap to a ..X...X. pattern along one axis (the X
   axis, say).  (Each . or X is 1/8 the size of the bitmap.)
   Cost: XSetFunction (3), XSetForeground (2),
	 XFillRectangle (2), XCopyArea (2)
   Could be improved slightly.

3) Loop for i from big-size/8 (64 in the example) through 1, dividing
   by 2 each time:

   a) Perform a abcd->acbd style swap.
      Cost: XSetFunction (4), XSetForeground (1), XSetBackground (1),
	    XCopyArea (4), XCopyPlane (4)

   b) Shrink the mask by a factor of 2 and replicate it.
      Cost: XSetFunction (2), XCopyArea(2)

4) Initialize the bitmap to a ..X. pattern (this time, each . or X is
   1/4 the size of the bitmap.)
   Cost: XSetFunction (1), XSetForeground (2), XFillRectangle (2).

5) Loop for i from big-size/4 (128 in the example) through 2, dividing
   by 2 each time.  Body of loop is same as in step 3.

6) Repeat steps 2 through 5 along the other dimension.
...
9)

Total cost, for magnifying a 2^N pixmap to 2^(N+2):

XSetFunction	9 + 24N
XSetForeground	8 + 4N
XSetBackground	4N
XCopyArea	9 + 24N
XCopyPlane	16N
XFillRectangle	8

This is actually a special case of an algorithm to zoom a 2^N pixmap to
2^(N+M).  Cost estimates for the more general algorithm:

XSetFunction	1 + 2M^2 + 12NM
XSetForeground	4M + 2NM
XSetBackground	2NM
XCopyArea	1 + 2M^2 + 12NM
XCopyPlane	8NM
XFillRectangle	4M

Some of the XSet* calls could be collapsed into XChangeGC calls, but a
good Xlib will deal with this automatically.  The major cost is of
course all those copy calls.

But it beats copying it all through a straw to the client and back
again - if you're unlucky enough to be stuck trying to feed things
through a straw between the client and the server.

Full program available on request.

					der Mouse

			old: mcgill-vision!mouse
			new: mouse@larry.mcrcim.mcgill.edu