Graphics Reference
In-Depth Information
integer
pushrx, pushlx;
pushrx := rx + 1; pushlx := lx - 1;
Push (lx,rx,pushlx,pushrx,y+dir,dir);
if
rx > dadRx
then
Push (dadRx+1,rx,pushlx,pushrx,y-dir,dir);
if
lx < dadLx
then
Push (lx,dadLx-1,pushlx,pushrx,y-dir,dir);
end;
Algorithm 2.4.3.
Continued
2.5
Generating Discrete Curves
Now we start a central topic of this chapter, namely, curves and the problem that one
runs into when one tries to represent them with a discrete set of points. Clearly, we
want any mapping of continuous structures into discrete ones to preserve the visual
shape properties, such as smoothness and uniform thickness, as much as possible but
this is not easy. We shall look at the problem of defining and generating discrete lines
first and then conics.
Lines, or more accurately segments, are the most basic of computer graphics
objects because most modeling systems use linear approximations to all objects so
that displaying them reduces to drawing lots of lines. It is possible to actually give a
formal definition of a discrete “straight” line (see [ArcM75] and [BoLZ75]). Not sur-
prisingly, such definitions get complicated, but from a practical point of view we are
not really interested in a definition. Rather, we are happy with an algorithm that gen-
erates a satisfactory set of points for a line. What is satisfactory? Well, that is not very
precise, but some attributes that we want the generated discrete lines to have are:
(1) Visually, the line should appear as straight as possible.
(2) The line should start and end accurately, so that, for example, if several con-
tiguous line segment are drawn, then there is no gap between them.
(3) Each line should appear to have an even visual thickness, that is, it should
have as constant a density as possible, and this thickness should be inde-
pendent of its length and slope.
(4) The conversion process must be fast.
In Sections 2.5.1-2.5.3 we look at line-drawing algorithms for the monochrome
case, that is, where the raster is an array of 0's and 1's and the line consists of those
pixels that are set to 1. Section 2.6 looks at some deeper problems that one encoun-
ters in the process of discretizing continuous objects and making them look smooth.
Section 2.9.1 looks at a scan line algorithm for lists of lines and fill algorithm for
polygons.
Conics are the next most common curve after the “straight” line. The circle is one
obvious such curve, but the other conics are also encountered frequently. Their geo-
