6 DUIM-Graphics Library
6.4 Rendering conventions for geometric shapes
This section describes the conventions for how DUIM renders a shape on a display device.
When DUIM draws a geometric shape on a display device, the idealized geometric shape must somehow be rendered on that device. This involves mapping points on the idealized geometric shape onto points on the display device.
Idealized geometric shapes are made up of a set of mathematical points which have no size. The rendering of these shapes on the display device is usually composed of pixels, which are roughly square, and are specified in "device coordinates". Device coordinates are calculated by transforming the user-supplied coordinates by each of the following:
- The user-supplied transformation
- The medium transformation
- The transformation that maps from the sheet to the display device
Note: If the last of these is a pure translation that translates by an integer multiple of device units, then it has no effect on the rendering other than placement of the figure drawn on the display device.
Roughly speaking, a pixel is affected by drawing a shape only when it is inside that shape. Since pixels are little squares, and the abstract points in an idealized geometric shape have no size, most shapes will have many pixels that lie only partially inside the shape. It is important, therefore, to describe which pixels will be affected when rendering a shape, and which will not.
On devices that support color or grayscale, the rendering engine uses anti-aliasing techniques to render pixels that lie only partially inside the shape. That is, the affected pixels are drawn a little lighter than pixels that are wholly within the shape, the precise shade depending on how much of it is inside the shape.
The conventions used by DUIM are the same as the conventions used by X11:
- A pixel is a addressed by its upper-left corner.
- A pixel is considered to be inside a shape, and hence affected by the rendering of that shape, if the center of the pixel is inside the shape. If the center of the pixel lies exactly on the boundary of the shape, it is considered to be inside the shape if the inside of the shape is immediately to the right of the center point of the pixel (that is, an increasing x direction on the display device). If the center of the pixel lies exactly on a horizontal boundary, it is considered to be inside the shape if the inside of the shape is immediately below the center point of the pixel (that is, an increasing y direction on the display device). This situation is illustrated in Figure 6.1.
- An unfilled idealized geometric shape is drawn by calculating an artificial area for the shape, and then deciding which pixels are inside or outside that area, using the rules described above. The artificial area is calculated by taking the filled shape consisting of those points that are within half the line thickness from the outline curve (using a normal distance function, that is, the length of the line drawn at right angles to the tangent to the outline curve at the nearest point). To visualize this, imagine a filled shape the same size as the unfilled shape, and overlay on this filled shape an identical, but slightly smaller, unfilled shape.
Figure 6.1 How pixels are defined to be "inside" and "outside" shapes
It is important to note that these rules imply that the decision point used for insideness checking is offset from the point used for addressing the pixel by half a device unit in both the x and y directions. It is worth considering the motivations for these conventions.
When two shapes share a common edge, it is important that only one of the shapes own any pixel. The two triangles in Figure 6.2 illustrate this. The pixels along the diagonal belong to the lower figure. When the decision point of the pixel (its center) lies to one side of the line or the other, there is no issue. When the boundary passes through a decision point, which side the inside of the figure is on is used to decide.
The reason for choosing the decision point half a pixel offset from the address point is to reduce the number of common figures (such as rectilinear lines and rectangles with integral coordinates) that invoke the boundary condition rule. This usually leads to more symmetrical results. For instance, shows a circle drawn when the decision point is the same as the address point. The four lighter points are indeterminate: it is not clear whether they are inside or outside the shape. Since each boundary case is determined according to which side has the figure on it, and since the same rule must be applied uniformly for all figures, there is no choice but to pick only two of the four points, leading to an undesirable lopsided figure.
Figure 6.3 Choosing any two of the shaded pixels causes asymmetry
If all four boundary points had been chosen instead, the result would be a symmetrical figure. However, since this figure is symmetrical about a whole pixel, it is one pixel wider than it ought to be. The problem with this can be seen clearly in Figure 6.4, in which a circle is drawn over a square. In the left-hand figure, the decision point is at the center of the pixel, but in the right-hand figure, it is not.
It is for this reason that the decision point is at the center of the pixel. This draws circles that look like the one in Figure 6.5.
A consequence of these rendering conventions is that, when the start or end coordinate (minus half the line thickness, if the shape is a path) is not an integer, then rendering is not symmetric under reflection transformations. Thus, to correctly and portably draw an outline of thickness 1 around a (rectilinear) rectangular area with integral coordinates, the outline path must have half-integral coordinates. Drawing rectilinear areas whose boundaries are not on pixel boundaries cannot be guaranteed to be portable. In other words, the "control points" for a rectangular area are at the corners, while the control points for a rectilinear path are in the center of the path, not at the corners. Therefore, in order for a path and an area to abut seamlessly, the coordinates of the path must be offset from the coordinates of the area by half the thickness of the path.