逐点判断法 3)编码方法:累计角度方法的离散方法(略) Step: a.预处理,测试点在边上否? b.V为中点作局部坐标系,对象限按逆 时针(或顺时针)编码; C.顶点编码Ipi, d.边编码。PP1+1:△PP1+1=Ip-1p1 e.计算∑△PP11(其中△PnPn+1=△PP0) 若∑为0,V在P外; 若∑为+/-4,V在P内 逐点判断法程序简单, 速度太慢,效率低。 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 3）编码方法：累计角度方法的离散方法（略） Step: a.预处理，测试点在边上否？ b.V为中点作局部坐标系,对象限按逆 时针（或顺时针）编码； c.顶点编码Ipi， d.边编码。PiPi+1: △PiPi+1=Ipi+1-Ipi e.计算∑ △PiPi+1 （其中△PnPn+1 = △PnP0)： 若 ∑ 为0, V在P外； 若 ∑ 为+/-4，V 在P内； 逐点判断法程序简单， 速度太慢，效率低。 P0 P1 P2 v 逐点判断法
逐点判断法 ·逐点判断的算法虽然程序简单,但不可取。原 因是速度太慢,主要是由于该算法割断了各象 素之间的联系,孤立地考察各象素与多边形的 内外关系,使得几十万甚至几百万个象素都要 判别,每次判别又要多次求交点,需要做 大量的乘除运算,花费很多时间 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 逐点判断法 • 逐点判断的算法虽然程序简单，但不可取。原 因是速度太慢，主要是由于该算法割断了各象 素之间的联系，孤立地考察各象素与多边形的 内外关系，使得几十万甚至几百万个象素都要 一一判别，每次判别又要多次求交点，需要做 大量的乘除运算，花费很多时间
扫描线算法 扫描线算法 目标:利用相邻像素之间的连贯性,提高 算法效率 处理对象:非自交多边形(边与边之间除 了顶点外无其它交点) 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 扫描线算法 • 扫描线算法 –目标：利用相邻像素之间的连贯性，提高 算法效率 –处理对象：非自交多边形 （边与边之间除 了顶点外无其它交点）
扫描线算法 交点的取整规则 要求:使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致 部分像素位于多边形之外,从而不可用 假定非水平边与扫描线y=e 相交,交点的横坐标为x, 规则如下 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 扫描线算法 –交点的取整规则 • 要求：使生成的像素全部位于多边形之内 –用于线画图元扫描转换的四舍五入原则导致 部分像素位于多边形之外，从而不可用 • 假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下
扫描线算法 ●规则1: X为小数,即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上,向右取整 (b)交点位于右边之上,向左取整 (x,) (x,e) 浙江大学信息学院 计算机图形学
浙江大学信息学院 计算机图形学 扫描线算法 ●规则1： X为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整