方法一:顶点与扫描线之间的拓扑关系 通过标识相交边与扫描线的相对位置关系而鉴别扫描线间的 拓扑差异一顶点两条边位于扫描线的同侧异侧 通过以顺时针或逆时针方向搜索多边形边界,并观察从一条边移到另 条边时顶点y坐标的相对变化: 假如两条顺序连接边的端点y值单调增加或减少,那么,对于任何 穿过该点的扫描线就必须将该中间顶点计为一个交点 否则,共享顶点表示多边形边界上的一个局部极值,将该顶点记 为两个交点 扫描线y+1 扫描线 扫描线1 2-17
2-17 方法一：顶点与扫描线之间的拓扑关系 • 通过标识相交边与扫描线的相对位置关系而鉴别扫描线间的 拓扑差异 — 顶点两条边位于扫描线的同侧/异侧 – 通过以顺时针或逆时针方向搜索多边形边界，并观察从一条边移到另 一条边时顶点y坐标的相对变化： • 假如两条顺序连接边的端点y值单调增加或减少，那么，对于任何 穿过该点的扫描线就必须将该中间顶点计为一个交点 • 否则，共享顶点表示多边形边界上的一个局部极值，将该顶点记 为两个交点
顶点与扫描线之间的拓扑关系 D 扫描线2 E 扫描线1 2-18
2-18 顶点与扫描线之间的拓扑关系
方法二:特殊顶点分离处理 将多边形某些边缩短,以分离应计为1个交点的顶点 以顺时针或逆时针方向处理整个多边形边界上的非水平边。 在处理每条边时进行下列检测: 该边与下一条非水平边是否有单调递増或单调递减的端点y值? 假如有,可将较低一条边缩短,以保证对通过连接两条边公共顶 点的扫描线仅有一个交点生成 当两条边的端点y值增加时,当前边较高端点y值减去1 当端点y值单调递减时,紧随边较高端点的y坐标值减就去1 扫描线y+1 扫描线 扫描线 2-19
2-19 方法二：特殊顶点分离处理 ◼ 将多边形某些边缩短，以分离应计为1个交点的顶点 – 以顺时针或逆时针方向处理整个多边形边界上的非水平边。 在处理每条边时进行下列检测： • 该边与下一条非水平边是否有单调递增或单调递减的端点y值？ • 假如有，可将较低一条边缩短，以保证对通过连接两条边公共顶 点的扫描线仅有一个交点生成： – 当两条边的端点y值增加时，当前边较高端点y值减去1 – 当端点y值单调递减时，紧随边较高端点的y坐标值减就去1
连贯性和增量计算原理 在扫描转换及其它图形算法中常充分利用待显示场景的各 种连贯特性 连贯性可简单地看作场景中的一部分的特性以某种方 式与场景中的其它部分相关,这种关系可用来减少处 理 ■利用沿一条边从一条扫描线到下一条扫描时斜率为常数这 连贯性,确定边交点时可采用增量坐标计算 (x+,+)/扫描线y+1 扫描线y x+2=x+(1/m) 2-20
2-20 连贯性和增量计算原理 ◼ 在扫描转换及其它图形算法中常充分利用待显示场景的各 种连贯特性 ◼ 连贯性可简单地看作场景中的一部分的特性以某种方 式与场景中的其它部分相关，这种关系可用来减少处 理 ◼ 利用沿一条边从一条扫描线到下一条扫描时斜率为常数这 一连贯性，确定边交点时可采用增量坐标计算
连贯性和增量计算原理 两扫描线间y坐标的变化为: yk+1-Ok=1 扫描线交点的x值xk+1可从前一条 扫描线上X交点值x来决定: k+=Xk+(1/m) 每个后继交点的x值都由加斜率mLa2x2/扫 的倒数并取整而计算出来。 kw%上 扫描线 k条扫描线沿一条边、相对于最初 x1+1=x+(1/m 扫描线交点ⅹ值计算为: XK=Xo+(kIm) 2-21
2-21 连贯性和增量计算原理 – 两扫描线间y坐标的变化为： yk+1-yk=1 – 扫描线交点的x值xk+1可从前一条 扫描线上x交点值xk来决定： xk+1=xk+(1/m) – 每个后继交点的x值都由加斜率m 的倒数并取整而计算出来。 – k条扫描线沿一条边、相对于最初 扫描线交点xk值计算为： xk=x0+(k/m)