[Oberon] FPGA - Simple Graph Fill

[Jörg Straube]

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