Khun Yee Fung

Date of Award


Degree Type


Degree Name

Doctor of Philosophy


Line clipping and drawing are two important processes in the graphics output pipeline. Improving the efficiency of these two processes will improve the overall efficiency of the output pipeline. My thesis is that the efficiency of these two processes can be improved significantly.;Traditionally, line clipping is done in floating point numbers and line drawing in integers. A line is first clipped, probably more than once, and then rasterized. Since line segments must be rasterized at the end, doing clipping and rasterization together improves the overall efficiency, avoids computation in floating point numbers, and eliminates inconsistencies introduced in the line clipping process. However, line clipping in floating point numbers is still required for line segments in three and higher dimensions.;In this thesis, the efficiency of higher dimensional line clipping is improved via the extension of the Nicholl-Lee-Nicholl line clipping algorithm to higher dimensions. The efficiency of line drawing is improved by a new run-length slice line drawing algorithm which does not use multiplications and divisions. Line clipping and line drawing are amalgamated by using new algorithms that find the first visible grid point in constant or logarithmic time in terms of then umber of grid points from the first endpoint to the first visible grid point.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.