johnf@apollo.UUCP (06/09/87)
On looking at the X version 11 description of which pixels constitute the
"interior" of a region to be filled, I notice a discrepancy between the
decision procedure used to decide what to do when a pixel centre falls
exactly on the boundary of the region (a "tie-breaker" algorithm) and the
algorithm used to make the same sort of decisions in rasterizing a line.
To summarize these algorithms briefly, the algorithm used for filled regions
includes the same pixels as would be included if the boundary lines were to
be displaced an infinitesimal amount to the left (ignoring the special case
of horizontal lines). This is a simple, consistent model. The algorithm used
in line rasterization does not seem to be as well thought out - it seems to
have been chosen in an ad hoc fashion, with the only internal consistency
constraint being to make sure that the same pixels are hit independent of
the order in which the end points are specified.
For an example of the current line drawing, look at the diagrams below.
Here "*" indicates the specified end-points of the line, and "x" shows
the pixel that will be touched as part of the line drawing rasterization:
+---+---+ +---+---+
+---+---+---+ | * | | | | * | +---+---+---+
| * | x | | +---+---+ +---+---+ | | | * |
+---+---+---+ | x | | | x | | +---+---+---+
| | | * | +---+---+ +---+---+ | * | x | |
+---+---+---+ | | * | | * | | +---+---+---+
+---+---+ +---+---+
It would be desirable for the tie-breaker algorithm used for line drawing
to be consistent with that used for defining interiors of filled regions.
If we apply the same decision procedure of imagining the line to be moved
an infinitesimal amount to the left we would want to draw lines as follows:
+---+---+ +---+---+
+---+---+---+ | * | | | | * | +---+---+---+
| * | | | +---+---+ +---+---+ | | x | * |
+---+---+---+ | x | | | x | | +---+---+---+
| | x | * | +---+---+ +---+---+ | * | | |
+---+---+---+ | | * | | * | | +---+---+---+
+---+---+ +---+---+
Note that this only changes the rasterization of lines when the major axis
is the x-axis (and, of course, only for those pixels where we need to make
a choice between two equally close candidate pixels).
The pixels where we need to make a tie-breaker decision are those pixels
for which the Bresenham error term is exactly zero. The way to implement
this change is to change the code in the low-level Bresenham routines as
follows (using mfbbres.c as the example)
if (axis == X_AXIS)
{
if (signdx > 0)
{
. . . .
if (e < 0) /* Change this to if (e <= 0) */
. . . .
else
. . . .
}
else
{
. . . .
if (e <= 0) /* Change this to if (e < 0) */
. . . .
else
. . . .
}