drawing ellipse with rotation cause inaccurate result

Question

i'am a junior in computer graphics , currently i learn how to draw ellipses with rotation .

when i preform rotation with 90deg or 180deg nothing unusual happened , but when i try to rotate with any other value the result will be like this :

here's a pseudo-code of what iam doing , i didn't put the original function because it's huge .

function draw_circle( x_origin , y_origin , width , height ){

// go in scan-line order and try to find intercept x,y around the ellipse
   for( y = 0 ; y <= height ; y++ ){   

       for( x = width  ; x >= 0; x-- ){

            // when we find point x , y
            if( ( x*x / width ) + ( y*y / height  ) <= 1 ){

                  // rotate a copy of x,y
                  rotate_z( x , y , by_angle );

                  // draw the rotate x,y copy
                  set_pixle( x_origin + x , y_origin + y );
                   
                  /*
                     then preform reflection in the other side 
                     of the ellipse 
                  */
            }

       }
   }
}

Answer 1

The guilty is the post-rotation after you have generated points of the un-rotated ellipse. Because rotation on a raster does not preserve the density of the pixels.

A solution is to work directly with the equation of the rotated ellipse, of the (centered) form

$$px^2+2qxy+ry^2=1.$$

You can obtain it by plugging $u=x\cos\theta-y\sin\theta,v=x\sin\theta+y\cos\theta$ in

$$\frac{u^2}{a^2}+\frac{v^2}{b^2}=1.$$

---

Note that your computation is fairly heavy because you try all pixels, i.e. $w\cdot h$ of them, which can be a lot.

You can reduce the number of computations by

• looping on $y$,

• for a given value of $y$, solving the quadratic equation $px^2+2qxy+ry^2-1=0$ for $x$

• when the slope of the curve becomes less than $1$ (so that a row will contain several pixels of the outline), switching to a loop on $x$, computing the corresponding $y$.

The switching points occur when the slope is $\pm1$, or

$$|px+qy|=|qx+ry|.$$

---

Yet a faster method is by using an outline-following algorithm on the digital domain

$$px^2+2qxy+ry^2\le1.$$

https://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html

Answer 2

I think you should transform your coordinates before checking if they touch the boundary. You seem to use a scatter approach and every pixel that touch the non-transformed ellipse will land on only one pixel. Because the number of pixels that touch the boundary are "uniform" along curves that correspond to a rotated pixel grid, you will get holes and clusters which you can see in your zoomed in example.