03-基本图形生成算法

基本图形生成算法

直线

DDA数值微分法

中点Bresenham算法

Bresenham算法

圆

八分法画圆

由于圆的对称性，只要画出圆的八分之一即可

中点Bresenham画圆

椭圆的特征

椭圆是四分象限中对称的，需要进一步对一象限内分为上(-1<=k<=0)下(-1<=1/k<=0)两部分，即二分量相等的法向量

多边形

多边形的表示方法：顶点表示（顶点坐标表示边），点阵表示（内部像素表示形）

x扫描线的特点

判定顶点交点取舍问题：共享顶点的另外两个端点的y值，大于交点的个数决定0，1，2

改进的有效边表算法

• NET（新边表）
  • 一个纵向的链表，长度为最大扫描线数，横向指向吊桶链表（只有顶点交点指向，若包括全部边后不再向后循环）
  • 吊桶：线段链表(当前==线段==的y最小值端的x值，当前==线段==的最大y值，x的增量即斜率倒数，指向下一条==边==的指针）
  • 水平线无需管
• 某扫描线的ATE表（活性边表）：（当前==交点==的x值，该条边的顶点y最大值，x的增量即斜率倒数，指向下一个==点==的指针）

区域填充

边界填充算法

用户勾划出轮廓后，填充颜色

泛填充算法

给区域重新着色

内外测试

奇偶规则：做射线，与多边形交点是奇数则是内部，否则是外部

非零环绕数规则：做射线，多边形边为方向矢量，穿过正向向量环绕数+1,反之-1，最后环绕数0在外部，否则在外部

字符存储

点阵字符：每个字符由点阵位图表示，存储空间大，缩放失真

矢量字符：记录笔画信息，需要时间进行笔画扫描转换

反走样

走样：离散量表示连续量引起的失真

非加权区域采样方法：根据物体覆盖像素的覆盖率，来给像素填充不同亮度的颜色

加权区域采样方法：将一个像素分隔成为九宫格，每个宫格的权值不同，权值如此$\left[ \begin{matrix} 1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1 \end{matrix} \right]$，根据覆盖权值之和来给像素填充不同颜色