2010年12月21日 星期二

I/Q調變 ( I/Q Data) I/F調變 & 類比與數位調變

概觀

 I: 指的是同相(in-phase)資料
笛卡兒座標系, 也稱直角坐標系,是一種正交坐標系。(Cartesian coordinate ) 之Real (in-phase)

Q:指的是正交(quadrature)資料
笛卡兒座標系 之Imaginary(quadrature)

用最簡單的形態來看,IQ 資料顯示正弦波的強度相位的改變。如果正弦波的強度和相位變化是以有秩序、預先決定的方式來進行,就可以使用這些強度/相位變化將正弦波的資料編碼,這個過程稱為調變(modulation)。 調變是將高頻訊號依比例轉換為低頻訊號。高頻訊號稱為載子訊號 (carrier signal),低頻訊號則稱為訊息訊號 (message signal)、資訊訊號(information signal),或調變訊號 (modulating signal)。在RF通訊系統中,IQ 資料非常普遍,而且因為它在處理調變訊號時所提供的便利性,更常應用在訊號調變中。本篇討論將涵蓋IQ資料的理論背景,以及使得IQ資料在通訊中如此獲得廣泛採用的實際考量。

訊號的背景知識

訊號調變包括對正弦波進行變動,以便將資訊編碼。用來代表正弦波的數學算式如下:

2010年12月20日 星期一

康乃爾大學微處理器課程-有設計過程介紹,電路圖,源代碼,成本等...

http://courses.cit.cornell.edu/ee476/FinalProjects/

這個網站的內容是美國康乃爾大學(Cornell University)微處理器課程

我看了幾個項目,全是用ATMEGA32做的(他們實驗室只有ATMEGA32XX),有無線鍵盤,控制PALM觸摸屏的遊戲機,電腦溫度監控等等,看了之後,我覺得國外的課程對動手能力的要求真高,. 再說這個網站,每個項目有介紹,設計過程,電路圖,源代碼,成本等,有的真的很有創意!強烈推薦!


2010年12月15日 星期三

博碩士論文查詢系統

博碩士論文聯邦論文查詢系統
http://fedetd.mis.nsysu.edu.tw/FED-db/cgi-bin/FED-search/search_s

臺灣博碩士論文知識加值系統:自由的博碩士論文全文資料庫
http://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/ccd=Q.51tM/webmge?mode=basic

國立交通大學博碩士論文全文檢索系統
http://etd.lib.nctu.edu.tw/cgi-bin/gs/tugsweb.cgi?o=dnctucdr&i=sGT009412514.id

臺灣科技大學機構典藏系統
http://ir.lib.ntust.edu.tw/

科技產業資訊室--全球專利資訊檢索
http://cdnet.stpi.org.tw/patentsearch.htm

科技政策研究與資訊中心  資訊服務處
http://library.stpi.org.tw/service.htm

2010年12月12日 星期日

ECG Measurement System 心電圖量測系統概念

        在開始決定拿自己作為實驗物件之前,你需要瞭解如何保護自己?一想到,按啟動按鈕是自己的最後一個有意識的動作,你會不會問自己,何必跟自己過不去呢?所以在實驗你的殺人機器之前,我非常嚴肅的警告你,這樣做,後果很嚴重!!!在確定你的機器確實可用之前,請不要拿自己、自己的家人、別人的家人做實驗

       220V 500mA的電流足以徹底摧毀一個人的神經系統。相對穩妥的辦法,是保證您的系統由低電壓的電池供電,並加上不可恢復的熔斷保險絲。在開始試驗之前,檢查電路兩次以上。確保您不是獨自一個人在實驗,以防萬一。

2010年12月10日 星期五

Progressive Wiring Techniques 手工PCB繞線的先進佈線技術

Progressive Wiring Techniques (手工PCB繞線的先進佈線技術)



GPS Data Logger




     I have got a GPS module last year and I built a GPS data logger that records position data from the GPS module. The position data is output in NMEA-0183 format  and store its sentence into any storage device. The position data can be processed with existing GPS utilities for interesting applications.

2010年12月6日 星期一

相變化記憶體

相變化記憶體(phase-change memory,PCM)已經悄悄現身在手機產品中?根據工程顧問機構 UBM TechInsights 的一份拆解分析報告,發現在某款神秘手機中,有一顆由三星電子(Samsung Electronics)出品的多晶片封裝(multi-chip package,MCP)記憶體,內含與NOR快閃記憶體相容的相變化記憶體晶片。

2010年12月4日 星期六

歐洲暴雪 -30度

嚴寒天候連日來籠罩歐洲,有些地方氣溫低到攝氏零下二、三十度,各地冰封雪阻,一片白色世界。各地都傳出凍死人的事件,至今已有三十人凍死。大雪也導致鐵路交通中斷,許多重要機場被迫關閉,成千上萬輛汽車半途熄火,卡在路上動彈不得。根據氣象預報,惡劣天氣至少會持續到本周末。

2010年12月3日 星期五

半導體破解– A new approach to hardware security analysis

劍橋大學博士
論文關於MCU 破解方法, 設計者不可不知!!!(戰者,止戰也)

This technical report is based on a dissertation submitted September 2004 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Darwin College.

Abstract

Semiconductor chips are used today not only to control systems, but also to protect them against security threats. A continuous battle is waged between manufacturers who invent new security solutions, learning their lessons from previous mistakes, and the hacker community, constantly trying to break implemented protections. Some chip manufacturers do not pay enough attention to the proper design and testing of protection mechanisms. Even where they claim their products are highly secure, they do not guarantee this and do not take any responsibility if a device is compromised. In this situation, it is crucial for the design engineer to have a convenient and reliable method of testing secure chips.

2010年12月2日 星期四

2010年11月30日 星期二

CNC emc linux logo G-code test run

Running the emc2 logo G code that came with emc linux. It looks like most of the noise issues have been resolved. Might be time to hook up the porter cable and carve something. Still need to make some (most likely MANY) adjustments in order to get any kind of accuracy out of this contraption

2010年11月25日 星期四

Hamamatsu APD module

C5331-01



Operates an APD with single 5 V supply, near infrared type


Hamamatsu Si APD

Hamamatsu Si APD
S2383



APD optimized for Infrared Low Bias Voltage type


World Top 搜尋引擎

1.   Google ( Search Engine )          2.   Aol Search ( Search Engine )  3. MSN ( Search Engine )

Laser als Entfernungsmesser

http://www.roboternetz.de/phpBB2/printview.php?t=35877&start=0
http://robotikportal.de/phpBB2/viewtopic.php?t=35877
http://de.wikipedia.org/wiki/Fotodiode#Betriebsarten
http://robotikportal.de/phpBB2/viewtopic.php?t=35877
http://www.mikrocontroller.net/topic/61558
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=701455
http://www.mikrocontroller.net/topic/171325
http://embedded-casestudy.wikispaces.com/

2010年11月14日 星期日

ARM+PCL6045B的嵌入式運動控制器設計

引 言
  運動控制器是運動控制系統的核心部件。目前,國內的運動控制器大致可以分爲3類:

  第1類是以單片機等 微處理器 作爲控制核心的運動控制器。這類運動控制器速度較慢、精度不高、成本相對較低,只能在一些低速運行和對軌迹要求不高的輪廓運動控制場合應用。
  

2010年11月7日 星期日

環型線圈式超穎材料 --- 改變光的路徑 隱形斗篷

儀科中心簡訊第九十七期: 本期簡訊全文 PDF 檔 (2.46 Mbyte)

台大物理系教授蔡定平已研發出製作斗篷的材料─「環型線圈式超穎材料」的樣品,相關論文還登上十一月五日最新一期的科學(Science)月刊。

蔡定平表示,所謂的隱形斗篷,是斗篷的「材質」會讓人看不見斗篷,簡單說,斗篷的材料「環型線圈式超穎材料」可以改變光的路徑,使光繞圈圈或者使光轉彎,就成了隱形斗篷。

LOW speed AVR oscilloscope (5 Khz---square wave)

LOW speed AVR oscilloscope (5 Khz---square wave)







stanford 大學 web site 上AVR GCC library

URL: http://ccrma.stanford.edu/courses/250a-fall-2003/docs/avrlib-new/files.html
/a2d.c [code] Analog-to-Digital converter function library
/a2d.h [code] Analog-to-Digital converter function library
/ata.c [code] IDE-ATA hard disk interface driver
/ata.h [code] IDE-ATA hard disk interface driver
/avrlibdefs.h [code] AVRlib global defines and macros
/avrlibtypes.h [code] AVRlib global types and typedefines

2010年11月4日 星期四

sprintf用法解析

作者:晨星     http://www.cnitblog.com/liaoqingshan/archive/ 2008/03/06 /40573.html

1
sprintf 最常見的應用之一莫過於把整數列印到字串中,所以,spritnf在大多數場合可以替代itoa
這樣,一個整數的16 進制字串就很容易得到,但我們在列印16 進制內容時,通常想要一種左邊補0 的等寬格式,那該怎麼做呢?很簡單,在表示寬度的數位前面加個0 就可以了。

sprintf(s, "%08X", 4567); //
產生:"000011D7"上面以”%d”進行的10 進制列印同樣也可以使用這種左邊補0 的方式。
這裏要注意一個符號擴展的問題:比如,假如我們想列印短整數(short-1的記憶體16 進制表示形式,在Win32 平臺上,一個short 型占2 個位元組,所以我們自然希望用4 16 進制數字來列印它:

short si = -1;

2010年11月1日 星期一

Matlab 的用法

一. 總結了MATLAB中冒號的用法和作用。附演示

1a:b   表示[a,a+1,……,b]
>> A=1:5
A =

     1     2     3     4     5


2當然如果b-a不是整數的話,則向量的最後一位數是n+a,且n=fixb-a
>> A=1.2: 4.9
A =
    1.2000    2.2000    3.2000    4.2000


2010年10月22日 星期五

反聖嬰發威 學者警告颱風和洪災

台灣醒報 (2010-10-14 09:35)
        反聖嬰年氣候異常,近來印尼、越南、孟加拉等地,因熱帶低氣壓造成嚴重洪災,台灣也拉警報。多位受訪學者專家均強調,今年年底可能還會有颱風甚至是東北季風來襲,並且夾帶旺盛水氣,恐造成非常嚴重的災情,政府和民眾都應多加留意。

2012當科學遇上預言

    全球的自然災難發生頻率越來越高,馬雅人2012的預言難道會成真?科學家是如何看待這個預言?到底2012年會發生什麼事?

100個美麗家園岌岌可危

 
100個美麗家園岌岌可危/汪中和
在地球的任何角落,如今都可以感受到天氣激烈變化所帶來的影響。
以二○○九年為例,八月初台灣的莫拉克颱風所帶來的豪大雨重創南台灣,也是半世紀以來傷亡最慘重的水災,小林村一夕消失。八月二十七日,中國四川重慶一夜之間,天空閃電高達一萬一千四百七十一次,居民難以入眠。

2010年10月19日 星期二

期待「Win 8」與ARM的天作之合

 Windows 7 熱度還很高,現在卻已經開始預測下一件大事──但事實是:這些年來並沒有出現一個引起市場熱潮的 Windows 版本,而ARM的支援可能正是微軟(Microsoft)非常需要的。

如果未來的Windows 8能與ARM聯姻,將會是天作之合;這樁婚事可替微軟打開一扇門,得以進軍從一般消費性平板電腦到網咖設備等低價、低耗電產品領域。在這個節骨眼上,像是Windows這樣的專利產品若能取得一個新市場,無啻是天降甘霖。

Download the Android SDK (SW Development Kit)

 Android SDK 是GOOGLE手機軟體開發平台,可以買一支手機來玩玩喔!!!

Download address  :
 http://developer.android.com/sdk/index.html

       Welcome Developers! If you are new to the Android SDK, please read the Quick Start, below, for an overview of how to install and set up the SDK.

2010年10月14日 星期四

幹細胞再生心臟

      成大謝清河率領的研究團隊,獨步全球,以蘭嶼豬的大動物實驗證實,利用奈米纖維水膠結合自體骨髓幹細胞移植的技術,可促進急性心肌梗塞後的心肌保護與血管再生,讓壞死的心肌長出新血管,成功治療豬的急性心肌梗塞,創全球首例。

人類第六感官 : 速度感官

 
  馬來西亞大學的10歲混血兒神童艾南,兩年前發現人類有5個感官之外的第六個感官,並花1年的時間將他的這項發現,在父親的協助下發表在網路學術期刊。

2010年10月13日 星期三

Undersampling of Modulated Signals

      According to the Nyquist sampling theorem, in order to recover a signal via sampling, the sample rate must be greater than or equal to the two time (2x) the highest frequency in the signal. Doing so prevents aliasing due to frequency foldback about the 0 Hz (DC) axis. So, if you were digitally sampling a human voice with a maximum frequency content of, say, 6 kHz, then your sampling rate would need to be at least 12 kHz. In practice, the sample rate used is a little higher to provide a buffer, and a lowpass filter is placed in front of the A-to-D converter to make certain that higher frequency content does not make its way into the converter and subsequently get translated into an aliased (false) component. The concept applies to digital signals as well as with analog signals.

2010年10月10日 星期日

Fuzebox : Open source 8-bit game console





Introducing the Fuzebox

The WEATHER RECORDER

This project is only for experienced home builder.

Front view


  The narrow trace is the outside temperature graph.
  The wide trace is the pressure graph.

碳粉熱轉印法 (Toner Transfer) 製作 微控製器PCB

中文 : http://www.qsl.net/bv3fg/tech/TTPCB.htm
中文詳細說明 : http://gc.digitw.com/Circuit/PCB-BY-TRANS.pdf
Make your own Microcontroller PCB using the Toner Transfer Method

   As the electronics hobbyist one of knowledge that we have to be familiar with is how to make our own printed circuit board (PCB). Making our own simple single side PCB actually is not require a sophisticated technique and technology as you might think, instead most of the required materials is already available at your home. I’ve started make my first single side through-hole PCB for a simple two transistors astable multivibrator project using just a water proof marker and draw the PCB layout directly on the PCB copper surface.

Building your own Simple Laser Projector

The 8 pins PIC12F683 microcontroller is one of the smallest members of the Microchip 8-bit microcontroller families but equipped with powerful peripherals such as ADC and PWM capabilities. This make this tiny microcontroller is suitable for controlling the DC motor speed. In order to demonstrate the PIC12F683 capabilities and to make this tutorial more attractive, I decided to use the PIC12F683 microcontroller to generate simple and yet fascinating laser light show from a cheap keychain laser pointer.

The basic of laser light shown in many entertainments club or park mostly use two method; the first one is to beam the laser shower on the spectators and the second one is to display the laser drawing pattern on the screen. On this tutorial we are going to build the laser projector that displays the spirograph pattern on the screen using the tiny Microchip PIC12F683 microcontroller.



Atmel MP3 player

http://mcu.cz/news.php?extend.1803.7
Atmel MP3 player


AVR JTAG Debugger/Programmer

http://www.avrportal.com/?page=jtag

AVR JTAG : Credit to IsoJtagIsp for schematic and bootloader. I've been modified a schematic from IsoJtagIsp by remove USB interface from schematic because I'd like to use AVR JTAG with USB2RS232 and serial port.
















AVR JTAG schematic.

    Download bootloader onto ATMEGA16, If you don't have a AVR programmer I recommended a simple

Eagle3D

Some time ago there was a question in one of the Eagle-Newsgroups if it is possible to translate the 2D-layout into a 3-dimensional view. It was not possible. So I started the development of Eagle3D. After a couple of days I had an ULP and a library with 3D-POVRay models of electronic components. Out of a board like this:



ISO JTAG ISP programmer

ISO JTAG ISP programmer
JTAG header pinout:
1: TCK
2: GND
3: TDO
4: VCC
5: TMS
6:
7: VCC
8:
9: TDI
10: GND
ISP Programming header pinout:
1: SCK
2: GND
3: MISO
4: VCC
5: RESET
6:
7: VCC
8:
9: MOSI
10: GND


Atmel AVR USBisp

The USBisp is another AVR programmer. Compared to the other freely available programmers out there mine has some advantages, I think:
  • USB-Interface
The USBisp is very interesting on notebooks where no serial or parallel port is available
  • STK500-Protocol

2010年10月8日 星期五

太陽循環衰退期

       太陽活動的衰退期不但不會如預期般造成地球冷卻,反而可能讓地球更溫暖。這項驚人的發現不僅徹底改變科學界對太陽週期的認識,還有助於解釋極端的地方天氣型態。這篇研究預定七日發表於「自然」期刊。

2010年10月6日 星期三

UEFI:-統一可延伸韌體介面

       未來電腦開機只要數秒即可完成!已完成適用電腦的「統一可延伸韌體介面」 (UEFI)技術,將取代長達25年之久的BIOS技術。

      未來透過UEFI 技術(統一可延伸韌體介面),從開機到使用電腦只需短短數秒鐘,根據UEFI 論壇主管多倫表示,「有了這項新技術,開始只需幾秒鐘,雖還不是即時,與傳統BIOS 速度比較,已經超出許多,」自1979年開始應用在開機的BIOS ,也將宣告功成身退。

2010年10月1日 星期五

好書報報-----看得到的化學



你知道香蕉也有放射性嗎?「鑽石恆久遠」只是一句並非事實的廣告詞嗎?「看得到的化學」書中除了有很多漂亮的化學元素照片,也有不少打破一般人迷思的內容。

磁鐵干擾大腦後頂葉皮質區腦細胞

美 國科學家近日發現,只要用一小塊磁鐵,就能將慣用右手的人瞬間變為左撇子。

AVR Studio 入門教學

from: http://www.avrtv.com/

     In this AVR TV In-depth, we present a basic, but close look into AVR Studio; the FREE development suite for Atmels 8-bit MCU range.
     NB! The flash videos are bit small for full-screen captures. So please download the H.264 file for a full 768×576 video. Find the source file for the LEDchaser here.

you can download the video here:
http://www.avrtv.com/mint/pepper/orderedlist/downloads/download.php?file=http%3A//www.avrtv.com/wp-content/avrtvIssues/avrtv_issue_009/avrtv_issue_009.mov

Arduino 入門教學

home page: http://arduino.tw/index.php
入門教學: http://arduino.tw/whatsarduino/novice.html

Procyon AVR C Library

C-Language Function Library for Atmel AVR Processors
  • AVRlib is a library of easy-to-use C functions for a variety of common and uncommon tasks using AVR processors.
  • The goal of AVRlib is to allow programmers to work quickly towards their end goal by reducing the time needed to write basic support functions and code.
  • Most AVRlib header (*.h) files have lengthy descriptions of how to use the supplied library functions. All code (*.c) files are heavily commented with additional information.
  • Documentation is still being improved and refined on many libraries. When getting familiar with a library, look first at the HTML docs and any example code that is available in the examples directory. Then look inside the *.h and *conf.h files, and then the *.c file for that library for more details and documentation.
  • Significant example code is included in avrlib.zip. The example code is heavily commented and strives to illustrate how to use various AVRlib function libraries.
  • Download AVRlib (with docs and code examples) 
  • On-line HTML Documentation

2010年9月28日 星期二

2010年9月26日 星期日

住得越高老得越快

美國一群物理學家最近經過精算發現,人在地球上住得越高,老得越快。雖然差別非常微小,但是足以驗證「愛因斯坦」相對論。

抗老長壽丸問世 染色體終端酵素

      俄羅斯科學家23日表示,能使人類壽命大大延長而且活得更健康的藥丸,可能在2012年問世。

領導研究計畫的莫斯科國立大學生物能量系教授史古拉喬夫(Vladimir Skulachev)表示,他們已發現強效抗氧化混合物,可延緩老化過程。

2010年9月23日 星期四

太陽風暴2013衝擊地球

 更新日期:2010/09/22 04:11
威力如100枚氫彈爆炸
〔編譯陳成良/綜合報導〕科學家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 had
to 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日 星期六

模仿植物光合作用 效率達40% MIT開發高效率太陽能電池

佈滿磷脂碟狀物(phospholipid disks)的碳奈米管,能讓太陽能電池具備自我修復(self-repairing)的功能,就像是植物行光合作用。這種光電化學(photoelectrochemical)太陽能電池是由美國麻省理工學院(MIT)的研究人員所開發,其能源轉換效率號稱可達到目前效能最佳之固態太陽能光電板的兩倍。

2010年9月6日 星期一

維生素

許多人會有補充維生素的習慣,然而補充劑量若超出每日所需標準,反而會造成危害。

注意藥物交互作用

有心血管疾病風險的病人,醫師可能處方抗血小板藥物(例如阿斯匹靈)或口服抗凝血劑(例如warfarin),以預防血栓堵住血管。

2010年9月2日 星期四

Bresenham 直線演算法 [布雷森漢姆直線演算法]



Bresenham 直線演算法是用來描繪由兩點所決定的直線的演算法,它會算出一條線段在 n 維光柵上最接近的點。這個演算法只會用到較為快速的整數加法、減法和位元移位,常用於繪製電腦畫面中的直線。是計算機圖形學中最先發展出來的演算法。


經過少量的延伸之後,原本用來畫直線的演算法也可用來畫圓。且同樣可用較簡單的算術運算來完成,避免了計算二次方程式或三角函數,或遞歸地分解為較簡單的步驟。


以上特性使其仍是一種重要的演算法,並且用在繪圖儀繪圖卡中的繪圖晶片,以及各種圖形程式庫。這個演算法非常的精簡,使它被實作於各種裝置的韌體,以及繪圖晶片的硬體之中。


「Bresenham」至今仍經常作為一整個演算法家族的名稱,即使家族中絕大部份演算法的實際開發者是其他人。該家族的演算法繼承了 Bresenham 的基本方法並加以發展,詳見參考資料。



演算方法



假設我們需要由 (x0, y0) 這一點,繪畫一直線至右下角的另一點(x1, y1),x,y分別代表其水平及垂直座標,並且 x1 - x0 > y1 - y0。在此我們使用電腦系統常用的座標系,即x座標值沿x軸向右增長,y座標值沿y軸向下增長。


因此x及y之值分別向右及向下增加,而兩點之水平距離為x1x0且垂直距離為y1-y0。由此得之,該線的斜率必定介乎於1至0之間。而此演算法之目的,就是找出在x0x1之間,第x行相對應的第y列,從而得出一像素點,使得該像素點的位置最接近原本的線。


對於由(x0, y0)及(x1, y1)兩點所組成之直線,公式如下:




因此,對於每一點的x,其y的值是




因為x及y皆為整數,但並非每一點x所對應的y皆為整數,故此沒有必要去計算每一點x所對應之y值。反之由於此線之斜率介乎於1至0之間,故此我們只需要找出當x到達那一個數值時,會使y上升1,若x尚未到此值,則y不變。至於如何找出相關的x值,則需依靠斜率。斜率之計算方法為m = (y1y0) / (x1x0)。由於此值不變,故可於運算前預先計算,減少運算次數。


要實行此演算法,我們需計算每一像素點與該線之間的誤差。於上述例子中,誤差應為每一點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時交換起點和終點來做到。


第二個擴展是繪畫斜率為負的直線。可以檢查y0y1是否成立;若該不等式成立,誤差超出0.5時y的值改為加-1。


第三,我們還需要擴展該演算法,使之可以繪畫斜率絕對值大於1的直線。要做到這點,我們可以利用大斜率直線對直線y=x反射是一條小斜率直線的事實,在整個計算過程中交換 xy,並一併將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直線演算法。


最佳化



以上的程序有一個問題:電腦處理浮點運算的速度比較慢,而errordeltaerr的計算是浮點運算。此外,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 1
Bresenham(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 2
void  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.5y2 = y1 + 1, 否則y2 = y1
  
我們已經能根據上面的兩個關係式寫出演算法, 不過為了消除乘法和浮點數, 我們將這兩個關係式兩端同時乘以2 * deltaX,   並且設e = 2 * deltaX * d, 則我們有
3) e2 =  e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)
4)
e1 + 2 * deltaY > deltaXy2 = 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 > deltaXy2 = 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
或者
我們根據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不成立. 即情況1y2 = 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不成立. 即情況2y2 = 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