## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 786

This Forum Only

Filled Clipped Ellipsis [Bresenham?] Posted by Cyt on 5 Feb 2002 at 2:49 AM
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:
I'm starting to make a routine ASAP, but would like to know if any fast way of doing it already exists.

One approach - not all that optmised Posted by Cyt on 5 Feb 2002 at 5:38 AM
: 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.
```	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<nYEnd;nY++)
{
nYk=nY-sCenter.Y;
nYk*=nYk;
nK=(int)((nRX*(sqrt(1-nYk/(double)(nRY*nRY)))+0.5));

nXStart=sCenter.X-nK;
if(nXStart<0) nXStart=0;
nXEnd=sCenter.X+nK;
if(nXEnd>=nWidth) nXEnd=nWidth-1;

pP=pStartYP+nXStart;
for(;nXStart<=nXEnd;nXStart++)
{
*pP++=lColour;
}
pStartYP+=nWidth;
}
```

... 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

Re: One approach - not all that optmised Posted by MrEd on 8 Feb 2002 at 9:53 PM
: : 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.
:
```: 	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<nYEnd;nY++)
: 	{
: 		nYk=nY-sCenter.Y;
: 		nYk*=nYk;
: 		nK=(int)((nRX*(sqrt(1-nYk/(double)(nRY*nRY)))+0.5));
:
: 		nXStart=sCenter.X-nK;
: 		if(nXStart<0) nXStart=0;
: 		nXEnd=sCenter.X+nK;
: 		if(nXEnd>=nWidth) nXEnd=nWidth-1;
:
: 		pP=pStartYP+nXStart;
: 		for(;nXStart<=nXEnd;nXStart++)
: 		{
: 			*pP++=lColour;
: 		}
: 		pStartYP+=nWidth;
: 	}
: ```

: ... 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 :)

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic