[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