How to draw lines, circles and other curves

These ideas were developed more than 30 years without knowing that they were already known at that time…

Today the graphics cards can easily do things like this in very little time. And today’s CPUs are of course really good at multiplying. So this has lost a lot of its immediate relevance, but it is a fun topic and why not have some fun…

Let us assume we have a two dimensional coordinate system and a visible area that goes from $x_{\min}$ to $x_{\max}$ and $y_{\min}$ to $y_{\max}$ . Coordinates are discrete.

In this world we can easily measure an angle against a (directed) line parallel to the $x$ -axis, for example up to an accuracy of $45^\circ=\frac{\pi}{4}$ :

$y=0 \wedge x > 0 \implies \alpha = 0 (= 0^\circ)$
$0 < y < x \implies 0 < \alpha < \frac{\pi}{4}(=45^\circ)$
$0 < y = x \implies \alpha = \frac{\pi}{4}$
$0 < x < y \implies \frac{\pi}{4} < \alpha < \frac{\pi}{2}(=90^\circ)$
$x = 0 \land y > 0\implies \alpha = \frac{\pi}{2}$
$x < 0 \land y > 0 \land |x| < |y|\implies \frac{\pi}{2} < \alpha < \frac{3\pi}{4}(=135^\circ)$
$x < 0 \land y > 0 \land -x = y\implies \alpha = \frac{3\pi}{4}(=135^\circ)$
…

So let us assume we have a curve that is described by a polynomial function in two variables $x$ and $y$ , like this:

$f(x, y) = \sum_{j=0}^m\sum_{k=0}^n a_{j,k}x^jy^k = 0$

We have to apply some math to understand that the curve behaves nicely in the sense that it does not behave to chaotic in scales that are below our accuracy, that it is connected etc. We might possibly scale and move it a bit by substituting something like $c_1u+c_2$ for $x$ and $c_3v+c_4$ for $y$ .

For example we may think of

line: $f(x,y)=ax+by+c$
circle: $f(x, y)=x^2+y^2-r^2$
eclipse: $f(x, y)=\frac{x^2}{a^2}+\frac{y^2}{b^2}-1$
…

We can assume our drawing is done with something like a king of chess. We need to find a starting point that is accurately on the curve or at least as accurately as possible. You could use knights or other chess figures or even fictive chess figures..

Now we have a starting point $(x_0, y_0)$ which lies ideally exactly on the curve. We have a deviation from the curve, which is $f(x_0, y_0)=d_0$ . So we have $f(x_n, y_n)=d_n$ . Than we move to $x_{n+1}=x_n + s$ and $y_{n+1}=y_n+t$ with $s, t = \{-1, 0, 1\}$ . Often only two or three combinations of $(s, t)$ need to be considered. When calculating $d_{n+1}$ from $d_n$ for the different variants, it shows that for calculating $d_{n+1}-d_n$ the difference becomes a polynomial with lower degree, because the highest terms cancel out. So drawing a line between two points or a circle with a given radius around a given point or an ellipse or a parabola or a hyperbola can be drawn without any multiplications… And powers of $n$ -th powers of $x$ can always be calculated with additions and subtractions only from the previous $x$ -values, by using successive differences:
$d_{m,1}=(x-m)^n-(x-m-1)^n$
$d_{m,l+1}=d_{m+1,l}-d_{m,l}$
These become constant for $l=n$ , just as the $l$ th derivatives, so by using this triangle, successive powers can be calculated with some preparational work using just additions.
It was quite natural to program these in assembly language, even in 8-bit assembly languages that are primitive by today’s standards. And it was possible to draw such figures reasonably fast with only one MHz (yes, not GHz).

We don’t need this stuff any more. Usually the graphics card is much better than anything we can with reasonable effort program. Usually the performance is sufficient when we just program in high level languages and use standard libraries.

But occasionally situations occur where we need to think about how to get the performance we need:
Make it work,
make it right,
make it fast,
but don’t stop after the first of those.

It is important that we choose our steps wisely and use adequate methods to solve our problem. Please understand this article as a fun issue about how we could write software some decades ago, but also as an inspiration to actually look into bits and bytes when it is really helping to get the necessary performance without defeating the maintainability of the software.

How to draw lines, circles and other curves

Schreibe einen Kommentar

Antworten abbrechen