Path: utzoo!attcan!uunet!husc6!bloom-beacon!adt.UUCP!madd
From: madd@adt.UUCP (jim frost)
Newsgroups: comp.windows.x
Subject: A developer's view of the X fill policy (or: what needs to be done)
Message-ID: <8812211720.AA11260@adt.uucp>
Date: 21 Dec 88 17:20:59 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 76

For the past six months, my job has been to port a product which is
essentially a graphical database from the Silicon Graphics environment
to the X Windows environment.

This product draws a LOT.  The minimal screen has about 115 graphical
objects, which translates into over a thousand shape draws which are a
fairly even mixture of ellipses, polylines, and rectangles both filled
and empty.  Users can create screens of arbitrary complexity -- 15,000
graphical objects, or about 100,000 shape draws, are not uncommon.
Several users have screens which take over a million shape draws to
construct.  If our product is not the most graphically intense ever to
be ported to X, it certainly has the potential to be.

Using the SGI geometry engine, it was possible to redraw the entire
screen fast enough to make things usable under most circumstances.
Since X has substantially inferior performance on most (probably all)
systems, a complete rewrite of our graphics drawing routines was
necessary to minimize redrawing.

In the course this rewrite, we came across one peculiarity in the X
drawing routines for which I have been unable to find justification.

Under every other graphical system I've ever used, there were two
possible ways in which a fill was done:  border-inclusive or not.
Under X, filling is border-sometimes-inclusive.  What this means is
that the border will be included depending on which direction the
border is facing.  North and west facing borders are included in the
fill, south and east borders are not.  What this means in a practical
sense is that a rectangle (x, y, w, h) is drawn filled as (x, y, w -
1, h - 1).  This oddity is simple to overcome -- if you're filling a
rectangle.  If you are filling anything else, the only way to
accomplish a border-inclusive fill is to both draw the polygon and
fill it.  Since many X servers have fairly poor performance, this is a
substantial performance loss.  When drawing a million shapes, this
drop in performance is painful.

From a client's point of view, it is obvious that the fill policy is
not optimal.  Now I would like to point out that it is not optimal
from the server's point of view either.

Many companies have hardware support for graphics.  Obviously they
would want an X server that could take advantage of their hardware.
For example, Silicon Graphics' hardware has support for drawing and
filling polygons.  It does not, however, have support for such things
as border-sometimes-inclusive fills -- they'll have to do it in
software, a pixel at a time.  This is, again, a substantial
performance loss.  In this case it's not a loss of a few percent, but
a loss that will vary from a few percent for small polygons to running
millions of times slower for very large ones.  This loss is likely to
become very obvious when drawing, say, a million shapes.  It also will
make life very difficult on those who are porting the server, since
they cannot use existing routines.

I have, in the past, stated that X's fill policy shows a considerable
lack of foresight on the part of the designers.  I maintain this point
of view.  To me, it has the feel of someone writing the algorithm and
using it without thought as to whether it was a particularly good
algorithm for the job.  The X fill policy is a loss to both servers
and clients:  servers cannot make proper use of available hardware,
and clients need to go to extra work to get proper results.  About the
only gain I can see is that the original implementor didn't have to
use a different algorithm, saving some time at the expense of everyone
else.

As a developer, I call for a change or extension to the X protocol to
correct this.

Before I go, I would like to point out that most graphically intense
programs that I have seen run under X (eg oops, fig) have bypassed the
X shape drawing routines in favor of their own, using X as a stupid
graphics terminal instead of a high-level graphics description
language.  Would anyone like to venture a guess as to why?

Jim Frost
Associative Design Technology
madd@bu-it.bu.edu