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@gclements.plus.com>