[Oberon] FPGA - Simple Graph Fill

Dieter d.gloetzel at web.de
Mon Jan 14 17:17:17 CET 2019


Comparing Joergs algorithm for drawing filled circles to Bresenham's 
algorithm
I found the following: For large circles there is not much difference, 
but when
you look with a magnifying glass at a circle with  radius = 10 pixels, 
you see the difference.

I also include a test sample with straight lines, also following Bresenham.


Reference: N. Wirth "Drawing, Lines, Circles, and Ellipses in a Raster


Am 10.11.2018 um 10:25 schrieb Jörg:
> I added a small optimization by drawing the line at y=0 only once iso twice.
> But I almost doubled the speed by reversing the x search direction :-)
>
> PROCEDURE Fill*;
> 	VAR x, y, R, R2, lim: INTEGER;
> 	BEGIN
> 		R := 100;
> 		R2 := R*R;
> 		Display.ReplConst(Display.white, 150-R, 150, 2*R, 1, Display.paint);
> 		FOR y := 1 TO R DO
> 			lim := R2 - y*y; x := R; WHILE x*x > lim DO DEC(x) END;
> 			Display.ReplConst(Display.white, 150-x, 150+y, 2*x, 1, Display.paint);
> 			Display.ReplConst(Display.white, 150-x, 150-y, 2*x, 1, Display.paint)
> 		END;
> 	END Fill;
>
>> Am 10.11.2018 um 09:21 schrieb Jörg<joerg.straube at iaeth.ch>:
>>
>> A little bit „brute force“ (I mean not as elegant as Bresenham) but this is fairly fast as well:
>> Draws a filled circle at (150/150) with radius 100.
>>
>> MODULE Circle; (* jr/10nov18 *)
>>
>> IMPORT Display;
>>
>> PROCEDURE Fill*;
>> 	VAR x, y, R, R2, lim: INTEGER;
>> 	BEGIN
>> 		R := 100;
>> 		R2 := R*R;
>> 		FOR y := 0 TO R DO
>> 			lim := R2 - y*y; x := 0; WHILE x*x <= lim DO INC(x) END;
>> 			Display.ReplConst(Display.white, 150-x, 150+y, 2*x, 1, Display.paint);
>> 			Display.ReplConst(Display.white, 150-x, 150-y, 2*x, 1, Display.paint)
>> 		END;
>> 	END Fill;
>>
>> END Circle.Fill
>>
>>
>> Jörg
>>
>>
>>> Am 09.11.2018 um 19:10 schrieb Jörg Straube<joerg.straube at iaeth.ch>:
>>>
>>> Wim used as error term „d“ the first derivative
>>> Magnus used the second derivative (error in x and y are easier to calculate but need to be cumulated (=integrated) to come to „d“, in his code called „f“)
>>>
>>> Both algos draw horizontal lines several times.
>>> Two of the lines have to be drawn always, the other two only when y changes.
>>>
>>> Jörg
>>>
>>>> Am 09.11.2018 um 18:49 schrieb Magnus Karlsson<magnus at saanlima.com>:
>>>>
>>>> Here is the code I used in a project to draw a filled circle using a routine to draw a horizontal line (adapted from Adafruit GFX arduino library):
>>>>
>>>> void circle(int x0, int y0, int r) {
>>>> int f = 1 - r;
>>>> int ddF_x = 1;
>>>> int ddF_y = -2 * r;
>>>> int x = 0;
>>>> int y = r;
>>>>
>>>> hline(x0 - r, x0 + r, y0);
>>>> hline(x0, x0, y0 + r);
>>>> hline(x0, x0, y0 - r);
>>>>
>>>> while (x < y) {
>>>>    if (f >= 0) {
>>>>      y--;
>>>>      ddF_y += 2;
>>>>      f += ddF_y;
>>>>    }
>>>>    x++;
>>>>    ddF_x += 2;
>>>>    f += ddF_x;
>>>>    hline(x0 - x, x0 + x, y0 + y);
>>>>    hline(x0 - x, x0 + x, y0 - y);
>>>>    hline(x0 - y, x0 + y, y0 + x);
>>>>    hline(x0 - y, x0 + y, y0 - x);
>>>> }
>>>> }
>>>>
>>>> Magnus
>>>>
>>>>
>>>>> On 11/9/2018 7:16 AM, Wim Niemann wrote:
>>>>> Hi,
>>>>>
>>>>> bug solved.
>>>>> The trace says '0 303 201  north start'. Now the color must become the fill color 8 but a few lines further on the trace prints again '0 303 201'.
>>>>>
>>>>> Like Jörg says, the order of S, E, N, W is not relevant. I'm sorry for the confusion but the directions East and South-East stemmed from the outline algorithm and were not related to a flood fill.
>>>>>
>>>>> The recursion can be replaced by iteration but a quick internet search indicated you still push new candidate pixels on a stack. For larger images, this is really memory and cpu intensive. From memory, I believe it is possible to iterate top down and do two scans left and right to prevent a pixel stack but I don't have an example by hand.
>>>>>
>>>>> Here's another approach which draws a filled circle in a single color without flood-fill:
>>>>>
>>>>> The 'Bresenham circle' version in 'Foley and van Dam' differs slightly from the Oberon version and is presented in C:  (kudos for keeping it human readable)
>>>>>
>>>>> void MidpointCircle(int radius, int color)
>>>>> /* Assumes the center of circle is at origin. */
>>>>> {
>>>>>   int    x = 0;
>>>>>   int    y = radius;
>>>>>   int    d = 1 - radius;
>>>>>   CirclePoints(x, y, color);    /* draw eight-fold symmetric points */
>>>>>   while (y > x) {
>>>>>       if (d < 0) {    /* Select E */
>>>>>           d += 2*x + 3;
>>>>>       } else {    /* Select SE */
>>>>>           d += 2*(x-y) + 5;
>>>>>           y--;
>>>>>       }
>>>>>       x++;
>>>>>       CirclePoints(x, y, color);
>>>>>   }
>>>>> }
>>>>>
>>>>> This version either draws pixels at the same horizontal line or decreases y to a new scanline. Instead of drawing the eight pixels you can fill a horizontal line section when y is decreased to obtained a filled circle.
>>>>>
>>>>> A border color can then be achieved by drawing an outline in the border color.
>>>>>
>>>>> Wim
>>>>> --
>>>>> Oberon at lists.inf.ethz.ch  mailing list for ETH Oberon and related systems
>>>>> https://lists.inf.ethz.ch/mailman/listinfo/oberon
>>>>>
>>>> --
>>>> Oberon at lists.inf.ethz.ch  mailing list for ETH Oberon and related systems
>>>> https://lists.inf.ethz.ch/mailman/listinfo/oberon
>> --
>> Oberon at lists.inf.ethz.ch  mailing list for ETH Oberon and related systems
>> https://lists.inf.ethz.ch/mailman/listinfo/oberon
> --
> Oberon at lists.inf.ethz.ch  mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon


-- 
____________________________________
Dr. Dieter Glötzel
Im Rosengarten 27
64367 Mühltal
Tel.: 06151 / 360 82 72

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Joerg.jpg
Type: image/jpeg
Size: 82542 bytes
Desc: not available
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20190114/0a0b2f96/attachment-0003.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Bresenham.jpg
Type: image/jpeg
Size: 85188 bytes
Desc: not available
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20190114/0a0b2f96/attachment-0004.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: circle.and.lines.test.jpg
Type: image/jpeg
Size: 38512 bytes
Desc: not available
URL: <http://lists.inf.ethz.ch/pipermail/oberon/attachments/20190114/0a0b2f96/attachment-0005.jpg>


More information about the Oberon mailing list