# Optimal Determination of Object Extents

OCT90: OPTIMAL DETERMINATION OF OBJECT EXTENTS

## Find min and max the best possible way

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.

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):

1. Compare the first two items to each other. Place the larger in max and the smaller in min.

2. Take the next two items and compare them to each other. Then compare the larger item to max and the smaller item to min. If the larger item is larger than max place it in max. If the smaller item is smaller than min place it in min.

3. Take care of the last item if the number of items is odd. If this item is greater than max it can not be smaller than min, so there is no need to compare to min.

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.

### Application

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:

1. The vertices of each polygon could be tested to see if all of them fall within the 3-D display window. This implies that 400,000 vertices must be checked against two boundaries in each dimension (for example, window_x_min and window_x_max), or six comparisons per vertex. In other words, this requires 2,400,000 comparisons per second, or 2.4 Mflops.2

2. Extents (min and max) of each polygon could be found and compared to the window boundaries. This implies 2(4 -1) comparisons per dimension, plus a comparison of min to the window minimum and of max to the window maximum -- a total of eight comparisons per dimension. Therefore, 24 comparisons per polygon would have to be made, or 2.4 Mflops (as before).

3. Perform (3*4/2-2) or four comparisons per dimension plus the two comparisons to the window boundaries, for a total of six comparisons per dimension. Therefore, 18 comparisons would be made per polygon, or 1.8 Mflops. This is a savings of 0.6 Mflops, or 25 percent of 2.4 Mflops.

This example demonstrates that valuable computing resources are being wasted by performing redundant work using the first two methods.

### Benchmarks

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.

#### Table 1: Results of MIN/MAX algorithm

```  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.

### References

1. S. Baase. Computer Algorithms: Introduction to Design and Analysis, second edition, Reading Mass:, Addison-Wesley, Nov. 1988, pp. 24-26, pp. 125-128.

2. K. Akeley and T. Jermoluk. "High-Performance Polygon Rendering," SIGGRAPH, Computer Graphics, vol. 22, no. 4, August 1988.

_OPTIMAL DETERMINATION OF OBJECT EXTENTS_ by by Victor J. Duvanenko, W.E. Robbins, and Ronald S. Gyurcsik

```<a name="0202_0008">

/* 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 );
}

<a name="0202_0009"><a name="0202_0009">
<a name="0202_000a">```
[LISTING TWO]
```<a name="0202_000a">

/* 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];
}
}

```

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>