Attributes of Output Primitives Lectured by Hua Yan

Contents 图元属性参数概念 颜色和灰度(Color and gray scale) 直线的属性Line attributes 曲线的属性Curve attributes 字符属性 填充区属性及填充算法(Area-Fill attributes) 反走样(Antialiasing) Q&A

4.1 属性参数 Def. 任何影响图元显示方法的参数 属性选择设计 扩展每个输出图元函数的参数列表 维护一张系统当前属性值表，并且软件包提供相应的函数设置当前值 OpenGL的所有图元使用当前属性值表中的属性显示 Def. Any parameter that affects the way a primitive is to be displayed. Such as size, color, depth information, visibility etc. Attribute options design Extend the parameter list associated with each output primitive function Maintain a system list of current attribute values

4.2 颜色和灰度 颜色信息存储方式 直接存储 Color Lookup Tables颜色查找表 灰度的概念 OpenGL颜色函数(P.143-147)

直接存储 Idea: 帧缓冲区像素信息直接控制RGB三枪强度（直接存储策略） 如何增大系统支持色彩数？

Color Lookup Tables Idea：存储在颜色查找表中的信息控制RGB三枪 如何增大系统支持色彩数？

直接存储 Advantages Disadvantages 特别灵活 – 可同时使用颜色范围的任一颜色 硬件简单（仅仅在概念上） 帧缓冲区存储容量需求大 视频操作速度慢（例如24位色光栅系统，改变一个像素需要操作3个字节） Advantages Extremely flexible - we may simultaneously use any colors required from the range available Simple hardware (in concept only!) Disadvantages The large amount of memory required for the frame buffer Slower video operations. Changing a single pixel requires three bytes to be altered.

Color Lookup Tables Advantages 使用彩色表可提供合理的同时显示的颜色数量，而无需大容量帧缓冲器。 256或512种不同颜色足以显示单个图像。 表项可随时改变，容易试验在设计、场景或图形中使用不同的颜色组合，而无需改变对图形数据结构的属性设置。 视频操作速度快，因为每个像素在帧缓冲区中占有更少的数据位。 有些图形系统提供两种能力，方便用户选择 Advantages Lower memory size. Faster video operations since less memory is handled for each pixel. Disadvantages Requirement for a high speed RAM-DAC (lookup table). Limited number of colors available simultaneously.

Color Lookup Tables Disadvantages 需要高速 RAM-DAC 能同时使用颜色数有限 Advantages Lower memory size. Faster video operations since less memory is handled for each pixel. Disadvantages Requirement for a high speed RAM-DAC (lookup table). Limited number of colors available simultaneously.

灰度的概念 Green Yellow Cyan W Black Red Megenta Blue 当RGB函数中指定相同的红、绿、蓝分量时，产生的色彩是某种程度的灰色。 Cyan Megenta Yellow W Black Green Red Blue 对于无彩色能力的显示器，颜色功能在应用程序中可用于设置显示元素的灰度等级。使用从0到1范围内的数值来指定灰度级别，而后被转换成适当的二进制存储在光栅中。 如果每个像素有3位，则可以实现8个灰度等级，而如果每个像素有8位就可给出256种灰度效果。

4.3 Line Attributes线属性 Line Type线型 How to? 绘制像素段 Pixel mask像素掩码 eg. 1111000 Problem 根据直线斜率调整实心段和空白段的像素数目

display adjacent parallel lines显示相邻平行线段 4.3 Line Attributes Line Width How to? display adjacent parallel lines显示相邻平行线段 |m|<1 (x,y) & (x,y+1)

|m|>1 (x,y) & (x+1,y)& (x-1,y)&(x-2,y) Other problems: line cap & line join P110~111 |m|>1 (x,y) & (x+1,y)& (x-1,y)&(x-2,y)

4.3 Line Attributes Pen and Brush Options Pixel Mask Shape形状 Size尺寸 Pattern 样式 Pixel Mask

4.3 Line Attributes Line Color

4.4 Curve Attributes曲线属性 Curve type Pixel masks eg.11100 根据曲线斜率设置像素掩码的实心段和空白段像素数目

水平(|m|>1)或垂直 (|m|<1)像素段 4.4 Curve Attributes Curve width 水平(|m|>1)或垂直 (|m|<1)像素段 Horizontal(|m|>1)or vertical (|m|<1)pixel spans

4.4 Curve Attributes Curve width 填充平行曲线路径之间的区域 Eg. R=16 17 14

Eg. Rectangular pen 3x3 4.4 Curve Attributes Pen & Brush options Replicate a pen shape along the curve path.

4.5 Character Attributes 字体 宋体 仿宋体 楷体 黑体 隶书 字高 宋体 宋体 宋体 宋体 宋体 字宽 字倾斜角 倾斜 倾斜 对齐 (左对齐、中心对齐、右对齐) 字色 红色、绿色、蓝色 ……

4.6 Area-Fill Attributes Hollow Solid Patterned

区域填充算法 简单边界，例如多边形，圆，椭圆以及其他简单曲线，通过扫描线与边界交点确定填充区域。 Simple boundary polygon, circle , ellipse and other simple curves Complex boundary 复杂边界，从内部给定位置开始填充，递归填充直至边界。

洪泛填充算法 扫描线填充算法 扫描线多边形填充算法 递归填充算法 边界填充算法 Scan - Line Polygon Fill Algorithm Inside – Outside Tests Boundary - Fill Algorithm Flood - Fill Algorithm

4.6.1 扫描线多边形填充算法 Idea(P.159) 算法技巧 数据结构 算法描述 程序实现(第二版P.87) 如何处理奇数个交点？ 如何处理水平边？ 如何计算交点坐标？ 数据结构 算法描述 程序实现(第二版P.87)

Idea x-扫描线算法填充多边形 x y 2 1 3 4 5 6 7 8 9 11 10 12 扫描线自底向上扫描，计算扫描线与多边形边界的交点确定填充区间，再用要求的颜色显示这些区间的像素，即完成填充工作。一条扫描线的填充过程分为求交、排序、配对和填色四个步骤。 对于一条扫描线填充过程可以分为四个步骤： （1）求交（2）排序 （3）配对（4）填色

算法技巧 – 交点数 扫描线y1 扫描线y2 将较低的一条边缩短，保证对通过公共顶点的扫描线仅产生一个交点 单调减 单调增

Example 扫描线y1 扫描线y2 扫描线y3 A B C D E F G H I 对于横越多边形的每条扫描线，区域填充算法确定扫描线与多边形边的交点位置。而后，将这些点自左至右存储，并给每对交点间对应的帧缓冲器位置设置指定的填充颜色。 由于有时交点数目并不为偶数个。因此，有些多边形顶点处的扫描线交点需要专门处理。在这些位置上，扫描线通过一个顶点与多边形的两条边相交，在这根扫描线的交点表上要增加两个点。关键要保证交点数目成偶数

多边形顶点的调整---单调递增情况 扫描线y2 将较低的一条边缩短，保证对通过公共顶点的扫描线仅产生一个交点

多边形顶点的调整---单调递减情况 扫描线y3 将较低的一条边缩短，保证对通过公共顶点的扫描线仅产生一个交点

多边形顶点调整后 扫描线y1 扫描线y2 扫描线y3 A B C D E F G H I H' C'

算法技巧 – 水平边 不计算水平边和扫描线的交点

Xi+1 Yi+1 xi yi 算法技巧 – 交点坐标计算 交点坐标计算 Yi+1 = Yi + 1 Xi+1 = xi + 1/m m=dy/dx Yi+1 yi Xi+1 xi Intersection calculating

数据结构 数据结构 输入参数 有序边表sorted edge table 活化边表active edge table 顶点数以及顶点坐标 B 算法输入参数为：

有序边表 有序边表构建过程 AE AB CD DE CB 1 YA YD YC Window height AE AB CD DE CB 有序边表 有序边表构建过程 按顶点输入顺序依次形成边，存储到每条边最小Y值所对应的扫描线位置(水平边除外)；相同最小y值的边按较低顶点x值升序排列 Sorted edge table construction procedure:

有序边表 typedef struct tEdge { int yUpper; float xIntersect; Window height 有序边表 CB typedef struct tEdge { int yUpper; float xIntersect; float dxPerScan; struct tEdge * next; }Edge; YC CD DE YD AE AB YA 最大Y值 1/m 较低顶点X值 1

活化边表 把与当前扫描线相交的边称为活化边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,形成活化边表。 CD DE AE AB 扫描线Y 活化边表的操作包括插入边、删除边，更新边信息。 CD DE AE AB

算法描述 1)输入多边形顶点数及顶点坐标； 2)建立有序边表； 3)根据当前扫描值建立活化边表； 4)求出扫描线与多边形边界交点，交点配对、填充； 5)更新活化边表并重新排序； 6)进入下一条扫描线，重复步骤3，直至扫描线值为窗口高度。

4.6.2 边界填充算法 IDEA –填充区域边界以一种颜色指定；从区域的一个内部点开始，由内至外绘制直到边界。 适用于单色边界

填充方式 4-连通 8-连通 问题 4连通有时不能完整填充(P.164)

4-连通算法描述 算法输入：指定内部点坐标，填充色，边界色 算法步骤 指定内部点入栈；当栈非空时重复执行如下操作： (1)获得当前栈顶像素的颜色； (2)若像素颜色既不是边界色也不是填充色，则置成填充色；依次将右、左、上、下四邻接点压栈； (3)若当前栈顶像素已是边界点或已填充，则弹栈。

程序实现 void boundaryFill4(int x, int y, int fill, int boundary) { int current = getPixel(x, y); if ((current != boundary) && (current != fill)) { setPixel(x, y, fill); boundaryFill4(x+1, y, fill, boundary); boundaryFill4(x, y+1, fill, boundary); boundaryFill4(x-1, y, fill, boundary); boundaryFill4(x, y-1, fill, boundary); }

特点 堆栈空间需求量非常大 算法改进 沿扫描线填充水平像素区段 仅仅将水平像素区段的起始位置放进堆栈 Example (P.166)

4.6.3 洪泛填充算法 IDEA – 填充区域以一种颜色指定；从指定的内部点 (x,y) 开始，将填充色赋给颜色为给定内部色的邻接像素。 适用于多色边界

程序实现 void floodFill4(int x, int y, int fill, int old) { if (getpixel(x, y) == old) { setpixel(x, y, fill); floodFill(x+1, y, fill, old); floodFill(x, y+1, fill, old); floodFill(x-1, y, fill, old); floodFill(x, y-1, fill, old); }

4.7 Antialiasing反走样 Concept of Aliasing走样概念 Antialiasing Tech.反走样技术

4.7.1 Concept of Aliasing Problem

4.7.1 Concept of Aliasing Def. The distortion of information due to low-frequency sampling (undersampling) is called aliasing. 图形数字化过程中，由于低频采样而造成的图形畸变->走样 Simple method Display objects at higher resolution提高分辨率

讲解清楚走样产生的原因 图中显示的不充分取样的效果。为了避免 这种周期型对象中丢失信息，必须把取样频率至少设置为出现在对象中的最高频率的两倍，这个频率称为Nyquist取样频率(或Nyquist取样率)fs： fs=2fmax 另一种解释是，取样区间不应超过循环区间(Nyquist取样区间)的一半。对于x区间取样，Nyquist取样区间Δxs为 Δxs=Δxcycle/2

Sampling theorem Nyquist theorem: the sampling frequency should be at least 2 times the max frequency in the signal f=1 rpm 1 sample per revolution A little more than 1 sample/revolution 2 samples per revolution >2 samples per revolution

通过修改沿图元边界的像素的亮度来平滑边界减小锯齿现象 4.7.2 Antialiasing Tech. IDEA 通过修改沿图元边界的像素的亮度来平滑边界减小锯齿现象 Hardware requirement硬件需求 Types Supersampling 过取样技术 区域取样技术 像素移相技术 … Hardware requirements:The system is capable of displaying more than two intensity levels. Supersampling(postfiltering):This technique of sampling object characteristics at a high resolution and displaying the results at a lower resolution. Area sampling (prefiltering) is a way which determine pixel intensity by calculating the areas of overlap of each pixel with the objects to be displayed. Raster objects can also be antialiased by shifting the display location of pixel areas. This tech, called pixel phasing, is applied by “micropositioning” the electron beam in relation to object geometry.

Supersampling Def. 在高分辨率下对对象取样而在较低分辨率下显示结果的技术。 把屏幕看成比实际所具有的更细的网格来增加取样率 沿这种更细网格使用取样点来确定每个屏幕像素的合适亮度等级 Hardware requirements:The system is capable of displaying more than two intensity levels. Supersampling(postfiltering):This technique of sampling object characteristics at a high resolution and displaying the results at a lower resolution. Area sampling (prefiltering) is a way which determine pixel intensity by calculating the areas of overlap of each pixel with the objects to be displayed. Raster objects can also be antialiased by shifting the display location of pixel areas. This tech, called pixel phasing, is applied by “micropositioning” the electron beam in relation to object geometry.

区域取样技术 像素移相技术 Def. 通过计算待显示的对象在每个像素上的覆盖区域从而确定像素亮度的技术。 像素覆盖区域通过确定对象边界与单个像素边界的相交处而得到 像素移相技术 Def. 通过移动像素区域的显示位置实现反走样的技术。 通过与对象几何形状相关的电子束的微定位而作用

A. 直线段过取样 IDEA 每个像素分为若干子像素； 统计沿直线路径的子像素数目； 每个像素的亮度等级正比于子像素数目 We can divide each pixel into a number of subpixels and count the number of subpixels that are along the line path. The intensity level for each pixel is then set to a value that is proportional to this subpixel count.

20 21 22 10 11 12 Level 3 (10,20) Level 2 (11,21) (12,21) Level 1 (11,20) (12,22)

Supersampling Finite-width line 22 21 Advantages:总的线亮度分布在更多的像素上 总的线亮度分布在更多的像素上 在图的过取样例子中，我们考虑了有限尺寸的像素区域，但我们把线处理成具有零宽度的数学实体。实际上，显示的线具有大约与像素等宽的宽度。如果考虑直线的宽度，我们可设置象素的亮度正比于表示线段的多边形内部的子象素个数。如图 注：一个子象素的左下角坐标在多边形内部，则认为该子象素在多边形内部。 另一个优点 总的线亮度分布在更多的像素上。一个像素的效果可以来自其相邻像素。 20 10 11 12

IDEA B. Pixel-weighting Masks加权像素掩码 赋给接近于像素区域中心的子像素更大的权值 1 2 4 give more weight to subpixels near the center of a pixel area Relative weights for a grid of 3 by 3 subpixels

IDEA C. 直线段区域采样 设置每个像素亮度正比于像素与有限宽度直线的重叠区域 set each pixel intensity proportional to the area of overlap of the pixel with the finite-width line 如果子像素足够小，则子像素的总数近似等于覆盖区域。

D. Filtering Tech 过滤技术是一种更精确的反走样方法。 类似于应用加权像素掩模，用一个连续的加权曲面(或过滤函数)覆盖像素，而不是一个离散的象素掩模。 用正方形、圆锥和高斯函数作为过滤函数 应用过滤函数的方法是将像素曲面集成来得到加权的平均亮度 为减少计算，常用查找表来求整数值。

可以用正方形、圆锥和高斯函数作为过滤函数。应用过滤函数的方法类似于应用加权掩模，但现在是将像素曲面集成来得到加权的平均亮度。为减少计算，常用查找表来求整数值。

E. Pixel Phasing像素移相 Basic idea micropositioning the electron beam to more nearly approximate positions. 微定位电子束到与实际位置更接近的近似位置 The electron beam is typically shifted by ¼, ½, or ¾ of a pixel diameter to plot points closer to the true path of a line or object edge. 将电子束移动象素点直径的1/4，1/2或3/4，使描绘的点更接近直线的真实路径。

原因：斜线单位长度的亮度低于水平线和垂直线 调整方式： F. 直线亮度差的校正 现象：光栅系统中，斜线比水平和垂直线暗 原因：斜线单位长度的亮度低于水平线和垂直线 调整方式： Compensating for the Line Intensity Differences Min brightness Max brightness Min brightness