Filled Clipped Ellipsis [Bresenham?] - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Filled Clipped Ellipsis [Bresenham?]

CytCyt Posts: 557Member
Does a nice solution exist for [subj]?

I'm looking for an algorithm that lets me draw a filled, clipped ellipsis. The required input for such a routine is:
XRadius,YRadius,Center,Bounding Rectangle.
I'm starting to make a routine ASAP, but would like to know if any fast way of doing it already exists.

Thanks in advance.


Comments

  • CytCyt Posts: 557Member
    : Does a nice solution exist for [subj]?
    Just to show my approach - in C/C++
    The function is a member function of a class that contains nWidth and nHeight. nColour is always long, and sPoint is simply a struct with two signed shorts, X and Y.
    Any comments are welcomed:
    [code]
    int nXStart;
    int nYEnd;
    int nXEnd;
    int nYk;
    int nK;
    long *pP;
    long *pStartYP;
    int nY;

    nY=sCenter.Y-nRY;
    if(nY<0) nY=0;
    nYEnd=sCenter.Y+nRY;
    if(nYEnd>nHeight) nYEnd=nHeight;
    pStartYP=pPixels+nY*nWidth;

    for(;nY=nWidth) nXEnd=nWidth-1;

    pP=pStartYP+nXStart;
    for(;nXStart<=nXEnd;nXStart++)
    {
    *pP++=lColour;
    }
    pStartYP+=nWidth;
    }
    [/code]
    ... Hmm.. One comment of my own: Optimisation for the case that the entire ellipsis is out of bounds is only done for the vertical case. If one made an ellipsis with a very big nRY and an out-of-bounds, x-interval, effictively nHeight nonnescessary divs and sqrts would be performed :-/. Oh well. It hardly ever happens :-)

  • MrEdMrEd Posts: 180Member
    : : Does a nice solution exist for [subj]?
    : Just to show my approach - in C/C++
    : The function is a member function of a class that contains nWidth and nHeight. nColour is always long, and sPoint is simply a struct with two signed shorts, X and Y.
    : Any comments are welcomed:
    : [code]
    : int nXStart;
    : int nYEnd;
    : int nXEnd;
    : int nYk;
    : int nK;
    : long *pP;
    : long *pStartYP;
    : int nY;
    :
    : nY=sCenter.Y-nRY;
    : if(nY<0) nY=0;
    : nYEnd=sCenter.Y+nRY;
    : if(nYEnd>nHeight) nYEnd=nHeight;
    : pStartYP=pPixels+nY*nWidth;
    :
    : for(;nY=nWidth) nXEnd=nWidth-1;
    :
    : pP=pStartYP+nXStart;
    : for(;nXStart<=nXEnd;nXStart++)
    : {
    : *pP++=lColour;
    : }
    : pStartYP+=nWidth;
    : }
    : [/code]
    : ... Hmm.. One comment of my own: Optimisation for the case that the entire ellipsis is out of bounds is only done for the vertical case. If one made an ellipsis with a very big nRY and an out-of-bounds, x-interval, effictively nHeight nonnescessary divs and sqrts would be performed :-/. Oh well. It hardly ever happens :-)
    :
    :

    i know nothing of geometry, but let me share my limited optimisation knowledge.

    1. get rid of the sqrt NOW!!! use a look-up table instead. you'll need to figure out the range of values you would use for a parameter and build a table appropriately.

    2. instead of setting one pixel at a time, try using memset or whatever its called to set a particular chunk of memory to the same value.

    3. remove as many multiplications and divisions as possible. eg instead of calcing nYk every loop with a * can you just increment it each loop with a +

    4. nRY is constant so dont calc nRY*nRY every loop! do it once and save the value.

    im sure theres more, but im tired :)
Sign In or Register to comment.