本文出自svtter.com 本文可以随意转载,但是转载请保留本信息. 本身自己看这些东西没有很简单,但是李老师讲的的确深入浅出,使得同学们更加容易明白。 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> 首先构造边表,然后再构造有效边表……

阅读全文