Thread: Drawing Ellipses and Efficiency?

  1. 11-05-2013 #1
    HelpfulPerson
    HelpfulPerson is offline
    Registered User HelpfulPerson's Avatar
    Join Date
    Jun 2013
    Location
    Over the rainbow
    Posts
    288

    Drawing Ellipses and Efficiency?

    This code is C combined with SDL, but I figured it was close enough to be able to post here. The two functions below is my successful attempt at somewhat efficiently drawing a circle directly onto the client area of my fullscreen application. I'm unsure of how to convert to ellipses for a more versatile shape( ellipses can be circles ) with the formula I currently use. I also am unsure of how maximize efficiency by only testing the minimal amount of area, right now I just test a smaller rectangular area depending on the circle circumference. Here is my code :

    Code:
    void put_pixel( SDL_Surface * image, int x, int y, uint32_t pixel )
{
    uint32_t * pixels = ( uint32_t * )image->pixels;


    pixels[( ( ( x + ( y * image->w ) ) + 1 ) )] = pixel;


    return;
}


int draw_circle( application_data * application, int h, int k, int radius, int r, int g, int b )
{
    const int start_x = ( h - radius ) <= 0 ? 0 : ( h - radius );
    const int start_y = ( k - radius ) <= 0 ? 0 : ( k - radius );


    int x = 0, y = 0;


    if ( radius * 2 > application->console->w )
        return 1;
    if ( ( !h || !k ) || ( ( h < 0 ) || ( k < 0 ) ) )
        return 1;


    if ( SDL_MUSTLOCK( application->console ) )
        SDL_LockSurface( application->console );


    for ( x = start_x; x <= ( h + radius ) && x < application->console->w; x++ )
    {
        for ( y = start_y; y <= ( k + radius ) && y < application->console->h; y++ )
            if ( ( x - h ) * ( x - h ) + ( y - k ) * ( y - k ) <= radius * radius )
                put_pixel( application->console, x, y, RGB( r, g, b ) );
    }


    if ( SDL_MUSTLOCK( application->console ) )
        SDL_UnlockSurface( application->console );


    return 0;
}
    Edit :
    If you find it interesting, I did some homemade profiling to see how my code is shaping up so far. Here is a sampling of what the results were :

    Code:
    radius = 504, h = 840, k = 27; time to draw = 11
radius = 519, h = 282, k = 307; time to draw = 15
radius = 377, h = 139, k = 794; time to draw = 7
radius = 279, h = 174, k = 247; time to draw = 4
radius = 227, h = 956, k = 659; time to draw = 3
radius = 508, h = 944, k = 425; time to draw = 20
radius = 155, h = 471, k = 645; time to draw = 1
radius = 384, h = 21, k = 286; time to draw = 8
radius = 50, h = 967, k = 1008; time to draw = 0
radius = 99, h = 133, k = 66; time to draw = 1
radius = 76, h = 1081, k = 918; time to draw = 0
radius = 489, h = 836, k = 121; time to draw = 10
radius = 80, h = 676, k = 243; time to draw = 0
radius = 293, h = 1119, k = 825; time to draw = 4
radius = 594, h = 408, k = 381; time to draw = 25
radius = 519, h = 795, k = 1000; time to draw = 9
radius = 61, h = 1094, k = 32; time to draw = 0
radius = 547, h = 154, k = 1010; time to draw = 6
radius = 580, h = 848, k = 244; time to draw = 19
radius = 324, h = 462, k = 302; time to draw = 8
radius = 9, h = 210, k = 320; time to draw = 0
radius = 176, h = 163, k = 627; time to draw = 1
radius = 143, h = 1200, k = 947; time to draw = 0
radius = 573, h = 359, k = 629; time to draw = 22
radius = 221, h = 545, k = 225; time to draw = 4
radius = 532, h = 380, k = 228; time to draw = 15
radius = 371, h = 892, k = 1019; time to draw = 4
radius = 195, h = 321, k = 455; time to draw = 2
radius = 369, h = 321, k = 978; time to draw = 5
radius = 521, h = 573, k = 789; time to draw = 16
radius = 261, h = 1130, k = 14; time to draw = 2
radius = 93, h = 653, k = 148; time to draw = 0
radius = 277, h = 499, k = 682; time to draw = 4
radius = 447, h = 911, k = 502; time to draw = 15
radius = 45, h = 678, k = 435; time to draw = 0
radius = 194, h = 463, k = 817; time to draw = 2
radius = 298, h = 812, k = 321; time to draw = 5
radius = 345, h = 305, k = 798; time to draw = 6
radius = 295, h = 337, k = 436; time to draw = 5
radius = 97, h = 607, k = 85; time to draw = 0
radius = 295, h = 662, k = 563; time to draw = 5
radius = 112, h = 885, k = 70; time to draw = 0
radius = 132, h = 1275, k = 866; time to draw = 1
radius = 604, h = 746, k = 155; time to draw = 17
radius = 279, h = 526, k = 610; time to draw = 6
radius = 525, h = 706, k = 718; time to draw = 24
radius = 424, h = 47, k = 14; time to draw = 3
radius = 390, h = 753, k = 517; time to draw = 12
radius = 280, h = 549, k = 114; time to draw = 3
radius = 49, h = 1041, k = 821; time to draw = 0
radius = 588, h = 1254, k = 655; time to draw = 13
radius = 234, h = 1095, k = 886; time to draw = 2
radius = 603, h = 929, k = 77; time to draw = 12
radius = 463, h = 882, k = 163; time to draw = 9
radius = 379, h = 784, k = 704; time to draw = 10
radius = 326, h = 1174, k = 53; time to draw = 2
radius = 553, h = 1020, k = 671; time to draw = 17
radius = 78, h = 647, k = 96; time to draw = 1
radius = 279, h = 272, k = 257; time to draw = 5
radius = 522, h = 728, k = 879; time to draw = 13
    With time to draw being in milliseconds.
    Last edited by HelpfulPerson; 11-05-2013 at 05:40 PM.
    "Some people think they can outsmart me, maybe. Maybe. I've yet to meet one that can outsmart bullet" - Meet the Heavy, Team Fortress 2
  2. 11-06-2013 #2
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,666
    Rearrange your equation as
    y^2 = r^2 - x^2

    Then calculate the bounding box for your shape, to find the minY and maxY values you need to process.

    Code:
    for ( y = minY ; y <= maxY ; y++ ) {
}
    Inside the loop, you solve the above equation to work out the two x values (or single x at the same point).
    You then use the drawHorizontalLine primitive between those two points (in other words, fill a scan line).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
  3. 11-06-2013 #3
    SirPrattlepod
    SirPrattlepod is offline
    11DE784A SirPrattlepod's Avatar
    Join Date
    Aug 2013
    Posts
    485
    It might be nice to have some compilable code...

    Not sure how close this is to what you have, but if it's "close enough" then maybe optimizations can be suggested based on this (so at least we can have something to compare with on our own computers)

    How are you measuring circle drawing time?

    Code:
    #include <SDL/SDL.h>

#define RGB(surface,r,g,b) (SDL_MapRGB((surface)->format,(r),(g),(b)))

#define W 800
#define H 600

void put_pixel( SDL_Surface * image, int x, int y, uint32_t pixel )
{
    uint32_t * pixels = ( uint32_t * )image->pixels;
 
 
    pixels[( ( ( x + ( y * image->w ) ) + 1 ) )] = pixel;
 
 
    return;
}
 
int draw_circle(SDL_Surface *surface, int h, int k, int radius, int r, int g, int b )
{
    const int start_x = ( h - radius ) <= 0 ? 0 : ( h - radius );
    const int start_y = ( k - radius ) <= 0 ? 0 : ( k - radius );
 
    int x = 0, y = 0;
 
    if ( radius * 2 > surface->w )
        return 1;
    if ( ( !h || !k ) || ( ( h < 0 ) || ( k < 0 ) ) )
        return 1;
 
    if ( SDL_MUSTLOCK( surface ) )
        SDL_LockSurface( surface );
 
    for ( x = start_x; x <= ( h + radius ) && x < surface->w; x++ )
    {
        for ( y = start_y; y <= ( k + radius ) && y < surface->h; y++ )
            if ( ( x - h ) * ( x - h ) + ( y - k ) * ( y - k ) <= radius * radius )
                put_pixel( surface, x, y, RGB( surface, r, g, b ) );
    }
 
 
    if ( SDL_MUSTLOCK( surface ) )
        SDL_UnlockSurface( surface );
 
 
    return 0;
}

/******************************************************************************
 * boilerplate
 *****************************************************************************/
SDL_Surface *init(int w, int h)
{
    SDL_Surface *surface;
    if (SDL_Init(SDL_INIT_VIDEO) != 0)
        return NULL;
    atexit(SDL_Quit);
    surface = SDL_SetVideoMode(w, h, 32, SDL_HWSURFACE | SDL_DOUBLEBUF);
    return surface;
}

int pe(void)
{
    int quit = 0;
    SDL_Event event;

    while(SDL_PollEvent(&event)) {
        switch (event.type) {
        case SDL_QUIT:
            quit = 1;
            break;
        case SDL_KEYDOWN:
            quit = event.key.keysym.sym == SDLK_ESCAPE;
            break;
        }
    }
    return quit;
}

int main(void)
{
    SDL_Surface *surface;
    
    if ((surface = init(W, H)) != NULL) {
        draw_circle(surface, 400, 300, 200, 0, 0, 255);
        SDL_Flip(surface);
        while (!pe())
            ;
    }
    
    return 0;
}
  4. 11-06-2013 #4
    SirPrattlepod
    SirPrattlepod is offline
    11DE784A SirPrattlepod's Avatar
    Join Date
    Aug 2013
    Posts
    485
    Since this is a filled circle then the only significant efficiency gains are (probably)
    a) What Salem suggested
    b) Reflect above/below y-axis (halve the calculations required)
    c) Move the invariants out of the loop (but gcc -O2 or -O3 probably does the anyway)
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. efficiency
    By xiaohuai in forum Tech Board
    Replies: 3
    Last Post: 06-14-2011, 07:24 PM
  2. Efficiency with c++
    By pastitprogram in forum C++ Programming
    Replies: 17
    Last Post: 08-08-2008, 11:18 AM
  3. Ellipses (that stretch) in DirectDraw
    By Cheeze-It in forum Game Programming
    Replies: 2
    Last Post: 02-26-2006, 04:11 PM
  4. Drawing lines and ellipses with DirectDraw
    By Hunter2 in forum Game Programming
    Replies: 9
    Last Post: 01-08-2003, 01:25 PM
  5. Looking for efficiency in my app
    By dead_cell in forum C++ Programming
    Replies: 7
    Last Post: 07-01-2002, 10:22 PM