几类裁剪算法和三次曲线生成算法研究

摘要

光栅图形显示器是一种重要的图形显示设备，在光栅显示器上显示的任何一种图形，实际上都是一些具有一种或多种颜色的象素的集合，图形的扫描转换就是确定一个象素集合及其颜色，用于显示一个图形的过程。在图形的扫描转换中，图形的绘制和裁剪是两个重要的方面。 本文对图形进行光栅化时，确定最佳逼近于该图形的一组象素，并对这些象素进行写操作，这就是图形的绘制过程。提高图形的绘制速度和精确度，是计算机图形学研究的重要方面。同时，在对任何图形进行光栅化时，必须显示在屏幕的一个窗口内，确定一个图形的哪些部分在窗口内，进行显示，超出窗口的图形不予显示，这就是裁剪的过程。 本文将对基本图形的生成算法以及图形的裁剪问题进行若干讨论。本文共分为四章： 第一章对图形的裁剪和基本图形的生成算法进行了概述。简述了两种常见的裁剪算法：Cohen-SutherLand裁剪算法和中点分割算法，并介绍了近期对裁剪算法的研究；第二部分概述了直线和圆的几种经典生成算法，又介绍了现有的各种不同类型的直线和曲线生成算法。 第二章提出了一种关于椭圆形窗口的线段裁剪算法，利用预先制备的规范化表，通过映射法查表，从而避免了一元二次方程的求解，提高了裁剪速度。 第三章提出了一种针对抛物线段在圆形窗口中的裁剪算法，利用抛物线和圆的几何特征，对各类抛物线段进行详细的分析，进行预处理和必要的运算，实现抛物线段在圆形窗口中的裁剪。 第四章本章对于y=ax3+bx2+cx+d这类三次曲线，提出了一种新的生成算法，本算法采用双步增量的方法，具有递归性，而且只通过一次逻辑判断，从而提高了绘图速度。

目录

致谢

摘要

第一章概述

第二章一种快速的椭圆形窗口的裁剪算法

第三章圆形窗口对于抛物线段的裁剪算法

第四章一类三次曲线的双步增量生成算法

参考文献