扫描线算法 ●规则2: 边界上象素的取舍问题,避免填充扩大化。 ●解决方法: 边界象素:规定落在右上边界的象素不予填充 具体实现时,只要对扫描线与多边形的相交区间左闭右开 (x,e) 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 ●规则2： 边界上象素的取舍问题，避免填充扩大化。 ●解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开 扫描线算法
扫描线算法 ●规则3: 扫描线与多边形的顶点相交时,交点的取舍,保证交点正 确配对 ●解决方法: 检査两相邻边在扫描线的哪一侧 只要检查顶点的两条边的另外两个端点的Y值,两个Y值 中大于交点Y值的个数是0,1,2,来决定取0,1,2个交点 22 F1 y-e 22 2
浙江大学信息学院 计算机图形学 ●规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正 确配对。 ●解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值 中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 扫描线算法
扫描线算法 扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比,扫描线算法充分利用了相 邻象素之间的连贯性,避免了对象素的逐点判断 和反复求交的运算,达到了减少了计算量和提高 速度的目的。 开发和利用相邻象素之间的连贯性是光栅图 形算法研究的重要内容。扫描转换算法综合利用 了区域的连贯性、扫描线连贯性和边的连贯性等 三种形式的连贯性 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 扫描线算法是多边形扫描转换的常用算法。 与逐点判断算法相比，扫描线算法充分利用了相 邻象素之间的连贯性，避免了对象素的逐点判断 和反复求交的运算，达到了减少了计算量和提高 速度的目的。 开发和利用相邻象素之间的连贯性是光栅图 形算法研究的重要内容。扫描转换算法综合利用 了区域的连贯性、扫描线连贯性和边的连贯性等 三种形式的连贯性。 扫描线算法
区域的连贯性 设多边形P的顶点P1=(x1,y1),i=0,1,…,n,又设 y10,yi1…y 是各顶点P的坐标y的递减数列,即yk≥y1k+1,0≤k≤n-1 这样,当y1≥y1k+1,0≤k≤n-1时,屏幕上位于y=y和 y=yik+1两条扫描线之间的长方形区域被多边形P的边分割 成若干梯形(三角形可看作其中一底边长为零的梯形), 它们具有下列性质:
浙江大学信息学院 计算机图形学 设多边形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=y+1两条扫描线上,腰 在多边形P的边上或在显示屏幕的边界上 2)这些梯形可分为两类:一类位于多边形P的内部;另 类在多边形P的外部 3)两类梯形在长方形区域{y,yk+t内相间的排列,即 相邻的两梯形必有一个在多边形P内,另一个在P外
浙江大学信息学院 计算机图形学 区域的连贯性 1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰 在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部；另 一类在多边形P的外部。 3）两类梯形在长方形区域{yik,yik+1}内相间的排列，即 相邻的两梯形必有一个在多边形P内，另一个在P外