[图形学] 基础图形绘制

本文转载自个人网站，后续更新将不会在此同步：

数值微分 DDA (Digital Differential Analyzer) 算法

给点两点 (x_1,y_1)、(x_2,y_2) ，考虑直线表达式： y=kx+b,k=\frac{y2-y1}{x2-x1}

显然我们可以直接模拟这个过程：从 (x_1,y_1) 走向 (x_2, y_2) ，每次 x+1 的时候 y+k 。

易发现，在斜率 k 较小的时候，所画直线比较合理，但是在 k 比较大的时候，会出现下图左侧这样割裂的问题：

于是，我们在 k 较大的时候，交换表达式中的 x、y ，这样就可以让 k 变小。

假设 k \in [0,1] ，在绘制一条直线的时候，我们考虑每次将 x+1 ，那么对于一个点 (x,y) ，理想的下一个点应该是 (x+1,y+k),k=\frac{y_2-y_1}{x_2-x_1} 。

但我们栅格化后，绘制的下一个点是 (x+1,y) 或 (x+1,y+1) ，于是考虑应该选择哪个点。

我们令 d 表示从 y 到理想位置的误差，显然有 d\in[0,1) ：

显然，当 d\le0.5 时，我们选择 (x+1,y) ；当 d\gt0.5 时，我们选择 (x+1,y+1) 。

首先：考虑怎么求这个 d，显然设 d 的初值为 0；每次 x+1 时候， d+k,k=\frac{\Delta y}{\Delta x} ；若 d\gt0.5 ，y 变成了 y+1，相对的也要 d-1 ，保证其相对性。

现在有： x_{i+1} = x_{i} + 1\\ y_{i+1} = \begin{cases} y_{i} & \text{if $d \leq 0.5$} \\ y_{i}+1 & \text{if $d \gt 0.5$} \end{cases}\\ d_0=0\\ d_{i+1}=d_i+\frac{\Delta y}{\Delta x}\\ d=d-1 \:\:\: \text{if $d \gt 0.5$}

我们考虑优化一下这个式子，去掉精度处理：

这样就可以实现 k \in [0,1] 的直线的绘制。

最后，我们扩展一下，处理一下其它情况即可。