河南理工大学万方科技学院课程设计报告2010 — 2011学年第二学期课程名称计算机图形学设计题目多边形裁剪算法学生姓名孙晓芳学号**********专业班级计算机科学与技术10升指导教师侯守明2011 年6 月29 日目录目录目录 (I)第1章程序运行环境................................................................................... 错误!未定义书签。

1.1 程序运行环境的简单介绍................................................................. 错误!未定义书签。

1.2 程序运行环境的安装......................................................................... 错误!未定义书签。

1.3 多边形裁剪算法设计的内容........................................................................... 第2章直线裁剪和多边形裁剪的简单比较 (4)2.1 直线裁剪的介绍 (4)2.1.1 直线裁剪的基本原理………………………………………......................................2.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算……………………………..2.2 多边形裁剪介绍 (9)2.2.1 多边形裁剪的基本思想……………………………………………………………..2.2.2 多边形和窗口相交的判定方法…………………………………………..第3章多边形裁剪方法的详细介绍 (12)3.1 Sutherland-Hodgman算法………………………………………………………………….3.2 多边形裁剪算法的流程图 (12)3.3多边形裁剪算法的实现 (13)第4章代码的实现 (14)第5章总结 (21)参考文献 (22)第1章程序的运行环境1.1 程序运行环境的简单介绍本次设计主要是运用了程序设计语言主要以C/C++语言为主，开发平台为Visual C++。

现在Windows系统的主流编译环境有Visual C++，C++ Builder，Dev-C++等，它们都是支持OpenGL的。

但这次设计主要选择Visual C++ 作为学习OpenGL的实验环境。

Microsoft Visual C++，（简称Visual C++、MSVC、VC++或VC）微软公司的C++开发工具，具有集成开发环境，可提供编辑C语言，C++以及C++/CLI等编程语言。

Microsoft Visual C++是Microsoft公司推出的开发Win32环境程序，面向对象的可视化集成编程系统。

它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock网络、3D控制界面。

OpenGL作为盖茨设计的主要软件它与其他软件相比主要有以下几个优点1）与C语言紧密结合：2）强大的可移植性：3、高性能的图形渲染：1.2 程序安装及步骤1．选择一个编译环境这里我们选择Visual C++ 作为学习OpenGL的实验环境2．安装GLUT工具包GLUT不是OpenGL所必须的，但它会给我们的学习带来一定的方便，推荐安装。

Windows 环境下的GLUT下载地址：（大小约为150k）/resources/libraries/glut/glutdlls37beta.zipWindows环境下安装GLUT的步骤：1）将下载的压缩包解开，将得到5个文件2）glut.h放到GL文件夹（VC6中一般是：C:\Program Files\Microsoft Visual Studio\VC98\Include\GL，VC2005中是：C:\Program Files\Microsoft Visual Studio 8\VC\Include，新建GL文件夹，再将glut.h放到GL文件夹中）。

3）glut.lib和glut32.lib放到静态函数库所在文件夹（VC6中一般是：C:\Program Files\Microsoft Visual Studio\VC98\Lib, VC2005中是：C:\Program Files\Microsoft Visual Studio 8\VC\Lib）。

4）把解压得到的glut.dll和glut32.dll放到操作系统目录下面的system32文件夹内。

（其路径为：C:\Windows\System32）3．建立一个OpenGL工程这里以VC为例：首先从开始->所有程序->Microsoft Visual C++ 6.0菜单中打开VC，也可单击文件：C:\Program Files\Microsoft Visual Studio\Visual C++6\Common\MSDev98\Bin\msdev.exe打开VC，在VC中选择File->New->Project，然后选择Win32 Console Application，输入一个工程名,设为A，然后按OK。

在谈出的对话框左边点Application Settings，找到A Simple application并勾上，选择Finish。

然后打开工程代码文件:A.cpp,将其内容替换为实验示范代码.点击运行按钮就可以执行调试程序了。

1.3 多边形裁剪算法设计的内容和要求这次设计的主要内容；1）理解多边形裁剪与直线段裁剪的区别；2）掌握多边形的裁剪过程；3）理解并掌握Sutherland-Hodgman算法的裁剪思想。

第2章直线裁剪和多边形裁剪的比较2.1 直线裁剪的介绍2.1.1直线裁剪的基本原理图1所示的为直线与窗口边界之间可能出现的几种关系。

可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪。

如果一直线的两个端点均在窗口边界之内（如图1中P5到P6的直线），则此直线应保留。

如果一条直线的一个端点在窗口外（如P9）另一个点在窗口内（如P10），则应从直线与边界的交点（P9）处裁剪掉边界之外的线段。

如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。

图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保留P7到P8的线段，其余部分均裁剪掉。

图1直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线。

对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉。

一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。

2.1.2直线裁剪算法的分类以及和窗口交点参数值的计算直线段裁剪算法是复杂图形裁剪的基础。

复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。

主要的四种算法直接求交算法Cohen-Sutherland算法中点算法梁友栋－barskey算法Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。

①若P1P2完全在窗口内，则显示该线段P1P2，简称“取”之。

②若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。

③若线段既不满足“取”的条件，也不满足“弃”的条件，则把线段分为两段。

其中一段完全在窗口外，可弃之。

然后对另一段重复上述处理。

1．区域码及其建立Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。

此代码称为区域码。

区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。

区域码从右到左的各位所代表的坐标区如下所示：位 4 3 2 1坐标区上下右左上述各位中某位为1，则表示点位于此坐标区。

窗口周围各坐标区的区域码如图2所示。

由图2可见，位于窗中内的点，其区域码应为0000，位于窗口左下方的点，其区域码应为0101，其余类推。

区域码各位的值可以通过对端点坐标（x，y）与窗口边界的比较求得。

如果x<x wmin，则区域码的第一位为1，其余各位的确定与此相似。

现在的计算机语言都可以进行位操作，因此，可以通过以下步骤建立区域码：①计算出端点坐标与窗口边界的差。

②按计算出的各个差的符号把区域码的相应位置为0或1，即区域码的第一位置为（x－x wmin）的符号位；区域码的第二位置为（x wmin-x）的符号位；区域码的第三位置为（y-y wmin）的符号位；图2 区域码区域码的第四位置为（y wmin -y ）的符号位。

2．区域码裁剪算法对所有直线的端点都建立了区域码之后，就可按区域码判断直线在窗口之内或窗口之外。

这可分为如下几种情况：①若一直线的两个端点的区域码均为0000则此直线在窗口边界之内，应子保留。

②若一直线的两个端点的区域码的同一位同时为1，则此直线全部在窗口边界之外，应子裁剪。

例如，若一直线的一个端点的区域码为1001，另一个端点的区域码为0101，则此两端点的区域码的第一位均为1，说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。

可用将直线两个端点的区域码进行与操作的方法，判断直线是否在窗口之外，若与操作的结果为0000则两端点的区域码任何位均不同时为1，此直线不一定被裁剪。

③以上两种情况之外的直线，有可能穿过窗口，也有可能不穿过窗口，如图87所示。

图中所示的两条直线都不符合情况②的要求，但一条直线（P 1P 2）穿过窗口，另一直线（P 3P 4）不守过窗口。

对这类直线可以进行如下处理：取窗口外的一个端点与窗口边界比较以确定可排除直线的哪一部分，然后，把直线剩下的部分与其他边界比较，这样一直到直线全部被排除或确定直线的哪一部分在窗口之内为止。

可按“左、右、下、上”的次序建立检查直线端点与窗口边界关系的算法。

下面介绍对图3所示的两条直线进行处理的过程。

从直线P 1P 2的下端点P 1开始，依次检查窗口的左、上、右及下边界，可发现此点在窗口之下（因为区域码的第三位为1）。

然后求得直线与下边界的交点P 1排除线段P 1 P 1这样直线就缩短为P 1 P 2。

因为P 2在边界之外，将此端点与各边界比较，可发现此端点在窗口上面。

计算出交点P 2线段P 1P 2保留下来。