直线的Bresenham算法
标签：oid 调整 spl art bsp 时间 大于 += 实验
在实验课上用自己的算法画直线被diss效率低
花了半天时间看了下Bresenham算法真????
总结一下其中的精妙之处
Bresebham直线生成算法的基本原理是，每次在最大位移方向上走一步，而另一个方向是走步还是不走步取决于误差项的判别。
声明k为斜率
在0≤k1,y1)，则下一个点在Pu(x1+1,y1+1)与Pd(x1+1,y1)中选一。
以M表示Pu与Pd的中点，即M(x1+1,y1+0.5)。设Q是理想直线与x=xi+1的交点；
显然，若M在Q的下方，则Pu(x1+1,y1+1)离直线较近，应取为下一个像素；否则应取Pd(x1+1,y1)。
理解并不难 主要在于实现
依据该算法的原理基本能够实现
窝先试着自己写了一会
如果要实现各个方向的二维直线绘制
需要考虑多种情况 写出来很不美观
教材上给出了更好的解决方案：
同样以0≤k
每次选取下个点时理想直线的y坐标都步进k个单位长度
累加值即为误差项di
当di大于0.5时选取Pu否则选取Pd并使di-1
令ei=di-0.5
则ei>0时选取Pu否则选取Pd
经过改进，算法的效率大幅提升
但其中在计算斜率与误差项时会用到小数和除法
并且下一步的选择只与误差项的符号有关
因此可以进一步改进：
可知ei的值由三种值组成：ei=-1/2(初始值)+(n个)y/x(步进值)-(m个)1(调整值)...
同乘2x即得2*x*ei=-x+(n个)2*y-(m个)2*x....
这样即可得到仅由整除构成的算法
以上仅为对0≤k
其余的情况类似
附一段杂乱无章的代码
1 void Line::Display()
2 {
3 // Window::InitColor();
4 point now_point = start;
5 glBegin(GL_POINTS);
6 if (step.x == 0 && step.y == 0) //No Step
7 return;
8 else if (step.x == 0) { // k is endless
9 do{
10 glVertex2i(now_point.x, now_point.y);
11 now_point.y += step.y / abs(step.y);
12 } while (now_point.y != end.y);
13 }
14 else if (step.y == 0) { //k is zero
15 do {
16 glVertex2i(now_point.x, now_point.y);
17 now_point.x += step.x / abs(step.x);
18 } while (now_point.x != end.x);
19 }
20 else if (abs(step.y / step.x) == 0) { // |k|
21 Type e = -2 * abs(step.x);
22 do {
23 glVertex2i(now_point.x, now_point.y);
24 e += 2 * abs(step.y);
25 now_point.x += step.x / abs(step.x);
26 if (e > 0) {
27 now_point.y += step.y / abs(step.y);
28 e -= 2 * abs(step.x);
29 }
30 } while (now_point.x != end.x);
31 }
32 else { // |k| >= 1
33 Type e = -2 * abs(step.y);
34 do {
35 glVertex2i(now_point.x, now_point.y);
36 e += 2 * abs(step.x);
37 now_point.y += step.y / abs(step.y);
38 if (e > 0) {
39 now_point.x += step.x / abs(step.x);
40 e -= 2 * abs(step.y);
41 }
42 } while (now_point.y != end.y);
43 }
44 glEnd();
45 glFlush();
46 }
本菜鸡的辣眼睛代码
直线的Bresenham算法
标签：oid 调整 spl art bsp 时间 大于 += 实验
原文地址：https://www.cnblogs.com/bugcreator/p/9665295.html
评论