计算机图形学课程设计-Weiler-Atherton多边形裁剪
更新时间:2024-05-30 06:43:01 阅读量: 综合文库 文档下载
《计算机图形学》课程设
计
实验报告书
安徽工业大学数理学院
姓 名 专 业 班 级 学 号 指导教师
2014年1月13日 鲍计炜
信息与计算科学
信112 119084177 侯为根
Weiler-Atherton多边形裁剪
Weiler-Atherton算法是一种通用的多边形算法,因此该过程可以用标准位置的裁剪窗口去裁剪多边形填充区域。
一,Weiler-Atherton思想方法
Weiler-Atherton算法适合与任意多边形。裁剪窗口和被裁剪多边形处于完全对等的地位,这里我们称:
1、被裁剪多边形为主多边形,记为A; 2、裁剪窗口为裁剪多边形,记为B。
主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域: 1、A∩B(交:属于A且属于B); 2、A-B(差:属于A不属于B); 3、B-A(差:属于B不属于A);
4、A∪B(并:属于A或属于B,取反;即:不属于A且不属于B)。
内裁剪即通常意义上的裁剪,取图元位于窗口之内的部分,结果为A∩B。
外裁剪取图元位于窗口之外的部分,结果为A-B。
观察右图不难发现裁剪结果区域的边界由被裁剪多边形的部分边界和裁剪窗口的部分边界两部分构成,并且在交点处边界发生交替,即由被裁剪多边
形的边界转至裁剪窗口的边界,或者反之。由于多边形构成一个封闭的区域,所以,如果被裁剪多边形和裁剪窗口有交点,则交点成对出现。这些交点分成两类: 一类称“入”点,即被裁剪多边形由此点进入裁剪窗口,如图中a、c、e; 一类称“出”点,即被裁剪多边形由此点离开裁剪窗口,如图中b、d、f。
二,Weiler-Atherton思想原理
假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时,交点必然成对出现,其中一个是从被裁剪多边形进入裁剪窗口的交点,称为“入点”,另一个是从被裁剪多边形离开裁剪窗口的交点,称为“出点”。 算法从被裁剪多边形的一个入点开始,碰到入点,沿着被裁剪多边形按顺时针方向搜集顶点序列;
而当遇到出点时,则沿着裁剪窗口按顺时针方向搜集顶点序列。
按上述规则,如此交替地沿着两个多边形的边线行进,直到回到起始点。这时,收集到的全部顶点序列就是裁剪所得的一个多边形。
由于可能存在分裂的多边形,因此算法要考虑:将搜集过的入点的入点记号删去,以免重复跟踪。将所有的入点搜集完毕后算法结束。
三,Weiler-Atherton算法步骤
1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。 2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。
3、求出被裁剪多边形和裁剪窗口相交的所有交点,并给每个交点打上“入”、“出”标记。
然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ,并放入数组3中; 同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ,放入数组4中; 4、初始化输出数组Q,令数组Q为空。接着从数组3中寻找“入”点。 如果“入”点没找到,程序结束。
5、如果找到“入”点,则将“入”点放入S中暂存。
6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。
7、沿数组3顺序取顶点:
如果顶点不是“出点”,则将顶点录入到输出数组Q中,流程转第7步。 否则,流程转第8步。 8、沿数组4顺序取顶点:
如果顶点不是“入点”,则将顶点录入到输出数组Q中,流程转第8步。 否则,流程转第9步。
9、如果顶点不等于起始点S,流程转第6步,继续跟踪数组3。 否则,将数组Q输出;
流程转第4步,寻找可能存在的分裂多边形。
算法在第4步:满足“入”点没找到的条件时,算法结束。算法的生成过程见下图所示。
四、Weiler-Atherton程序:
const int MAXVERT = 500;
const int MAXPOLYV = 50; const int MAXH = 10;
struct Point2D {float x,y; };
typedef Point2D Vertices[MAXVERT];
enum VerType = {Polygon, Intersection};
typedef struct ClipListRec * ClipPtr; struct ClipListRec { int Vindex;
ClipPtr next; VerType Kind; float t;
ClipPtr otherList; }
struct Polygon { int nVertex;
int vert[MAXPOLYV]; ClipPtr list; }
struct GenPolygon { Polygon exterior; int numHoles;
Polygon Holes[MAXH]; }
GenPolygon Sub,Clip;
int entering[MAXVERT],exiting[MAXVERT]; Vertices V;
int numVertex = 0; // size of the array of verticies int clipPoly[MAXVERT]; // a clip polygon
int readPoint();
{ cin >> inX; cin >> inY; if (numVertex < MAXVERT) { V[numVertex].x = inX; V[numVertex].y = inY; idNo = numVertex; numVertex++; } else
idNo = -1; return idNo; }
void readPolygon (GenPolygon p) { cin >> p.exterior.nVertex;
for (i = 0; i < p.exterior.nVertex; i++) { newId = readPoint(); if (newId < 0) error else
{ insertAtRear (p.exterior.list,newId);
p.exterior.vert[i] = newId; } }
// now do the holes basically the same way . . . }
// the \while (!EMPTY(entering)) { nextInter = delete (entering);
SEARCH (SubjectPolygon,nextInter,ptr1); AddToOutputList (ptr1->. . .) StartPoint = ptr1->. . . ptr1 = prt1->next;
while (ptr1->. . . != StartPoint) { AddToOutputList (ptr1->. . .);
if (ptr1-> . . == INTERSECTION) ptr1 = prt1->otherList->next; else
ptr1 = ptr1->next; }
FixListForOutput(); DrawPolygon(); EmptyOutputList(); }
五,实现结论
1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。
2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁,即保留窗口内的图形或保留窗口外的图形,因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。
3、裁剪思想新颖,方法简洁,裁剪一次完成,与裁剪窗口的边数无关。
4,Weiler-Atherton算法的的设计思想很巧妙,裁剪是一次完成,不象Sutherland-Hodgman多边形裁剪算法,每次只对裁剪窗口的一条边界及其延长线进行裁剪,如裁剪窗口有n条边,则要调用n次S-H算法后才能最后得出裁剪结果。
p.exterior.vert[i] = newId; } }
// now do the holes basically the same way . . . }
// the \while (!EMPTY(entering)) { nextInter = delete (entering);
SEARCH (SubjectPolygon,nextInter,ptr1); AddToOutputList (ptr1->. . .) StartPoint = ptr1->. . . ptr1 = prt1->next;
while (ptr1->. . . != StartPoint) { AddToOutputList (ptr1->. . .);
if (ptr1-> . . == INTERSECTION) ptr1 = prt1->otherList->next; else
ptr1 = ptr1->next; }
FixListForOutput(); DrawPolygon(); EmptyOutputList(); }
五,实现结论
1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。
2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁,即保留窗口内的图形或保留窗口外的图形,因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。
3、裁剪思想新颖,方法简洁,裁剪一次完成,与裁剪窗口的边数无关。
4,Weiler-Atherton算法的的设计思想很巧妙,裁剪是一次完成,不象Sutherland-Hodgman多边形裁剪算法,每次只对裁剪窗口的一条边界及其延长线进行裁剪,如裁剪窗口有n条边,则要调用n次S-H算法后才能最后得出裁剪结果。
正在阅读:
计算机图形学课程设计-Weiler-Atherton多边形裁剪05-30
山中小镇散文03-30
去除新车异味六招07-19
生物分离工程部分习题和答案11-18
大连市电工作业安全技术培训理论试卷02-28
15年13级matlab实验报告01-28
和平丽景售楼处施工图预算+++10-31
诗词曲18-2017年版新课标高中语文72篇必背古诗文理解性默写之《琵琶行》(含答案)11-25
撞车之后处理的绝招03-22
矿山地质IB姚玉增05-17
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 多边形
- 裁剪
- Atherton
- 图形
- 课程
- 计算机
- Weiler
- 设计
- 度米文库汇编之小学二年级班主任工作总结范文
- 五年级上册数学期末试题-2018-20192人教版含答案
- “十三五”重点项目-手动密集架项目可行性研究报告 - 图文
- Autodesk Inventor 2010 培训教程1 - 图文
- 主桥3#墩基础水下爆破施工方案终4.7.docx
- 自动控制原理课程设计 - 图文
- 中国文学史期末复习思考题
- 婚姻家庭继承法
- 中国平安LASS基础性向测评
- 1实验一先来先服务FCFS和短作业优先SJF进程调度算法
- 标准化工地创建规划方案
- 肿瘤代谢组学的研究进展
- 甲状腺指南(发排稿)
- 中考物理专题训练二 电学专题
- 京工促发69号(北京市认定工业企业技术中心管理办法)
- dota白牛攻略 - 图文
- 商场零售管理系统
- 中外文艺沙龙精鉴的辞典 - 图文
- 同学录论文
- 对团体辅导的认识和思考