[Oberon] FPGA - Simple Graph Fill

[Jörg]

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