User:Dexteroid/Scan Conversion Ellipse

Rasterization

Rasterization is the process of actually making an image on screen pixel by pixel, the way it works is it finds the vertices of the primitive in scene and then it colors the pixels between those vertices Rasterization is a very commonly used technique in Computer Graphics. Most of the GPU's work on rasterization.For more details on Rasterization refer

For drawing simple primitives like a circle or a Line if we follow the mathematical equation to locate the next pixel then it will be a slow process because the equation of line or circle will involve a lot of floating point calculations.Hence we need to come up with a faster way to draw the primitives. For example The Bresenham Line-Drawing Algorithm is commonly used to draw lines on a computer screen.This algorithm is very fast as it avoids floating point calculations and uses only integer operations(Addition,subtraction etc). Similar to the Line drawing algorithm, we have Midpoint circle algorithm which is a faster method of drawing circles.

In this article we will discuss an Ellipse drawing algorithm which is somewhat similar to the Midpoint circle algorithm.Circle is a special case of Ellipse and with a slight modification to the circle drawing algorithm we can obtain the Ellipse drawing algorithm.

Scan conversion of ellipse

Consider Figure 1: Standard ellipse centered at origin.

Fig1:A Standard Ellipse with major axis 2a and minor axis 2b

The Ellipse in Figure 1 could be described by $F(x,y)=b^{2}x^{2}+a^{2}y^{2}-a^{2}b^{2}=0$
For simplicity we will use the symmetry of the ellipse and we will discuss about the first quadrant only. ie $x>0,y>0$
For the above mentioned ellipse:Length of the major axis: $2a$ and minor axis: $2b$

As shown in Figure:2, The first quadrant can be divided in two regions, labeled R1 and R2 in Figure:2

The image describes the two regions in the ellipse made by the tangent. When the point is in R1 we need to make a decision between E and SE pixels and if the point is in R2 we need to make a decision between S and SE

The boundary between the two regions is the point at which the slope is -1. As shown in Figure:2 when the point lies in R1 the decision for next pixel has to be made between E and SE. However if the point lies in R2 the decision for next pixel has to be made between S and SE.

We need to define a gradient vector and this gradient vector helps us determine the boundary between R1 and R2. Gradient can be defined as:

               $grad[F(X,Y)]={\frac {\partial f}{\partial X}}i+{\frac {\partial f}{\partial Y}}j$

                           $=(2b^{2}X)i+(2a^{2}Y)j$

                 in R1  : ${\frac {\partial f}{\partial Y}}>{\frac {\partial f}{\partial X}}$

                 in R2 :  ${\frac {\partial f}{\partial X}}>{\frac {\partial f}{\partial Y}}$

         At the Boundary: ${\frac {\partial f}{\partial Y}}={\frac {\partial f}{\partial X}}$
 
    
         Condition to move from R1 to R2 = $a^{2}(y_{p}-{\frac {1}{2}})$ ≤ $b^{2}(x_{p}+1)$

Like any other mid point algorithm we evaluate the function at the mid point between two pixels and then use the sign to determine which pixel is close to the mid point.
for R1 if the current pixel is at $(x_{p},y_{p})$ then the decision variable for R1, D1 is evaluated at $(x_{p}+1,y_{p}-{\frac {1}{2}})$ i.e. the midpoint between E and SE.

For a move to E, we can find the next mid point by incrementing x.

              $D_{old}$ = $F(x_{p}+1,y_{p}-{\frac {1}{2}})=b^{2}(x_{p}+1)^{2}+a^{2}(y_{p}-{\frac {1}{2}})^{2}-a^{2}b^{2}$      //substitute the values in the main equation.
             
              $D_{new}$ = $F(x_{p}+2,y_{p}-{\frac {1}{2}})=b^{2}(x_{p}+2)^{2}+a^{2}(y_{p}-{\frac {1}{2}})^{2}-a^{2}b^{2}$

So we can clearly see that $D_{new}$=$D_{old}$ + $b^{2}(2x_{p}+3)$

              So our increment the ΔE = $b^{2}(2x_{p}+3)$

Similarity for a move to SE the next midpoint is located at one increment in x and one increment down in y

We can calculate the ΔSE by following the same procedure we followed for ΔE.

              So our increment the ΔSE = $b^{2}(2x_{p}+3)+a^{2}(-2y_{p}+2)$

For R2, if the current pixel is at $(x_{p},y_{p})$, then the decision variable is given by $(x_{p}+{\frac {1}{2}},y_{p}-1)$ which is the mid point between S and SE
We can calculate the ΔSE and ΔS by following the same method we followed for R1

Initial condition: ellipse starts at (0,b) and the first mid point calculated is $(1,b-{\frac {1}{2}})$
the after substituting these values in F(x,y) we get $F(1,b-{\frac {1}{2}})=b^{2}+a^{2}(-b+{\frac {1}{4}})$

Algorithm

The basic algorithm:

        for every iteration in R1:

               test decision variable

               update the Δ functions

               Plot pixels

               if(slope of the curve == -1)

                    Switch to region R2

               else

                    Continue 

Pseudocode

             void MidPointEllipse (int a, int b, int value);

                 {

                     double d2; int X = 0; int Y = 0;

                     squaredA = sqr(a); squaredB = sqr(b);        //Calculate $a^{2},b^{2}$
 
                     double d1 = squaredB – squaredA*b + 0.25*squaredA;

                     PlotEllipsePoints(X, Y, value);

                     /*Check Condition to move from R1 to R2*/

                     while ( squaredA*(Y - 0.5) > squaredB*(X + 1))      //Region R1 
                               
                            { 
              
                                if (d1 < 0) /*Select E */

                                      d1 += squaredB*((X<<1) + 3);

                                else /*Select SE */

                                     { 

                                      d1 += squaredB*((X<<1) + 3) + squaredA*(-(Y<<1) + 2);

                                      Y-- ; 

                                     }

                                X++ ;

                                PlotEllipsePoints(X, Y, value);

                            }

                     double d2 = squaredB*sqr(X + 0.5) + squaredA*sqr(Y - 1) - squaredA*squaredB;

                     while ( Y > 0)                                     //Region R2 

                        {
 
                            if (d2 < 0)                                 //Select SE 

                                  { 

                                     d2 += squaredB*((X<<1) + 2) + squaredA*(-(Y<<1) + 3);
                                       
                                     X++;

                                  }

                           else                                         //Select S 

                                     d2 += squaredA*(-(Y<<1) + 3);

                             Y-- ;

                             PlotEllipsePoints(X, Y, value);

                   }

                }