ตอน : มาเข้าใจอัลกอริทึมการวาดเส้นตรงกันดีกว่า !!

เคยมีเพื่อน ๆ ถามผมว่าผมกำลังทำพล็อตเตอร์โดยใช้สเต็ปเปอร์มอเตอร์สองตัว ในแนวตั้งและแนวนอน และสามารถต่อมันเสร็จเรียบร้อยแล้ว เหลือเพียง อยากจะทดลองให้มันวาดเส้นเอง ทำอย่างไรดี.. !!

ผมคิดว่าไอเดียนี้หลายคนคงอยากจะทราบ ดังนั้น วันนี้เราจะไปเข้าใจหลักการทำงานกันดีกว่าครับ !!

ความจริงแล้วการวาดเส้นตรงนั้น เป็นทฤษฎีของวิชาคอมพิวเตอร์กราฟิก มีทั้งหมด 3 อัลกอริทึม
1.สมการเส้นตรงธรรมดา
2.DDA Algorithm (Digital Differential Analyzer)
3. Bresenham's Line Algorithm

สองวิธีแรกใช้เวลาในการประมวลผลนานครับ ถ้าเขียนควบคุมด้วยคอนโทรลเลอร์ก็จะเป็นวิธีที่ต้องทำงานกันหนักหน่อย เพราะมีทั้งการคูณการหารอยู่ในนั้น..

ผมแนะนำให้ใช้วิธีที่สาม พัฒนาโดย Bresenham ปัจจุบันนี้ยังมีชีวิตนะครับ..
ท่านนี้ใช้วิธีการอันชาญฉลาด โดยให้เหลือเพียงการบวก และการคูณด้วยสอง ซึ่งเป็นปฏิบัติการที่ทำงานได้เร็วมากของหน่วย ALU และเนื่องจากการคูณด้วยสอง ก็คือการทำ Shift Left (เลื่อนบิตไปทางซ้ายเท่านั้น)
เรามาทดลองศึกษาตัวอย่างคำสั่งต่อไปนี้ครับ..
>>> def line_bresenham(xa,ya,xb,yb):
dx = abs(xa-xb)
dy = abs(ya-yb)
p = 2*dy-dx
twoDy = 2*dy
twoDyDx = 2*(dy-dx)
if(xa>xb):
x = xb
y = yb
xEnd = xa
else:
x = xa
y = ya
xEnd = xb
print "เขียนจุดลงบนพิกัด (%d,%d)"%(x,y)
while (x<xEnd):
x+=1
if(p<0):
p+=twoDy
else:
y+=1
p+=twoDyDx
print "เขียนจุดลงบนพิกัด (%d,%d)"%(x,y)

จากนั้นถ้าเราต้องการวาดเส้นตรงจากตำแหน่ง (25,14) ไปยังตำแหน่ง (32,19) สามารถทำได้โดยใช้คำสั่งต่อไปนี้
>>> line_bresenham(25,14,32,19)
เขียนจุดลงบนพิกัด (25,14)
เขียนจุดลงบนพิกัด (26,15)
เขียนจุดลงบนพิกัด (27,15)
เขียนจุดลงบนพิกัด (28,16)
เขียนจุดลงบนพิกัด (29,17)
เขียนจุดลงบนพิกัด (30,18)
เขียนจุดลงบนพิกัด (31,18)
เขียนจุดลงบนพิกัด (32,19)

เมื่อนำเส้นตรงไปวาดลงบนอุปกรณ์ใด ๆ ที่ใช้ระบบโคออดิเนตแบบคาร์ทีเซียน (x,y) จะได้เส้นตรงตามที่ต้องการครับ..

สำหรับวันนี้ผมขอนำเสนอหลักการวาดเส้นด้วยอัลกอริทึมของ Bresenham เพียงเท่านี้ครับ.. หวังว่าเพื่อน ๆ จะได้เป็นแนวทางในการพัฒนาต่อไป สำหรับวันนี้ขอกล่าวคำว่า .. สวัสดีครับ....บบ !!