خوارزمية Bresenham: كيف يُرسم الخط المستقيم على شبكة البكسل بدقة وسرعة

خوارزمية Bresenham هي طريقة لرسم خط مستقيم بين نقطتين على شاشة مكوّنة من بكسلات، باستخدام عمليات حسابية على الأعداد الصحيحة فقط (جمع وطرح ومقارنة) دون أي كسور عشرية أو قسمة. جوهرها بسيط: الشاشة شبكة مربّعات، والخط المثالي بين نقطتين نادراً ما يمرّ بمراكز البكسلات تماماً، فتقرّر الخوارزمية عند كل خطوة أيّ بكسل هو الأقرب إلى الخط الحقيقي فتُلوّنه. هذا الاختيار الذكي، المبني على الأعداد الصحيحة، هو ما يجعلها سريعة جداً ودقيقة، ولهذا ما زالت مستخدمة منذ عام 1962 حتى اليوم في كروت الرسوميات وأنظمة التشغيل والألعاب.

طوّرها جاك بريزنهام أثناء عمله في شركة IBM لتشغيل راسمات (plotters) رقمية، والفكرة التي جعلتها ثورية أنها تخلّصت من العمليات البطيئة على الأعداد العشرية التي كانت مكلفة على معالجات ذلك الزمن، وما زالت أبطأ نسبياً حتى الآن.

لماذا لا نرسم الخط بالمعادلة مباشرة؟

معادلة الخط المعروفة هي y = m·x + b. يمكنك نظرياً أن تزيد x خطوة خطوة وتحسب y ثم تقرّب الناتج لأقرب بكسل. المشكلة أن هذا يتطلب ضرباً في ميل كسري (m) وعملية تقريب عند كل بكسل، وهي عمليات على أعداد عشرية بطيئة، وقد تتراكم أخطاء التقريب على الخطوط الطويلة. عبقرية Bresenham أنها تصل إلى النتيجة نفسها بجمع وطرح أرقام صحيحة فقط.

الفكرة الأساسية: متغيّر القرار

لنفترض خطاً يتجه لليمين بميل بين 0 و1 (أي أن التغيّر الأفقي أكبر من الرأسي). نتحرك بكسلاً واحداً في اتجاه x عند كل خطوة، ويبقى السؤال الوحيد: هل نبقى على السطر الرأسي نفسه (y كما هو) أم نصعد بكسلاً واحداً (y+1)؟

تحتفظ الخوارزمية بقيمة تُسمى متغيّر القرار (أو خطأ التتبع) تقيس بُعد الخط الحقيقي عن البكسل الذي رسمناه للتو. إذا تجاوز هذا المتغيّر حدّاً معيّناً، فهذا يعني أن الخط الحقيقي صعد بما يكفي لنرفع y، وإلا نبقى في مكاننا. والأجمل أن تحديث هذا المتغيّر يتم بإضافة ثوابت صحيحة محسوبة مسبقاً، لا أكثر.

خطوات الخوارزمية بالأرقام

لخط من النقطة (x0, y0) إلى (x1, y1) بميل بين 0 و1:

1. احسب الفرقين: dx = x1 − x0 و dy = y1 − y0.
2. احسب متغيّر القرار الابتدائي: p = 2·dy − dx.
3. ابدأ من النقطة الأولى (x0, y0) ولوّنها.
4. عند كل خطوة، زد x بمقدار 1، ثم:
   • إذا كان p < 0: أبقِ y كما هو، وحدّث p ← p + 2·dy.
   • إذا كان p ≥ 0: زد y بمقدار 1، وحدّث p ← p + 2·dy − 2·dx.
5. لوّن البكسل الجديد، وكرّر حتى تصل إلى x1.

لاحظ أن كل العمليات جمع وطرح لأعداد صحيحة، والثابتان 2·dy و(2·dy − 2·dx) يُحسبان مرة واحدة فقط قبل بدء الحلقة.

مثال سريع

لخط من (0, 0) إلى (5, 2): dx = 5، dy = 2، وقيمة p الابتدائية = 2·2 − 5 = −1.

• عند x=0: نرسم (0,0). p = −1 (سالب) ⇐ نضيف 2·dy=4 فيصبح p = 3.
• عند x=1: p موجب ⇐ نرسم (1,1) ونضيف (4 − 10) = −6 فيصبح p = −3.
• عند x=2: p سالب ⇐ نرسم (2,1) ونضيف 4 فيصبح p = 1.
• عند x=3: p موجب ⇐ نرسم (3,2) ونضيف −6 فيصبح p = −5… وهكذا حتى (5,2).

النتيجة سلسلة بكسلات متدرّجة تقارب الخط المثالي بأقل انحراف ممكن.

Bresenham أم DDA؟

الخوارزمية المنافسة الأشهر هي DDA (المحلّل التفاضلي الرقمي). هذا الجدول يوضّح الفرق:

المعيار	Bresenham	DDA
نوع الحساب	أعداد صحيحة فقط	أعداد عشرية (كسور)
السرعة	أسرع	أبطأ بسبب العمليات العائمة
الدقة	خالية من أخطاء التراكم	قد تتراكم أخطاء التقريب
التعقيد	جمع وطرح ومقارنة	ضرب وتقريب عند كل خطوة
الاستخدام النموذجي	العتاد والأنظمة منخفضة الموارد	أكواد تعليمية ومرونة أعلى

الخلاصة العملية: عندما تكون السرعة والدقة أولوية (وهي كذلك في العتاد)، تتفوّق Bresenham بوضوح.

أين تُستخدم فعلياً؟

الاستخدام الأصلي هو رسم الخطوط، لكن الفكرة نفسها امتدّت إلى رسم الدوائر والأقواس عبر ما يُعرف بخوارزمية النقطة الوسطى (Midpoint Circle Algorithm) المبنية على المنطق ذاته. تجدها في محرّكات الألعاب، وبرامج التصميم الهندسي CAD، وطبقات الرسم في أنظمة التشغيل، وحتى في بعض تطبيقات معالجة الصور وتتبّع المسارات في الروبوتات.

نصيحة عملية وخطأ شائع

عند تطبيق الخوارزمية بنفسك، الخطأ الأكثر شيوعاً هو نسيان الحالات الثماني (octants). الخطوات أعلاه تفترض ميلاً بين 0 و1 واتجاهاً لليمين. أما إذا كان الخط شديد الانحدار (الميل أكبر من 1) فيجب تبديل دوري x و y، وإذا كان يتجه لليسار أو للأسفل فيجب عكس اتجاه الزيادة. الحل الأنيق هو كتابة النسخة الأساسية مرة واحدة ثم التعامل مع بقية الاتجاهات بمرآة رياضية (تبديل الإشارات والمحاور)، بدلاً من كتابة ثماني حالات منفصلة تتكرّر فيها الأخطاء.

الأسئلة الشائعة

هل خوارزمية Bresenham دقيقة تماماً؟ هي تختار في كل خطوة البكسل الأقرب للخط المثالي، فالنتيجة أدقّ تقريب ممكن على شبكة بكسلات؛ لكنها لا ترسم خطاً "أملس" ناعم الحواف لأن ذلك يتطلب تنعيماً (anti-aliasing) وهو موضوع مختلف.

ما الفرق بينها وبين تنعيم الحواف (Anti-aliasing)؟ Bresenham تقرّر أيّ البكسلات تُلوَّن بلون واحد صريح. أما التنعيم فيستخدم تدرّجات لونية لإخفاء تدرّج الحواف، وهو أثقل حسابياً ويُبنى فوق فكرة رسم الخط لا بدلاً منها.

هل تعمل مع الدوائر والمنحنيات؟ نعم عبر امتدادها المعروف بخوارزمية النقطة الوسطى للدوائر، الذي يستعمل نفس مبدأ متغيّر القرار الصحيح لتقرير البكسل التالي على محيط الدائرة.

لماذا ما زالت مهمة رغم قِدَمها؟ لأن اعتمادها على الأعداد الصحيحة يجعلها مثالية للعتاد والأنظمة محدودة الموارد، وما زال منطقها حاضراً في مكتبات الرسم منخفضة المستوى وفي المتحكّمات الدقيقة والشاشات الصغيرة حتى اليوم.