Bresenhams Circle Algo question.

Bresenhams Circle Algo question.

Post by §MoLe » Sat, 19 Oct 2002 23:56:09



Hi All,

Could anyone tell me if its possible to calculate how many pixels will be
drawn using Bresenhams circle algorithm, specifically when this algo is
used to draw circular arcs ?, this is for a stepping motor project and not
graphics, but the raster device model remains the same.

Thanks......
Ken.

 
 
 

Bresenhams Circle Algo question.

Post by Hans-Bernhard Broeke » Sun, 20 Oct 2002 00:12:40



> Hi All,
> Could anyone tell me if its possible to calculate how many pixels will be
> drawn using Bresenhams circle algorithm, specifically when this algo is
> used to draw circular arcs ?,

In every octant touched by the arc, the number of pixels is

        ceil(max(|x_end - x_begin|, |y_end - y_begin|))

The reason being that bresenham for circles, just like bresenham for
straight lines, works by choosing either a diagonal or a horizontal
step.  For a given octant, that means every step is exactly one unit
in one direction (x or y), and either zero or one in the other.  The
direction that changes every steps proceeds further, and thus wins the
max() in the above calculation.

For a full circle of radius r, that makes 8 * (r/sqrt(2)) pixels,
give or take 8 for rounding errors and double counting.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Bresenhams Circle Algo question.

Post by §MoLe » Sun, 20 Oct 2002 17:21:55



Quote:

> In every octant touched by the arc, the number of pixels is

> ceil(max(|x_end - x_begin|, |y_end - y_begin|))

> For a full circle of radius r, that makes 8 * (r/sqrt(2)) pixels,
> give or take 8 for rounding errors and double counting.

Thanks for taking the time to reply to my post, I was aware of the method
cited above, I was looking for a method of calculating the pixel count
for sub octants.
I am building a high speed plotter and I am using BiArc splines to generate
NURBS curves, as a result the arcs generated have varying start and end
angles & radii, I need to pre compute the lengths of these arcs to calculate
the velocities & accelerations correctly.

Because the Bresenhams is an approximation, normal arc length calculations
dont work, I can polygon approximate circular arcs but I was trying to use
the circular interoplation feature of the chipset that I am using, which
uses Bresenhams.

I should have been more specific with my original post to read:
How do I calculate the pixel count in sub octant arc segments using
bresenhams circle algorithm.

Many thanks .
Ken

 
 
 

Bresenhams Circle Algo question.

Post by §MoLe » Sun, 20 Oct 2002 17:21:55



Quote:

> In every octant touched by the arc, the number of pixels is

> ceil(max(|x_end - x_begin|, |y_end - y_begin|))

> For a full circle of radius r, that makes 8 * (r/sqrt(2)) pixels,
> give or take 8 for rounding errors and double counting.

Thanks for taking the time to reply to my post, I was aware of the method
cited above, I was looking for a method of calculating the pixel count
for sub octants.
I am building a high speed plotter and I am using BiArc splines to generate
NURBS curves, as a result the arcs generated have varying start and end
angles & radii, I need to pre compute the lengths of these arcs to calculate
the velocities & accelerations correctly.

Because the Bresenhams is an approximation, normal arc length calculations
dont work, I can polygon approximate circular arcs but I was trying to use
the circular interoplation feature of the chipset that I am using, which
uses Bresenhams.

I should have been more specific with my original post to read:
How do I calculate the pixel count in sub octant arc segments using
bresenhams circle algorithm.

Many thanks .
Ken

 
 
 

Bresenhams Circle Algo question.

Post by Hans-Bernhard Broeke » Tue, 22 Oct 2002 21:01:20



> I am building a high speed plotter and I am using BiArc splines to generate
> NURBS curves, as a result the arcs generated have varying start and end
> angles & radii, I need to pre compute the lengths of these arcs to calculate
> the velocities & accelerations correctly.

And how exactly does the formula I gave fail to compute those arc lengths?

Quote:> Because the Bresenhams is an approximation,

It's only an approximation if what you're comparing to is the
physically impossible "exact" solution.  Once you consider the output
device to be of fixed, finite resolution, i.e. that there really are
pixels, the Bresenham algo is the best possible solution, not an
approximation to that.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Bresenhams Circle Algo question.

Post by §MoLe » Wed, 23 Oct 2002 00:23:39




> And how exactly does the formula I gave fail to compute those arc lengths?

It doesn't ; Sorry it's me being an schmuck.., too impatient, didn't read
your post correctly, slapped legs, going to sit in a corner now
wearing a tall pointy hat with the letter "D" on the front..

The problem I had was with the chipset, The Bresenham "type" algo logic in
the IC also approximates the velocity by scaling the 2 axes when
simultaneously stepping.

Regards.
Ken.

 
 
 

1. Is bresenhams line algo the ONLY algo?

Actually, yes.

Even though the theoretical textbooks always use Bresenham's, everybody else
uses other algorythims.

Best bet, for the most part, is to reduce the angled line to a series of
horizontal or vertical lines and then process those.  Then you get a
relitively simple loop.

I'm handwaving a lot here..

But if you are doing appreciable calculations at each pixel -- more than
just drawing -- it's probably better to just use Bresenham's.

2. 3D map source needed

3. Bresenhams Circle Algorithm Question..

4. batch multi tiff separation ?

5. Wanted: Bresenhams Circle Drawing Algorithm

6. HELP! LENSFLARE FOR RELEASE 2 NEEDED.

7. 2D circles & connecting lines layout algo

8. Maya b3 and final release

9. URGENT-2D circles & connecting lines layout algo

10. Circle detection algo

11. URGENT-2D circles & connecting lines layout algo

12. 2D circles & connecting lines layout algo