不調用畫圖 API，用C 或 C++ 如何實現畫一條線？

01-13

如果能不調用任何api就更好!!!!
思路:
圖形學走筆演算法
彙編顯卡介面顯示器數據通路

信號傳遞

直線在這裡實際上是指線段，知道了線段的兩個端點位置，要把這個線段顯示在光柵化顯示器上，就是直線光柵化的目標。由於圖形學所有的渲染都是依靠無數線段的渲染來完成的，所以直線的光柵化演算法的效率顯得尤為重要。

從這裡開始

在數學的觀點來看線段是筆直的，沒有寬度的。但是在顯示器上由於像素呈現四邊形，理論上無法完全模擬線段的本來面目，所以只能用近似的方法來讓它「看起來」是一條線段，這就是直線的光柵化。

假設線段的兩個端點為 $(x_{0},y_{0})(x_{1},y_{1})$ 假設 $x_{0}leq x_{1}$

於是直線方程可以用斜截式 $y=kx+b$ (其中k b已知)表示,從而對x進行遍歷，根據方程得到實數點 $(x,y)$ 再四捨五入得到在光柵顯示器的顯示坐標 $(round(x),round(y))$

這樣的演算法是可以實現直線的光柵化的，而問題在於效率並不高。在遍歷x計算y的時候使用的方程有一個乘法的存在(k*x)，而這會大大影響渲染效率。於是一場消滅乘法的智慧盛宴開始了。

數值微分DDA(Digital Differential Analyzer)演算法

數值微分演算法引進了圖形學中很重要的增量思想。

考慮直線 $y=kx+b$ 假設我們遍歷橫坐標x來在屏幕上畫這條直線，也就是說我們每次向右前進一個像素，考慮在這個x坐標下的y是什麼。

假設我們考慮完了點 $(x_{i},y_{i})$ 這時我們看到 $(x_{i+1},y_{i+1})$ 中有:

$y_{i+1} = k*x_{i+1}+b = k*(x_{i}+1)+b=k*x_{i}+b+k=y_{i}+k$

也就是說，每次的縱坐標都是在前一個縱坐標的基礎上加上斜率k (其實學過解析幾何的話很容易想到)。這樣我們就可以不斷遞推，來將本來的乘法消滅了。

用二維數組模擬屏幕像素用DDA演算法顯示的一條線段

代碼:

#include & #include & using namespace std; bool pic[50][50]; void DrawLine(int x0,int y0,int x1,int y1) { double k = (y1-y0)*1.0/(x1-x0); double y = y0; for(auto x = x0 ; x &<= x1 ; ++ x) { pic[(int)round(y)][x] = true; y += k; } } void ShowPic() { for(auto i = 49 ; i &>= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout &<&< "x"; else cout &<&< "o"; } cout &<&< endl; } } int main() { DrawLine(2,2,48,30); ShowPic(); return 0; }

但是顯然我們需要更加完善的演算法，現在有兩個問題：

每次遞增x的方式顯然不適合斜率過大的直線。斜率過大會導致屏幕上顯示的點少而且稀疏，甚至並不能在屏幕上顯示出人可以辨識出的直線形狀。
效率仍然比較低

關於第1點是比較容易解決的。可以在斜率小於1的時候採用遞增x的方式，在斜率大於1的時候採用遞增y的方式來畫直線。

至於第2點的效率問題，雖然我們已經把乘法變成了加法，但是這是一個浮點數的加法。雖然現代計算機都有協處理器來計算浮點數，但和整數加法效率想想也知道是沒法比的。幸運的是人類的智慧沒有在此止步，採用整數加法的直線光柵化演算法很快便由 Jack E. Bresenham 發明了。

中點畫線演算法

中點畫線演算法使用直線的一般式，即 $Ax+By+C=0$ 來繪製直線。

一般式 $Ax+By+C=0$ 將平面上點分成3個部分，將點代入 $Ax+By+C$ ，等於0時點在直線上，大於0時在直線的一側，小於0在另一側。

怎麼看一點 $(x_{0},y_{0})$ 在一個一般式 $Ax+By+C=0$ 的上方還是下方(或是在線上)呢？結論是將點坐標代入式 $B(Ax_{0}+By_{0}+C)$ 中，和0比較。若式子等於0，則點在直線上，若式子大於0則在直線上方，小於0則在直線下方。這其實是一個很簡單的結論，但是問過的人包括一些老師絕大多數都把這點搞錯了。

考慮斜率屬於 $(0,1)$ 的情況。假設現在我們畫完了點 $(x_{i},y_{i})$ ，那麼下一個點必然畫在 $(x_{i}+1,y_{i})$ 或者 $(x_{i}+1,y_{i}+1)$ 。那麼我們不妨畫在那個最接近原始直線的點。我們考慮兩個點的中點 $(x_{i}+1,y_{i}+0.5)$ 在直線上方還是下方，從而確定應該畫哪個點。如果中點在直線上方，那麼顯然應該畫點 $(x_{i}+1,y_{i})$ ，反之畫點 $(x_{i}+1,y_{i}+1)$ 。

偽代碼

y = y0 foreach x in (x0,x1): draw(x,y) if(B*(A*(x+1)+B*(y+0.5)+C) &< 0) ++y;//中點與下面的點同側，所以畫上面的點

這樣的演算法效率顯然不夠好，有乘法，所以考慮使用增量演算法。仍然假設斜率為0到1之間，並且我們已經畫好了點 $(x_{i},y_{i})$ ，將中點 $M_{0}(x_{i}+1,y_{i}+0.5)$ 代入有 $d_{0}=F(x_{i}+1,y_{i}+0.5) = A(x_{i}+1)+B(y_{i}+0.5)+C= A+0.5B$

下面考慮:

如果下一個點畫在了 $(x_{i}+1,y_{i}+1)$ ,緊接著考慮的應該是中點 $M_{1}(x_{i}+2,y_{i}+1.5)$ ，代入直線一般式方程得到 $d_{1} = F(x_{i}+2,y_{i}+1.5)=A(x_{i}+2)+B(y_{i}+1.5)+C = A(x_{i}+1)+B(y_{i}+0.5)+C+A+B=d_{0}+A+B$

如果下一個點畫在了 $(x_{i}+1,y{i})$ 考慮的應該是中點 $M_{2}(x_{i}+2,y_{i}+0.5)$ ，代入直線一般式方程得到 $d_{2}=F(x_{i}+2,y_{i}+0.5)=A(x_{i}+2)+B(y_{i}+0.5)+C = A(x_{i}+1)+B(y_{i}+0.5)+C+A=d_{0}+A$

於是我們得到了關於d的遞推公式

$d_{new}=d_{old}+A+B$ (B*d&<0時)

$d_{new}=d_{old}+A$ (B*d&>=0時)

這時，我們的中點畫線演算法至少達到了和DDA演算法一樣的效率(浮點數加法)。但是這裡的A和B都是整數，所以我們考慮把d全部擴大一倍(因為和0比較不影響)，這樣 $2d_{0}=2A+B$ ，成功避開了浮點數加法。

使用中點畫線法模擬生成的直線:

代碼:

#include & #include & using namespace std; bool pic[50][50]; void DrawALine(int x0,int y0,int x1,int y1) { int d = 2*(y0-y1)+(x1-x0);//這裡的d為實際上d的兩倍 int y = y0; for(auto x = x0 ; x &<= x1 ; ++ x) { pic[y][x] = true; if(d &< 0) { d += 2*(y0-y1)+2*(x1-x0); ++ y; } else d += 2*(y0-y1); } } void ShowPic() { for(auto i = 49 ; i &>= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout &<&< "o"; else cout &<&< "x"; } cout &<&< endl; } } int main() { DrawALine(2,2,45,20); ShowPic(); return 0; }

至此，中點畫線演算法已經把直線光柵化的效率推至極限(整數加法)。Bresenham演算法在此基礎上，擴展了中點畫線演算法的適用範圍。

Bresenham演算法

效率已經達到了最佳，可是還不夠好。我們希望有一種演算法可以根據任何形式的直線方程都可以畫出直線，並且保持效率最佳。Bresenham在1962年將他一生最重要的貢獻Bresenham畫線演算法發表在了計算機界頂級刊物《Communication of the ACM》上。

Bresenham演算法的思想是將像素中心構造成虛擬網格線，按照直線起點到終點的順序，計算直線與各垂直網格線的交點，然後根據誤差項的符號確定該列像素中與此交點最近的像素。

如圖

如DDA演算法一樣，每次x加1的時候縱方向就加了k，保存一個d值，如果d $leq$ 0.5，那麼就畫在下面的點，如果d&>0.5就畫在上面的點。每次檢查d是否在[0,1)範圍內，不在需要d減1。演算法的偽代碼如下

d = 0 y = y0 ／／在此根據不同的方程處理好k的值 foreach x in (x0,x1) draw(x,y) d += k if(d&>=1) d -= 1; if(d &> 0.5) ++y;

這樣演算法的效率是浮點數加法，下面改進成整數加法。

首先可以將d與0.5比較(浮點數比較)進行優化

令 $e = d-0.5$ ，這樣e的初始值變成0.5，並且當e&>=0.5時將e-=1。這樣只需要看e的符號就可以知道畫在哪個像素上了。

從上一點繼續考慮

既然我們只用到了e的符號，那麼也可以用 $2eDelta x$ 做到這一點。所以現在e的初始值為 $-Delta x$ ，又因為 $k=Delta y/Delta x$ 所以每次加k就是加 $2Delta y$ 。如果大於 $Delta x$ 那麼就減去 $2Delta x$ 。

讓我們用經過優化的Bresenham演算法模擬畫一條直線

代碼:

#include & #include & using namespace std; bool pic[50][50]; void DrawALine(int x0,int y0,int x1,int y1) { int dx = fabs(x0-x1); int dy = fabs(y0-y1); int y = y0; int e = -2*dx; for(auto x = x0 ; x &<= x1 ; ++ x) { pic[y][x] = true; e += 2*dy; if(e &> 0) ++y; if(e &>= dx) e -= 2*dx; } } void ShowPic() { for(auto i = 49 ; i &>= 0 ; -- i) { for(auto j:pic[i]) { if(j) cout &<&< "x"; else cout &<&< "o"; } cout &<&< endl; } } int main() { DrawALine(2,2,40,10); ShowPic(); return 0; }

從代碼可以看到效率是整數加法的。Bresenham演算法總結了DDA演算法和中點畫線演算法的優點，應用更加廣泛。

至此，幾種最基本的直線光柵化演算法就介紹完了。直線光柵化是構造所有圖形的基礎，效率也極大程度影響渲染效率。

大千世界，始於直線。

這似乎是個很常見的圖形學入門問題，我專門寫了一篇專欄用 C 語言畫直線和 github 項目 miloyip/line，介紹一些思路和分析。

Bresenham演算法畫直線，計算機圖形學中基礎又基礎的演算法。但畫單個的點，或者自己在脫屏緩衝區里畫好再copy到屏幕上，仍然需要通過API。DOS下直接寫視頻緩衝區畫圖的作法早已成為歷史了。

printf( "-_________________________-" );

用筆直接在屏幕上畫，可以藉助鍵盤，直尺等工具。

首先寫個驅動打開顯存，然後想辦法弄到這本深入淺出的20年前寫的《Visual Basic高級圖形程序設計教程（兼容VB5.0！）》來學習各種掃描演算法，然後就搞定了。

為什麼我覺得是我上場的時候了（喂喂

.global start .code16 .text start: movw $0xb800,%ax movw %ax,%ds movb $151,(0) movb $0x1f,(1) movb $151,(2) movb $0x1f,(3) movb $151,(4) movb $0x1f,(5) movb $151,(6) movb $0x1f,(7) movb $151,(8) movb $0x1f,(9) movb $151,(10) movb $0x1f,(11) movb $151,(12) movb $0x1f,(13) hlt

ATT彙編。

嗯嗯，具體參考這個文章

手寫一個X86操作系統實戰：從零開始構建一個U盤啟動的自製操作系統（一）

另外在Windows下也可以寫驅動操縱顯存。有一篇看雪的文章介紹了相關的方法：【原創】通過DDK Driver直接寫顯卡內存

想起那個風扇吹空盒子的段子

講道理最純正的c/c++這個語言本身並沒有提供輸出方法，你想要畫出東西總要有輸出吧，那麼要麼調用api，或者自己寫api。可以用彙編語言寫一個與你邏輯相同的動態鏈接庫，然後用c/c++調用，本質上還是調用api

演算法方面見其他答主

補充：有一種圖像格式叫PPM

不描述應用場景、不給出目標平台，你耍流氓啊。

linux的話，framebuffer。

有人給出了彙編代碼，但是LINUX下戶態進程是不能調用顯卡BIOS的中斷直接寫屏的。你操作不了顯存，就畫不出圖來。

BIOS，系統調動，直寫視屏緩衝區。。。似乎學彙編的時候就是這幾種方法

printf或者cout算不算API？

當年我大學的圖形學課程，就是用C語言直接寫內存中的屏幕緩衝區做的。。。

用51單片機控制ili93xx畫可以嗎？

思路：

1.把spi調通（你如果無聊的話一根根插線核對或者扔73人民幣做板子 @嘉立創我不反對用並口）

2.複製粘貼過來屏廠家給的畫像素和初始化函數

3.用那個b什麼的演算法把線畫出來

感覺比這個更複雜一點的系統都沒必要做這種事

不調用底層API卻又要畫直線，那無非就是你把底層api的事自己做一遍，那這個問題應該是：畫直線有多少種演算法？

看了半天也沒看明白你們到底想表達什麼

BIOS不就是個例子

cout

easyx圖形庫，裡面有各種函數

cout &<&< "______________";

個人記得學習圖形學的時候有學過三種走筆演算法，可以畫直線，不知道樓主想要的是那種？樓上所所說的Bresenham演算法是其中的一種