[Oberon] FPGA - Simple Graph Fill

[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