Victor is a graduate student at North Carolina State University majoring in electrical and computer engineering with a minor in computer graphics. He can be reached at 1001 Japonica Court, Knightdale, NC 27545; or via e-mail victor@ecesting.ncsu.edu.
Extents are often used in computer graphics and constructive solid geometry where the edges of the smallest, axes-aligned rectangle enclosing an object are the extents of that object. In two-dimensional space, this is also called "boxing" and in three-dimensional it is a "three-dimensional (3-D) rectangle" -- a parallelpiped.
Graphical objects are often defined by a set of vertices (points) in three dimensions. Finding extents of an object defined by a set of points is a simple process once you realize that the extents are the minimum and the maximum of the object in every dimension. To find the minimum (or maximum) X coordinate, you must search the vertex list that defines the object. The well-known algorithms find_min and find_max are used to accomplish this (see Listing One, page 102). The procedure is then repeated for Y and Z dimensions.
If an object is defined by N vertices, this approach takes (N -1) comparisons to find the Xmin, (N -1) comparisons to find the Xmax, and so on, for a total of 6 (N -1) comparisons for a 3-D object. However, is this the minimal number of comparisons? It's been shown that (N -1) comparisons are necessary to determine the minimum (or the maximum) of N items.1 In other words, the algorithms find_min and find_max in Listing One are optimal and it is not possible to do any better by comparison of items! If you were to perform fewer than (N -1) comparisons, an incorrect answer would result for the same input. Yet, it is possible to perform fewer comparisons if both the minimum and maximum are needed, as is the case with object extents.
When minimizing the amount of work done by two separate operations -- searching for minimum and maximum in our case -- the usual technique is to look for any work or intermediate results that can be shared. In this case there does not seem to be any shared work; the find_max procedure compares all of the points to max and the find_min procedure compares all of the points to min. In many cases it may be beneficial to sort the list of items, or a sublist of items. Sorting the whole list makes things worse, because sorting is a slower order operation, O(NlogN), than finding a minimum or a maximum, O(N).1 However, sorting two items helps minimize the work since this takes only a single comparison.
The strategy used to find the extents is as follows (see the find_min_max procedure in Listing Two, page 102):
This procedure is slightly more complex, but the gains are dramatic. In fact, to find the minimum vertex and the maximum vertex in the X dimension for an object with N vertices (3N/2 -2) comparisons will be performed by find_min_max if N is even, and (3N/2-3/2) comparisons if N is odd. In contrast, 2(N -1) comparisons will be done by find_min and find_max. This amounts to a savings of approximately 25 percent. What is most important about this result is that it has been shown to be optimal!1 In other words, it is not possible to make any fewer comparisons of items! What's more, the find_min_max procedure is general purpose and can be used in many other applications.
As one example of computational savings, let's apply the find_min_max procedure to a polygon clipping test. Assume that 100,000, 4-vertex polygons need to be displayed per second.2 Each of the polygons must be tested to see if it falls completely inside of the display window's boundaries which are 3-D boundaries. Each polygon must be handled separately since no relationship can be assumed between polygons in general. There are three possible ways to handle this:
This example demonstrates that valuable computing resources are being wasted by performing redundant work using the first two methods.
The MIN/MAX algorithm was benchmarked on several computer systems using lists of floating-point numbers of various lengths. The results are summarized in Table 1. Note that the MIN/MAX algorithm delivers more than the promised 25 percent speedup, on the majority of the systems tested. Since the algorithm performs fewer comparisons, it performs fewer stores (writes) of items to min and max. In fact, the number of writes is potentially reduced in half, as each item is compared to either min or max, but never both, in the MIN/MAX algorithm. This may reduce bus traffic in some systems.
Machine MIN/MAX MIN & MAX Speed up --------------------------------------------------- PC/AT 8 MHz 600,000 items 34.82 sec. 48.20 sec. 27.8% VaxStation2000 1,200,000 items 13.70 sec. 18.70 sec 26.7% DEC 3100 24,000,000 items 17.30 sec. 32.70 sec. 47.1% Sun SparcStation 24,000,000 items 50.70 sec. 66.60 sec. 23.9% Cray Y-MP 60,000,000 items 30.21 sec. 43.97 sec. 31.3%
The method described is applicable to computational environments where a comparison is a binary operation. Most of today's sequential software environments satisfy this condition. However, it is possible to build hardware to find the min and the max of a fixed number of items in a single step.
_OPTIMAL DETERMINATION OF OBJECT EXTENTS_
by by Victor J. Duvanenko, W.E. Robbins, and Ronald S. Gyurcsik
[LISTING ONE]
/* min.c -- Procedure to find the smallest element of the array.
The number of elements in the array must be > 0. ( n > 0 ) */
float find_min( array, n )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
{
register i; float min;
min = array[0];
for( i = 1; i < n; i++ )
if ( min > array[i] ) min = array[i];
return( min );
}
/* Procedure to find the largest element of the array.
The number of elements in the array must be > 0. ( n > 0 ) */
float find_max( array, n )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
{
register i; float max;
max = array[0];
for( i = 1; i < n; i++ )
if ( max < array[i] ) max = array[i];
return( max );
}
[LISTING TWO]
/* min_max.c -- Procedure to find the smallest and the largest element of
the array. The number of elements in the array must be > 0. ( n > 0 ) */
void find_min_max( array, n, min, max )
float array[]; /* input array */
int n; /* number of elements in the array ( n > 0 ) */
float *min, *max; /* pointers to the return values */
{
register i;
if ( n <= 1 )
*min = *max = array[0];
else {
if ( array[0] > array[1] ) { /* establish the basis min and max */
*max = array[0];
*min = array[1];
}
else {
*max = array[1];
*min = array[0];
}
for( i = 2; ( i + 2 ) <= n; i += 2 )
if ( array[ i ] > array[ i + 1 ] ) {
if ( array[ i ] > *max ) *max = array[ i ];
if ( array[ i + 1 ] < *min ) *min = array[ i + 1 ];
}
else {
if ( array[ i + 1 ] > *max ) *max = array[ i + 1 ];
if ( array[ i ] < *min ) *min = array[ i ];
}
if ( i < n ) /* handle the odd/last array element */
if ( *max < array[i] ) *max = array[i];
else if ( *min > array[i] ) *min = array[i];
}
}