ความแตกต่างระหว่าง DDA และ Bresenham's Algorithm ความแตกต่างระหว่าง
Digital Differential Algorithm (DDA) อัลกอริธึม Bresenhams เป็นอัลกอริทึมการวาดเส้นแบบดิจิตอลและใช้ในการวาดภาพคอมพิวเตอร์ ก่อนหน้านี้เราใช้เครื่องวิเคราะห์เชิงวิเคราะห์เพื่อคำนวณพิกเซลและทำให้ภาพวาดเส้นเป็นไปได้ แต่วิธีการวิเคราะห์เหล่านี้ไม่ได้ถูกต้องเช่นเดียวกับวิธีการแบบดิจิทัลที่มีการใช้อัลกอริทึมดิจิทัลเหล่านี้และในทุกสาขาวิชาเราได้คิดค้นวิธีการที่มีคุณภาพสูงกว่าในด้านกราฟิกคอมพิวเตอร์ด้วย การประดิษฐ์อัลกอริทึมเหล่านี้เป็นตัวอย่างที่สมบูรณ์แบบ ก่อนที่เราจะดำเนินการต่อไปให้เราดูแนวคิดเบื้องหลังอัลกอริทึมเหล่านี้ แม้ว่าจะดูเหมือนว่าไม่อยู่ในขอบเขตของการอภิปรายเราจำเป็นต้องชี้ให้เห็นถึงความแตกต่างพื้นฐานระหว่างทั้งสองฝ่าย หากคุณคุ้นเคยกับอัลกอริทึมจริงๆคุณสามารถข้ามไปใช้ความแตกต่างที่เกิดขึ้นได้ที่ส่วนท้ายของหน้านี้
อัลกอริทึม Differential ดิจิตอล (DDA) คืออะไร?
DDA ส่วนใหญ่จะใช้เพื่อวาดเส้นในกราฟิกคอมพิวเตอร์และใช้ค่าที่แท้จริงในขณะที่ทำนายค่าพิกเซลถัดไป สมมติว่าค่าพิกเซลเริ่มต้นเป็น (X0, Y0) (X0, Y0) และพิกเซลปลายทางเป็น (X1, Y1) (X1, Y1) เราจะเรียนรู้วิธีคำนวณค่าพิกเซลปลายทางจากค่าพิกเซลที่รู้จักกัน (X0, Y0) (X0, Y0) ตามด้านล่าง
- วิธีการคำนวณค่าจุดปลายทางโดยใช้ DDA?
ขั้นตอนที่ 1: ที่นี่เรามีอินพุท (X0, Y0) (X0, Y0) และเราควรระบุว่าเส้นทำงานขนานไปกับแกน x หรือแกน y. หากต้องการทราบว่าขณะนี้เราจะคำนวณความแตกต่างระหว่างค่าพิกเซลเริ่มต้นและค่าพิกเซลปลายทาง
dx = X1 - X0
dy = Y1 - Y0
ขั้นตอน -2: ขณะนี้เราได้ระบุความแตกต่างแล้วเราควรวาดเส้นตามแนวแกน x ถ้า 'dx' เป็นศูนย์ มิฉะนั้นเราควรวาดเส้นคู่ขนานกับแกน y นี่คือการคำนวณที่เกิดขึ้นจริงในแง่ของภาษาคอมพิวเตอร์
(dx)> สัมบูรณ์ (dy))ขั้นตอน = สัมบูรณ์ (dx);
อื่น
ขั้นตอน = สัมบูรณ์ (dy);
ขั้นตอนที่ 3:
ตอนนี้ถึงเวลาที่จะระบุพิกัด 'x' หรือพิกัดพิกัด 'y' เพื่อวาดเส้น ขั้นตอนการเพิ่ม x = dx / (float);
ขั้นตอน Y increment = dy / (float);
ขั้นตอน -4:
การคำนวณนี้จะต้องคำนวณจนกว่าเราจะไปถึงพิกเซลปลายทาง อัลกอริทึม DDA จะปัดเศษค่าพิกเซลให้เป็นค่าจำนวนเต็มใกล้ที่สุดในขณะทำการคำนวณ นี่คือตัวอย่างโค้ดของสิ่งที่เราได้กล่าวถึงในตอนนี้ สำหรับ (int v = 0; v { x = x + X เพิ่มขึ้น; y = y + Y เพิ่มขึ้น; putpixel (Round (x), Round (y)); } เรากำลังทำกับการวาดเส้นโดยใช้ DDA และให้เราย้ายไปที่ Bresenham ในขณะนี้! อัลกอริธึมของ Bresenham คืออะไร? ขั้นตอนที่ 1: อัลกอริทึมของ Bresenham ใช้พิกัดพิกเซลเริ่มต้นเป็น (x a + 1 , y a ) ขั้นตอน -2: จะคำนวณค่าพิกเซลถัดไปเป็น (x a + 1 , y a + 1 ) นี่คือค่าที่เพิ่มขึ้น และอัลกอริธึมคำนวณโดยการเพิ่มหรือลบสมการที่เกิดขึ้น อัลกอริธึมนี้คำนวณค่าที่ถูกต้องโดยไม่ต้องปัดเศษและดูง่ายขึ้นเช่นกัน! ตัวอย่างเชิงตัวเลขของอัลกอริทึมของ Bresenham: ให้ข้อมูล (x1, y1) = (0, 0) และ (x2, y2) = (-8, -4) ขณะนี้ให้คำนวณค่าความแตกต่างดังนี้ Δx = x2-x1 = -8-0 = 8 ดังนั้นค่าที่เพิ่มขึ้นสำหรับ x = Δx / x2 = 8 / -8 = -1 Δy = y2-y1 = -4-0 = 4 ดังนั้นค่าที่เพิ่มขึ้นสำหรับ y = Δy / y2 = 4 / -4 = -1 Decision Variable = e = 2 * (Δy) - (Δx) ดังนั้น e = 2 * (4) - (8) = 8-8 = 0 ด้วยการคำนวณดังกล่าวให้ เรากำหนดค่าที่เป็นผลลัพธ์ ค่าของพิกัด y จะถูกปรับตามตัวแปรการตัดสินใจและเรากำลังละเว้นการคำนวณที่นี่ พิกเซล ไม่มีการใช้ค่าคงที่คงที่ในจุดคงที่ของ Bresenham ใช้ในการคำนวณเลขคณิต อัลกอริทึมของ Bresenham ใช้เลขคณิตจำนวนเต็มซึ่งแตกต่างจาก DDA ประเภทของการใช้งาน: DDA จะแก้สมการเชิงอนุพันธ์ด้วยการคูณและการหาร คุณสังเกตเห็นขั้นตอนเดียวกันที่นี่ x ขั้นตอนที่เพิ่มขึ้น = dx / (float) อัลกอริธึมของ Bresenham ใช้การบวกและการลบและคุณสามารถสังเกตได้ที่นี่ในสมการคำนวณสมการพิกัดถัดไป (x a + 1 a + 1 ) เลขคณิตที่ง่ายขึ้นใน Bresenham เมื่อเทียบกับ DDA ประสิทธิภาพ: ตามที่เราได้กล่าวไว้ก่อนหน้านี้อัลกอริธึมของ Bresenham ใช้เลขคณิตที่เรียบง่ายกว่า DDA และส่งผลให้ได้ผลลัพธ์ที่มีประสิทธิภาพ ความเร็ว: ความถูกต้อง: DDA มีความสามารถในการวาดวงกลมและเส้นโค้งนอกเหนือจากเส้นวาด อัลกอริธึมของ Bresenham ยังมีความสามารถในการวาดภาพทั้งหมดที่กล่าวข้างต้นและความถูกต้องของมันสูงกว่าของ DDA จริงๆ ในทำนองเดียวกันอัลกอริทึมของ Bresenham สามารถนำมาใช้กับเส้นโค้งที่มีประสิทธิภาพมากกว่าที่ผลิตโดย DDA ทั้งสองขั้นตอนสามารถวาดรูปสามเหลี่ยมและรูปหลายเหลี่ยมได้เช่นกัน ราคาแพงหรือไม่? ซึ่งเป็นอัลกอริทึมที่ดีที่สุด? ลองดูความแตกต่างในรูปแบบตาราง ความแตกต่างใน อัลกอริทึม Differential ดิจิตอลนอกจากนี้ยังเป็นอัลกอริทึมการวาดเส้นแบบดิจิทัลและถูกคิดค้นโดย Bresenham ในปี 1962 ด้วยเหตุนี้จึงมีชื่อเดียวกัน อัลกอริทึมนี้มีความแม่นยำมากขึ้นและใช้การลบและบวกกับการคำนวณค่าพิกเซลในขณะวาดเส้น ความถูกต้องของอัลกอริทึมของ Bresenham มีความน่าเชื่อถือในขณะที่วาดเส้นโค้งและแวดวงด้วย ลองดูวิธีการทำงานของอัลกอริธึมนี้
x
y
ตัวแปรการตัดสินใจ
(0, 0)
0
0
0
(- 1, 0)
1
0
ค่า
(- 2, -1)
-2
-1
0
(- 3, -1)
-3 < -1
ค่า
(- 4, -2)
-4
-2
0
(- 5, -2)
-5 > -2
ค่า
(- 6, -3)
-6
-3
0
(- 7, -3)
-7
-3
ค่า
(- 8, -4)
-8
-4
0
ความแตกต่างระหว่างอัลกอริธึมของ DDA และ Bresenham
:
การคำนวณเลขคณิต:
DDA ใช้ค่าจริงในการคำนวณโดยใช้จุดลอยตัว ค่าพิกเซลหรือจุดถัดไปจะถูกกำหนดด้วยสมการเชิงอนุพันธ์ ขั้นตอนที่เพิ่มขึ้น x = dx / (float)
