d MD
CS (DGR) < <c d -- >a
SH (DGR) <a < MD <a,b --
Victor is an engineer at Truevision in Indianapolis, IN. He can be contacted at victor@truevision.com.
Our previous article, "Improving Line Segment Clipping" (DDJ, July 1990), presented improvements on the Cohen-Sutherland (CS) line-clipping algorithm. Since then, we've made more improvements, some with the help of algorithms such as Nicholl-Lee-Nicholl (NLN). In this article, we'll discuss some of these improvements, extend the results to three dimensions, and introduce the Sutherland-Hodgman clipping algorithm.
The CS and NLN algorithms are based on the assumption that the database being viewed is much larger than the window. Thus, most of the spans (which are lines with endpoints, or line segments) will not appear in the window at all and must be eliminated as quickly as possible. Both algorithms have been optimized to reject spans quickly and are suboptimal for trivial acceptance. In the case of trivial acceptance, a span is completely inside the clipping window, which is assumed to be rectangular with axes-aligned (orthogonal) edges. In some cases, you may need an algorithm optimized for trivial acceptance of spans (for instance, if the database fits mostly inside the window).
CS and NLN trivially accept the span after completing eight floating-point comparisons for 2-D. CS trivially accepts a span after 12 floating-point comparisons for 3-D. (The NLN algorithm doesn't yet exist for 3-D.) Both algorithms compare the two span endpoints to each of the clipping window/volume boundaries (2*4=8 for 2-D, 2*6=12 for 3-D).
The only inputs to a span-clipping algorithm are the coordinates of the span endpoints and the clipping window boundaries. Since orthogonal window boundaries are assumed, the problem can be reduced to a series of independent, one-dimensional problems. Each problem tries to resolve whether the span endpoints are within the range defined by the window boundaries. If the endpoints are within the window boundaries of all dimensions, then the span must be inside the window. CS and NLN perform four comparisons per dimension for trivial acceptance. However, the minimal number of comparisons necessary for trivial acceptance is of interest.
A more precise way to state the problem is as follows: "What is the minimum number of comparisons necessary to ascertain that Xmin </= {X0,X1} </= Xmax, where X0 and X1 are the span endpoints and it is known that Xmin </= Xmax?"
The solution is a three-comparison method based on the MIN/MAX algorithm, as described in Baase's Computer Algorithms and our article, "Optimal Determination of Object Extents" (DDJ, October 1990). The algorithm is as follows:
If the larger point is smaller than Xmax and the smaller point is larger than Xmin, then both points are inside the range; see Figure 1. The new algorithm compares the endpoints to each other instead of always comparing the endpoints to the boundaries (as do the current CS and NLN implementations). This method allows the algorithm to obtain a greater amount of useful information. In fact, the most information is obtained by comparing two previously untouched items (two endpoints/vertices, in this case) to each other.
An implementation of this algorithm, applied to span trivial acceptance, is shown in Listing One. This algorithm accepts a span only for the cases E and F in Figure 2. MIN/MAX was applicable because of the orthogonal nature of the window boundaries, as the window boundary occupied a single value (Xmin or Xmax) in the dimension being checked. In summary, a minimum of six comparisons for 2-D and nine comparisons for 3-D are necessary to trivially accept a span, compared with eight comparisons performed by the CS and NLN algorithms for 2-D, and 12 comparisons by CS for 3-D. This constitutes a computational savings of 25 percent.
Trivial rejection is a special case of a span being completely outside of the window. The span must also be in a position such that both endpoints are located entirely within the outside half-space of one of the clipping-window boundaries (spans G and H, but not K in Figure 3). The endpoints of span G are above the top boundary, and the endpoints of span H are to the right of the right boundary. On the other hand, span K cannot be trivially rejected because both its endpoints are not located within the outside half-space of any one boundary. These conditions allow the use of a single comparison to determine the rejection of a span--and that makes the rejection trivial. The comparison is a one-dimensional operation.
NLN performs fewer floating-point comparisons than CS in all trivial-rejection cases. For example, NLN rejects a span after as few as two floating-point comparisons when a span is strictly to the left of the window, whereas CS performs as many as six floating-point comparisons. Thus, it is beneficial to determine the minimal number of comparisons necessary to reject a span.
In a single dimension, two boundaries (Xmin and Xmax) are present when clipping a span to a window, so the minimal number of comparisons necessary to reject a span to both boundaries is sought. A more precise way to state the problem is: "What's the minimum number of comparisons necessary to determine a True result of the logical expression ((X0<Xmin and X1<Xmin) or (X0>Xmax and X1>Xmax)), where X0 and X1 are the span endpoints and it is known that Xmin </= Xmax?"
In the best case, only two comparisons are needed (X0<Xmax and X1<Xmax). In the worst case, a True result is only possible after three comparisons (X0>Xmax and X1>Xmax) because the sequential nature of program execution forces a fixed order of comparisons. (There are several three-comparison solutions.)
The trivial-rejection method used by NLN (see Listing Two) achieves the minimal number of comparisons. However, achieving optimality in the worst case doesn't imply that a search for a better algorithm is futile. It may be possible to reduce the number of cases that require maximal work, thus achieving an algorithm that, on average, performs less work. Listing Three shows a one-dimensional decision tree used in NLN and an alternative method that performs fewer comparisons on average.
Table 1 shows a detailed analysis of all possible cases. A total of nine cases are possible, since each of the endpoints can reside in one of the three regions shown in Figure 2. Obviously, neither algorithm exceeds the minimal bound of three comparisons.
The NLN algorithm performs 2.33 comparisons on the average; the DGR algorithm performs 2.22. Thus, a more efficient decision tree exists, which will lead to a more efficient implementation of the NLN, and possibly of other algorithms.
In addition to being a well-established algorithm for clipping spans in 2-D, CS easily extends to 3-D. We enhanced the CS implementation without disturbing its ability to extend to 3-D. The result is an efficient 2-D and 3-D algorithm called CS (DGR); see Listing Four.
Also, once the first endpoint has been adjusted (at most, twice) to its final position, you know whether the span intersects the clipping window. At this point, the span either missed the window and is trivially rejected, or the first intersection point between the span and the window has been found. Thus, when adjusting the second endpoint no trivial-rejection testing is necessary, since only trivial acceptance is possible.
These enhancements are fairly independent of each other, allowing for a family of implementations varying in efficiency and complexity. For example, addition of the optimal trivial-rejection procedure and the slope-subproduct computation to the CS implementation results in a fairly efficient and simple implementation that extends to 3-D.
We found--but did not use because of the lack of extendibility to 3-D--one implementation enhancement in Hill's Computer Graphics: The slope can be computed only once. In the worst case, this improvement removes one multiplication and one division (averaged across symmetry). However, an additional floating-point comparison is required in every case not trivially rejected or accepted, since a vertical span (slope is infinity) is checked and handled as a separate case. But the IEEE P754 floating-point standard handles infinity properly: When dividing by 0, the result is infinity; when dividing by infinity, the result is 0. Thus, when you use a compiler or a processor that conforms to the IEEE P754 standard, no extra comparison is needed. The method is advantageous for all cases, since the redundant floating-point operations in slope computations are removed. Not all computer systems conform to the IEEE P754 standard however, which may make the implementation less portable.
Extending the CS (DGR) 2-D implementation to 3-D is not difficult. Parametric equations are used, but the slope subcomponents (dx, dy, and dz) are computed only once. If slopes were to be precomputed, three slope computations would be necessary (dy/dx, dz/dx, and dz/dy). This would require extra division-by-0 checks in a non-IEEE-compliant environment and an extra division for single-endpoint adjustment (as only two slopes are necessary for the intersection computation).
Finally, NLN and CS (DGR) rely on the top window boundary being above the bottom boundary and the left boundary being to the left of the right boundary. Otherwise, results produced by various algorithms will differ. Infractions of this rule can be easily detected when the clipping-window dimensions are changed. All rendering operations can then be disabled whenever the clipping-window dimensions are "unreasonable." However, differences in the outputs of span-clipping algorithms warrant cautious use.
Sutherland and Hodgman (SH) suggest the application of their polygon-clipping algorithm to span clipping. SH separates the process of clipping to a window into disjoint processes of clipping to each boundary. This approach resembles a pipeline: Each boundary is a stage in the pipeline and can be applied to graphics-system architectures such as the Geometry Engine and the Pixel Machine. Listing Five shows one possible 2-D implementation of SH, SH (DGR). This implementation gains efficiency by clipping to both X boundaries, Xmin and Xmax, in one stage of the pipeline. This suggests a shorter pipeline, with each stage treating a dimension instead of a single boundary. Other possible implementations and the 3-D algorithm are available electronically; see "Availability," page 3.
SH (DGR) works on a simple principle. If both endpoints of a span are in the "outside" half-space of a window boundary, the span is rejected. If one endpoint is in the "outside" half-space while the other endpoint is in the "inside" half-space, the "outside" portion of the span is clipped away. If both endpoints are in the "inside" half-space, nothing needs to be done. Thus, the algorithm always removes the invisible portion of a span. SH (DGR) is compact and conceptually simple. It provides symmetry (or reentrancy), extends easily to 3-D, performs few comparisons (8 for 2-D, 12 for 3-D), and has inherent parallelism.
Integer comparison can be eliminated from SH (DGR) by placing clip_D inline. You can unfold the algorithm completely so that the slope computations from the x-dimension clipping can be utilized during the y-dimension clipping. Finally, SH (DGR) can be extended to convex clipping windows, just like the SH polygon algorithm.
The SH (DGR) method has two inefficiencies, however. First, it performs redundant slope computations. Second, the trivial rejection of spans is nonoptimal. In fact, only the first call to clip_D (the first dimension) is optimal.
Nicholl, Lee, and Nicholl have developed metrics and techniques for direct comparison of clipping algorithms, which we further refined. Grouping cases in a reasonable manner simplifies presentation of algorithm analysis. For example, Figure 4 shows the results of all cases when the first span endpoint (P0) is inside the clipping window. The second span endpoint can be inside the window, in any of the four corner regions or in any of the four edge regions. The algorithm-analysis data can be reduced by averaging the four corner cases. Thus, the data is averaged over symmetry. We used the technique to automate the generation of all possible cases. Operation counters were added to all algorithms to obtain a precise count of all considered operations.
We compared CS, Liang-Barsky (LB), NLN, CS (DGR), and the fully expanded version of the SH (DGR) algorithms for various cases in 2-D. The conclusions in Table 2 apply to a general scalar, computational model. Each entry in Table 2 indicates the comparison between the algorithm that labels the row and the one that labels the column, where < means "performs less work than." For instance, the third row of Table 2 states that, in all cases, NLN performs less work than CS and LB and less than or equal to the amount of work done by CS (DGR); furthermore, comparison to SH (DGR) is machine dependent, and thus inconclusive.
We also compared CS, LB, CS (DGR), and SH (DGR) for various cases in 3-D. (NLN is not yet available in 3-D.) Four types of regions are created by the parallel-piped boundaries in 3-D space: one inside region, six face regions, twelve edge regions, and eight corner regions. The conclusions are presented in Table 3.
The fact that SH (DGR) performs the fewest number of comparisons may be important for general architectures that can chain an addition and a multiplication (some present DSPs and floating-point units), since comparisons become the bottleneck operation.
CS was designed for a hardware implementation and contains much parallelism. Sproull and Sutherland describe CS in terms of a hardware implementation, with all window-boundary comparison performed in parallel. Serial implementations, such as CS, CS (DGR), and NLN, suffer from a fixed, sequential comparison order that may not be most efficient for all spans.
Thanks to Dr. John F. Hughes for providing many useful suggestions on every aspect of the first draft of our paper, "Simple and Efficient 2-D and 3-D Span Clipping Algorithms," published in Computers and Graphics (January 1993).
Baase, S. Computer Algorithms. Reading, MA: Addison-Wesley, 1988.
Duvanenko, V.J. "Simple and Efficient 2-D and 3-D Span Clipping Algorithms." MS Thesis, North Carolina State University, December 1990.
Hill, F.S., Jr. Computer Graphics. Houston, TX: Macmillan Publishing, 1990.
Nicholl, T.M., D.T. Lee, and R.A. Nicholl. "Efficient New Algorithm for 2-D Line Clipping: Its Development and Analysis." Computer Graphics (ACM SIGGRAPH) (July 1987).
Rankin, J.R. Computer Graphics Software Construction. Englewood Cliffs, NJ: Prentice Hall, 1989.
Sproull, R.F., and I.E. Sutherland. "A Clipping Divider." Fall Joint Computer Conference, 1968.
Sutherland, I.E., and G.W. Hodgman. "Reentrant Polygon Clipping." Communications of the ACM (January 1974).
X0 X1 Comparisons Comparisons
(NLN) (DGR)
A A 2 2
A E 2 2
A C 2 2
E A 2 2
E E 2 2
E C 2 3
C A 3 2
C E 3 2
C C 3 3
CS (NS) LB NLN CS (DGR) SH (DGR)
CS (NS) -- MD >e > >a
LB MD -- > >c >
NLN <e < -- d MD
CS (DGR) < <c d -- >a
SH (DGR) <a < MD <a,b --
CS (NS) LB CS (DGR) SH (DGR)
CS (NS) -- MD > MD
LB MD -- >b >a
CS (DGR) < <b -- MD
SH (DGR) MD <a MD --
/* Optimal 3-D trivial accept procedures. Return as soon as
trivial acceptance fails. All dimensions must accept for the procedure
to accept. Acceptance is border inclusive. */
#define ACCEPT 1
#define BOOLEAN int
#define ACCEPT_TEST( p1, p2, min, max ) \
if ( p1 < p2 ) { \
if ( p1 < min ) return( !ACCEPT ); \
if ( p2 > max ) return( !ACCEPT ); \
} else { \
if ( p2 < min ) return( !ACCEPT ); \
if ( p1 > max ) return( !ACCEPT ); \
}
extern double x_min, x_max, y_min, y_max, z_min, z_max;
BOOLEAN optimal_triv_acc_3D( x1, y1, z1, x2, y2, z2 )
double x1, y1, z1, x2, y2, z2;
{
ACCEPT_TEST( x1, x2, x_min, x_max)
ACCEPT_TEST( y1, y2, y_min, y_max)
ACCEPT_TEST( z1, z2, z_min, z_max)
return( ACCEPT );
}
/* Nicholl-Lee-Nicholl trivial rejection (optimal). */
#define REJECT 1
#define BOOLEAN int
#define REJECT_TEST( p0, p1, min, max ) \
if ( p0 < min ) { \
if ( p1 < min ) return( REJECT ); \
} else if ( p0 > max ) \
if ( p1 > max ) return( REJECT );
extern double x_min, x_max, y_min, y_max, z_min, z_max;
BOOLEAN NLN_trivial_reject_3D( x0, y0, z0, x1, y1, z1 )
double x0, y0, z0, x1, y1, z1;
{
REJECT_TEST( x0, x1, x_min, x_max )
REJECT_TEST( y0, y1, y_min, y_max )
REJECT_TEST( z0, z1, z_min, z_max )
return( !REJECT ); /* couldn't reject */
}
/* NLN 1-D trivial rejection (worst case optimal). */
if ( x0 < x_a ) {
if ( x1 < x_a ) return( REJECT );
} else if ( x0 > x_b )
if ( x1 > x_b ) return( REJECT );
/* DGR 1-D trivial rejection (worst case optimal, better on average). */
if ( x0 < x_a ) {
if ( x1 < x_a ) return( REJECT );
} else if ( x1 > x_b )
if ( x0 > x_b ) return( REJECT );
/* 2D CS (DGR) implementation - achieves optimal trivial rejection. */
#define ACCEPT 1
#define REJECT 0
/* Clipping volume boundaries - accessable to all routines */
extern double x_right, x_left, y_bottom, y_top, z_front, z_back;
/* Reject lines as quickly as possible and set 'outcodes'. */
static reject_accept_outcodes( x0, y0, outcode0, x1, y1, outcode1 )
double x0, y0; int *outcode0;
double x1, y1; int *outcode1;
{
if ( x0 < x_left ) {
if ( x1 < x_left ) return( REJECT );
else *outcode0 = 1;
}
else if ( x0 > x_right ) {
if ( x1 > x_right ) return( REJECT );
else *outcode0 = 2;
}
else *outcode0 = 0;
if ( y0 < y_bottom ) {
if ( y1 < y_bottom ) return( REJECT );
else if ( y1 > y_top ) *outcode1 = 8;
else *outcode1 = 0;
*outcode0 |= 4;
}
else if ( y0 > y_top ) {
if ( y1 > y_top ) return( REJECT );
else if ( y1 < y_bottom ) *outcode1 = 4;
else *outcode1 = 0;
*outcode0 |= 8;
}
else {
if ( y1 < y_bottom ) *outcode1 = 4;
else if ( y1 > y_top ) *outcode1 = 8;
else *outcode1 = 0;
}
if ( x1 < x_left ) *outcode1 |= 1;
else if ( x1 > x_right ) *outcode1 |= 2;
return( !REJECT );
}
/* Body of the CS (DGR) 2D line clipping algorithm implementation. */
clip_2d_dgr( x0, y0, x1, y1 )
double *x0, *y0; /* first end point */
double *x1, *y1; /* second end point */
{
unsigned outcode0, outcode1;
double dx, dy, /* change in x and change in y */
edge; /* clipping edge */
if ( reject_accept_outcodes(*x0,*y0,&outcode0,*x1,*y1,&outcode1) == REJECT)
return( REJECT );
if ( ! ( outcode0 | outcode1 )) /* trivial accept */
return( ACCEPT );
dx = *x1 - *x0; /* Calculate the slope subproducts only once. */
dy = *y1 - *y0;
if ( outcode0 & 3 ) { /* divide line at right or left of window */
if ( outcode0 & 1 ) edge = x_left;
else edge = x_right;
*y0 += dy * ( edge - *x0 ) / dx;
*x0 = edge;
if ( *y0 < y_bottom )
if ( outcode1 & 4 ) return( REJECT );
else outcode0 = 4;
else if ( *y0 > y_top )
if ( outcode1 & 8 ) return( REJECT );
else outcode0 = 8;
else if ( ! outcode1 ) return( ACCEPT );
else outcode0 = 0;
}
if ( outcode0 & 12 ) { /* divide line at top or bottom of window */
if ( outcode0 & 4 ) edge = y_bottom;
else edge = y_top;
*x0 += dx * ( edge - *y0 ) / dy;
*y0 = edge;
if (( *x0 < x_left ) || ( *x0 > x_right )) return( REJECT );
if ( ! outcode1 ) return( ACCEPT );
}
/* Clip P1 end. P0 is inside the window. It's only possible to accept. */
if ( outcode1 & 3 ) { /* divide line at right or left of window */
if ( outcode1 & 1 ) edge = x_left;
else edge = x_right;
*y1 += dy * ( edge - *x1 ) / dx;
*x1 = edge;
if ( *y1 < y_bottom ) outcode1 = 4;
else if ( *y1 > y_top ) outcode1 = 8;
else return( ACCEPT ); /* (outcode0 | outcode1) == 0 */
}
if ( outcode1 & 12 ) { /* divide line at top or bottom of window */
if ( outcode1 & 4 ) edge = y_bottom;
else edge = y_top;
*x1 += dx * ( edge - *y1 ) / dy;
*y1 = edge;
return( ACCEPT );
}
}
/* SH (DGR) 2D algorithm. */
#define ACCEPT 1
#define REJECT 0
/* Clipping rectangle boundaries - accessable to all routines */
extern double y_bottom, y_top, x_right, x_left;
/* Clip X or Y dimension. */
static clip_D( x0, y0, x1, y1, min_boundary, max_boundary )
double *x0, *y0, *x1, *y1, min_boundary, max_boundary;
{
double m;
if ( *x0 < min_boundary ) { /* divide line at the min_boundary */
if ( *x1 < min_boundary ) return( REJECT );
m = ( *y1 - *y0 ) / ( *x1 - *x0 ); /* x1 >= min_boundary */
*y0 += m * ( min_boundary - *x0 );
*x0 = min_boundary;
if ( *x1 > max_boundary ) {
*y1 += m * ( max_boundary - *x1 );
*x1 = max_boundary;
}
}
else if ( *x0 > max_boundary ) { /* divide line at the max_boundary */
if ( *x1 > max_boundary ) return( REJECT );
m = ( *y1 - *y0 ) / ( *x1 - *x0 ); /* x1 <= max_boundary */
*y0 += m * ( max_boundary - *x0 );
*x0 = max_boundary;
if ( *x1 < min_boundary ) {
*y1 += m * ( min_boundary - *x1 );
*x1 = min_boundary;
}
}
else { /* x0 is inside the window */
if ( *x1 > max_boundary ) {
*y1 += ( *y1 - *y0 ) / ( *x1 - *x0 ) * ( max_boundary - *x1 );
*x1 = max_boundary;
}
else if ( *x1 < min_boundary ) {
*y1 += ( *y1 - *y0 ) / ( *x1 - *x0 ) * ( min_boundary - *x1 );
*x1 = min_boundary;
}
}
return( ACCEPT );
}
/* The body of the SH (DGR) algorithm. */
clip_2d_sh_dgr( x0, y0, x1, y1 )
double *x0, *y0, *x1, *y1;
{
if ( clip_D( x0, y0, x1, y1, x_left, x_right ) == REJECT) return( REJECT);
if ( clip_D( y0, x0, y1, x1, y_bottom, y_top ) == REJECT) return( REJECT);
return( ACCEPT );
}
DDJ