خوارزمية مربع الماس

خريطة ارتفاع

خريطة ارتفاع بعد أن حولت القيم إلى الفضاء الثلاثي الأبعاد

خوارزمية مربع الماس (بالإنجليزية: Diamond-square algorithm)‏ هي طريقة تستخدم في إنتاج خرائط ارتفاع heightmaps ذات درجة واقعية كبيرة من أجل تطبيقات الرسوميات الحاسوبية.^[1][2][3] تعتبر على أنها التطبيق الثلاثي الأبعاد لخوارزمية تشرد نقطة الوسط midpoint displacement algorithm التي تنتج تضاريس ثنائية الأبعاد.

الخوارزمية

• ضع قيمة ارتفاع لكل زاوية من زوايا مستطيل (صورة).
• قسم المستطيل إلى أربع أرباع مستطيل، وضع قيمة ارتفاع لهذه النقاط تساوي المتوسط الحسابي لقيم ارتفاعات الزوايا التي ترتبط بها.

${\displaystyle {\begin{bmatrix}0&2\\4&8\\\end{bmatrix}}}$ سيكون له قيم الارتفاع التالية

${\displaystyle {\begin{bmatrix}0&(0+2)/2\\(0+4)/2&(0+2+4+8)/4\\\end{bmatrix}}={\begin{bmatrix}0&1\\2&3.5\\\end{bmatrix}}}$

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

• يعاد بشكل تكراري تقسيم كل مستطيل ناتج إلى مستطيلات أصغر بحسب القاعدة في الأعلى. في النهاية ستكون صغيرة جداً حيث تعطي الفرق الواضح. تتوقف الخوارزمية عند الحاجة ومن ثم تحول قيم الارتفاع في الصورة إلى قيم ارتفاع في الفضاء الثلاثي الأبعاد.

تطبيقات

تستخدم هذه الخوارزمية في الحصول على تضاريس واقعية، ويوجد العديد من التطبيقات لها في الرسوميات الحاسوبية مثل برنامج برايس.

مراجع

1. Peitgen، Heinz-Otto, Dietmar Saupe (1988). The Science of fractal images. New York: Springer-Verlag. ISBN:0-387-96608-0.
2. Miller، Gavin S. P. (أغسطس 1986). "The definition and rendering of terrain maps". ACM SIGGRAPH Computer Graphics. ج. 20 ع. 4: 39–48. DOI:10.1145/15886.15890.
3. Fournier، Alain؛ Fussell، Don؛ Carpenter، Loren (يونيو 1982). "Computer rendering of stochastic models". Communications of the ACM. ج. 25 ع. 6: 371–384. DOI:10.1145/358523.358553.