光栅化 (Rasterization)

上一篇文章讨论了如何在多边形的某一点上分配光强度值，这里主要讨论如何为多边形确定实际的像素，即在栅格屏幕上的对应位置，这个过程称为光栅化(Rasterization)或者扫描转换 (Scan conversion)。

1 光栅化边

主要方法：DDA算法

起始点（xs，ys），终点（xe，ye）

Δy = 1，Δx 用 m 表示

∵ Δy/x= (ye-ys)/ (xe-xs), Δy = 1,

∴ m = (xe-xs)/(ye-ys)

浮点数伪代码：

整数伪代码：

这里 x = xi, xf > 0 时，一开始 xf = -0.5，四舍五入，如果 xf > 0,则说明 mf > 0.5，所以近1。

PS: div是整除，mod是取余，ye-ys为常数。

这里存在的一个问题是将3*3的正方形画成4*4，解决的办法是去掉第一个顶点或者去掉最后一个，这个根据个人习惯。

2 光栅化多边形

光栅化多边形可以用链表数组 a[n] 来实现，a[i] 代表 yi 所包含的所有的 x 值的链表（linked list）。链表的元素结构是 A(value， pointer)，pointer指向下一个元素。

如图所示，竖条的每一个小格代表一个 a[i]，y的值是无序的，扫描中，每一条扫描线每产生一对 (x,y)，找到对应y值，如果不存在这个y，则加入一个链表，即 a[n+1]，然后 x 根据升序插入，因为是链表，所以可以插入。在得出多边形在屏幕中相应位置时，也要计算改像素点的光强并存储。

PS: a[0] 出现两个相同的 x 值4，是因为它处于转折点。

实现光栅后，接下来要做的事情是多边形填充，可参见转载的文章 多边形区域填充算法－－扫描线填充算法。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168028.html原文链接：https://javaforall.cn