خوارزمية رسم الخطوط

أبسط طريقة لرسم خط تتضمن حساب مواقع البكسل مباشرةً من معادلة الخط. مع إعطاء نقطة بداية${\displaystyle (x_{1},y_{1})}$ونقطة نهاية${\displaystyle (x_{2},y_{2})}$، تحقق النقاط الواقعة على الخط المعادلة${\displaystyle y=m(x-x_{1})+y_{1}}$، مع${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$يمثل ميل الخط. ويمكن رسم الخط بتقييم هذه المعادلة عبر حلقة بسيطة، كما هو موضح في الشفرة الزائفة التالية :

dx = x2 − x1 dy = y2 − y1 m = dy/dx لكل قيمة x من x1 إلى x2 ، قم بما يلي: ص = م × (س - س1) + ص1 plot(x, y)

هنا، تم ترتيب النقاط بالفعل بحيث${\displaystyle x_{2}>x_{1}}$.

هذه الخوارزمية بطيئة بشكل غير مبرر لأن الحلقة تتضمن عملية ضرب، وهي أبطأ بكثير من الجمع أو الطرح على معظم الأجهزة. يمكن تحقيق طريقة أسرع من خلال حساب الفرق بين خطوتين متتاليتين.

${\displaystyle y_{i+1}-y_{i}\!}$	${\displaystyle =(m(x_{i+1}-x_{1})+y_{1})-(m(x_{i}-x_{1})+y_{1})\!}$
	${\displaystyle =m(x_{i+1}-x_{i})\!}$
	${\displaystyle =m\!}$.

لذلك، يكفي أن نبدأ من تلك النقطة${\displaystyle (x_{1},y_{1})}$ثم قم بزيادة${\displaystyle y}$بواسطة${\displaystyle m}$مرة واحدة في كل تكرار للحلقة. تُعرف هذه الخوارزمية باسم محلل التفاضل الرقمي .

بسبب التقريب${\displaystyle y}$التقريب إلى أقرب عدد صحيح يعادل التقريب${\displaystyle y+0.5}$يمكن تجنب التقريب باستخدام متغير تحكم إضافي يتم تهيئته بالقيمة 0.5.${\displaystyle m}$تُضاف قيمة هذا المتغير إلى كل تكرار. ثم، إذا تجاوزت قيمة هذا المتغير 1.0،${\displaystyle y}$يتم زيادة قيمة المتغير بمقدار 1، بينما يتم إنقاص قيمة متغير التحكم بمقدار 1. يسمح هذا للخوارزمية بتجنب التقريب واستخدام عمليات الأعداد الصحيحة فقط. مع ذلك، بالنسبة للأسطر القصيرة، لا تعوض هذه الحلقة الأسرع عن عملية القسمة المكلفة.${\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$، وهو أمر لا يزال ضرورياً في البداية.

تعمل هذه الخوارزمية بشكل جيد عندما${\displaystyle dx\geq dy}$(أي أن الميل أقل من أو يساوي 1)، ولكن إذا${\displaystyle dx<dy}$(أي، ميل أكبر من 1)، يصبح الخط متفرقًا جدًا مع وجود العديد من الفجوات، وفي الحالة الحدية لـ${\displaystyle dx=0}$سيحدث استثناء القسمة على صفر .

في بعض الحالات، تواجه خوارزميات رسم الخطوط أحادية اللون مشاكل:

تعتمد خوارزمية غوبتا-سبرول على خوارزمية بريسنهام للخطوط ولكنها تضيف خاصية منع التعرج .

يمكن كتابة نسخة محسّنة من خوارزمية غوبتا-سبرول بلغة شبه رمزية كما يلي:

DrawLine(x1, x2, y1, y2) { x = x1; y = y1; dx = x2 − x1; dy = y2 − y1; d = 2 * dy − dx; // المُمَيِّز // المسافة الإقليدية للنقطة (س، ص) من الخط (المُوَجَّه) D = 0؛ // المسافة الإقليدية بين النقطتين (x1, y1) و (x2, y2) الطول = الجذر التربيعي (dx * dx + dy * dy)؛ sin = dy / length; cos = dx / الطول؛ بينما (س <= س٢) { IntensifyPixels(x, y − 1, D + cos); IntensifyPixels(x, y, D); IntensifyPixels(x, y + 1, D − cos); س = س + 1 إذا كان (d <= 0) { D = D + sin; د = د + 2 * د ص؛ } آخر { D = D + sin − cos; d = d + 2 * (dy − dx)؛ y = y + 1; } } }

تأخذ الدالة IntensifyPixels(x,y,r) تحويل الخط الشعاعي وتضبط شدة البكسل (x,y) بقيمة متعددة الحدود التكعيبية التي تعتمد على مسافة البكسل r من الخط.

قدّم بوير وبوردان خوارزمية تقريبية لتلوين البكسلات الواقعة مباشرةً أسفل الخط المثالي. ^{[ 1 ]} يُظهر الخط المُصوَّر بهذه الطريقة بعض الخصائص المميزة التي يُمكن الاستفادة منها. على سبيل المثال، في مثل هذه الحالات، تكون أجزاء الخط دورية. ينتج عن ذلك خوارزمية أسرع بكثير من الخوارزميات الدقيقة، خاصةً للخطوط الطويلة. ولا يظهر أي تراجع في الجودة إلا على الخطوط ذات الانحدار المنخفض جدًا.

إحدى الطرق البسيطة لتوازي عملية تحويل الخطوط أحادية اللون إلى صور نقطية هي السماح لخوارزميات رسم الخطوط المتعددة برسم وحدات بكسل متباعدة بمسافة محددة. ^{[ 2 ]} وهناك طريقة أخرى تتضمن تقسيم الخط إلى عدة أقسام متساوية الطول تقريبًا، ثم تخصيص كل قسم منها لمعالج مختلف لتحويله إلى صورة نقطية. تكمن المشكلة الرئيسية في إيجاد نقاط البداية والنهاية الصحيحة لهذه الأقسام.

توجد أيضًا خوارزميات لبنى المعالجات المتوازية الضخمة التي تضم آلاف المعالجات. في هذه الخوارزميات، يُخصص كل بكسل من شبكة البكسلات لمعالج واحد، والذي يقرر بدوره ما إذا كان ينبغي تلوين هذا البكسل أم لا. ^{[ 3 ]}

تم تطوير هياكل ذاكرة خاصة لتسريع الوصول إلى الذاكرة أثناء عملية التحويل إلى صورة نقطية. على سبيل المثال، قد تقسم هذه الهياكل الذاكرة إلى خلايا متعددة، تقوم كل منها برسم جزء من السطر بشكل مستقل. ^{[ 4 ]} كما يمكن دعم التحويل إلى صورة نقطية باستخدام تقنية منع التعرج بواسطة أجهزة مخصصة. ^{[ 5 ]}