[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[epsilon-devel] Re: Learning to write I/O actions: paint_line
From: |
Luca Saiu |
Subject: |
[epsilon-devel] Re: Learning to write I/O actions: paint_line |
Date: |
Tue, 25 Nov 2003 16:14:21 +0100 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i586; en-US; rv:1.3a) Gecko/20021212 |
Matteo Golfarini wrote:
Sorry for writing late but, like i told you i can't use the internet on
saturday and sunday
Don't mind.
now i think i can continue
> to implement other primitives of graphics, and if you
want we can start on how we can develop algorithms to solve graph problems
We need other graphic primitives and you are welcome to write them,
even if I would prefer them to be written in C (c_libraries/sdl.c),
since they would be faster (especially now, since we don't have a real
optimizer yet). Alas, the documentation about C libraries is not
finished yet; I will send a message to this list as soon as it is ready.
For the time an epsilon implementation can do, and can also serve as
a prototype; the algorithms to be used in C are essentially the same
ones to be used in epsilon.
I think we need:
* generic polygon, represented by a list of vertices (difficult in
the filled version; the non-filled version is quite easy)
* rectangle (filled and non-filled)
* triangle (filled and non-filled)
* circle (filled and non-filled)
* ellipse (filled and non-filled)
* arc and pie (the most difficult and the least used; probably they
aren't worth the trouble)
The functions would be named draw_X and fill_X, for every primitive
X. draw_polygon and fill_polygon can be used to implement some of the
other primitives, if convenient.
However we could finish the implementation of paint_line before; if
you are willing, of course. The module you sent the last time was
correct, but I have cleaned it up just a bit; please spend a little time
reading the comments marked with --positron. The only problem not yet
solved (because I intentionally didn't expose the problem to you the
first time; it's not your fault) is how to draw a line which has
pendence > 45deg or < -45deg; see how the purple line in the attached
file appears.
The problem is that we are drawing a pixel for every natural value of x;
this is correct and efficient when the pendence is little (<= 45deg or
>= -45), but not when it's high. For high-pendency segments we should
draw one pixel for every natural value of *y*; this also automatically
solves the problem of vertical lines, as you will see in a moment.
We can represent high-pendency lines as equations x = m y + q. The
system of equations is
/ x1 = m y1 + q
\ x2 = m y2 + q
which has the solution
/ m = (x2 - x1) / (y2 - y1)
\ q = (y2 x1 - y1 x2) / (y2 - y1)
Note that this is perfectly equal to the low-pendency case,
exchanging x by y and vice-versa. And note that a vertical line (x1 =
x2) can be drawn without problems; an horizontal line (y1 = y2) can't.
You can try extending paint_line so that it automatically
distinguishes between low-pendency and high-pendency. Note that this can
require some remodularization; start from the cleaned file I have
attached if you are willing to do this exercise.
If you aren't willing then don't mind, you can start implementing the
other primitives using draw_line (it's in the new snapshot).
see you next time ...
the life in spain is going better
:)
I'm happy about that. Life in Italy is going like always. Luckily we
have epsilon :-).
Best regards,
--
Luca Saiu, maintainer of GNU epsilon
http://www.gnu.org/software/epsilon
import random;
import simple_graphics;
define loop = fix \ f . \ x . f x ;
/* --positron:
I added the following two trivial functions: */
define min = \ a . \ b . if a < b then a else b;
define max = \ a . \ b . if a > b then a else b;
/* --positron:
Types were a bit confused in find_m and find_q; in find_m you (rightly)
expected some integer parameters, in find_q you expected the same ones
in the same order, but as floats. I have changed find_q: */
define find_q = \ x1 . \ y1 . \ x2 . \ y2 .
(integer_to_float (x2 * y1 - x1 * y2)) /f (integer_to_float (x2 - x1));
/* --positron:
I have changed the names of the parameters; (x1, y1), (x2, y2) seems more
understandable than (x, y), (x1, y1). Nothing important. */
define find_m = \ x1 . \ y1 . \ x2 . \ y2 .
((integer_to_float y2) -f (integer_to_float y1)) /f
((integer_to_float x2) -f (integer_to_float x1))
;
/* --positron:
I have removed paint_line_ugly and friends. Note that it was difficult
to find good names for them; this is often a hint suggesting that the
code could be made cleaner; note that the complexity of paint_line_ugly2_
completely disappears if you use the trivial min and max functions.
It often pays to add some utility functions which seem so simple to be
unuseful. */
/* --positron:
This only recurs on x, so it's quite fast. Note the common pattern
"if CONDITION then skip else begin ... end"; it's the most common
way to write recursive functions returning actions. */
define paint_line_rec = \ m . \ q . \ max_x . \ c .
fix \ f . \ x . // we recur only on x!
if x > max_x then
skip
else begin
let y be
float_to_integer (m *f (integer_to_float x) +f q)
in
show_pixel x y c;
f (x + 1);
end;
/* --positron:
I have clarified this and arranged for recurring on a single variable,
for speed's sake; with the let it's much more redable. */
define paint_line = \ x1 . \ y1 . \ x2 . \ y2 . \ c .
let m be
find_m x1 y1 x2 y2
& q be
find_q x1 y1 x2 y2
& min_x be
min x1 x2
& max_x be
max x1 x2
in
// min_x is the recursion variable, hence it's the last one:
paint_line_rec m q max_x c min_x;
/* --positron:
A trivial driver, just to test: */
define main = begin
initialize_graphics 640 480;
paint_line 0 0 50 479 (255, 255, 255);
paint_line 100 100 639 470 (255, 0, 255);
loop ();
end;