Bib-version:: CS-TR-v2.0
Id:: UCB//CSD-92-691
Entry:: March 24, 1993
Title:: The Optimal Tree Algorithm for Line Clipping
Author:: Barsky, Brian A.
Author:: Liang, You-Dong
Pages:: 41
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 probably 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.
Retrieval:: o postscript (in all.ps)
End:: UCB//CSD-92-691