cosell@bbn.com (Bernie Cosell) (01/13/90)
I'm a pretty rotten PostScript programmer: although I can get my stuff work
and it isn't too hard to read or debug, it is invariably BEASTLY slow.
Well, my current bit of hackery is sufficiently slow that it is driving me
NUTS, and I thought I'd try here and maybe learn some trick and techniques
for making things go faster [and also, what sorts of things are slow].
My problem is that I need to draw a LOT of filled-in squares. like >100,000
of 'em. What I have
done is done a translate and a scale so that the edges of every box are
at integer coordinates [that is, (x,y), (x+1,y+1) are the corners of every
box]. Then to get the box drawn in the required shade of gray, I defined:
/box
{
setgray
moveto
0 1 rlineto
1 0 rlineto
0 -1 rlineto
closepath
fill
} def
and then the file has zillions of lines of the form:
33 42 .35 box
34 42 1 box
34 43 .28 box
etc. This is all generated from a program I wrote on Unix, so I can change
what 'box' is, its args, the general PostSCript environment, and stuff like
that. About the only thing I can't change is the order that the boxes are
drawn --- that is determined as a by-product of another whole big bunch of
processing [to *generate* what color each box should be]. Actually, now that
I write this, I see that what I'm doing is VERY VERY similar to generating a
raster-scan image with "megapixels".
Anyhow, how best to speed it up? I've played with the following ideas.
1) do run-length encoding... if a run of boxes in a row are the same
shade of gray, my UNIX program can notice that and compress them
all into a single "rectangle" call. THis'll actually help a *lot*!
2) Make as a special case to notice "setgray = 1.0" and just have the UNIX
program ignore those guys.
both of the above I understand and I will be hacking into the code over the
weekend. Now comes the sort of thing where I don't have a clue what might be
clever:
3) The UNIX program knows what the entire "gray palette" that it'll need
is before it starts out. Is there some way to "prebuild" a
'sample square' of each shade of gray and have "box" just become
"dump the square <there>", instad of having to calculate and fill
the square each time?
4) Can the above idea be extended to non-uniform areas? For example,
if I had a run of boxes with grays .6, .6, .4, .4, .3, and that
was repeated a hundred times here and there around the image,
I can detect those kinds of sequences in my UNIX program, but is
there some clever way to "precompile" regions like that? [something
like a BLIT, for example, might be useful for something like this].
Are there other general techniques for doing this kind of thing that I"m just
not thinking about right at all? Thanks!!
__
/ ) Bernie Cosell
/--< _ __ __ o _ BBN Sys & Tech, Cambridge, MA 02238
/___/_(<_/ (_/) )_(_(<_ cosell@bbn.comkevin@kosman.UUCP (Kevin O'Gorman) (01/14/90)
In article <50851@bbn.COM> cosell@BBN.COM (Bernie Cosell) writes: >I'm a pretty rotten PostScript programmer: although I can get my stuff work >and it isn't too hard to read or debug, it is invariably BEASTLY slow. .... >Anyhow, how best to speed it up? I've played with the following ideas. > .... > 3) The UNIX program knows what the entire "gray palette" that it'll need > is before it starts out. Is there some way to "prebuild" a > 'sample square' of each shade of gray and have "box" just become > "dump the square <there>", instad of having to calculate and fill > the square each time? This looks like a case for building a font with a few square "characters" and letting postscript cache them. It seems that with an alphabet of boxes in various shades of gray, you would be able to do what you want and let the most optimized part of postscript do the work for you. -- Kevin O'Gorman ( kevin@kosman.UUCP, kevin%kosman.uucp@nrc.com ) voice: 805-984-8042 Vital Computer Systems, 5115 Beachcomber, Oxnard, CA 93035 Non-Disclaimer: my boss is me, and he stands behind everything I say.
wcs) (01/14/90)
In article <50851@bbn.COM> cosell@BBN.COM (Bernie Cosell) writes:
] My problem is that I need to draw a LOT of filled-in squares.
] like >100,000 of 'em. ... [(x,y), (x+1,y+1) are the corners of every box]
] /box
] {
] setgray
] moveto
] 0 1 rlineto
] 1 0 rlineto
] 0 -1 rlineto
] closepath
] fill
] } def
] and then the file has zillions of lines of the form:
] 33 42 .35 box
] 34 42 1 box
Well, I have only epsilon experience with Postscript programming, so
these ideas mostly will be about programming techniques,
and any syntax presented below will be incorrect :-)
1) use "bind def", not just "def" - you're always using the same
basic routines, and you're not redefining them - so do the
parsing and dictionary lookups for the routine once up front.
2) The important trick:
] About the only thing I can't change is the order that the boxes are drawn
Not true - this is UNIX! You're generating an ascii text file,
with a simple structure on every line, so you can do
standard UNIXy things like running it through sort and then
through an awk/shell/C filter: I assume your program generates
boxes for almost the entire screen, and they're all the same size?
Define a routine "nbox", which draws a box next to the
previous one, using the syntax "grayness nbox" -
it's the same program as box, only you do
0 1 rmoveto
instead of the "moveto" you had. This means you won't have
to transmit, parse, and evaluate the x and y parameters most
of the time. Make a filter like this pseudocode
while read x y gray box ; do
if ( x == oldx && y == oldy + 1 )
then print "gray nbox"
else print "x y gray box" ; fi
oldx = x ; oldy = y
done
This means you almost always need only one parameter, the
gray level. It also makes it easy to do your run length encoding:
either define a "ngbox" to do the next box in the same gray,
or have your program further crunch the output to do rectangles.
3) Cut down your transmission times and parsing a little more by
naming your routines "b" and "n" instead of "box" and "nbox";
it probably matters more if you're on an RS232 line than if
you're on parallel or Appletalk. Use >9600 baud if possible.
--
# Bill Stewart AT&T Bell Labs 4M312 Holmdel NJ 201-949-0705 erebus.att.com!wcs
# ho95c has gone the way of all VAX/785s, so I'm now on erebus.att.comjmr@nada.kth.se (Jan Michael Rynning) (01/15/90)
In article <50851@bbn.COM> cosell@BBN.COM (Bernie Cosell) writes: >[...] My problem is that I need to draw a LOT of filled-in squares. >like >100,000 of 'em. [...] About the only thing I can't change >is the order that the boxes are drawn --- that is determined as a >by-product of another whole big bunch of processing [to *generate* >what color each box should be]. [...] I would use a large array (representing the drawing area) in the UNIX program, to record the grey values for all the squares. Then, after I finished the grey value computations, I would send the grey values for all the squares to the printer using the ``image'' operator. If 95 grey values were enough, I would code them as ASCII characters to save transmission time. It takes less than two minutes to send that data to the printer over a 9600 baud line. Using AppleTalk, it took 24 seconds to print on our Apple LaserWriter II NTX. Here's my test program: %! /linestring 80 string def systemdict /currentpacking known {currentpacking true setpacking} if [ 32 255 div /sub cvx 255 94 div /mul cvx /dup cvx 0.0 /lt cvx [/pop cvx 0.0] cvx bind [/dup cvx 1.0 /gt cvx [/pop cvx 1.0] cvx bind /if cvx] cvx bind /ifelse cvx currenttransfer /exec cvx ] cvx bind settransfer systemdict /currentpacking known {setpacking} if 72 dup translate 6.5 72 mul dup scale 317 317 8 [317 0 0 317 0 0] {currentfile linestring readline pop} bind image Here comes the data, coded as ASCII, with ASCII code 32=black, and 127=white. You don't want to see more than 100,000 bytes of test data on the net, do you? showpage Jan Michael Rynning, jmr@nada.kth.se Department of Numerical Analysis If you can't fully handle domains: and Computing Science, ARPA: jmr%nada.kth.se@uunet.uu.net Royal Institute of Technology, UUCP: {uunet,mcvax,...}!nada.kth.se!jmr S-100 44 Stockholm, BITNET: jmr@sekth Sweden. Phone: +46-8-7906288
batcheldern@hannah.enet.dec.com (Ned Batchelder) (01/17/90)
You've gotten some good suggestions. The "image" idea is probably the biggest win, but only works if your squares really do line up properly. If they have to overlap each other, or if the result is sparse in some way, it may not be the best way to go. If the data doesn't lend itself to "image"ing for some reason, then a font is the right way to go. But, you can't create a font with each character a different shade of gray as suggested. The font cache only remembers shapes, not shades. So your best bet is a font with different sizes and shapes of boxes, like your idea of run length encoding. You then have to set the gray explicitly. With text, the way to go fast is to get as much done with each "show" as possible. So if you need to do a mix of two grays, you might be better off doing one string that is all of the light gray, with spaces for the dark, and then another that is all the dark with spaces for the light, and they'll mesh together on the page. Ned Batchelder, Digital Equipment Corp., BatchelderN@Hannah.enet.DEC.com