一个快速有效的直线反走样算法

小 型 微 型 计 算 机 系 统
( 3) ( 4) ( 5)
2005 年
I0 是预期光强, I0 使不同斜率的直线有着同样的光强: 假设有 线段 s 1 ( ( 0, 0) , (X , 0) ) 与s 2 ( ( 0, 0) , (X, X ) ) , 由于s2 的长度是
s1 的
证明公式 ( 8) 设当前线段s i 的预期光强为 I 0 , 在s i 中取样点的个数为n; 取样点的步长为△x= 1 n; 每个点的实际光强为 I0 n, 按照公 式 ( 1) — ( 5) 即:
1 引 言
直线的生成是计算机图形学中一个基本内容. 目前的显 示器通常指光栅显示器, 每个象素用一对整数型坐标及其灰 度值来表示. 所谓在光栅显示器中绘制一条直线 y= f ( x ) , 就 是将之模拟成一个由一系列连续的点组成的弧. 设一条线段的斜率为 m ( 0 ≤m ≤ 1 ) , 生成的方法一般为 每取一个 x 的整数值, 通过 y= f (x ) 来计算 y 的值, y 值可以是 非整数的, 由于光栅显示器的点是一对整型值, 常见的方法 是: 根据 [ f ( x ) ] 和 [ f ( x ) ] 哪一个更与 f ( x ) 值接近, 来确定 y 值. DDA 和B resenham 的算法是将 ( x, [ y ] ) 或 (x, [ y ] ) 强化为 一个常量. 以上的方法都会产生锯齿形边和图形细节失真现 象, 这种现象即为走样. 反走样技术一般有以下几种方法: 1. 1 提高显示器的分辨率 提高了分辨率也就相应增加了采样率, 但受技术和设备 的限制, 由于屏幕的分辨率是既定的, 不可能随方法增加, 因 此失真降低是有限的. 1. 2 后处理法 指得到实际图形的采样后, 在显示之前一般先做边缘检 测, 后对边缘做平滑. 由于边缘检测一般对整幅画面进行搜 索, 再加上平滑也需要时间, 所以这种方法在计算量和存储量
( 15)
图 2 取样点 P 光强由四个象素决定 h = f ( i) - [ f ( i) ]
I(i, [ f ( i) ]) 1 = I0 ( 2
m m
( 7) ( 8) ( 9)
6 + +
m
h
h
I(j+ 1, [ f
( j ) ] + 1)
= I0 (
m
2 ) )
)
6
L 3)
( 16)
I(i, [ f ( i) ]) = I0 ( I(i+ 1, [ f I(i+ 1, [ f
Abstract: Con sidering f (x ) = m x+ b, 0≤m ≤1; conven tiona l line draw ing a lgo rithm s sam p le ( x, f ( x ) ) on the line, w here x m u st be an in teger, and restrict f (x ) to be an in teger acco rding to fam ou s DDA , B resenham and W u a lgo rithm . In th is p ap er , acco rd 2 ing to the genera tion of the line and the au tho r ana lyse the an tia lia sing techno logy , the p ropo se to si m u la te a sam p led po in t (x, f (x ) ) by the fou r p ixels a round it w here x and f (x ) a re no t necessa ry to be in tegers, and show tha t the effect of the in ten sities of the sam p led po in t can no t dep and on the num ber bu t the slop of the line, in the fact, it show s a better an tia lia sing effect. Key words: an tia lia sing; line draw ing; a lgo rithm
n- 1
I(i, [ f ( i) ]) =
n (n - 1)
2 倍, 如果在 s 1 线段中取样点为N , 每个点的光强
∑ I0 n ( 12k △x ) ( 12km △x 2h ) = I0 n ( n 2 k= 0
2 m △x +
n (n - 1)
2 6
△x 2
n (n - 1)
2
h △x 2nh +
上花费的代价是比较大的, 实用性受到限制. 1. 3 调节象素光强法 具体有扩展的B resenham 算法和使用不同卷积核的多种 滤波算法 [1 ] , 著名的W u 算法 [ 2 ] 是以 f (x ) 两侧的点 [ f ( x ) ] 和 [ f (x ) ] 为宽带, 根据其与 f (x ) 距离的反比例来分配实际光强 如下:
m
m
511
设 S j 中取样点数为 n, 其中线段 ( q1, q2 ) 取样点数为 r; 线段 (q2, q3) 样点数为 s; n= r+ s;
2 3 L 2 L ) 2 6 如 ca se1 与 ca se2 所述, 点的光强与直线上样点的数量无
m m
( 12)
I(j, [ f ( j ) ]) = I0 (
2
L2 -
6
L 3)
( 13)
I(j, [ f ( j ) ]) = I0 (L -
m
2 I0 (
L2 - L2 2 +
m
m
6
L 3) +
6
(1 - L 3) )
( 14)
Ij , [ f ( j ) ]+ 1 = I0 (
m
6
(1 - L 3) )
2 算法描述
2. 1 基本思想
光栅显示器中, 定义一个单元 u ( i, j) 是由 ( i, j) ( i, j+ 1) ( i + 1, j) ( i+ 1, j+ 1) 组成的一个方形网格, 设一点 P ( x, y ) 在 u ( i, j) 内, 且 x 和 y 不为整型 ( 如图 1 所示) xa = x - [ x ]; xb = [ x ] 2x; ya = y- [ y ]; yb = [ y ] 2y ( 1) 点 P (x, y ) 的光强可由与之相邻的四个象素的关系获得: ( 2) I([ x ], [ y ]) = I0 xbyb
n (n - 1) ( 2n - 1)
( △x ) 2m )
n →∞
则: I(i, [ f ( i) ]) = lim I(i, [ f ( i) ]) = I0 ( 其它公式证明同理. 2. 3 ca se2 光强的分配
1 m h 2 2 ) 2 6 2
图 1 样点 P 光强的分配 为 I, 那么在 s 2 线段中若也是N 个取样点, 则每点的光强则一 定小于 I, 因此预期光强 I0 必须使直线的长度与取样点数成正 比, 设直线 p 1 (x1, y1) , p 2 (x2, y2) , 即: p 1, p 2 2 ( 6) I0 = p 1, p 2 ∞ 分子表示 p 1, p 2 两点之间的长度, 而分母表示生成直线的取 样点数: m ax ( x22x1 , y22y1 ). 由于直线的对称性, 我们以斜率0≤m ≤1 为例, 来讨论本 算法, 设直线 l ( ( 0, 0) , (x, y ) ) , m = y x, 因此 x ≥y; { ( i, f ( i) ) i= 0, 1, …, x} 是直线上的系列点; 线段 l ( ( i, f ( i) ) , ( i+ 1, f ( i+ 1) ) 为一个线段单元 s i: 若 [ f ( i+ 1) ]= [ f ( i) ] 或 [ f ( i+ 1 ) ]= [ f ( i) ] 则 s i 在一个 单元格内; ca se1 若 [ f ( i+ 1) ]= [ f ( i ) + 1 ]; 则 s i 贯穿两个单元格; ca se2 2. 2 ca se1 光强的分配
( 10)
h
I( j + 1, [ f
( j ) ])
= I0 (
m
2
L ( 12 L ) 22
m
3
( 12 L ) 3)
= I0 (
1 2
3
2
)
( 11)
证明公式 ( 13) :
3 期
韩 丽 等: 一个快速有效的直线反走样算法 因 12c= Lm 所以 I( j , [ f ( j ) ]) = I0 (
图 3 取样点 P 光强由四个象素决定 直线段S j 为q1, q3, 它贯穿了两个单元格u (j, [ f ( j ) ]) 和 (u, [ f ( j ) ] ) ; 实际光强的获得由六个点来决定, 如图 3. q2 是直线在两个单元格的交点, 其中 y= [ f ( j ) ]
L = X (q2) - j; X (q2) 表示 q2 点的横坐标; c = f ( j) - [ f ( j ) ]
I(x, (x ) ] ) I 为预期光强, 而 I(x, y) 为实际获得光强.
[ f (x ) ])
ห้องสมุดไป่ตู้
= I ( f ( x ) 2[ f ( x ) ] ) ; I(x, [ f ( x ) ] ) = I ( f ( x ) 2[ f
本文在W u 算法的基础上, 提出了取样点 P ( x, y ) 的光强 由与之相邻的四个象素来决定, x 和 y 的值不必约束为整型, 并经过实践证明, 此种算法具有更强的反走样效果.
摘 要: 直线 f (x ) = m x+ b, 0≤m ≤1; 传统的生成算法是取样点 ( x, f ( x ) ) , 其中 x 为整型, 并将 f ( x ) 约束成整型, 其实现过程有 著名的DDA 、 B resenham 及W u 算法, 本文针对直线的生成, 分析了反走样技术, 提出了直线的反走样生成算法, 其取样点的光 强由与之相邻的四个象素决定, 且 x 和 f (x ) 不必约束为整型, 同时推导出点的光强与取样点数量无关而与直线的斜率有着直接 的关系, 并给出了具体的公式, 实践证明, 该算法具有更强的反走样效果. 关 键 词: 反走样; 直线生成; 算法 中图分类号: T P391. 4 文献标识码: A 文 章 编 号: 100021220 ( 2005) 0320509203
收稿日期: 2003206222 作者简介: 韩 丽, 女, 1973 年生, 硕士, 讲师, 研究方向为计算机图形学, 模式识别; 唐 棣, 女, 1960 年生, 教授, 从 事计算机图形学的科研与教学工作.
510 I([ x ], [ y ]) = I0 xbya I([ x ], [ y ]) = I0 xa yb I([ x ], [ y ]) = I0 xa ya
( i) ]) ( i) ])
6
m
2
m I(j+ 1, [ f ( j ) ]) = I0 (L 2 22 L 3 ) + I0 (L ( 12 L)+ 6 2 2 ( 12 L ) 22 m 2L ( 12 L) 2 m 3 ( 12 L ) 3)
( 17) ( 18)
= I0 (
h
3
2 -
第 26 卷 第 3 期 2005 年 3 月
小型微型计算机系统 M I N I- M ICRO SYST EM S
V o l126 N o. 3 M a r. 2005
一个快速有效的直线反走样算法
韩 丽, 唐 棣
( 辽宁师范大学 计算机与信息学院, 辽宁 大连 116029) E2 m ail: HL - DLL S@DL. CN
Rap id A lgor ithm for An tia l ia s ing of L ine D raw ing
HAN L i, TAN G D i
(L iaon ing N orm a l U n iversity Com p u ter and Im f orm a tion Colleg e, D a lian 116029, Ch ina )