You-Dong Liang and Brian A. Barsky

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-691
July 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-691.pdf

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.

BibTeX citation:

@techreport{Liang:CSD-92-691,
    Author = {Liang, You-Dong and Barsky, Brian A.},
    Title = {The Optimal Tree Algorithm for Line Clipping},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6246.html},
    Number = {UCB/CSD-92-691},
    Abstract = {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.}
}

EndNote citation:

%0 Report
%A Liang, You-Dong
%A Barsky, Brian A.
%T The Optimal Tree Algorithm for Line Clipping
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-691
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6246.html
%F Liang:CSD-92-691