本文出自svtter.github.io

本文可以随意转载，但是转载请保留本信息.

本身自己看这些东西没有很简单，但是李老师讲的的确深入浅出，使得同学们更加容易明白。

CSG树

画CSG树很简单，左边为原始元素，右边为变换。原始元素 + 变换 = T 变换, 叶子节点，都是画在图上，T节点也要画在图上。

T变换下的节点不需要重画。U为求并。

四叉树

如果满则为F[ull], 不满则为B[oundary], 空则为E[mpty].

四叉树主要是就是划分，按照象限划分即可，把多重颜色递归的进行划分即可。

中点bresenham算法

  • $ 0 <= k <= 1$

bresenham算法用于绘制直线，可以计算出直线的斜率。

从起点开始，代入x的值，然后求$(2*y_1+1)/2$值。

这个算法就是求两个点的中点，然后取距离中点近的那一个点来绘制直线

下一个点的求法是$(x_1+1,y_1+1), (x_1+1,y_1)$然后求中点，重复过程

以上是原理，下面是求解方法：

  1. 输入直线两个端点$P_0(X_0, Y_0), P_1(X_1,Y_1)$
  2. 首先计算$d = {\Delta}x – 2{\Delta}y$
  3. 绘制点(x,y) 如果$d<0$, 则(x,y)更新为(x+1,y+1)，d更新为$d+2{\Delta}x-2{\Delta}y$;
否则(x,y)更新为(x+1,y)，d更新为$d-2{\Delta}y$

  1. 直线没有画完，重复3。

  2. $ k > 1 $

对y的操作搞到x上即可

改进的有效边表算法

?

<th align="center">
  最大的y
</th>

<th align="center">
  $1/k$
</th>

<th align="center">
  next
</th>

<td>
</td>

<td>
</td>

<td>
</td>

首先构造边表，然后再构造有效边表

按照边数依次扫描

二维变换及二维观察，三维变换以及三维观察

无论是二维还是三维，补充一个1构成[x,y,z,1]矩阵，再对应乘变换矩阵即可。注意的要点是将变换点移动到坐标原点，然后进行

比例变换等。