# [Oberon] FPGA - Display3.Mod - porting

Wim Niemann niemannw at xs4all.nl
Wed Nov 7 18:21:08 CET 2018

```
This is the Bresenham Midpoint algorithm for a circle (1977). One quarter circle is computed, the rest is symmetry.
See for example 'Computer Graphics, principles and practice', Foley, van Dam, Feiner, Hughes (or just Foley and van Dam).

The function F(x, y) = x^2 + y^2 - R^2 is 0 on the circle positive outside and negative inside the circle.
In short, from a given (x, y), evaluate F(x+1, y-1/2) which dictates wether to go East or South-East for the next pixel.

In general, for curves it really pays to observe second-order or even higher-order derivatives to obtain simple difference expressions.

I believe modern vector fonts use scan line algorithms to determine filling. A horizontal scan line is crossed with all straight line sections of the glyph outline. The in-product of the scanline coordinate with the line segment vector indicates left or right side of the line segment. An odd number of crossings means inside the outline.

Wim Niemann

On Wed, 7 Nov 2018 12:51:46 +0100
Tomas Kral <thomas.kral at email.cz> wrote:

> > I wish to port some of the drawing primitives to Oberon-7, so we could
> > draw filled rectangles, polygons, ellipses, splines, etc.
>
> Studying `Display3.Mod', code seems a way too complex, I have started
> coding something simple on my own. Looking into `Curves.Mod' for
> inspiration.
>
> Circle does not use SIN(x) or COS(y) at all, how is that possible? I
> have always thought we need some trigonometry to draw a circle.
>
> Reading wiki about the concept of flood fill, I think that is needed
> only for curved shapes, rectangles can be filled without flood,
> correct?
>
> Now tricky part may come with pattern filling, I remember ATARI elipse
> demo, filled with Fuji logo and clipped. How to do in Oberon?
>
> MODULE Graph; (*Simple graph primitives, implementing fill*)
>   IMPORT SYSTEM, Display := Display, O := Out, Oberon;
>
>   PROCEDURE Circle*(col: INTEGER; x0, y0, r: LONGINT);
>     VAR x, y, u: LONGINT;
>   BEGIN u := 1 - r; x := r; y := 0;
>     WHILE y <= x DO
>       Display.Dot(col, x0+x, y0+y, Display.replace);
>       Display.Dot(col, x0+y, y0+x, Display.replace);
>       Display.Dot(col, x0-y, y0+x, Display.replace);
>       Display.Dot(col, x0-x, y0+y, Display.replace);
>       Display.Dot(col, x0-x, y0-y, Display.replace);
>       Display.Dot(col, x0-y, y0-x, Display.replace);
>       Display.Dot(col, x0+y, y0-x, Display.replace);
>       Display.Dot(col, x0+x, y0-y, Display.replace);
>       IF u < 0 THEN INC(u, 2*y+3) ELSE INC(u, 2*(y-x)+5); DEC(x) END ;
>       INC(y)
>     END
>   END Circle;
>
> END Graph.
>
>
> --
> Tomas Kral <thomas.kral at email.cz>
> --
> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon
```