本文出自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)$然后求中点，重复过程
以上是原理，下面是求解方法：
- 输入直线两个端点$P_0(X_0, Y_0), P_1(X_1,Y_1)$
- 首先计算$d = {\Delta}x – 2{\Delta}y$
- 绘制点(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$
-
直线没有画完，重复3。
-
$ 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]矩阵，再对应乘变换矩阵即可。注意的要点是将变换点移动到坐标原点，然后进行
比例变换等。