[comp.windows.x] A developer's view of the X fill policy

madd@adt.UUCP (jim frost) (12/22/88)

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

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (12/22/88)

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

I hear a complaint, but I don't hear a proposal.  If you're willing to take
the time to write down a detailed semantic description of what you want, take
a shot at a syntactic description, identify incompatibilities with the current
protocol, and include a rationale as to why the benefits of those
incompatibilities outweigh the disadvantages, I'm certainly willing to listen.

I don't think I've ever seen a well-defined semantics for "border+interior".
I know PHIGS has edge/hollow/interior stuff, but I've never seen a PHIGS spec
that managed to really give precise semantics, although I've heard the CGI
folks may be doing some work here.  I suppose I could say "your application
sounds like a great match with PEX", and that the PEX extension is capable
of supporting your fill model as well as providing server-side structure
traversal which sounds like something you could use; I don't know if that
comes anywhere near satisfying you.

The X model doesn't really have "borders" per se.  Lines aren't borders,
they are filled polygons defined from a path.  The X fill semantics are
designed to allow seamless placement of contiguous polygons without having
pixels hit more than once.  This is viewed as a feature.  It is true
that there is hardware out there for which matching this semantics is
painful.  But, the
"obvious" alternative of leaving the semantics essentially undefined also seems
painful, from the developer's viewpoint.

Anyway, I'd be happy to get any further comments you have.

madd@adt.UUCP (jim frost) (12/31/88)

>I hear a complaint, but I don't hear a proposal.

Add two additional values to the GC field fill_rule, FillWithinPath
and FillIncludingPath.  Leave the fill algorithm selection up to the
server.  The ability of a client to select how insidedness is
determined is of limited use anyway.

FillWithinPath will fill all points within the given path and will not
fill points which lie on the path.

FillIncludingPath will fill all points within the given path and will
additionally fill points which lie on the path.

[These are very simple definitions but they should be adequate with
the additional definition of "path", which already exists in the X
protocol.]

Incompatibilities:

None that I can see, although software will require a server which
implements the additional functionality.  Since this is also the case
with extensions, I don't see a particular problem with this.

Benefits:

A lot of software will be easier to write.  Anything that uses the
idea of filled vs unfilled or bordered vs unbordered will take
considerably less time to write.  Currently you have to adjust your
polygons to get this kind of thing to work properly, which is easy
enough to do on a rectangle but is very difficult to do on more
complex polygons.

Many servers will be able to take advantage of special hardware.  It's
my opinion that getting the high-end workstation people on your side
will be good for X in general.

Detriments:

No loss of functionality.  No loss of performance.  Backwards
compatibility problem, but not a serious one.  You can always make use
of the old method if you like.

Comments:

>The X fill semantics are
>designed to allow seamless placement of contiguous polygons without having
>pixels hit more than once.  This is viewed as a feature.

I'm not so sure.  Just how many people make use of that "feature"?  If
you're placing polygons next to each other, can't you make the
adjustments yourself?  This is what I've always done in the past.  I
think this feature has limited use and causes far more problems than
it solves.

>It is true that there is hardware out there for which matching this
>semantics is painful.

Look at it from the other side: how much hardware is there out there
for which it is NOT painful?  I'd say just flat frame buffer stuff,
where you can pick and choose your technique anyway.

>But, the "obvious" alternative of leaving the semantics
>essentially undefined also seems painful, from the developer's
>viewpoint.

This is true, but some thought should be put into finding useful
semantics (or semantics which are useful to the greater audience), not
just defining them.

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

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (12/31/88)

    Leave the fill algorithm selection up to the
    server.  The ability of a client to select how insidedness is
    determined is of limited use anyway.

You may find it of limited use, but I suspect a developer that drew
a 5-pointed star using either of these fill_rules wanted to be sure
they got it all filled would be rather upset if it came up with a hole.
Are you *sure* you really mean this?

    Just how many people make use of that "feature"?

I don't know (any more than I'm likely to know how many would make
use of your proposed features).

    If you're placing polygons next to each other, can't you make the
    adjustments yourself?

Suppose I want to draw a filled diamond:
	(0, 200), (100, 100), (200, 200), (100, 200)
in one color and then extend it out to a large diamond in another color:
	(100, 100), (200, 0), (400, 200), (200, 400), (100, 200), (200, 200)
(did I get those right?).  I don't want any pixel lit twice.  Can you explain
what "adjustments" I make to achieve that (I really don't want to have to
figure out how to decompose polygons to achieve it).

    Look at it from the other side: how much hardware is there out there
    for which it is NOT painful?

Can you actually name some real hardware that would benefit from your
proposal, i.e. that follow the X rules except for the inside/outside
of the border pixels?  E.g., is it instead more typical of hardware to do
things like use Bresenham outlines for polygon paths, which *isn't* the X
definition of the path.  I'm wondering if you are really only solving part
of your problem, and whether your proposal won't in fact make the server
implementor's life even worse.  (I'm not really sure, I'm asking.)  You
may be making the programmer's life easier, but your original concerns
seemed primarily centered on server performance.

    This is true, but some thought should be put into finding useful
    semantics (or semantics which are useful to the greater audience), not
    just defining them.

We did put thought into the semantics.  We even had the semantics out for
public review.  Of course, maybe those who now care didn't care then,
or didn't know; we did the best we could.  I have heard various complaints
about the fill rule from various people, but it is far from clear to me that
I have heard common threads yet, except "make it implementation dependent",
and I'm not convinced that's "useful to the greater audience".

[Comments from other folks on this proposal would be welcome by me.]

madd@adt.UUCP (jim frost) (12/31/88)

>    Leave the fill algorithm selection up to the
>    server.

>You may find it of limited use, but I suspect a developer that drew
>a 5-pointed star using either of these fill_rules wanted to be sure
>they got it all filled would be rather upset if it came up with a hole.
>Are you *sure* you really mean this?

No, I didn't.  I didn't realize that the fill rules were supposed to
determine how complex polygons should be filled (considering the
description of each in the manual, this is not surprising -- it reads
very much like IBM's _Principles_Of_Operation_).  With this in mind,
perhaps we should make a new GC field, say border_fill, with possible
values FillWithinPath, FillIncludingPath, and FillPartialPath (which
of course would be the current method and should be the default).
This would certainly break a lot more things, but I believe it is a
necessary evil.

>    If you're placing polygons next to each other, can't you make the
>    adjustments yourself?
>
>Suppose I want to draw a filled diamond:
>	(0, 200), (100, 100), (200, 200), (100, 200)
>in one color and then extend it out to a large diamond in another color:
>	(100, 100), (200, 0), (400, 200), (200, 400), (100, 200), (200, 200)
>(did I get those right?).  I don't want any pixel lit twice.  Can you explain
>what "adjustments" I make to achieve that (I really don't want to have to
>figure out how to decompose polygons to achieve it).

Consider that I'm in exactly the same place.  How do I create a filled
complex polygon with no points on the path?  Currently it's
virtually impossible.  Is it useful?  For object-oriented graphics it
sure is!  Also, to create a complex polygon with all points on the
path I currently have to do both a fill and a draw, elsewise I get a
polygon with some edges missing.  This causes half of the edges on my
polygon to be "lit twice", by the way, which is exactly the problem
you said you avoid with the current fill technique.  If you're dealing
with objects like I describe, you loose very badly.

>    Look at it from the other side: how much hardware is there out there
>    for which it is NOT painful?
>
>Can you actually name some real hardware that would benefit from your
>proposal, i.e. that follow the X rules except for the inside/outside
>of the border pixels?

Silicon Graphics' hardware follows many of the X rules but would have
real problems with the X polygon fill definition.  I think the only
way they'd be able to make use of their hardware currently would be to
cause a fill inside a path and then draw the edges that X would have
filled.  Blech.

Even if it's not possible to make use of hardware and still follow the
X protocol, keep in mind that an awful lot of graphics is done in
object-oriented systems.  It is common to deal with shapes as objects
and to allow them to be bordered, unbordered, or have the border a
different color than the region it contains.  An addition to our
application, FIG and OOPS come to mind.  Interestingly, both FIG and
OOPS bypass almost all of the X high-level graphics, instead using X
as a point-by-point system.  I'm hoping not to have to go to that
level for our application.

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

bzs@Encore.COM (Barry Shein) (01/01/89)

Correct me if I'm wrong but isn't the current fill policy equivalent
to using CoordModePrevious with the first point (p0) satisfying
MIN(x,y) and adding (1,1) to p0(x,y) before filling to shift it? (I
realize not all the Fill calls use mode, but let's ignore that for the
moment)?

If that's so it seems Jim Madd's proposal to allow
FillWithinPath/FillIncludingPath or not is sound since the problem
that the protocol claims to solve now is fairly easily solved by the
above operation with FillIncludingPath whereas it's the current
approach which makes it hard to FillWithinPath for arbitrary shapes.

Like I said, I could be missing something, but I did get bit by
this also (just yesterday), the "fix" is rather ugly.

	-Barry Shein, ||Encore||

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/01/89)

    considering the
    description of each in the manual, this is not surprising -- it reads
    very much like IBM's _Principles_Of_Operation_

Documenting this stuff is hard.  If you have constructive suggestions
(viz. prose) for improving it, by all means send it to us.

    With this in mind,
    perhaps we should make a new GC field, say border_fill, with possible
    values FillWithinPath, FillIncludingPath, and FillPartialPath

So now I'll get to second-level semantics.  Are you sure you don't care
that this tracks the line-width, that you're only interested in essentially
one-pixel wide borders?  (Have you ever seen a one-pixel wide line on a
MegaScan display?  I've drawn one, but I haven't seen it :-)  Are you
sure you don't want "inside" to mean "not including the pixels that would
be drawn by the path outline using the current line-width"?  Or are you
sure that you wouldn't also like the capability of having the "outline"
start at the path and go "outwards", rather than being centered on the
path?  I'm describing things that are rather difficult to implement, but
again, I'm trying to make sure your proposal actually matches what you
think you're actually proposing, and that you're satisfied with the way
it turns out.

    >Can you explain
    >what "adjustments" I make to achieve that (I really don't want to have to
    >figure out how to decompose polygons to achieve it).
    Consider that I'm in exactly the same place.

Fine.  At least we now both understand that neither has "the" right answer.

    Silicon Graphics' hardware follows many of the X rules but would have
    real problems with the X polygon fill definition.  I think the only
    way they'd be able to make use of their hardware currently would be to
    cause a fill inside a path and then draw the edges that X would have
    filled.

I'm not sure this answered my question.  Are you sure their hardware defines
"inside" the same way?  Are you sure they don't, for example, define the
polygon edges with Bresenham lines?

    It is common to deal with shapes as objects
    and to allow them to be bordered, unbordered, or have the border a
    different color than the region it contains.

Yes, but as I've said, I've yet to see a crisp definition (agreed to
by many parties) of what constitute "borders" for objects.

dshr@SUN.COM (David Rosenthal) (01/01/89)

To my memory,  I was the person in the X11 design team that argued most
strongly for leaving the rules implementation-dependent,  in order
to allow the best possible use of available hardware.  I lost the
argument,  and (with the experience of porting the MIT server,
implementing the X11/NeWS server,  and using both X11's pixel semantics
and NeWS's continuous-space semantics) I now think it was best that
I lost the argument.

From the server implementor's point of view,  the problem of adapting
available hardware to ANY pixel-exact semantics specifications is severe.
But filling is no worse than anything else.  So the argument is not about
fills,  it is about whether pixel-exact semantics is appropriate for
all the X drawing operators.

From the client programmer's point of view,  if you are going to have
some drawing semantics pixel-exact,  you must have them all pixel-exact.
Anything else is a nightmare.  When writing client code for X11,  you
need to know exactly which pixels will be hit and which will not.
The sensible alternative to pixel-exact semantics is not leaving
the semantics to the implementors,  but PostScript-style semantics
which specify graphics in a continuous not a discrete space.
A graphics systems that leaves drawing semantics to the implementors is
useless (believe me,  I have been involved in doing this in my mis-spent
youth with GKS).

	David.

madd@adt.UUCP (jim frost) (01/03/89)

>So now I'll get to second-level semantics.  Are you sure you don't care
>that this tracks the line-width, that you're only interested in essentially
>one-pixel wide borders? [...] Are you
>sure you don't want "inside" to mean "not including the pixels that would
>be drawn by the path outline using the current line-width"?  Or are you
>sure that you wouldn't also like the capability of having the "outline"
>start at the path and go "outwards", rather than being centered on the
>path?

Given that wide lines are centered on the path, I'd say "inside"
should be whatever's inside and doesn't lie on the wide path.  I
wouldn't make the line go outward (or inward) from the path because
complex polygons (your star, for example) would really be interesting
if you did this.

jim

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/03/89)

    Given that wide lines are centered on the path, I'd say "inside"
    should be whatever's inside and doesn't lie on the wide path.

OK, now another question.  Wide lines in X are defined using the X
fill rule, which you are now trying to make variable.  So, when you
say "doesn't lie on the wide path", what fill rule is supposed to be
used to determine the set of pixels comprising the wide line?

madd@adt.UUCP (jim frost) (01/04/89)

>Ok, now another question.  Wide lines in X are defined using the X
>fill rule, which you are now trying to make variable.  So, when you
>say "doesn't lie on the wide path", what fill rule is supposed to be
>used to determine the set of pixels comprising the wide line?

I'm confused here.  The manual says "The fill_rule defines what pixels
are inside (drawn) for paths given in XFillPolygon requests."  I
believe you mean that fill_style is used to determine this.

I would treat the path as the line drawn using FillSolid since any
other method could leave a broken path.  Obviously cap_style should
be taken into consideration.

Note: I have no idea if anyone else on xpert is discussing this since
I'm not on the list.  Please send a copy to madd@bu-it.bu.edu if you
are replying to this.  Additionally, I get about ten bounces on
everything I send to xpert -- several of which are bad addresses -- so
someone might want to fix them.  I will compile the bounces and email
them to whomever maintains xpert if requested.

jim

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/04/89)

    I'm confused here.  The manual says "The fill_rule defines what pixels
    are inside (drawn) for paths given in XFillPolygon requests."  I
    believe you mean that fill_style is used to determine this.

Oops, sorry, actually I meant what border_fill (your new field) gets used
to define the wide outline?

MMcM@STONY-BROOK.SCRC.SYMBOLICS.COM (Mike McMahon) (01/04/89)

We have a generic graphics toolkit.  Its lack of specificity has already
caused problems for users.  For instance, the variation in the
interpretation of coordinate arguments among X, QuickDraw, PostScript,
and Windows makes it difficult to reliably draw a thick edge border
within a given rectangle.  We are forced to consider optional half
thickness minor adjustments in the native coordinate system toward some
ideal model, and/or a proliferation of virtual procedures.  I would
hesitate to recommend such fuzziness in the relatively lower level X
standard.  Perhaps where there is a large hardware advantage, access to
its capabilities could be provided via extensions, to be used
intelligently by higher level toolkits.

george@mnetor.UUCP (George Hart) (01/05/89)

>    Given that wide lines are centered on the path, I'd say "inside"
>    should be whatever's inside and doesn't lie on the wide path.
>
>OK, now another question.  Wide lines in X are defined using the X
>fill rule, which you are now trying to make variable.  So, when you
>say "doesn't lie on the wide path", what fill rule is supposed to be
>used to determine the set of pixels comprising the wide line?

It would seem that specifying FillIncludingPath and not drawing the
path itself would suffice.

Incidentally, (in case anyone thinks that Jim's is an isolated case),
I face the same dilemma that Jim does trying to move existing software
from our current object based system to X.
-- 
Regards.....George Hart, Computer X Canada Ltd.

UUCP: {utzoo,uunet}!mnetor!george
BELL: (416)475-8980

madd@adt.UUCP (jim frost) (01/05/89)

>actually I meant what border_fill (your new field) gets used
>to define the wide outline?

I don't understand the question.  The border ought to be defined using
the normal line description fields of the GC (line_width, line_style,
join_style, cap_style) with the exception of fill_style which should
be assumed to be FillSolid so that the border will be unbroken.

I've given it some more thought and I don't think it would be
necessary to add a new field.  Instead, fill_rule could have the
following values:

	EvenOddRule
	WindingRule
	UnborderedEvenOddRule
	UnborderedWindingRule
	BorderedEvenOddRule
	BorderedWindingRule

I really like this idea better since there wouldn't be any changes to
the structures.

Another idea would be to treat fill_rule as a bit field.  This would
be backward compatible if you did something like the following:

	#define EvenOddRule    0x0
	#define WindingRule    0x1
	#define UnborderedRule 0x2
	#define BorderedRule   0x4

jim
madd@bu-it.bu.edu

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/06/89)

    I don't understand the question.  The border ought to be defined using
    the normal line description fields of the GC

Let me try again.  You've said you want the border to be a wide line.  The
question is how the exact set of pixels comprising that line is defined.
A wide line in the protocol is defined using the definition of what it means
to fill a shape defined by an infinitely thin outline.  You originally proposed
changes to the rules so that there is variable semantics for whether pixels
on the outline are "in" or "out".  The proposal was later modified to apply
to the "border" rather than the "outline".  But, there is still the question
as to whether the outline of the border is "in" or "out" of the border.
George Hart has suggested:

    It would seem that specifying FillIncludingPath and not drawing the
    path itself would suffice.

But I'm not sure I parse that correctly.  If I take FillIncludingPath to
mean that the outline of the border should be "in" the border, then that
means I would "draw the [outline] itself", but George says "not".

George also says

    Incidentally, (in case anyone thinks that Jim's is an isolated case),
    I face the same dilemma that Jim does trying to move existing software
    from our current object based system to X.

and indeed, my question after all this is worked out is "Who else cares
a whole lot about this, and why?".

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/06/89)

	EvenOddRule
	WindingRule
	UnborderedEvenOddRule
	UnborderedWindingRule
	BorderedEvenOddRule
	BorderedWindingRule

    I really like this idea better since there wouldn't be any changes to
    the structures.

Perhaps, but the two concepts seem rather orthogonal to me, and a real kludge
to smash them together.

madd@adt.UUCP (jim frost) (01/07/89)

Ok, I understand what you mean now.  I hadn't realized that the fill
definition extended to lines as well, although I admit that this makes
sense.

Why should we have the proposed border_fill affect line drawing at
all?  If we don't, there isn't a problem with what's in the border and
what's not.  Just as the fill rule has no effect on lines, it would
seem that my proposed addition need have no effect (unless I'm
overlooking something, which is entirely possible -- am I?).

>and indeed, my question after all this is worked out is "Who else cares
>a whole lot about this, and why?".

Who cares?  At least two DEVELOPERS, both of which are doing object
oriented graphical systems.  They may not be the wave of the future
but object oriented systems are very useful things, and it might be to
X's advantage to make it easy (or at least easier) to write them.  I
might be missing the boat here but I thought the idea was to
standardize the industry on a graphical environment.  Making it
difficult to do common things isn't going to help.  We originally
picked X as an environment because it would give us such a wide range
of machines as a base after the port.  Unfortunately it turns out to
be easier to port to other systems than it is to get around some of
the limitations of X.  I'm trying very hard to correct this, not only
for my own good but for that of the industry.

jim
madd@bu-it.bu.edu

rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (01/07/89)

    Why should we have the proposed border_fill affect line drawing at all?

We shouldn't necessarily.  I'm just trying to get you to think through all
the issues, so that the proposal really proposes what you want (and also so
that you can begin to understand that design isn't always as simple as it
seems).  So, if border_fill doesn't apply to lines, I assume that means
you're happy with the existing ("partial border") semantics for wide lines?

    Who cares?  At least two DEVELOPERS, both of which are doing object
    oriented graphical systems.

Geez, stay calm.  I wasn't trying to write you off.  I already know about
you two developers, the question is whether there are more.  I'm not trying
to put down your idea, but for almost *any* idea I can probably find two
people who think it's a good one; the question is whether there is reasonable
consensus that it is a good idea.

   Making it difficult to do common things isn't going to help.

True, but the hard part is figuring out what is "common".  (For example,
PostScript doesn't seem to provide a "fill-sans-strokepath" primitive.)
That's why I'm asking the question of who else cares your proposed semantics.

madd@adt.UUCP (jim frost) (01/09/89)

>So, if border_fill doesn't apply to lines, I assume that means
>you're happy with the existing ("partial border") semantics for wide lines?

Sure, if someone else doesn't have problems with it.

>the hard part is figuring out what is "common".

Agreed.

jim
madd@bu-it.bu.edu