Path: utzoo!attcan!uunet!samsung!think!bbn!bbn.com!cosell
From: cosell@bbn.com (Bernie Cosell)
Newsgroups: comp.lang.postscript
Subject: Advice sought: drawing boxes faster
Message-ID: <50851@bbn.COM>
Date: 12 Jan 90 19:33:34 GMT
Sender: news@bbn.COM
Reply-To: cosell@BBN.COM (Bernie Cosell)
Organization: BBN Systems and Technologies, Inc, Cambridge MA
Lines: 69

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.com