This paper develops a new algorithm for line clipping based on the concept of the optimal tree. A careful analysis results in an algorithm that classifies a given line segment in such a way that at most one procedure is invoked to clip it; furthermore, there are five such procedures that cover all cases. The result is an algorithm that is provably optimal and according to experimental tests outperforms previous algorithms. For both the two-dimensional and three-dimensional cases, and on both the Sun 3/160 and the DECStation 5000/200, the new algorithm performed uniformly faster than all the other "standard" algorithms for each of four different sizes of data space. Only the two-dimensional case is described in detail. Although in the three-dimensional case this algorithm is significantly faster than the other known algorithms, the code is huge and more complex than the new two-dimensional algorithm, and there are more special cases that need to be handled.




Download Full History