[GRASS5] R_cont_rel & R_polygon_rel

[Glynn Clements]

Huidae Cho wrote:

> I tried to draw two boxes with R_cont_rel and R_polygon_rel (or R_box_rel).
> Even if I used the same coordinates, these two commands produced boxes with
> different areas.
> 
> For example,
> 
> R_move_abs(100, 100);
> R_cont_rel(1,0);
> R_cont_rel(0,-1);
> R_cont_rel(-1,0);
> R_cont_rel(0,1);
> 
> creates a 2*2 pixel box.  four edges are: (100,100)-(101,100)-(101,99)-(100,99).

The above sequence draws an unfilled diamond (rhombus). When rendered
on a pixel grid, the filled pixels may form a square, but it's a
rather odd way to achieve that goal.

> R_move_abs(100, 100);
> R_box_rel(1,1);

This ought to produce a 1x1 square, and is a sane approach.

> or
> 
> R_move_abs(100, 100);
> xarr[0] = 0; yarr[0] = 0;
> xarr[1] = 1; yarr[1] = 0;
> xarr[2] = 0; yarr[2] = -1;
> xarr[3] = -1; yarr[3] = 0;
> xarr[4] = 0; yarr[4] = 1;
> R_polygon_rel(xarr, yarr, 4);
> 
> creates a 1*1 pixel box.  (100, __99__).

This draws a filled diamond.

> R_move_abs(0,0);
> xarr[0] = 0; yarr[0] = 0;
> xarr[1] = 1; yarr[1] = 0;
> xarr[2] = 0; yarr[2] = -1;
> xarr[3] = -1; yarr[3] = 0;
> xarr[4] = 0; yarr[4] = 1;
> R_polygon_rel(xarr, yarr, 4);
> 
> draws nothing. that is (0, -1).

Seems reasonable.

> R_box_*() commands use XFillRectangle() which has width and height arguments.
> The width and height of a box are given by x2-x1 and y2-y1 respectively, so we
> lose one pixel both from width and height.  It looks like XFillPolygon() also
> behaves similarly.  It seems trivial, but it's sometimes really annoying.
> 
> What do you think about this?

Welcome to the world of pixel coordinates.

Area-filling operations typically treat the "canvas" (window, pixmap
etc) as a finite subregion of the continuous 2D plane (the
mathematical set R^2).

In this context, the coordinate <x,y> refers to the point (in the
mathematical sense, not a pixel) at the top-left corner of the pixel
with array indices <x,y> (assuming that the origin is at the top-left;
some systems use the bottom-left). IOW, the pixel <x,y> is a 1x1
square with its top-left corner at <x,y> and its bottom-right corner
at <x+1,y+1>.

A filled rectangle with width w and height h, and with its top-left
corner at <x0,y0> corresponds to the set of all points <x,y>
satisfying x0 <= x < x0+w and y0 <= y < y0+w. The bottom-right
filled pixel will have array indices <x0+w-1,y0+h-1>, i.e. the square
with its top-left corner at <x0+w-1,y0+h-1> and its bottom-right
corner at <x0+w,y0+h>.

A filled polygon consists of the set of points which lie inside the
boundary. For a convex polygon, "inside" is straightforward enough to
define. So far as rendering on a pixel grid is concerned, filling a
polygon will modify any pixel whose centre lies inside the polygon. If
the polygon's boundary passes exactly through the centre of a pixel,
the normal behaviour is to treat the pixel as inside if it lies on the
polygon's left edge (or top horizontal edge) and outside if it lies on
the right edge (or bottom horizontal edge).

A filled polygon is rendered by "drawing" a horizontal line along the
centre of each row of pixels (i.e. for row y, the line is the set of
points <x,y+1/2> for all x), and clipping that line against the
polygon, such that the clipped line comprises all points for which
x0 <= x < x1, where x0 and x1 are the intersections of the line with
the left and right edges of the polygon.

The reason why all of these cases are "open below, closed above" (i.e. 
the value has to be greater than *or equal to* the minimum but
strictly less than the maximum) is so that tessellation works
correctly.

Consider a 3x3 square, tessellated into two right-angled triangles:

  0,0   3,0
    +---+
    |\  |
    | \ |
    |  \|
    +---+
  0,3   3,3

Due to the open below, closed above rule, the pixels along the main
diagonal will be included in the upper-right triangle but not the
lower-left triangle. Always; regardless of which order the triangles
are drawn in, the order of the points, etc.

Sometimes, this can be important. E.g. for "XOR" or translucent fills,
it's important that each pixel in the above tessellation is drawn only
once. Or, if the two triangles are different colours, and the drawing
order varies, you probably don't want the pixels on the diagonal to
flicker.

All sane graphics systems work essentially as described above. Those
systems which don't (e.g. by treating coordinates as "inclusive" on
both sides) tend to fall down in non-trivial cases (e.g. 
tessellation).

OTOH, line-drawing operations tend to treat the canvas as a
2-dimensional array of squares (pixels), and coordinates refer to
either array indices or to pixel centres.

Thus, while a polygon edge from <0,0> to <0,10> runs down the exact
left-hand edge of the canvas, a line drawn from <0,0> to <0,10> runs
down the centres of the left-hand column of pixels, i.e. from
<1/2,1/2> to <1/2,10+1/2>.

When drawing diagonal lines, particularly those passing exactly
through many pixel corners (e.g. 45-degree angles), the situation
tends to get rather ugly. When a line passes exactly through a pixel
corner, exactly which pixels get rendered can vary between rendering
models, or even between implementations of a given model (when
hardware acceleration is involved, the choice is usually whatever is
easiest for the hardware), and may depend upon the sign of the line's
gradient and/or the direction in which it is drawn.

The only practical alternative to all of this complexity is to
dispense with pixels altogether. This is essentially what PostScript
does (but then it can afford to; with even the oldest and cheapest
laser printers having resolutions of at least 300 dpi, single-pixel
errors are irrelevant). All coordinates are floating-point, and there
are no line-drawing primitives.

If you draw a 1mm wide line in PostScript, it offsets the edges by
0.5mm on each side, adds caps at each end, and fills the resulting
closed region using the fill-closed-region primitive which is the
heart of the PostScript renderer. The only other primitive is bitmap
image rendering, although that is essentially just optimising the
process of drawing a 2D grid of filled parallelograms.

-- 
Glynn Clements <glynn at gclements.plus.com>