A.D.A. Amiga Demoscene Archive

Well, I was desperately looking for a hint to do a circle draw routine.
Since I didn't found any decent assembler links I tried my luck at ... wikipedia of course. I found this algo by Mr. Bresenham and thought to give the port of the C version a try.

After writing a little control routy to "rape" the linedraw for single pixel use
I ported the C source almost line by line. So the thing is lame to the max...
but it works.....well, almost.
ze source

By drawing the circle in the desired measures on the screen there
happened a bit a bit more that puzzled me o_O
Around the circle the routine continued to draw lines just like that:



Is that the result of some hex-rounding error?
Did I some bad moves (most likely :)
Or is it just the algorithm ?

Take a look at the AmyCoders page:

http://membres.lycos.fr/amycoders/

Look under Compos and then Circlecompo. There you will find a lot of different ways to draw a circle. My own entry is a clean and simple Bresenham'ish routine - you should be able to get the idea from it (it's not a lot of code).

I have recently coded a routine for drawing a filled circle clipped to the screen borders with subpixel-precise center and radius. That's "a bit" more cumbersome. ;)

While you are at Amycoders, take a look around. There is quite a lot of interesting code there actually.

Thanks for the hint. I thought amycoders vanished a long time ago.
Apparently it did not :) So I'll take a peek there.

d0DgE, you need to clear variables between runs if you call the routine more than once.

All right, after taking some peeks at the compo entries I surely found some nice hints especially regarding ze unbearable muls.w ;)
BTW: this strange effect was caused in fact by the pixel routine not the
circle routine at all
/me stupid

some strongly revised version is here

Just a few minor comments on the coding style:


* There is a block of variables down at the end of the source. Some of these should be set before drawCircle is called, while others are used for temporary storage during the rendering process. Just looking at the names of the variables, it is difficult to tell which is which.

I suggest that you separate them into two sections.

Or, better: let the calling code send values for (x0,y0,radius) in (d0,d1,d2).

Sure, this is a test program, but those of us that did take the time to look at your source had to read it all through and analyze it before we even knew where the in-parameters were located.
Ordinary calling conventions or some comments would have helped.


* x,y,f are cleared at the *end* of the circle routine. This means that the circle routine is potentially behaving differently on the first run, compared to subsequent runs:
- during the first run, the value from the "dc.w" statement is used
- during subsequent runs, the value from the "move.w" operation is used

Also, when analyzing the algorithm, one needs to look thorugh the *whole* routine just to figure out whether x,y,f are always cleared upon entry.

If you clear x,y,f at the beginning of drawCircle, the code is easier to follow and less error-prone. (And it would be easier for you to spot that you don't need to clear y & f either.)

the last source was merely just a snippet from an in-work-system but nevertheless kthx for the hints & comments - will provide more convenient
snippets the next time.

Sorry if I sounded a bit pissy - been helping a few people with their very first programming assignments (in Ada nonetheless) and I've therefore seen a bit too much of "code-in-progress" over the past weeks...

I had a go at implementing the same routine. I started with this version, which is a straight conversion of the c-example. I didn't use any variables within the loop anymore, but still a lot of branching to subroutines.

I had a peek at hitchhikr's entry in the circle compo at amycoders, where i learned about calculating the middle point and going from there. This resulted in a shorter routine without any branching. The routine is is here. Still got a lot of mulu's though. The amycoder examples are all meant for a 256*256 screen, which avoids all those mulu #320 by doing a shift 8 instead (*256) for each line offset calculation.

* yes, move those multiplications out of the loop.
* instead of having a0 point to the upper-left corner of the screen, let it point to the center of the circle.
(The latter would require that you support negative offsets in the index register, btw.)

* yes, move those multiplications out of the loop.

done

How about supporting different colours, either paletted or RGB for 18 bit c2p?

Can somebody give me any tips on how you incorporate thickness into a circle drawing routine?

First, make a routine that draws a filled circle.

Such a routine is normally done by decomposing the circle into a set of horizontal lines. Something like:



... that is, for every line from y0-radius to y0+radius, you calculate the starting and stopping X-position using the x^2 + y^2 = r^2 identity.


Once you have that working, by running that logic twice (once for the outer radius, once for the inner radius) you can then figure out which horizontal line segments should be drawn in order to generate a "thick", non-filled circle.

@kalms:

(The latter would require that you support negative offsets in the index register, btw.)

I'd be very interested to know what you mean as i'm hitting that exact problem after converting the circle routine to work from the middle point (as you suggested).

I searched quite a bit on this one. In the indirect addressing mode with index register (a0,d0.w), d0 is allowed to be signed as is, isn't it? It seems to be according to the internet. So why do i need to support negative offsets to the index register?

z5:

When using the addressing mode (a0,d0.w), d0 is always treated as a signed 16-bit value. So when computing the value that is stored in d0, you need to ensure that the resulting value makes sense when interpreted as a signed 16-bit value.

When using the addressing mode (a0,d0.l), d0 can be considered to be either signed or unsigned, it will make no difference. So when computing the value that is stored in d0, you need to ensure that the resulting value makes sense when interpreted as either a signed or an unsigned 32-bit value.

The latest circle routine you showed had a flow like:

moveq #0,d2
...
word-size computations against d2
...
move.b #1,(a0,d2.l)

Notice that no matter how the word-size computations are being done, the upper half of d2 will always be zero. That means that d2.l will always contain a value within the range 0...65535.

And that's fine as long as you don't attempt to produce any negative indexes. To support negative offsets in d2, you need to either:

1) switch addressing mode to (a0,d2.w), or

2) sign-extend the value in d2 from word-size to longword-size just before the (a0,d2.l) access, or

3) modify the word-size computations to be longword-size instead, and then use (a0,d2.l) access.


Option 1 is the easiest. Option 3 allows you to have larger circles.

Ok, one last question for the circle routine (with which you can nice things). I'd be very interested in how you approach implementing clipping.

I added x-clipping by checking each possible x-plot: x0+x, x0-x, x0+y, x0-y. When outside the 0 to 320 screen coord => skip the corresponding plot-routine. This was fairly easy since coord = bytes in x-direction.

I then added y-clipping by doing the same: checking every y-plot: y0-y, y0+y, y0-x, y0+x. Things got a bit more "complicated" (or more work) since the max y (320*200) > 16-bit. But i could extend from word to longword in that case. I could probably have kept checking in pure y coord (0 to 200) but i'm running out of registers to use in my subroutine.

Any cunning clipping tricks?

Any cunning clipping tricks?

Eh, nope.

:)

I'd just patch in whatever works there -- probably an extra "pure y counter" (i.e. not premultiplied by 320) -- and be done with it. If you're short on data registers, you can move some variables over into address registers.

Just a small anecdote:

At two occasions today, my bresenham circle routine wasn't outputting circles, put far cooler looking "patterns" (two different ones actually). They looked great. I saved my code, resetted winuae and hoped they would still be there but they were plain boring circles again... damn... Pity they didn't reappear because i could never have coded these on purpose :)

I hope they are going to re-appear again when showed on some big screen.

It's a pity that i couldn't determine the cause (uhum...bug) as it would have turned out as my best effect yet (and probably ever).

Maybe some uncleared variables somewhere when you call the routine?

I wish i knew as i would have used it as an effect. The circle routine outputted such nice patterns. Let's hope it appears again sometime as i definately would like to find out how to code these patterns.

I know what you mean

did they appear as "kosmoplovci"- style random line patterns ?