多用途軟性電子基板
2010年9月26日 星期日
2010年9月23日 星期四
太陽風暴2013衝擊地球
更新日期:
威力如100枚氫彈爆炸2010/09/22 04:11
〔編譯陳成良／綜合報導〕科學家20日在倫敦一場國際會議中警告，2013年地球可能遭受威力比擬100枚氫彈爆炸的太陽風暴侵襲，屆時太陽表面劇烈的閃焰爆發，可能導致全球大停電、通訊及網路系統中斷、飛機無法起飛、食物供給出問題、網際網路中斷，從家用冰箱到汽車衛星導航器的各種東西都會受到影響，地球恐因此陷入癱瘓。
2010年9月21日 星期二
AVR@IAR 中堆疊的設定
Controlling the stack size
Have you ever experienced strange errors in your code, caused by an overflowing stack? Have you hadto run an application on a system with very little memory available? Then you know why the stack must
be sufficiently large, but not too large. Traditionally, this has been solved by using a mixture of qualified
guesses and experience, or by keeping track of every function and its needs. Another way to check
whether the stack was overflowing was to use a predetermined pattern in the topmost memory cells
used and check whether they had been written to after the code had finished running.
2010年9月11日 星期六
2010年9月6日 星期一
2010年9月2日 星期四
Bresenham 直線演算法 [布雷森漢姆直線演算法]
Bresenham 直線演算法是用來描繪由兩點所決定的直線的演算法，它會算出一條線段在 n 維光柵上最接近的點。這個演算法只會用到較為快速的整數加法、減法和位元移位，常用於繪製電腦畫面中的直線。是計算機圖形學中最先發展出來的演算法。
經過少量的延伸之後，原本用來畫直線的演算法也可用來畫圓。且同樣可用較簡單的算術運算來完成，避免了計算二次方程式或三角函數，或遞歸地分解為較簡單的步驟。
以上特性使其仍是一種重要的演算法，並且用在繪圖儀、繪圖卡中的繪圖晶片，以及各種圖形程式庫。這個演算法非常的精簡，使它被實作於各種裝置的韌體，以及繪圖晶片的硬體之中。
「Bresenham」至今仍經常作為一整個演算法家族的名稱，即使家族中絕大部份演算法的實際開發者是其他人。該家族的演算法繼承了 Bresenham 的基本方法並加以發展，詳見參考資料。
演算方法
假設我們需要由 (x0, y0) 這一點，繪畫一直線至右下角的另一點(x1, y1)，x,y分別代表其水平及垂直座標，並且 x1 - x0 > y1 - y0。在此我們使用電腦系統常用的座標系，即x座標值沿x軸向右增長，y座標值沿y軸向下增長。
因此x及y之值分別向右及向下增加，而兩點之水平距離為x1 − x0且垂直距離為y1-y0。由此得之，該線的斜率必定介乎於1至0之間。而此演算法之目的，就是找出在x0與x1之間，第x行相對應的第y列，從而得出一像素點，使得該像素點的位置最接近原本的線。
對於由(x0, y0)及(x1, y1)兩點所組成之直線，公式如下：
因此，對於每一點的x，其y的值是
因為x及y皆為整數，但並非每一點x所對應的y皆為整數，故此沒有必要去計算每一點x所對應之y值。反之由於此線之斜率介乎於1至0之間，故此我們只需要找出當x到達那一個數值時，會使y上升1，若x尚未到此值，則y不變。至於如何找出相關的x值，則需依靠斜率。斜率之計算方法為m = (y1 − y0) / (x1 − x0)。由於此值不變，故可於運算前預先計算，減少運算次數。
要實行此演算法，我們需計算每一像素點與該線之間的誤差。於上述例子中，誤差應為每一點x中，其相對的像素點之y值與該線實際之y值的差距。每當x的值增加1，誤差的值就會增加m。每當誤差的值超出0.5，線就會比較靠近下一個映像點，因此y的值便會加1，且誤差減1。
下列偽代碼是這演算法的簡單表達（其中的plot(x,y)繪畫該點，abs返回的是絕對值）。雖然用了代價較高的浮點運算，但很容易就可以改用整數運算（詳見最佳化）：
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax // 假設 deltax != 0 （非垂直線），
// 注意：需保留除法運算結果的小數部份
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs(error) ≥ 0.5 then
y := y + 1
error := error - 1.0
一般化
雖然以上的演算法只能繪畫由右上至左下，且斜率小於或等於1的直線，但我們可以擴展此演算法，使之可繪畫任何的直線。
第一個擴展是繪畫反方向，即由左下至右上的直線。這可以簡單地透過在x0 > x1時交換起點和終點來做到。
第二個擴展是繪畫斜率為負的直線。可以檢查y0 ≥ y1是否成立；若該不等式成立，誤差超出0.5時y的值改為加-1。
第三,我們還需要擴展該演算法，使之可以繪畫斜率絕對值大於1的直線。要做到這點，我們可以利用大斜率直線對直線y=x的反射是一條小斜率直線的事實，在整個計算過程中交換 x 和 y，並一併將plot的參數順序交換。擴展後的偽代碼如下：
function line(x0, x1, y0, y1)
boolean steep := abs(y1 - y0) > abs(x1 - x0)
if steep then
swap(x0, y0)
swap(x1, y1)
if x0 > x1 then
swap(x0, x1)
swap(y0, y1)
int deltax := x1 - x0
int deltay := abs(y1 - y0)
real error := 0
real deltaerr := deltay / deltax
int ystep
int y := y0
if y0 < y1 then ystep := 1 else ystep := -1
for x from x0 to x1
if steep then plot(y,x) else plot(x,y)
error := error + deltaerr
if error ≥ 0.5 then
y := y + ystep
error := error - 1.0
以上的程序可以處理任何的直線，實作了完整的Bresenham直線演算法。
最佳化
以上的程序有一個問題：電腦處理浮點運算的速度比較慢，而error與deltaerr的計算是浮點運算。此外，error的值經過多次浮點數加法之後，可能有累積誤差。使用整數運算可令演算法更快、更準確。只要將所有以上的分數數值乘以deltax，我們就可以用整數來表示它們。唯一的問題是程序中的常數0.5—我們可以透過改變error的初始方法，以及將error的計算由遞增改為遞減來解決。新的程序如下：
function line(x0, x1, y0, y1)
boolean steep := abs(y1 - y0) > abs(x1 - x0)
if steep then
swap(x0, y0)
swap(x1, y1)
if x0 > x1 then
swap(x0, x1)
swap(y0, y1)
int deltax := x1 - x0
int deltay := abs(y1 - y0)
int error := deltax / 2
int ystep
int y := y0
if y0 < y1 then ystep := 1 else ystep := -1
for x from x0 to x1
if steep then plot(y,x) else plot(x,y)
error := error - deltay
if error < 0 then
y := y + ystep
error := error + deltax
歷史Jack E. Bresenham於1962年在IBM發明了此演算法。據他本人表示，他於1963年在丹佛舉行的美國計算機協會全國大會上發表了該演算法，論文則登載於1965年的《IBM系統期刊》 (IBM Systems Journal) 之中。[1]Bresenham直線演算法其後被修改為能夠畫圓，修改後的演算法有時被稱為「Bresenham畫圓演算法」或中點畫圓演算法。Sample C code 1Bresenham(int x1,int y1,int x2,int y2)
{
int dx, dy, i, e;
int incx, incy, inc1, inc2;
int x,y; dx = x2 - x1;
dy = y2 - y1; if(dx < 0) dx = -dx;
if(dy < 0) dy = -dy;
incx = 1;
if(x2 < x1) incx = -1;
incy = 1;
if(y2 < y1) incy = -1;
x=x1;
y=y1; if(dx > dy)
{
draw_pixel(x,y, BLACK);
e = 2*dy - dx;
inc1 = 2*( dy -dx);
inc2 = 2*dy;
for(i = 0; i < dx; i++)
{
if(e >= 0)
{
y += incy;
e += inc1;
}
else e += inc2;
x += incx;
draw_pixel(x,y, BLACK);
}
}
else
{
draw_pixel(x,y, BLACK);
e = 2*dx - dy;
inc1 = 2*( dx - dy);
inc2 = 2*dx;
for(i = 0; i < dy; i++)
{
if(e >= 0)
{
x += incx;
e += inc1;
}
else e += inc2;
y += incy;
draw_pixel(x,y, BLACK);
}
}
}Sample C code 2void GUI_Line(U16 x0, U16 y0, U16 x1, U16 y1, TCOLOR color)
{ U16 dx, dy;
U8 dx_sym,dy_sym;
U16 dx_x2, dy_x2, di;
dx = x1-x0; dy = y1-y0;
if(dx>0)
{ dx_sym = 1;
}
else
{ if(dx<0)
{ dx_sym = -1;
}
else
{
GUI_RLine(x0, y0, y1, color);
return;
}
}
if(dy>0)
{ dy_sym = 1;
}
else
{ if(dy<0)
{ dy_sym = -1;
}
else
{
GUI_HLine(x0, y0, x1, color);
return;
}
}
dx = dx_sym * dx;
dy = dy_sym * dy;
dx_x2 = dx << 1;
dy_x2 = dy << 1;
/* 使用Bresenham法進行畫直線 */
if(dx>=dy)
{ di = dy_x2 - dx;
while(x0!=x1)
{ GUI_Point(x0, y0, color);
x0 += dx_sym;
if(di<0)
{ di += dy_x2; }
else
{ di += dy_x2 - dx_x2;
y0 += dy_sym;
}
}
GUI_Point(x0, y0, color);
}
else
{ di = dx_x2 - dy;
while(y0!=y1)
{ GUI_Point(x0, y0, color);
y0 += dy_sym;
if(di<0)
{ di += dx_x2;
}
else
{ di += dx_x2 - dy_x2;
x0 += dx_sym;
}
}
GUI_Point(x0, y0, color);
}
}构建仪表、图表控件的绘制框架:http://www.vckbase.com/document/viewdoc/?id=1727
2010年9月1日 星期三
Bresenham演算法
original author : http://liar.pangwa.com/2009/04/12/bresenham/
在看一本書《Windows遊戲編程大師技巧》 (Tricks of Windows Game Programming Gurus). 這次繼續書裏的內容: 直線光柵化的Bresenham演算法. 書上講的比較含糊, 沒有講演算法的推導過程, 更沒講演算法是怎麼想出來的. 所以我們只好自己動手, …
直線光柵化
直線光柵化是指用圖元點來類比直線. 比如下圖中用藍色的圖元點來類比紅色的直線. 圖中坐標系是顯示器上的坐標系: x軸向右, y軸向下.
設deltaX = endX – startX, deltaY = endY – startY. 那麼斜率為k = deltaY / deltaX. 我們先考慮簡單的情況: 當 0 < k < 1即直線更貼近x軸. 在這種情況下deltaY < deltaX, 所以在光柵化的過程中, 在y軸上描的點比在x軸上描點少. 那麼就有一個很直觀的光柵化演算法:
line_bresenham(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;
for (x = startX, y = startY; x <= endX; ++x)
{
if (滿足一定條件)
{
++y;
}
drawPixel(x, y);
}
}
基於斜率 / 距離的兩個簡單直線光柵化演算法
好了，貌似很簡單, 就剩一個問題: “滿足一定條件”是什麼? 可以用斜率判斷, 也可以用上圖中直線與光柵線交點 (紅點) 與光柵點 (藍點) 的距離來判斷. 繼續用偽代碼說話:
// 演算法1: 用斜率判斷
void line_bresenham_k(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;
for (x = startX, y = startY; x <= endX; ++x)
{
if (x - startX != 0)
{
// 計算當前斜率
currentK = (y - startY) / (x - startX);
// 如果當前斜率 < k, 則增加y座標
if (currentK < k)
{
++y
}
}
drawPixel(x, y);
}
}
// 演算法2: 用距離判斷. 計算直線與光柵線交點y座標我們需要用到
// 直線方程 y = k (x - startX) + startY
line_bresenham_dist(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
k = deltaY / deltaX;
for (x = startX, y = startY; x <= endX; ++x)
{
// 計算直線與光柵線交點的y座標, 以及與光柵點的距離
ptY = k * (x - startX) + startY;
dist = ptY - y;
// 如果距離 > 0.5或者 < -0.5, 說明我們需要增加y以
// 將距離的絕對值控制在0.5之類
if (dist > 0.5 || dist < -0.5)
{
++y;
}
drawPixel(x, y);
}
}
消滅浮點數!
以上都是很直觀的演算法, 下面不直觀的來了 – 上面的演算法都需要在循環體內執行乘法, 準確的說, 是進行浮點數的乘法. 我們怎麼能減少這些浮點數的乘法開銷呢? 以基於距離的演算法2為例: 首先, k是一個浮點數, 0.5也是浮點數. 我們可以通過將這些運算式都乘以2 * deltaX (整數) 來解決浮點數的問題. 偽代碼:
// 演算法3: 在演算法2的基礎上消滅浮點數!
line_bresenham_dist(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
for (x = startX, y = startY; x <= endX; ++x)
{
// 計算直線與光柵線交點的y座標, 以及與光柵點的距離
ptY1 = deltaY * (x - startX) + startY * deltaX;
dist1 = ptY1 - y * deltaX;
dist1 = dist1 << 1; // dist1 = dist1 * 2
// 如果距離 > 0.5或者 < -0.5, 說明我們需要增加y以
// 將距離的絕對值控制在0.5之類
if (dist1 > deltaX || dist < -deltaX)
{
++y;
}
drawPixel(x, y);
}
}
消滅乘法!
圓滿解決浮點數運算問題! 不過…乘法運算還在. 消滅乘法問題的辦法比較不直觀, 讓我們想一想: 還有什麼辦法能簡化運算. 直線方程已經不能再簡化, 所以唯一的突破口就是能不能利用遞推 / 用上一次迴圈的計算結果推導下一次迴圈的計算結果.
首先我們來看看在演算法2的基礎上 (因為演算法2計算紅點藍點之間的距離, 比較直觀), 怎麼通過第n – 1次迴圈計算出的dist值 (設為d1) 來推導出第n次迴圈的dist值 (設為d2). 先回顧一下: dist = 直線與光柵線交點的y座標 – 相應光柵點的y座標. 我們從幾何上直觀地考慮: 在第n次迴圈中, 我們先根據上一次迴圈所計算出來的d1, 暫時令d2 = d1 + k, 因為我們要保證-0.5 < d2 < 0.5, 而d1 + k滿足d1 + k > –0.5, 所以我們只需要考慮當d1 + k > 0.5時, 我們需要將光柵點y座標增加1, 並且將d2減去1. 顯然, 設y1是第n – 1次迴圈中光柵點的y座標, y2是第n次迴圈中光柵點的y座標. 我們有
1) d2 = d1 + k – (y2 – y1)
2) 當d1 + k > 0.5時y2 = y1 + 1, 否則y2 = y1
我們已經能根據上面的兩個關係式寫出演算法, 不過為了消除乘法和浮點數, 我們將這兩個關係式兩端同時乘以2 * deltaX, 並且設e = 2 * deltaX * d, 則我們有
3) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
4) 當e1 + 2 * deltaY > deltaX時y2 = y1 + 1, 否則y2 = y1
終於, 沒有了乘法 (2 * deltaY在循環體外計算且被簡化為左移一位的運算), 沒有了浮點數, 根據關係式3) 和 4), 寫出演算法:
// 演算法4: 在演算法2, 3的基礎上利用遞推消滅乘法和浮點數!
line_bresenham(startX, startY, endX, endY)
{
deltaX = endX - startX;
deltaY = endY - startY;
e = 0;
deltaX2 = deltaX << 1;
deltaY2 = deltaY << 1;
drawPixel(startX, startY);
for (x = startX + 1, y = startY; x <= endX; ++x)
{
// 關係式3) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
// 關係式4) 當e1 + 2 * deltaY > deltaX時y2 = y1 + 1, 否則y2 = y1
e += deltaY2;
if (e > deltaX)
{
e -= deltaX2;
++y;
}
drawPixel(x, y);
}
}
消滅浮點數! 代數推導
上面遞推關係的推導過程是從圖形上”直觀”地分析得來的, 但是不嚴密. 我們能不能形式化地證明關係式1), 2), 3), 4)呢? 因為關係式3), 4)和1), 2)能互相推導, 我們只證明3), 4)如下:
在演算法3的基礎上設第n – 1次迴圈計算出的dist1值為e1, 對應的y值為y1, 第n次迴圈計算出的dist1值為e2, 對應的y值為y2. 根據演算法3,
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)
所以e2 = e1 + deltaY – 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
我們根據e1 + 2 * deltaY的取值範圍進行討論. 首先, 因為不等式6), 我們有
2 * deltaY – deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX
情況1: 如果2 * deltaY – deltaX < e1 + 2 * deltaY < deltaX, 則
2 * deltaY – deltaX – 2 * deltaX * (y2 – y1) < e2 < deltaX– 2 * deltaX * (y2 – y1)
反證: 若y2 – y1 = 1, 則 2 * deltaY – deltaX – 2 * deltaX < e2 < deltaX – 2 * deltaX = -deltaX, 所以y2 – y1 = 1不成立. 即情況1中y2 = y1.
情況2: 如果 deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX, 則
deltaX – 2 * deltaX * (y2 – y1) < e2 < 2 * deltaY + deltaX – 2 * deltaX * (y2 – y1)
反證: 若y2 – y1 = 0, 則 deltaX < e2 < 2 * deltaY + deltaX 所以y2 – y1 = 0不成立. 即情況2中y2 = y1 + 1.
打了這麼多字, 累…以上就是當0 < k < 1的情況, 剩餘幾種情況 (k > 1, –1 < k < 0, k < –1. 不要挑剔我不用”>=”這種符號…) 都可以通過簡單的x, y交換以及正負交換來搞定.
The other line:http://www.cnblogs.com/soroman/archive/2006/07/27/509602.html
Atmega 128 Port C as normal I/O
I am trying to use PC0-PC7 as normal I/O on an Atmega 128. The lower external address bits AD0-AD7 are used for external memory and function correctly. PC0-PC7 are released for normal I/O in XMCRB. All reads of Port C and PORTC in Studio's I/O window are 1's (pullups enabled) and 0's (pullups disabled). What am I missing?
MCUCR = 0x80; // enable external memory, no wait states, disable
// sleep, sleep mode idle, int vectors not in boot
// flash, no int vector change enable
XMCRA = 0x00; // no external memory sectors, no wait states
XMCRB = 0x07; // release high address bits for normal i/o
DDRC = 0x00; // set pc7-pc0 inputs
PORTC = 0xff; // enable pc7-pc0 pullups
//PORTC = 0x00; // disable pc7-pc0 pullups
MCUCR = 0x80; // enable external memory, no wait states, disable
// sleep, sleep mode idle, int vectors not in boot
// flash, no int vector change enable
XMCRA = 0x00; // no external memory sectors, no wait states
XMCRB = 0x07; // release high address bits for normal i/o
DDRC = 0x00; // set pc7-pc0 inputs
PORTC = 0xff; // enable pc7-pc0 pullups
//PORTC = 0x00; // disable pc7-pc0 pullups
DIY unique PCB Drill
This PCB drill is made of wood and looks really cool. Wouldn’t mind to have one on my table. Design is very unique – it uses various custom made parts, motors from old printers and VCR’s. Author even simulated all design code on a Labcenter’s Proteus VSM.
Building AVR Jtag clone
Finally I found some time to finish AVRJTAG clone. It was hanging for a while on a breadboard with bunch of wires. I have made an Eagle CAD project with PCB layout you will find at the bottom of article.
AVR DDS signal generator V2.0
Finally second and improved AVR DDS signal generator is here. First AVR DDS V1.0 generator was only an attempt of running DDS algorithm without any amplitude control. This time I still wanted to keep things simple like minimum count of widely accessible components circuit, single sided PCB that comes together with good functionality.
AVR ISP
http://www.scienceprog.com/avr-isp/
AVRISP is very popular Parallel port programmer for flashing AVR type microcontrollers. Earlier I used programmer connected to com port, but frequently I needed this port for other purposes, I decided to make it work on parallel port. The programmer on parallel port is much simpler than connected to serial port, because there is no needed voltage adapter like MAX232. You can only connect your MCU directly to port. But for safety reasons there is good practice to use buffer ship like 74HC244.
AVRISP is very popular Parallel port programmer for flashing AVR type microcontrollers. Earlier I used programmer connected to com port, but frequently I needed this port for other purposes, I decided to make it work on parallel port. The programmer on parallel port is much simpler than connected to serial port, because there is no needed voltage adapter like MAX232. You can only connect your MCU directly to port. But for safety reasons there is good practice to use buffer ship like 74HC244.
Build your own AVR JTAG ICE clone (自製 AVR JTAG ICE debugger)
Build your own AVR JTAG ICE clone
After unsuccessful attempts to run few programs who drive peripherals like USART and Timers on Atmega128 I decided to make JTAG debugger. I hope it will allow me to see what is really happening – is may atmega128 corrupted or something is really wrong with software or with hardware
After unsuccessful attempts to run few programs who drive peripherals like USART and Timers on Atmega128 I decided to make JTAG debugger. I hope it will allow me to see what is really happening – is may atmega128 corrupted or something is really wrong with software or with hardware
訂閱：
文章 (Atom)