岁扫描线算法 扫描线算法是多边形扫描转换的常用算法 与逐点判断算法相比,扫描线算法充分利用了相 邻象素之间的连贯性,避免了对象素的逐点判断 和反复求交的运算,达到了减少了计算量和提高 速度的目的。 开发和利用相邻象素之间的连贯性是光栅图 形算法研究的重要内容。扫描转换算法综合利用 了区域的连贯性、扫描线连贯性和边的连贯性等 三种形式的连贯性。 2021/1/21 浙江大学计算机图形学 17
2021/1/21 浙江大学计算机图形学 17 扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比，扫描线算法充分利用了相 邻象素之间的连贯性，避免了对象素的逐点判断 和反复求交的运算，达到了减少了计算量和提高 速度的目的。 开发和利用相邻象素之间的连贯性是光栅图 形算法研究的重要内容。扫描转换算法综合利用 了区域的连贯性、扫描线连贯性和边的连贯性等 三种形式的连贯性。 扫描线算法
区域的连贯性 设多边形P的顶点P1(x1,y1),i=0,1,…,n,又设 0,yi1 In 是各顶点P的坐标y的递减数列,即y1k≥yk,0≤k≤n-1 这样,当y1k≥y1+1,0≤k≤n-1时,屏幕上位于y=y和 y=y;k+两条扫描线之间的长方形区域被多边形P的边分割 成若干梯形(三角形可看作其中一底边长为零的梯形), 它们具有下列性质: 6 2( 18
2021/1/21 浙江大学计算机图形学 18 设多边形P的顶点Pi=(xi,yi),i=0,1, …,n，又设 yi0,yi1,…yin 是各顶点Pi的坐标yi的递减数列，即yik≥yik+1,0≤k≤n-1 这样，当yik≥yik+1,0≤k≤n-1时，屏幕上位于y=yik和 y=yik+1两条扫描线之间的长方形区域被多边形P的边分割 成若干梯形（三角形可看作其中一底边长为零的梯形）， 它们具有下列性质： 区域的连贯性
区域的连贯性 1)梯形的两底边分别在y=y和y=yk两条扫描线上,腰 在多边形P的边上或在显示屏幕的边界上 2)这些梯形可分为两类:一类位于多边形P的内部;另 类在多边形P的外部。 3)两类梯形在长方形区域{y,y1k+t}内相间的排列,即 相邻的两梯形必有一个在多边形P内,另一个在P外。 P P P 19
2021/1/21 浙江大学计算机图形学 19 区域的连贯性 1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰 在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部；另 一类在多边形P的外部。 3）两类梯形在长方形区域{yik,yik+1}内相间的排列，即 相邻的两梯形必有一个在多边形P内，另一个在P外
区域的连贯性 根据这些性质,实际上只需知道该长方形 区域内任一梯形内一点关于多边形P的内 外关系后,即可确定区域内所有梯形关 于P的内外关系 P P 2021/1/21 浙江大学计算机图形学 20
2021/1/21 浙江大学计算机图形学 20 区域的连贯性 根据这些性质，实际上只需知道该长方形 区域内任一梯形内一点关于多边形P的内 外关系后，即可确定区域内所有梯形关 于P的内外关系
v扫描线的连贯性 设e为一整数,yio≥e≥yino若扫描线y=e与多边形P的 P;-1P2相交,则记其交点的横坐标为xa1 现设xi1,xa12,xa13,…,xa1是该扫描线与P的边界各交 点横坐标的递增序列,称此序列为交点序列。由区域的连 贯性可知,此交点序列具有以下性质 P3 8 e? 2 P 202 人、J"≠"Du
2021/1/21 浙江大学计算机图形学 21 设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的 Pi-1Pi相交，则记其交点的横坐标为xei。 现设xei1,xei2,xei3,…,xeil 是该扫描线与P的边界各交 点横坐标的递增序列，称此序列为交点序列。由区域的连 贯性可知，此交点序列具有以下性质： 扫描线的连贯性