# Bresenham算法

`line_bresenham(startX, startY, endX, endY)`
`{`
`    deltaX = endX - startX;`
`    deltaY = endY - startY;`
`    k = deltaY / deltaX;`
` `
`    <span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)`
`    {`
`        <span style="color: #0000ff">if</span> (满足一定条件)`
`        {`
`            ++y;`
`        }`
`        drawPixel(x, y);`
`    }`
`}`

`<span style="color: #008000">// 算法1: 用斜率判断</span>`
`<span style="color: #0000ff">void</span> line_bresenham_k(startX, startY, endX, endY)`
`{`
`    deltaX = endX - startX;`
`    deltaY = endY - startY;`
`    k = deltaY / deltaX;`
` `
`    <span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)`
`    {`
`        <span style="color: #0000ff">if</span> (x - startX != 0)`
`        {`
`            <span style="color: #008000">// 计算当前斜率</span>`
`            currentK = (y - startY) / (x - startX);`
` `
`            <span style="color: #008000">// 如果当前斜率 &lt; k, 则增加y坐标</span>`
`            <span style="color: #0000ff">if</span> (currentK &lt; k)`
`            {`
`                ++y`
`            }`
`        }`
`        drawPixel(x, y);`
`    }`
`}`
` `
`<span style="color: #008000">// 算法2: 用距离判断. 计算直线与光栅线交点y坐标我们需要用到</span>`
`<span style="color: #008000">// 直线方程 y = k (x - startX) + startY</span>`
`line_bresenham_dist(startX, startY, endX, endY)`
`{`
`    deltaX = endX - startX;`
`    deltaY = endY - startY;`
`    k = deltaY / deltaX;`
` `
`    <span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)`
`    {`
`        <span style="color: #008000">// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离</span>`
`        ptY = k * (x - startX) + startY;`
`        dist = ptY - y;`
` `
`        <span style="color: #008000">// 如果距离 &gt; 0.5或者 &lt; -0.5, 说明我们需要增加y以</span>`
`        <span style="color: #008000">// 将距离的绝对值控制在0.5之类</span>`
`        <span style="color: #0000ff">if</span> (dist &gt; 0.5 || dist &lt; -0.5)`
`        {`
`            ++y;`
`        }`
`        drawPixel(x, y);`
`    }`
`}`

`<span style="color: #008000">// 算法3: 在算法2的基础上消灭浮点数!</span>`
`line_bresenham_dist(startX, startY, endX, endY)`
`{`
`    deltaX = endX - startX;`
`    deltaY = endY - startY;`
` `
`    <span style="color: #0000ff">for</span> (x = startX, y = startY; x &lt;= endX; ++x)`
`    {`
`        <span style="color: #008000">// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离</span>`
`        ptY1 = deltaY * (x - startX) + startY * deltaX;`
`        dist1 = ptY1 - y * deltaX;`
`        dist1 = dist1 &lt;&lt; 1; <span style="color: #008000">// dist1 = dist1 * 2</span>`
` `
`        <span style="color: #008000">// 如果距离 &gt; 0.5或者 &lt; -0.5, 说明我们需要增加y以</span>`
`        <span style="color: #008000">// 将距离的绝对值控制在0.5之类</span>`
`        <span style="color: #0000ff">if</span> (dist1 &gt; deltaX || dist &lt; -deltaX)`
`        {`
`            ++y;`
`        }`
`        drawPixel(x, y);`
`    }`
`}`

1) d2 = d1 + k –  (y2 – y1)
2) 当d1 + k > 0.5时y2 = y1 + 1, 否则y2 = y1

3) e2 =  e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
4) 当e1 + 2 * deltaY > deltaX时y2 = y1 + 1, 否则y2 = y1

`<span style="color: #008000">// 算法4: 在算法2, 3的基础上利用递推消灭乘法和浮点数!</span>`
`line_bresenham(startX, startY, endX, endY)`
`{`
`    deltaX = endX - startX;`
`    deltaY = endY - startY;`
`    e = 0;`
`    deltaX2 = deltaX &lt;&lt; 1;`
`    deltaY2 = deltaY &lt;&lt; 1;`
` `
`    drawPixel(startX, startY);`
` `
`    <span style="color: #0000ff">for</span> (x = startX + 1, y = startY; x &lt;= endX; ++x)`
`    {`
`        <span style="color: #008000">// 关系式3) e2 =  e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)</span>`
`        <span style="color: #008000">// 关系式4) 当e2 + 2 * deltaY &gt; deltaX时y2 = y1 + 1, 否则y2 = y1</span>`
`        e += deltaY2;`
`        <span style="color: #0000ff">if</span> (e &gt; deltaX)`
`        {`
`            e -= deltaX2;`
`            ++y;`
`        }`
`        drawPixel(x, y);`
`    }`
`}`

dist1 = 2 * deltaY * (x – startX) + 2 * startY * deltaX – 2 * y * deltaX, 则
e2 – e1
= 2 * deltaY * (x – startX) + 2 * startY * deltaX – 2 * y2 * deltaX – [2 * deltaY * (x – 1 – startX) + 2 * startY * deltaX – 2 * y1 * deltaX ]
=  – 2 * y2 * deltaX + 2 * deltaY + 2 * y1 * deltaX
= 2 * deltaY – 2 * deltaX * (y2 – y1)

1) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
2) –deltaX <  e1 < deltaX
3) –deltaX < e2 < deltaX
4)  y2 – y1 = 0 或者 1

2 * deltaY – deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX

2 * deltaY – deltaX – 2 * deltaX * (y2 – y1) < e2 < deltaX– 2 * deltaX * (y2 – y1)

deltaX – 2 * deltaX * (y2 – y1) < e2 < 2 * deltaY + deltaX – 2 * deltaX * (y2 – y1)

# Makefile 自动生成头文件的依赖关系

How to build?

`all:    freakout.exe`
` `
`freakout.exe: freakout.o blackbox.o`
`    g++ freakout.o blackbox.o -o stupid.exe -L D:gamedevdx81sdkDXFDXSDKlib -lddraw -mwindows`
` `
`freakout.o: freakout.cpp <strong><span style="color: #ff0000;">blackbox.h</span></strong>`
`    g++ -c freakout.cpp -o freakout.o -I D:gamedevdx81sdkDXFDXSDKinclude`
` `
`blackbox.o: blackbox.cpp <strong><span style="color: #ff0000;">blackbox.h</span></strong>`
`    g++ -c blackbox.cpp -o blackbox.o -I D:gamedevdx81sdkDXFDXSDKinclude`

Problem?

Solution – 自动生成依赖关系

Google一下”makefile 头文件 依赖”会发现大多数编译器都提供了一个选项生成.o目标文件所依赖的文件列表. 比如GCC的”-MM”选项. 运行GCC –MM freakout.cpp blackbox.cpp <库文件和头文件选项>得到输出:

`freakout.o: freakout.cpp blackbox.h D:/gamedev/dx81sdk/DXF/DXSDK/include/ddraw.h`
`blackbox.o: blackbox.cpp blackbox.h D:/gamedev/dx81sdk/DXF/DXSDK/include/ddraw.h`

`CPP = g++`
`OBJ = freakout.o blackbox.o`
`LIB = -L D:gamedevdx81sdkDXFDXSDKlib -mwindows -l ddraw`
`INC = -I D:gamedevdx81sdkDXFDXSDKinclude`
` `
`all: freakout.exe`
` `
`freakout.exe: \${OBJ}`
`    \${CPP} \${OBJ} -o freakout.exe \${LIB}`
` `
`<span style="color: #ff0000;"><strong>include depend</strong></span>`
` `
`# note the symbols: \$&lt; and '[email protected]`
`%.o: %.cpp`
`    \${CPP} -c \$&lt; -o [email protected] \${INC}`
` `
`# generate depend file`
`<span style="color: #ff0000;"><strong>depend:</strong></span>`
`    <span style="color: #ff0000;"><strong>\${CPP} -MM \${OBJ:.o=.cpp} \${INC} &gt; depend</strong></span>`

1) 在需要更新依赖关系的时候 (比如在某个文件里多加了一条#include指令) 运行make depend.

2) 运行make.

Makefile Auto Dependency – 只运行一次make

`# freakout.d`
`freakout.o <strong><span style="color: #ff0000;">freakout.d</span></strong>: freakout.cpp D:/gamedev/dx81sdk/DXF/DXSDK/include/ddraw.h blackbox.h`
` `
`# blackbox.d`
`blackbox.o <strong><span style="color: #ff0000;">blackbox.d</span></strong>: blackbox.cpp D:/gamedev/dx81sdk/DXF/DXSDK/include/ddraw.h blackbox.h`

`CPP = g++`
`OBJ = freakout.o blackbox.o`
`LIB = -L D:gamedevdx81sdkDXFDXSDKlib -mwindows -l ddraw`
`INC = -I D:gamedevdx81sdkDXFDXSDKinclude`
` `
`all: freakout.exe`
` `
`freakout.exe: \${OBJ}`
`    \${CPP} \${OBJ} -o freakout.exe \${LIB}`
` `
`<span style="color: #ff0000;"><strong>include \${OBJ:.o=.d}</strong></span>`
` `
`%.o: %.cpp`
`    \${CPP} -c \$&lt; -o [email protected] \${INC}`
` `
`<strong><span style="color: #ff0000;">%.d: %.cpp</span></strong>`
`    rm -f [email protected] &amp; `
`    \${CPP} -MM \$&lt; \${INC} &gt; [email protected]\$\$ &amp; `
`    insertdfile.exe \$&lt; [email protected]\$\$ &gt; [email protected] &amp; `
`    rm -f [email protected]\$\$`

P.S. insertdfile.exe是我自己写的一个小程序, 用来把.d文件加入到第二行生成的依赖关系中, 例如把”blackbox.o: blackbox.cpp blackbox.h”转换为”blackbox.o blackbox.d: blackbox.cpp blackbox.h”. 我为什么要自己写一个字符串替换的程序? 因为我没有装sed工具…如果有, 当然用官方推荐的办法, 把第三行换成神奇的符咒: sed ‘s,(\$*).o[ :]*,1.o [email protected] : ,g’ < [email protected]\$\$ > [email protected] .

1) make尝试去包含blackbox.d和freakout.d文件, 没有发现, 所以检查有没有规则可以生成这些.d文件, 发现我们%.d: %.cpp的这条规则, 于是运行这条规则生成所有的.d文件并且包含进来.
2) 按照正常规则生成.o文件, 然后生成.exe.

1) make把第一个目标all加入到需要生成的目标列表中.
2) make包含blackbox.d和freakout.d文件. 注意在这个过程中这两个.d文件也会被加入到make的需要生成的目标列表中 – 因为可能有规则能更新这两个.d文件.
3) 根据blackbox.d和freakout.d包含的规则: .d文件 (已经被入到了make的需要生成目标列表中) 需要被更新, 于是相应地运行%.d: %.cpp规则更新.d文件： 新加入的 stupid.h文件被加入到两个.d文件的依赖项中.
4) make发现包含的两个.d文件在第2)步中都被更新, 于是重新包含这两个.d文件.
5) make根据在第2)步生成在第3)步被包含进来的规则, 发现stupid.h的日期比两个.o文件的日期都要新, 于是重新生成.o文件.
6) 根据规则生成.exe.