You-Dong Liang and Brian A. Barsky

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-691

, 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},
    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