计算机图形学 3多边形

计算机图形学

学时：48

第一章绪论1

第二章直线与直线的图形3

第四章二次曲线4

第五章裁剪6

第六章曲线曲面4

第七章图形变换2

考试2

第三章多边形

■1多边形的概念

■2多边形的填充

■3polygonfill-areaalgorithm

■4反走样基础

■3.1多边形的概念

■一多边形的分类

■多边形：由一些首尾连接的线段构成的图形，

线段为多边形的边线段的端点成为多边形的顶

点。

■多边形分为凸多边形和凹多边形。

■多边形的特征:

■Vertex:P15P2,.--.Pn

■Edge:PiR+i

■二多边形的描述

■如果要用来描述多边形则应该描述多边形

的特征，比如边和顶点。

■多边形的顶点序列为：P1,P2,.…Pn,

Pio则用一个二维数组来表示。

3.2多边形的填充

■1点在多边形内外的判断：

■方法：射线法:过该点划射线与多边形的边界的交点如果

为偶数，则该点在多边形外，如果为奇数，则该点在多

边形内。

■交点个数：射线1跨越多边形P得边界次数。

■交点：设A为1与P的边界公共点，当沿着1在A点附近从P的

外部（内部）跨入内部（外部），则认为是一个交点，否

则不作为一个交点。

■奇点：射线1与多边形P公共点为P的顶点时该点为奇点。

■奇点处理：与奇点相连的多边形P的边，若在射线1的同侧,

该奇点不作为交点，若在射线1的同侧，该奇点作为一个交

点，

■在带状区域：Y1＜y1+1o

■区＜二xV=Xj+i,乂＜=yV二％+i］内的象素被P的

边界分割成梯形和三角形。

■作用：1）区域中的梯形或三角形关于P的

内外关系一旦确定，各个梯形或三角形关

于P的内外关系也随之确定。

■2）区域内关于大量点P的关系的判别转换

为一个点的判别。

■2,扫描线的连贯性:

设扫描线y=c与多边形P的各边的交点的坐标

递增序列为x2，，X]O

■1）1为偶数（?）

■2）交点序列,

■3）在P内外线段沿y=c的扫描线相间排列。

■在P内的线段的区间：的，x2）,区，x4）

■（X11，X1）

3边的连贯性：

设扫描线丫=(：-1与P的各边交点的x坐标递增序

列为X'I,x'2,....,x'h,如果：yij<c,c-1<yi>i

则1)h=1;

2)(x；c-1),(x.c)位于多边形P的同

一边pkpk+1上。

3)XI=Xi+△Xik,AXik为Pkpk-1的斜率的负倒数

••・♦008软，Q

“••••••••cocoeo。

iiifiii

・••••••・••see♦得

煞求初挑

3.3polygonfill-areaalgorithm

■一多边形扫描转换的扫描线算法

■1,思想：

■1）取最上端的一条扫描线与多边形的各边相交,

（xl，x2）,（x3，x4）.,（xl-1，xl）,在第一，条

甘福线时，xl=x2,x3=x4o

■2）排序

■3）填色

■4）下—^条扫描线

■5）区域会化：金边的下端点变化

■I）换新边，ii）一起退出

■2,要求的序列

■1）交点序列：动态，可调。

■I）x值可修改（Axik）

■II）区域发生变化时，老边退出，新边加入。

■2）y下：判别带状区域是否发生变化。

■3）y上

■3,数据结构

■回顾：

■1)建立边结构：new(element),alloc()

■2)判断是否到尾：next==Null

■3)插入一*兀素(element)

head

二＞

■4)删除某一元素：delete()

■5)排序:

■6)搜索:

■扫描线算法的数据结构：

■1)用来保存交点序列的链表：AEL(Active_Edge_List)

2)elementinlist(金生表.中白勺元(素)：edge(ii)

3)saveedgeinEdgeTable(ET)

Edge:x△xy下next

X:该边与当前扫寸苗线交点、白勺乂值,

初值.为边的上漏，占、的x值

△x：彳亥关于y的向后—F介差分":上立岩，悬（x上,y上）

湍，息（x下,y下）

△x=xb-xH

y上一y下

ymin：=y下°

next:与旨4十,才旨向Edge自勺才旨4十

AEL：与旨4十，寺旨向Edge白勺月^4十。

ET娄t组;寸旨Edge白勺寺旨4十数红L,长度为显半屏扫才苗

名与白勺条我。

■algorithm：

■structEdge

■{floatx;

■floatAx;

■fl°atYmin；

■Edge*next;

■）；

■Stepl：（初始化）将ET表中各元素置空，建立ET表

■Step2：（basketsort,分桶分类）为多边形P的每一条边建立

边结构按该边的上端点的y值y上插入ET表中的第y上类

（组），即插入ET[y上].

■Step3：（初始化）AEL置空//AEL=Null

■y:ET表中非空元素的区域号最大值。

■Step4：扫描转化

■while（AELorETmS空）

■do

■{No.l（边插入）如果ET[y]非空，贝1J将ET[y]

■由各边插入AEL。

■No.2（排序）将AEL中的各边按照x（若x相等按Ax

■的递增顺序排序。

■No.3（如果AEL非空填色）将AEL中各边依次组成对，在横坐标为上

的扫描线上，将以每对边的x坐标为端点的区间上填上多边形所需重

的颜色.

■No.4（下一条扫描线）y-----o

■No.5（边删除）将AEL中满足尸ymin的边删除。

■No.6（边更新）将AEL中的各边x值更新，x=x+

■Ax}

注：1)y=ymin体现了奇点处理。

2)Ax体现了边的连贯性。

3)AEL体现了扫描线的连贯性

多边形各顶点为：

(1,6),(1,4),(3,1),(6,2)

(8,1),(10,5),(7,8),

(5,8),(3,10),(2,6)

1,建立ET表

申请与屏幕扫描线

条数相同的指向edge

的数组指针

el=[l,0,4,next]插入

ET[6]

e2=[1,2/3,1,next]插入

ET[4]

e3=[3,-3,1,next]插入

ET[2]

e4二[6,2,1,next]插入

ET[2]

2,为多边形的10条边建立边结构。并按该边的上

端点的y值插入ET表中的y上类。

e5=[8,-l/2,1,next]插入ET[5];

e6=[l0,1,5,next]fiAET[8];

e7=[5,l,8,next]fi|AET[10];

e8=[3,-l/4,6,next]fiAET[10];

■3,AEL置空；y=10；

4,扫描转换

8-]1015n

AEL93-0-256n—A518n

■1）inserttheedge（边插入）。

■6）updatetheedge（边更新）。

■2）sort（排序）。

■3）filling（填曲）。

■4）nextscanline（下一条扫描线）。

■5）deletetheedge（边删除）。

■remark：

■1）充分利用连贯性

■2）避免求交点运算，计算量少，速度快

■3）数据结构复杂

■4）程序复杂

■二区域的种子填充算法

■1）点邻域：四邻域，八邻域

■四邻域：四个点为A点的邻域，对于上下左右四个

■方向运动而言，上下左右四点构成一点的四邻域。

■八邻域同样可得。

■2）路径：四连通路径，八连通路径

■四连通路径：点集中相邻两点均在对方的四邻域中

■3）区域：四连通区域，八连通区域

■四连通区域：如果一点集内任意两点都存在一条完全有

■该点集中的内点组成的四连通路径相连接则称该点集为

■四连通区域。

■注：如果四连通区域内的任意点出发只经

过上下左右四个方向的运动可以到达区域

的任何一点，即为漫延。

■种子填充法：有一点出发逐步影响周围的

点。

■种子填充算法：

■1)递归算法：出口：种子点seedpoint

■flood_fi114(x5y?oldcolor,newcolor)

■{if(frame_buffer(x?y)==oldcolor)

■{frame_buffer(x5y)==newcolor;

■flood_fill4(x5y+15oldcolor,newcolor);

■flood_fill4(x,y-l,oldcolor,newcolor);

■flood_fill4(x-l,y,oldcolor,newcolor);

■flood_fill4(x+1,y,oldcolor,newcolor);

■逐点漫延，用堆栈实现。

■注：

■1）点进出系统堆栈达4次

■2）程序简单明了

■3）算法采用递归（尽量不用）

■4）费时费内存。

■2种子填充的扫描线算法

■Algorithm:

■stepl:给定种子点（x,y）在种子点所在扫描线上找出包

含种子点所在区域内的最长的区间（xbxr）

■step?:在种子点所在扫描线上下相邻的扫描线上的(xl,xr)的区间

的标一个点做为种子点处理。

■程序：

■Stepl：初始化：

■"stack置空。•种子点进栈push(x,x,y)

■Step2：区域填充

■while(stack_is_not_empty)

■{2.1出栈pop(x,x,y)

■2.2向左延伸

■if(frame_buffer(xl,y)==oldcolor)

■{if(frame_buffer(xl-l,y)==oldcolor)xl=xl-1

■}

■2.3向右延伸(同上)

■2.4确定子区间(xl,xr),在纵坐标为y的扫描线的区间(xl,xr)内

定义区间内的各子区间，从对到xr逐一鱼查象素的颜色

■若frame_buffer(xl,y)==oldcolor,则将该象素变色，否则

确定(X—1,y)，(x+1,y)是否为端,占，也即：(X—

1,y)是否为学区间的右端点，(x+1,y)是否为子区间

的若端点。

■2.5(填色进栈)