本文出自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> 首先构造边表，然后再构造有效边表……

Continue reading