This section presents algorithms and demos for high performance digital drawing techniques. Most of them disclose new methods for improving the performance of existing applications. Some papers are provided which describe the methods in detail, so graphics designers may implement them as needed. No copyrights are asserted with respect to any of the disclosures and no acknowledgments or attributions are required for their use.
The code for the demos and applications themselves are not portable, because they consist of a hybrid mix of Borland C++ Builder, Intel '86 assembler language and non-standard Windows bitmaps.
A New Line Drawing Algorithm
This image is a screenshot of the line-draw demo program. To download the application, click on the snapshot.
The common objective in creating a viable line drawing algorithm is to plot points of a grid-restricted line which most closely match an ideal continuous line joining the end points. In other words, each plotted point must be the closest grid point to the desired line. There are, of course, many ways to solve this approximation problem. Each has its own strengths and weaknesses, and a major concern in devising an algorithm is to eliminate performance bottlenecks. Bottlenecks in line drawing primitives come in several flavors. Processor intensive floating point operations, type conversions, divides, complex integer operations (shifts, rotates), compare and branch instructions, etc.
A number of efficient solutions which avoid the most serious bottlenecks have been proposed by Bresenham and others. These algorithms use incremental techniques which, for the most part, involve only simple integer operations. Some, like the midpoint algorithm, are derived directly from the nearest point requirement. Typically, algorithms are defined for a restricted range of line slopes and separately coded for each octant or require signed integers which are precomputed for the particular octant under consideration . See any text on computer graphics for explanations, derivations and examples.
Details of the proposed new algorithm are documented in this pdf file Unlike other line draw algorithms, this method is derived from sample rate conversion concepts, in particular decimation. Mapping the problem to a signal processing domain leads to efficiency improvements which are not obvious in the original line drawing context.
The new algorithm avoids common performance bottlenecks by using a special, normalized integer control variable to perform updates within the inner loop. Recall that the usual strategy for drawing lines in the first octant is to increment the 'x' position at every iteration of the pixel drawing loop, and to increment the 'y' position periodically as determined by some update strategy. Our strategy is to begin with the quantity dy/dx, representing the slope of the line, which ranges from 0 to 1 in the first octant. We produce a scaled version of dy which ranges from 0 to 65535 or 0 to 4294967295 depending on whether 16 bit integers or 32 bit integers are specified. This new unsigned quantity, incr, is effectively the fractional part of a fixed point number having a 16 or 32 bit fractional part. For the 16 bit integer case, incr is calculated from the equation: dy/dx = incr/65536.
Thus, assuming 16 bit integers, if dy/dx=0.5 then incr = 0x8000. If dy/dx = 6/7 then incr = 0xDB6D. These values are found by performing an unsigned integer divide before entering the inner loop. Now, on each iteration of the inner loop, an unsigned integer control variable, cvar, is updated by adding incr to it. Rollover (cvar > 65535) signifies that the 'y' variable needs to be incremented, and since this condition generates a processor carry, we only need to add the carry to 'y' to perform the update. With Intel and AMD processors, the adc (add with carry) instruction with an immediate value of zero does the job. If a decrement is required, sbb (subtract with borrow) would be used.
A simple pseudo-code representation looks like this:
plot(x,y)
increment x
add incr to cvar
add 0 with carry from previous operation to y
loop
In superscalar processors, increments and adds are fully pipelined -- unlike the complex operations such as divide or multibit shift. No explicit decision points are required within the loop because the decision is handled implicitly by carry management. Other than the loop control, there are no compares or branches. No divides, multiplies or shifts are required in the inner loop.
Note that the loop control variable and the 'x' variable both step in unit increments at each iteration. This suggests that it may be advantageous to combine the loop variable and the 'x' value to reduce the number of increments per loop. There are a number of ways to do this, but observe that the extent of any performance improvement is processor dependent. The fourth step in the above algorithm can be eliminated by a method described in the paper.
As with other line algorithms, there are several ways to adapt the above algorithm for use in any octant. Interchanging the roles of 'x' or 'y' maps the basic algorithm from octant I to octant II. Changing the polarity (sign) of 'x' and/or 'y' maps to other octants. Some of the mappings can be most easily done without performance penalties by changing increments to decrements and adds to subtracts. The management of the control variable is the same in each case.
For a comprehensive plotting strategy, the basic algorithm can be implemented 8 times, once for each octant, and a decision tree traversed to identify the correct octant for a particular line, Alternatively, a set of signed loop variables can be generated and the basic algorithm invoked with signed update quantities. Both methods have been used successfully with other line drawing algorithms and can be applied to this one as well.
This algorithm has been implemented in assembler language for an Intel Pentium and tested for correctness (plotting the correct pixels). It was found that all the required variables can be held in processor registers, so no memory accesses are required except for the pixel plot itself. An application using this algorithm is available here, and a more detailed exposition describing the method can be downloaded for additional information.
An Incremental Method for Drawing Arcs
Although students of graphics algorithms are well acquainted with the incremental algorithms of Bresenham and the midpoint strategies devised by others, these algorithms only directly address lines and circles (or ellipses). There is very little published literature dealing with the problem of applying the same strategies to arcs. A new method, described in the paper available here, uses the algebraic properties of oriented lines to distinguish pixels along the circle which are on the arc or outside it. Source code for a simple DOS demo file in the C language is also provided. The Windows Demo shown above was built using the same C code.
An internet search reveals that the typical solutions to drawing arcs resort to floating point operations, which dramatically slows the plotting routines. With the strategy proposed heere, floating point is only used to identify the starting and ending pixels of the desired arc. All other operations only use the kind of incremental methods that are used by the best methods for drawing full circles.
This method is easily adapted to work with elliptical arcs and in filled sectors. It is only necessary to perform the plot test as each candidate pixel is chosen.
A New Generalized Ellipse Algorithm
Efficient graphics primitives supporting ellipses at arbitrary orientations and aspect ratios are relatively rare. Unfortunately, the published algorithms typically fail to plot the correct pixels for ellipses with large aspect ratios. The problem occurs at the corners where the derivative of the curve may change drastically over a sub-pixel distance. Here is a paper that describes a new method which solves this problem, and a Windows application demonstrating it can be downloaded here, or by clicking the image on the left. Note that the image contains ellipses that are highly elongated -- a serious problem for previously published algorithms.
The method requires that the location of certain critical points on the ellipse be calculated prior to plotting. These points are used to switch algorithms dealing with sections of the ellipse which have different slopes.