论文部分内容阅读
引言：我们现代人生活在各种各样的信息之中，如何应用计算机处理信息，处理图形成为了一个越来越重要的课题。本论文主要介绍了计算机图形学，以及两种基础算法：多边形裁剪算法和逐点生成算法。
1. 计算机图形学
1.1 计算机图形学概述
我们现代人生活在各种各样的信息之中，如何应用计算机处理信息，处理图形成为了一个越来越重要的课题。本论文所要介绍的计算机图形技术，是计算机领域的热门领域之一，它是同电子硬件和计算机的周边设备一同发展而来。随着人类在航空航天、军事和通信等领域的突破，计算机图形学也得到了很快的发展。
计算机图形学是一门实用计算机产生、显示以及处理图形界面的知识体系。计算机图形学已经变得越来越重要，主要原因是：人们接收和发出信息，图形是很好的一种传递信息的方式。一个图形本身，就具有很丰富的信息，人们根据图形能够很自然快速地与外界进行交流。
1.2 计算机图形学研究热点
计算机图形学主要研究以下三个方面的内容。第一：隐藏线（面）的消除；第二：基本曲线的裁剪以及绘制；第三：现代图形学热点研究的内容，主要是虚拟现实技术、可视化、三维立体的重建等等。
由于在一个图形应用或图形软件中要大量重复调用这些基础算法，因此在这方面的任何进步都会对整个图形系统产生很大的影响。计算机图形学的基础算法经过人们几十年的研究，己比较成熟。但每一个进步对解决图形技术所面临的存储、传输、显示等问题都有很大的帮助。
2. 基础算法的研究
2.1 多边形裁剪算法
裁剪是处理图形一种很基础的方法，常见的裁剪操作主要有将不同的图形裁剪拼接形成新的图形。我们可以看出，裁剪算法在计算机图形学中是一种十分基础但是却又十分重要的操作[1]。
本论文所提到的裁剪方法，主要是针对凸多边形的。裁剪方法主要可以分为四个方法：中点算法、CS算法、CB算法、梁B算法。
（1）CS算法是Cohen-Sutherland的一种分区编码算法[2]。CS算法以前是计算机图形学中很重要的一种算法。CS算法对线段可以分为以下三种情况：窗内、窗外以及其它情况。我们在使用CS算法的时候，需要判断线段两端端点的编码，进而判断窗口和线段之间的位置关系，这种算法的缺点是对于判断所做的工作比其他算法多。端点编码检查算法的核心代码如下：
end point code algorithm
P1 and P2 are the end points of the line
xL，xn，yT，yB are the left， right， top and bottom window coordinates calculate the end point codes
put the codes for each end into 1*4 arrays called P1code and P2code
first end point： P1
if x1 < xL then P1code（4） = 1 else P1code（4） = 0
if x1 > xR then P1code（3） = 1 else P1code（3） = 0
if y1 < yB then P1code（2） = 1 else P1code（2） = 0
if y1 < yT then P1code（1） = 1 else P1code（1） = 0
second end point： P2
if x2 < xL then P1code（4） = 1 else P1code（4） = 0
if x2 > xR then P1code（3） = 1 else P1code（3） = 0
if y2 < yB then P1code（2） = 1 else P1code（2） = 0
if y2 < yT then P1code（1） = 1 else P1code（1） = 0
finish
（2）中点算法是基于硬件实现的。重点算法同样把窗口和线段的关系分成三种情况：窗内、窗外以及其它情况。对于窗内和窗外这两种情况，中点算法和CS算法的处理方法相同；对于第三种情况，中点算法简单地将线段分成两段。中点算法是基于硬件的，所以算法比较简单，相对于用软件来实现，更偏重于用硬件来实现。
（3）CB算法能够裁剪任意一种凸多边形的窗口。CB算法会将交点简化成上下两组，主要判断的方法是：直线段的方向矢量和窗口边法矢量的点积是否大于零。CB算法会取上组部分最小的交点以及下组最大的交点，作为可见部分的端点。由于CB算法更适用于一般情况，所以CB算法的运算更加复杂。
（4）梁B算法在四种方法中，运算速度最快。但是在某些特殊情况下，梁B算法也需要进行大量的运算。
四种基础算法的适用情况，如表2-1所示。
2.2 逐点生成算法
上一小节主要介绍了图像的裁剪，本小节的逐点生成算法主要着重于研究图形曲线的绘制。由于任何图像都是根据图形而来，而任何图形都需要绘制，所以图形曲线的绘制也是一项非常基础性的研究课题。
科学家最开始采用几何算法作为绘图算法，这是因为以前的图形显示器都是扫描类型的显示器。目前这种算法已经很少采用，但是在工程制图的绘制过程中，受到各方面的限制，我们往往不得不采取这种方法。这种算法的基本思想就是：步长之间的两个点，采取直线的方法连接。但是由于步长很小，我们实际看起来就是一条曲线。由于绘制条件以及算法本身的限制，这类算法有着自身的缺点：运算量非常大而且绘制不够精细。
不同于曲线的几何算法，像素级生成算法是一种全新的基于计算机的算法，这种算法主要分成两种。第一种是对参数方程进行求导，进而计算出小于或等于一个像素迭代步长的距离的点。这类算法的优点是能够适用于大多数曲线的绘制；这类算法的缺点是计算量很大，而且会造成多余的计算。第二种是根据曲线的隐式方程，找出曲线走向中下一个像素中最近的点。正是由于采用了这种原理进行曲线绘制，所以曲线的误差在一个像素范围内。这类算法的优点是速度快，因为每一次的步长都是一个像素点的距离；这类算法的缺点是适用范围狭窄[3]。
3. 结论
我们现代人生活在各种各样的信息之中，如何应用计算机处理信息，处理图形成为了一个越来越重要的课题。本论文主要介绍了计算机图形学，以及两种基础算法：多边形裁剪算法和逐点生成算法。对于这些基础算法的研究，对提高计算机图形系统系能具有重要的意义。
参考文献
[1]高云 计算机图形学若干基础算法的研究[J] 沈阳工业大学，2002.
[2]沈颖，宋文强 计算机图形学的基本算法实现研究[J] 电脑知识与技术，2009，17（5）：4518-4519.
[3]陈丽，陈根才 改进的增量式关联规则维护算法[J] 计算机工程与设计，2002，（1）：60-63.
（作者单位：福州大学）
1. 计算机图形学
1.1 计算机图形学概述
我们现代人生活在各种各样的信息之中，如何应用计算机处理信息，处理图形成为了一个越来越重要的课题。本论文所要介绍的计算机图形技术，是计算机领域的热门领域之一，它是同电子硬件和计算机的周边设备一同发展而来。随着人类在航空航天、军事和通信等领域的突破，计算机图形学也得到了很快的发展。
计算机图形学是一门实用计算机产生、显示以及处理图形界面的知识体系。计算机图形学已经变得越来越重要，主要原因是：人们接收和发出信息，图形是很好的一种传递信息的方式。一个图形本身，就具有很丰富的信息，人们根据图形能够很自然快速地与外界进行交流。
1.2 计算机图形学研究热点
计算机图形学主要研究以下三个方面的内容。第一：隐藏线（面）的消除；第二：基本曲线的裁剪以及绘制；第三：现代图形学热点研究的内容，主要是虚拟现实技术、可视化、三维立体的重建等等。
由于在一个图形应用或图形软件中要大量重复调用这些基础算法，因此在这方面的任何进步都会对整个图形系统产生很大的影响。计算机图形学的基础算法经过人们几十年的研究，己比较成熟。但每一个进步对解决图形技术所面临的存储、传输、显示等问题都有很大的帮助。
2. 基础算法的研究
2.1 多边形裁剪算法
裁剪是处理图形一种很基础的方法，常见的裁剪操作主要有将不同的图形裁剪拼接形成新的图形。我们可以看出，裁剪算法在计算机图形学中是一种十分基础但是却又十分重要的操作[1]。
本论文所提到的裁剪方法，主要是针对凸多边形的。裁剪方法主要可以分为四个方法：中点算法、CS算法、CB算法、梁B算法。
（1）CS算法是Cohen-Sutherland的一种分区编码算法[2]。CS算法以前是计算机图形学中很重要的一种算法。CS算法对线段可以分为以下三种情况：窗内、窗外以及其它情况。我们在使用CS算法的时候，需要判断线段两端端点的编码，进而判断窗口和线段之间的位置关系，这种算法的缺点是对于判断所做的工作比其他算法多。端点编码检查算法的核心代码如下：
end point code algorithm
P1 and P2 are the end points of the line
xL，xn，yT，yB are the left， right， top and bottom window coordinates calculate the end point codes
put the codes for each end into 1*4 arrays called P1code and P2code
first end point： P1
if x1 < xL then P1code（4） = 1 else P1code（4） = 0
if x1 > xR then P1code（3） = 1 else P1code（3） = 0
if y1 < yB then P1code（2） = 1 else P1code（2） = 0
if y1 < yT then P1code（1） = 1 else P1code（1） = 0
second end point： P2
if x2 < xL then P1code（4） = 1 else P1code（4） = 0
if x2 > xR then P1code（3） = 1 else P1code（3） = 0
if y2 < yB then P1code（2） = 1 else P1code（2） = 0
if y2 < yT then P1code（1） = 1 else P1code（1） = 0
finish
（2）中点算法是基于硬件实现的。重点算法同样把窗口和线段的关系分成三种情况：窗内、窗外以及其它情况。对于窗内和窗外这两种情况，中点算法和CS算法的处理方法相同；对于第三种情况，中点算法简单地将线段分成两段。中点算法是基于硬件的，所以算法比较简单，相对于用软件来实现，更偏重于用硬件来实现。
（3）CB算法能够裁剪任意一种凸多边形的窗口。CB算法会将交点简化成上下两组，主要判断的方法是：直线段的方向矢量和窗口边法矢量的点积是否大于零。CB算法会取上组部分最小的交点以及下组最大的交点，作为可见部分的端点。由于CB算法更适用于一般情况，所以CB算法的运算更加复杂。
（4）梁B算法在四种方法中，运算速度最快。但是在某些特殊情况下，梁B算法也需要进行大量的运算。
四种基础算法的适用情况，如表2-1所示。
2.2 逐点生成算法
上一小节主要介绍了图像的裁剪，本小节的逐点生成算法主要着重于研究图形曲线的绘制。由于任何图像都是根据图形而来，而任何图形都需要绘制，所以图形曲线的绘制也是一项非常基础性的研究课题。
科学家最开始采用几何算法作为绘图算法，这是因为以前的图形显示器都是扫描类型的显示器。目前这种算法已经很少采用，但是在工程制图的绘制过程中，受到各方面的限制，我们往往不得不采取这种方法。这种算法的基本思想就是：步长之间的两个点，采取直线的方法连接。但是由于步长很小，我们实际看起来就是一条曲线。由于绘制条件以及算法本身的限制，这类算法有着自身的缺点：运算量非常大而且绘制不够精细。
不同于曲线的几何算法，像素级生成算法是一种全新的基于计算机的算法，这种算法主要分成两种。第一种是对参数方程进行求导，进而计算出小于或等于一个像素迭代步长的距离的点。这类算法的优点是能够适用于大多数曲线的绘制；这类算法的缺点是计算量很大，而且会造成多余的计算。第二种是根据曲线的隐式方程，找出曲线走向中下一个像素中最近的点。正是由于采用了这种原理进行曲线绘制，所以曲线的误差在一个像素范围内。这类算法的优点是速度快，因为每一次的步长都是一个像素点的距离；这类算法的缺点是适用范围狭窄[3]。
3. 结论
我们现代人生活在各种各样的信息之中，如何应用计算机处理信息，处理图形成为了一个越来越重要的课题。本论文主要介绍了计算机图形学，以及两种基础算法：多边形裁剪算法和逐点生成算法。对于这些基础算法的研究，对提高计算机图形系统系能具有重要的意义。
参考文献
[1]高云 计算机图形学若干基础算法的研究[J] 沈阳工业大学，2002.
[2]沈颖，宋文强 计算机图形学的基本算法实现研究[J] 电脑知识与技术，2009，17（5）：4518-4519.
[3]陈丽，陈根才 改进的增量式关联规则维护算法[J] 计算机工程与设计，2002，（1）：60-63.
（作者单位：福州大学）