CS351 Computer Graphics

1.1. Slope-Intercept formula Line Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} y & = M x + B \\ & where: \\ M & = \frac{y_2 - y_1}{x_2 - x_1} \\ B & = y_1 - M x_1 \end{split} \end{equation} $$

خطوات الحل

يتم حساب قيمة ميل الخط المستقيم (M) وقيمة نقطة تفاطع الخط مع المحور الرأسي (B) ثم توليد النقاط عن طريق التعويض في المعادلة ابتداء نقطة البداية حتي نقطة النهاية
العيوب: أستخدام العمليات العشرية

Code sample

      
          float x1,x2,y1,y2,m,b,i,y;
          x1 = -400;
          x2 =  100;
          y1 =  120;
          y2 =  200;
          m  =  (y2 - y1) / (x2 - x1);
          b  =  y1 - (m * x1);

            glBegin(GL_POINTS);

                for(i = x1; i <= x2; i += 0.1)
                {
                    y = m * i + b;
                    glVertex2i(i,y);
                }
                
            glEnd();

1.2. Parametric Form Line Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} x & = x_1 + t (x_2-x_1) \\ y & = y_1 + t (y_2-y_1) \\ & where: \\ & 0 \leq t \leq 1 \end{split} \end{equation} $$

خطوات الحل

يتم توليد النقاط بالتعويض في كلا المعادلتين بجميع القيم للمتغير (t) من 0 حتي 1
ملحوظة: عدد النقاط المولدة هو خارج قسمة 1 علي معدل زيادة المتغير (t) أي اذا كان المتغير (t) يزيد بمعدل 0.01 فأن عدد النقاط يساوي 1\0.01 أي 100 نقطة
العيوب: أستخدام العمليات العشرية

Code sample

      
        float x1,x2,y1,y2,x,y,t;
        x1 = -400;
        x2 = -100;
        y1 =  120;
        y2 =  200;

          glBegin(GL_POINTS);

              for(t = 0; t <= 1; t += 0.001)
              {
                  x = x1 + t * (x2 - x1);
                  y = y1 + t * (y2 - y1);
                  glVertex2i(x,y);
              }

          glEnd();

1.3. Digital Differential Analyzer Line Drawing Algorithm (DDA)

Algorithm Equation

$$ \begin{equation} \begin{split} x_{inc} & = \frac{\Delta x}{n} \\ y_{inc} & = \frac{\Delta y}{n} \\ & where: \\ n & = max(\Delta x, \Delta y) \end{split} \end{equation} $$

خطوات الحل

أولا يتم حساب متغير عدد الخطوات (n) وهو القيمة الاكبر بين معدل التغير الرأسي والأفقي (dx,dy) ثم يتم حساب معامل زيادة لكل من المحورين الافقي والرأسي (X_inc, Y_inc) كما بالمعادلة ثم اضافة معامل الزيادة الافقي (X_inc) الي قيمة ال (x) السابقة, وبالمثل مع المحور الرأسي ثم نبدأ من نقطة البداية حتي بلوغ نقطة النهاية
ملحوظة: يجب مراعاة التقريب لاقرب رقم صحيح عقب كل اضافة
العيوب: أستخدام 4 عمليات عشرية و 2 صحيحة
مثال للجدول:

i	X	Y	Round(X)	Round(Y)

Code sample

      
        float x1,x2,y1,y2,x,y,dx,dy,steps,Xinc,Yinc;
        x1 = -400;
        x2 =  100;
        y1 =  120;
        y2 =  200;
        x  = x1;
        y  = y1;
        dx = x2 - x1;
        dy = y2 - y1;
        steps = fmax(dx,dy);
        Xinc = dx / steps;
        Yinc = dy / steps;


          glBegin(GL_POINTS);

              for(int i = 0; i <= steps; i++)
              {
                  glVertex2i(round(x),round(y));
                  x += Xinc;
                  y += Yinc;
              }

          glEnd();

1.4. Bresenham's Line Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} P_0 & = 2\Delta y - \Delta x \\ P_k & = \begin{cases} < 0 , & P_{k+1} = P_k + 2\Delta y \\ & (x_k + 1, y_k) \\ \geq 0 , & P_{k+1} = P_k + 2\Delta y - 2\Delta x \\ & (x_k + 1, y_k + 1) \end{cases} \end{split} \end{equation} $$

خطوات الحل

أولا يتم حساب القيمة الأبتدائية للمتغير (P) ثم وضع النقطة الاولي هي نقطة البداية
نحسب قيمة المتغير (P) الجديدة بناء علي القيمة السابقة للمتعير اذا كانت اقل من الصفر او عير ذلك كما موضح بالمعادلة, ثم نضع قيمة المتعير (y) الجديدة بناء علي القيمة السابقة للمتغير (p) اذا كانت القيمة موجبة نضيف الي المتعير (y) واحد صحيح واذا كانت سالبة نضغ قيمة المتعير (y) كما هي.
ملحوظة: دائما نضيف لقيمة المتعير (x) واحد صحيح بينما نحسب القيم الجديدة لكل من المتعير (y) والمتغير (p) بناء علي القيم السابقة ولذلك تعتمد الخوارزمية علي مبدأ ال Parameter Desicion.
المميزات: أستخدام عمليات علي ارقام صحيحة فقط لا غير, بالاضافة الي امكانية أستخدام التحويلات الرياضية لرسم الخط المستقيم في اي جزء من الشاشة كما يلي
خطوات رسم أي خد علي الشاشة: القاعدتين المستخدمتين لرسم الخط المستقيم في اي جزء من الشاشة

القاعدة الاولي: حساب القيمة المطلقة لخارج قسمة معدل التغير الرأسي dy علي معدل التغير الافقي dx أي |dy/dx|
الحالة الاولي اذا كان الناتج اصغر من الواحد الصحيح نكمل باقي الخطوات
الحالة الثانية اذا كان الناتج اكبر من الواحد الصحيح سوف نقوم بتبديل كل من قيم ال (x) مع قيم ال (y)، أي سوف نرسم من النقطة (y1,x1) الي النقطة (y2,x2) بدلا من النقطة (x1,y1) الي النقطة (x2,y2) وبعد توليد النقاط نقوم بتبديل نقاط ال (x) مع نقاط ال (y) مجددا

القاعدة الثانية نقوم بحساب قيمة معدل تغير كل من المحورين
الحالة الاولي اذا كانت القيم موجبة او اكبر من الصفر نكمل باقي الخطوات
الحالة الثانية اذا كان احدهما سالب او اصغر من الصفر نقوم بوضع قيمة معدل التغير لهذا المحور بالقيمة الموجبة له ونستعوض عن الاضافة في هذا الاتجاح بالطرح، علي سبيل المثال بدلا من اضافة واحد الي الي المتغير (y) في حالة قيمة المتغير (p) أكبر من الصفر سوف نقوم بطرح واحد صحيح من المتغير (y) اذا كانت قيمة المتغير (p) اكبر من الصفر في حال كان معدل التغير الرأسي (dy) سالب او اصغر من الصفر
مثال للجدول:

K	P	X	Y

Code sample

      
        void bresenham(int x1,int y1,int x2,int y2)
        {
            int dx,dy,p0,xk,yk,Xinc,Yinc;
            dx = x2 - x1;
            dy = y2 - y1;

            Xinc = (dx >= 0)? 1 : -1;
            Yinc = (dy >= 0)? 1 : -1;

            dx = abs(dx);
            dy = abs(dy);

            xk = x1;
            yk = y1;

            if (dy < dx)
            {
                p0 = 2 * dy - dx;
                setPixel(x1,y1);

                for (int k = x1; k < x2; k++)
                {
                    if (p0 < 0)
                    {
                        setPixel(++xk, yk);
                        p0 += 2 * dy;
                    }
                    else
                    {
                        setPixel(++xk, yk += Yinc);
                        p0 += 2 * dy - 2 * dx;
                    }
                }
            }
            else
            {
                p0 = 2 * dx - dy;
                setPixel(x1,y1);

                for (int k = y1; k < y2; k++)
                {
                    if (p0 < 0)
                    {
                        setPixel(xk, ++yk);
                        p0 += 2 * dx;
                    }
                    else
                    {
                        setPixel(xk += Xinc, ++yk);
                        p0 += 2 * dx - 2 * dy;
                    }
                }
            }
        }

2.1. Basic equation Circle Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} y & = y_c \pm \sqrt{r^2 - (x-x_c)^2} \\ & where: \\ & -r \leq x \leq r \\ & center = (x_c,y_c) \end{split} \end{equation} $$

خطوات الحل

أولا يتم توليد قيم المتعير (x) ابتداء من سالب نصف القطر (r-) حتي موجب نصف القطر (r) والتعويض في المعادلة لتوليد نقط (y).
العيوب: أستخدام عمليات عشرية بالاضافة الي الجزر التربيعي والنربيع

Code sample

      
        float x,root,xc = 0,yc = 0,r = 100;

        glBegin(GL_POINTS);

            for(x = -r; x <= r; x += 0.1)
            {
                root = yc + sqrt(r*r - (x-xc)*(x-xc));
                glVertex2i(x,yc - root);
                glVertex2i(x,yc + root);
            }

        glEnd();

2.2. Trigonometric formula Circle Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} x & = r * \cos (\theta) \\ y & = r * \sin (\theta) \\ & where: \\ & 0 \leq \theta \leq 2\pi \end{split} \end{equation} $$

خطوات الحل

اولا يتم توليد قيم الزاوية ثيتا ابتداء من الصفر حتي (2pi) ويتم حساب قيمة حاصل ضرب نصف القطر (r) في كل من جيب الزاوية (sin) وحيب تمام الزاوية (cos) وتوليد نقط الدائرة كما بالمعادلة
العيوب: أستخدام الدوال المثلثية مثل جيب الزاوية وجيب تمام الزاوية

Code sample

      
        float x,y,i,r = 250;
    
            glBegin(GL_POINTS);
    
                for(i = 0; i <= M_PI * 2; i += 0.001)
                {
                    x = r * cos(i);
                    y = r * sin(i);
                    glVertex2i(x,y);
                }

            glEnd();

2.3. Midpoint Circle Drawing Algorithm

Algorithm Equation

$$ \begin{equation} \begin{split} P_0 & = 1 - r \\ P_k & = \begin{cases} < 0 , & P_{k+1} = P_k + 2x_{k+1} + 1 \\ & (x_k + 1, y_k) \\ \geq 0 , & P_{k+1} = P_k + 2x_{k+1} + 1 - 2y_{k+1}\\ & (x_k + 1, y_k - 1) \end{cases} \end{split} \end{equation} $$

خطوات الحل

أولا نقوم بحساب القيمة الابتدائية للمتغير (p) ثم نقوم بتحديد القيمة التالية لكل من متغير المحور الأفقي (y) ومتغير المحور الرأسي (x) وقيمة المتغير (p) التالية من خلال قيمة المتغير (p) الحالية.
الحالة الاولي اذا كانت قيمة (p) الحالية سالبة او اقل من الصفر نضيف الي قيمة المتغير (x) واحد صحيح
الحالة الثانية اذا كانت قيمة (p) الحالية موجبة او اكبر من الصفر نضيف الي كل من المتغيرين (x) و (y) واحد صحيح
بعد توليد النقاط نقوم بتكرار النقاط 4 مرات ثم نقوم بتبديل نقاط ال (x) وال (y) ثم تكرار النقاط 4 مرات وتطبيق قاعدة الاشارات علي ال 8 مجموعات.
ملحوظة: دائما ما نضيف واحد صحيح الي قيمة المتغير (x) ويكون شرط التوقف عندما تكون قيمة المتغير (x) التالية (x_k+1) اكبر من او تتساوي مع قيمة المتغير (y) التالية (y_k+1)، وايضا تعتمد هذه الخوارزمية علي مبدأ Parameter Desicion
مثال للجدول:

K	P	X_k+1	Y_k+1	2*X_k+1	2*Y_k+1

Code sample

      
        void plotOn8Octants(ScreenPointStructure center,ScreenPointClass point)
        {
            setPixel(center.x + point.getX(),
                     center.y + point.getY());
            setPixel(center.x - point.getX(),
                     center.y + point.getY());
            setPixel(center.x + point.getX(),
                     center.y - point.getY());
            setPixel(center.x - point.getX(),
                     center.y - point.getY());

            setPixel(center.x + point.getY(),
                     center.y + point.getX());
            setPixel(center.x - point.getY(),
                     center.y + point.getX());
            setPixel(center.x + point.getY(),
                     center.y - point.getX());
            setPixel(center.x - point.getY(),
                     center.y - point.getX());
        }

      
        void midPointAlgorithm(ScreenPointStructure center,GLint radius)
        {
            ScreenPointClass currentPoint;
            currentPoint.setX(0);
            currentPoint.setY(radius);
            plotOn8Octants(center,currentPoint);
        
            GLint p = 1 - radius;
            while(currentPoint.getX() < currentPoint.getY())
            {
                currentPoint.incrementX();
                if (p < 0)
                {
                    p += 2*currentPoint.getX() + 1;
                }
                else
                {
                    currentPoint.decrementY();
                    p += 2*currentPoint.getX() + 1 - 2*currentPoint.getY();
                }
                plotOn8Octants(center,currentPoint);
            }
        }

3.1. Midpoint Ellipse Drawing Algorithm

$$ \begin{equation} \text{General Equation for Ellipse} \\ 1 = (\frac{x-x_c}{r_x})^2 + (\frac{y-y_c}{ry})^2 \end{equation} $$

Algorithm Equation

$$ \begin{equation} \begin{split} & Region 1 \\ P1_0 & = r_y^2 - r_x^2 r_y + \frac {1}{4} r_x^2 \\ P1_k & = \begin{cases} < 0 , & P1_{k+1} = P1_k + 2r_{y}^2 x_{k+1} + r_{y}^2 \\ & (x_k + 1, y_k) \\ \geq 0 , & P1_{k+1} = P1_k + 2r_{y}^2 x_{k+1} -2r_x^2 y_{k+1}+ r_{y}^2 \\ & (x_k + 1, y_k - 1) \end{cases} \\ \\ & Region 2 \\ P2_0 & = r_y^2 (x_0 + \frac{1}{2})^2 + r_x^2(y_0 - 1)^2 - r_x^2 r_y^2 \\ P2_k & = \begin{cases} > 0 , & P2_{k+1} = P2_k - 2r_x^2 y_{k+1} + r_x^2 \\ & (x_k, y_k - 1) \\ \leq 0 , & P2_{k+1} = P2_k + 2r_{y}^2 x_{k+1} -2r_x^2 y_{k+1}+ r_x^2 \\ & (x_k + 1, y_k - 1) \end{cases} \\ \end{split} \end{equation} $$

خطوات الحل

تعتمد الطريقة علي رسم الربع الموجب في القطاع الناقص ثم استخدام خواص التماثل لرسم باقي ارباع القطاع الناقص يتكون كل ربع من منطقتين الاولي (Region 1) والثانية (Region 2) ولكل منهما قوانين في الرسم كما موضح

المنطقة الاولي (Region 1) نبدأ من النقطة (ry,0) ونقوم بحساب القيمة الابتدائية للمتغير الاول (p1) نستمر في حساب القيم الجديدة لكل من المتغير (y) والمتغير (p1) طبقا للمعادلة الموضحة بينما قيمة المتغير (x) دائما يزداد بمقدار واحد صحيح حتي الوصول لشرط التوقف وهو (حاصل ضرب تربيع نصف القطر الرأسي (ry) في القيمة التالية للمتغير (x)) اكبر من او يساوي (حاصل ضرب تربيع نصف القطر الافقي (rx) في القيمة التالية للمتغير (y)) اي (rx*rx*y_k+1) =< (ry*ry*x_k+1)

المنطقة الثانية (Region 2) نبدأ من اخر نقطة بعد شرط توقف المنطقة الاولي (y0,x0) ونقوم بحساب القيمة الابتدائية للمتغير الثاني (p2) ونستمر في حساب القيم الجديدة لكل من المتغير (x) والمتغير (p2) طبقا للمعادلة الموضحة بينما قيمة المتغير (y) دائما تنقص بمقدار واحد صحيح حتي الوصول لشرط التوقف وهو ان تصل قيمة المتغير (y) الي الصفر (y=0)
ملحوظة: تعتمد هذه الخوارزمية علي مبدأ Parameter Desicion
مثال للجدول:

K	P	X_k+1	Y_k+1	2r_y^2X_k+1	2r_x^2Y_k+1

Code sample

      
        void plot4Points(ScreenPointStructure center,ScreenPointClass point)
        {
            setPixel(center.x + point.getX(),
                     center.y + point.getY());
            setPixel(center.x - point.getX(),
                     center.y + point.getY());
            setPixel(center.x + point.getX(),
                     center.y - point.getY());
            setPixel(center.x - point.getX(),
                     center.y - point.getY());
        }

      
        void MidPointEllipseDrawingAlgorithm(ScreenPointStructure center,GLint rx,GLint ry)
        {
            ScreenPointClass currentPoint;
            currentPoint.setX(0);
            currentPoint.setY(ry);
            GLint dx,dy,Pk2,Pk1;

            Pk1 = ry*ry - rx*rx*ry - .25*rx*rx;
            do
            {
                plot4Points(center,currentPoint);
                currentPoint.incrementX();
                dx = 2*ry*ry*currentPoint.getX();
                dy = 2*rx*rx*currentPoint.getY();
                if (Pk1 >= 0)
                {
                    currentPoint.decrementY();
                    dy = 2*rx*rx*currentPoint.getY();

                    Pk1 -= dy;
                }
                Pk1 += dx + ry*ry;
            } while (dx < dy);

            Pk2 =     ry*ry*(currentPoint.getX()+.5)*(currentPoint.getX()+.5)
                    + rx*rx*(currentPoint.getY() -1)*(currentPoint.getY() -1)
                    - rx*rx*ry*ry;
            do
            {
                plot4Points(center,currentPoint);
                currentPoint.decrementY();
                dx = 2*ry*ry*currentPoint.getX();
                dy = 2*rx*rx*currentPoint.getY();
                if (Pk2 <= 0)
                {
                    currentPoint.incrementX();
                    dx = 2*ry*ry*currentPoint.getX();
                    Pk2 += dx;
                }
                Pk2 += -dy + rx*rx;
            } while (currentPoint.getY() >= 0);
        }

4.1. Translation

$$ \begin{equation} \begin{split} x^t & = x + T_x \\ y^t & = y + T_y \\ \\ T = & \begin{bmatrix} 1 & 0 & T_x \\ 0 & 1 & T_y \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & where : \\ & T_x \text{ is horizontal offset} \\ & T_y \text{ is vertical offset} \end{split} \end{equation} $$

4.2. Rotation

$$ \begin{equation} \begin{split} x^t & = x \cos{\Theta} - y \sin{\Theta} \\ y^t & = x \sin{\Theta} + y \cos{\Theta} \\ \\ T & = \begin{bmatrix} \cos{\Theta} & -\sin{\Theta} & 0 \\ \sin{\Theta} & \cos{\Theta} & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & where : \\ & \Theta \text{ is rotation angle} \\ \\ & \textbf{with respect to fixed point } (x_r, y_r) \\ x^t & = x \cos{\Theta} - y \sin{\Theta} + (x_r - x \cos{\Theta} + y \sin{\Theta}) \\ y^t & = x \sin{\Theta} + y \cos{\Theta} + (y_r - x \sin{\Theta} - y \cos{\Theta}) \\ \\ T & = \begin{bmatrix} \cos{\Theta} & -\sin{\Theta} & x_r - \cos{\Theta} + \sin{\Theta} \\ \sin{\Theta} & \cos{\Theta} & y_r - \sin{\Theta} - \cos{\Theta} \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \end{split} \end{equation} $$

4.3. Scaling

$$ \begin{equation} \begin{split} x^t & = S_x x \\ y^t & = S_y y \\ \\ T & = \begin{bmatrix} S_x & 0 & 0 \\ 0 & S_y & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & where : \\ & S_x \text{ is horizontal scaling factor} \\ & S_y \text{ is vertical scaling factor} \\ \\ & \textbf{with respect to fixed point} (x_f, y_f) \\ \\ x^t & = x_f + S_x (x - x_f) \\ y^t & = y_f + S_y (y - y_f) \\ \\ T & = \begin{bmatrix} S_x & 0 & x_f (1 - S_x) \\ 0 & S_y & y_f (1 - S_y) \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \end{split} \end{equation} $$

4.4. Reflection

$$ \begin{equation} \begin{split} \textbf{Against } x \textbf{ axis} & = \begin{bmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ \textbf{Against } y \textbf{ axis} & = \begin{bmatrix} -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ \textbf{Against origin} & = \begin{bmatrix} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ \textbf{When } x = y & = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ \textbf{When } x = - y & = \begin{bmatrix} 0 & -1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \end{split} \end{equation} $$

4.5. Shear

$$ \begin{equation} \begin{split} & \textbf{X-direction shear} \\ x^t & = x + sh_x y \\ y^t & = y \\ T & = \begin{bmatrix} 1 & sh_x & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & \textbf{Y-direction shear} \\ x^t & = x \\ y^t & = y + sh_y x\\ T & = \begin{bmatrix} 1 & 0 & 0 \\ sh_y & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & \textbf{Shear relative to fixed point } (x_f, y_f) \\ \\ & \textbf{X-direction shear} \\ x^t & = x + sh_x y - sh_x y_f \\ y^t & = y \\ T & = \begin{bmatrix} 1 & sh_x & - sh_x y_f \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \\ \\ & \textbf{Y-direction shear} \\ x^t & = x \\ y^t & = y + sh_y x - sh_y x_f \\ T & = \begin{bmatrix} 1 & 0 & 0 \\ sh_y & 1 & - sh_y x_f \\ 0 & 0 & 1 \\ \end{bmatrix} \end{split} \end{equation} $$

5.1. Scan line polygon fill Algorithm

خطوات العمل

الخطوات:
1 - أرسم الشكل المراد تظليله

2 - رتب نقاط الشكل تصاعديا من حيث قيمة المتغير (y)

3 - حدد المدي أي أصغر وأكبر قيمة للمتغير (y) ان لم تعطي لك

4 - أرسم مصفوفة مرقمة بالمتغير (i) تبدأ من أصغر قيمة للمتغير (y) حتي أكبر قيمة للمتغير (y)

5 - ضع أول عنصر في كل صف في المصفوفة هو النقاط التي عندها قيمة المتغير (y) تتساوي مع متغير ترقيم المصفوفة (i) وان لم يكن ضع (null)

6 - حدد جميع النقاط الاعلي فقط من النقطة الحالية في قيمة المتغير (y) لكل نقطة في المصفوفة وأبدا بحساب العقدة (node) المعبرة عن هذا الضلع او المسار بين النقطتين بهكذا تكون انشأت Global Edge Table

طريقة حساب العقدة (node):
تتكون كل عقدة (node) من 3 قيم، الاولي او اقسي اليمين تعبر عن القيمة العظمي او الأكبر للمتغير (y) بين النقطتين (y_max)، والثانية او المنتصف تعبر عن قيمة المتغير (x) في النقطة الأصغر في قيمة المتغير (y) بين النقطتين (x(y_min))، الثالثة تكون المعكوس الضربي لميل الخط المستقيم المار بالنقطتين (1/m)

7 - أبدأ بأول نقطة في المصفوفة السابقة ايا كان الترقيم (i) وقم بأضافة العقد الموجودة في المصفوفة بترتيب تصاعدي طبقا للقيمة المتوسطة بالعقدة

8 - كون أول زوجين مرتبين حيث قيمة المتغير (y) في كلاهما تكون قيمة ترقيم المصفوفة الحالية (i) وقيمة المتغير (x) في الزوج الاول هي القيمة المتوسطة في العقدة الأصغر، بينما قيمة المتغير (x) في الزوج الثاني هي القيمة المتوسطة في العقدة الأكبر

9 - أضف العقد السابقة الي العقدة الموجودة في المصفوفة في القيمة التالية للمتغير (i+1) إن وُجد في ترتيب تصاعدي حسب القيمة المتوسطة لكل عقدة
10 - تأكد من الا تتساوي القيمة اليسري لأي عقدة مع قيمة المتغير (i) الحالية وان تساوت احذف العقدة

11 - أبدا واضف القيمة اليسري اي معكوس الميل الي القيمة المتوسطة للعقدة في كل من النقاط الموجودة مسبقاً، بينما لا تضيف في العقد الجديدة من المصفوفة

12 - كون الزوجين المرتبين رقم (i) حيث قيمة المتغير (y) في كل من الزوجين هي قيمة المتغير (i) وقيمة المتغير (x) في الزوج الاول تكون القيمة المتوسطة بعد الاصافة ان لزم للعقدة الأصغر وتكون قيمة المتغير (x) في الزوج الثاني هي القيمة المتوسطة بعد الاصافة ان لزم للعقدة الأكبر

13 - كرر الخطوات من 9 ال 12 حتي انتهاءك من المصفوفة و وصولك الي اخر قيمة للمتغير (i)

5.2. Boundary fill Algorithm

خطوات العمل

تعتمد طريقة عمل الخوارزمية علي تلوين الشكل المرسوم حيث يكون شرط توقفها هو حدود الشكل، تبدأ ب اي نقطة داخل الشكل المرسوم وتنفذ الخطوات كالتالي
1 - تأكد من ان النقطة الحالية لا تتساوي في اللون مع حدود الشكل او اللون المراد تلوينه
2 - تلوين النقطة الحالية
3 - استدعاء نفس الداله علي النقاط المجاورة (Neighbors)
عيوب: تتجاهل هذه الخوارزمية طبيعة الالوان الاصلية داخل الشكل حيث انها تستبدلها بالكامل بلون واحد محدد

pseudo code

      
        void boundaryFill4Neighbours(x,y,fillColor,boundaryColor)
        {
            if(pixelColor(x,y) != boundaryColor 
            && pixelColor(x,y) != fillColor)
            {
                fillPixel(x,y,fillColor);
                boundaryFill4Neighbours(x+1 , y  , fillColor, boundaryColor);
                boundaryFill4Neighbours(x   , y+1, fillColor, boundaryColor);
                boundaryFill4Neighbours(x-1 , y  , fillColor, boundaryColor);
                boundaryFill4Neighbours(x   , y-1, fillColor, boundaryColor);
            }
        }

5.3. Flood-fill Algorithm

خطوات العمل

تعتمد طريقة عمل الخوارزمية علي تلوين لون محدد في التصميم حيث يكون شرط توقفها هو نهاية اللون، تبدأ من اي نقطة داخل الجزء الملون وتنفذ الخطوات كالتالي
1 - تأكد من ان النقطة الحالية تتساوي في اللون مع اللون المراد استبداله
2 - تلوين النقطة الحالية
3 - استدعاء نفس الداله علي النقاط المجاورة (Neighbors)

pseudo code

      
        void floodFill4Neighbours(x,y,fillColor,interiorColor)
        {
            if(pixelColor(x,y) == interiorColor)
            {
                fillPixel(x,y,fillColor);
                floodFill4Neighbours(x+1 , y  , fillColor, interiorColor);
                floodFill4Neighbours(x   , y+1, fillColor, interiorColor);
                floodFill4Neighbours(x-1 , y  , fillColor, interiorColor);
                floodFill4Neighbours(x   , y-1, fillColor, interiorColor);
            }
        }

Neighbors

4 Connected Neighbors

هم النقطتان الشرق والغرب علي المحور الافقي مع الشمال والجنوب علي المحور الرأسي
عيوب: تواجهة الطريقة بعض المشاكل مع الاشكال او الحدود القطرية كالصورة التالية

8 Connected Neighbors

هم النقطتان الشرق والغرب علي المحور الافقي مع الشمال والجنوب علي المحور الرأسي مع الشمال الشرقي والجنوب الغربي علي القطر الايمن مع الشمال الغربي والجنوب الشرقي علي القطر الايسر

6.1. Bezier Curve Explicit

Algorithm Equation

$$ \begin{equation} b(t) = \sum_{i = 0}^{n} \binom{n}{i} t^i (1-t)^{n-i} P \\ where: \\ 0 \leq t \leq 1 \end{equation} $$

خطوات العمل

تعتمد الطريقة علي المعادلة السابقة حيث يتم تكوين معادلتين مشتقتين من المعادلة السابقة الاولي خاصة بقيمة المحور الأفقي (x) والثانية خاصة بقيمة المحور الرأسي (y)، بعد تكوين المعادلتين يتم التعويض بقيمة معينة للمتغير (t) بين الصفر و الواحد او بالفترة ما بين الصفر والواحد [1, 0] لرسم الخط كامل
نقاط التحكم (Control Points)

$$ \begin{equation} \begin{split} P_0 & = (1 , 2 ) \\ P_1 & = (3 , 10) \\ P_2 & = (5 , 15) \\ P_3 & = (7 , 2 ) \\ P_4 & = (9 , 8 ) \\ P_5 & = (11, 2 ) \\ \end{split} \end{equation} $$

معادلة المحور الأفقي (x)

$$ \begin{equation} \begin{split} x(t) & = \binom{5}{0} t^0 (1-t)^5 * 1 \\ & + \binom{5}{1} t^1 (1-t)^4 * 3 \\ & + \binom{5}{2} t^2 (1-t)^3 * 5 \\ & + \binom{5}{3} t^3 (1-t)^2 * 7 \\ & + \binom{5}{4} t^4 (1-t)^2 * 9 \\ & + \binom{5}{5} t^5 (1-t)^1 * 11 \end{split} \end{equation} $$

معادلة المحور الرأسي (y)

$$ \begin{equation} \begin{split} y(t) & = \binom{5}{0} t^0 (1-t)^5 * 2 \\ & + \binom{5}{1} t^1 (1-t)^4 * 10 \\ & + \binom{5}{2} t^2 (1-t)^3 * 15 \\ & + \binom{5}{3} t^3 (1-t)^2 * 2 \\ & + \binom{5}{4} t^4 (1-t)^2 * 8 \\ & + \binom{5}{5} t^5 (1-t)^1 * 2 \end{split} \end{equation} $$

قيمة النقطة عندما (t = 0.3)

$$ \begin{equation} \begin{split} x(0.3) & = 4 \\ y(0.3) & = 9.0644 \end{split} \end{equation} $$

6.2. Bezier Curve Recursive

خطوات العمل

تعتمد الطريقة علي القيم السابقة للمتغير (t) حيث نقوم ببعض الحسابات بدلا من التعويض المباشر في معادلة، طريقة الحل عبارة عن مستويات (Levels) يحتوي كل مستوي علي مجموعة رأسية من النقاط عددها (r) نحدد قيمة ال (t) كما بالمثال السابق (t = 0.3) ونحسب ايضا مكملة المتغيرة ونرمز له (u) حيث (u = 1 - t)
الخطوة الاولي: نضع المستوي الاول هو قيم المتغير (x) حيث ان عدد عناصر المستوي (r) يساوي عدد قيم المتغير (x)

الخطوة الثانية: نقوم بحساب قيم عناصر المستوي الثاني حيث ان عددهم اقل من عدد عناصر المستوي السابق بواحد صحيح وقيمة كل عنصر تحسب عن طريق كل من العنصرين المناظرين في المستوي السابق

حيث قيمة كل عنصر تساوي حاصل جمع قيمة مكملة المتغير (t) الا وهو (u) في العنصر المناظر الاعلي في المستوي السابق مع قيمة المتغير (t) في العنصر المناظر الادني في المستوي السابق

الخطوة الثالثة: نقوم بتكرار الخطوات وحساب قيم عناصر كل مستوي حتي نصل للمستوي الاخير ذو العنصر الواحد ويصبح هو قيمة المتغير (x) عندما (t = 0.3)

حساب قيمة المتغير (y): نكرر الخطوات السابقة مع قيم المتغير (y) حتي نصل لقيمة المتغير (y) عندما (t = 0.3)

7. Cohen Sutherland Line Clipping Algorithm

خطوات العمل

تهدف الخوارزمية الي تحديد حالة المشهد الكامل من العرض، حيث ان اي مشهد قد يكون داخل حدود الرؤية بالكامل او خارجها بالكامل او جزء مرئي والاخر لا ملحوظة قيمة ميل الخط المستقيم (m) لا يتغير طوال السؤال بينما قد تتغير قيم نقطتين البداية والنهاية (x1, y1) , (x2, y2)
الخطوة الاولي: يجب تعيين رمز لكل جزء من الشاشة طبقا للقاعدة (TBRL = Top Buttom Right Left) كما بالصورة التالية

الخطوة الثانية: نحدد الرمز الخاص بالمنطقة الواقع بها كل من نقطة البداية والنهاية الخاصين بالخط المستقيم المراد التحقق منه
الخطوة الثالثة: نطبق (OR Gate) علي كل من الرمزين الخاصين بالنقطتين ونطابق ما اذا كان الناتج مساوي ل 0000 تكون الحالة (Trivially Accepted) اي الخط بالكامل داخل حدود الرؤية
الخطوة الرابعة: اذا لم تتحقق الثالثة سوف نطبق (AND Gate) علي كل من رمزين النقطتين واذا كان الناتج غير مساوي ل 0000 تكون الحالة (Trivially Rejected) اي الخط بالكامل خارج حدود الرؤية
الخطوة الخامسة نبدأ خطوات الخوارزمية بإيجاد نقطة تقاطع الخط مع حد من حدود الشاشة بالتعويض في المعادلة التالية واعادة خطوات الخوارزمية من الخطوة الثانية بنقطة التقاطع الجديدة حتي تحقيق الخطوة الثالثة بنجاح

Algorithm Equation

$$ \begin{equation} \begin{split} m & = \frac{y_2 - y_1}{x_2 - x_1} \\ x & = x_1 + \frac{y - y_1}{m} \\ y & = y_1 + m (x - x_1) \\ \end{split} \end{equation} $$